1/* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. 7 * 8 * This code is distributed in the hope that it will be useful, but WITHOUT 9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 11 * version 2 for more details (a copy is included in the LICENSE file that 12 * accompanied this code). 13 * 14 * You should have received a copy of the GNU General Public License version 15 * 2 along with this work; if not, write to the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 17 * 18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 19 * or visit www.oracle.com if you need additional information or have any 20 * questions. 21 */ 22 23/* 24 * This file is available under and governed by the GNU General Public 25 * License version 2 only, as published by the Free Software Foundation. 26 * However, the following notice accompanied the original version of this 27 * file: 28 * 29 * Written by Doug Lea with assistance from members of JCP JSR-166 30 * Expert Group and released to the public domain, as explained at 31 * http://creativecommons.org/publicdomain/zero/1.0/ 32 */ 33 34import java.util.Arrays; 35import java.util.Comparator; 36import java.util.Iterator; 37import java.util.NavigableSet; 38import java.util.SortedSet; 39import java.util.concurrent.ConcurrentSkipListSet; 40 41import junit.framework.Test; 42import junit.framework.TestSuite; 43 44public class ConcurrentSkipListSubSetTest extends JSR166TestCase { 45 public static void main(String[] args) { 46 main(suite(), args); 47 } 48 public static Test suite() { 49 return new TestSuite(ConcurrentSkipListSubSetTest.class); 50 } 51 52 static class MyReverseComparator implements Comparator { 53 public int compare(Object x, Object y) { 54 return ((Comparable)y).compareTo(x); 55 } 56 } 57 58 /** 59 * Returns a new set of given size containing consecutive 60 * Integers 0 ... n - 1. 61 */ 62 private NavigableSet<Integer> populatedSet(int n) { 63 ConcurrentSkipListSet<Integer> q = 64 new ConcurrentSkipListSet<Integer>(); 65 assertTrue(q.isEmpty()); 66 67 for (int i = n - 1; i >= 0; i -= 2) 68 assertTrue(q.add(new Integer(i))); 69 for (int i = (n & 1); i < n; i += 2) 70 assertTrue(q.add(new Integer(i))); 71 assertTrue(q.add(new Integer(-n))); 72 assertTrue(q.add(new Integer(n))); 73 NavigableSet s = q.subSet(new Integer(0), true, new Integer(n), false); 74 assertFalse(s.isEmpty()); 75 assertEquals(n, s.size()); 76 return s; 77 } 78 79 /** 80 * Returns a new set of first 5 ints. 81 */ 82 private NavigableSet set5() { 83 ConcurrentSkipListSet q = new ConcurrentSkipListSet(); 84 assertTrue(q.isEmpty()); 85 q.add(one); 86 q.add(two); 87 q.add(three); 88 q.add(four); 89 q.add(five); 90 q.add(zero); 91 q.add(seven); 92 NavigableSet s = q.subSet(one, true, seven, false); 93 assertEquals(5, s.size()); 94 return s; 95 } 96 97 /** 98 * Returns a new set of first 5 negative ints. 99 */ 100 private NavigableSet dset5() { 101 ConcurrentSkipListSet q = new ConcurrentSkipListSet(); 102 assertTrue(q.isEmpty()); 103 q.add(m1); 104 q.add(m2); 105 q.add(m3); 106 q.add(m4); 107 q.add(m5); 108 NavigableSet s = q.descendingSet(); 109 assertEquals(5, s.size()); 110 return s; 111 } 112 113 private static NavigableSet set0() { 114 ConcurrentSkipListSet set = new ConcurrentSkipListSet(); 115 assertTrue(set.isEmpty()); 116 return set.tailSet(m1, true); 117 } 118 119 private static NavigableSet dset0() { 120 ConcurrentSkipListSet set = new ConcurrentSkipListSet(); 121 assertTrue(set.isEmpty()); 122 return set; 123 } 124 125 /** 126 * A new set has unbounded capacity 127 */ 128 public void testConstructor1() { 129 assertEquals(0, set0().size()); 130 } 131 132 /** 133 * isEmpty is true before add, false after 134 */ 135 public void testEmpty() { 136 NavigableSet q = set0(); 137 assertTrue(q.isEmpty()); 138 q.add(new Integer(1)); 139 assertFalse(q.isEmpty()); 140 q.add(new Integer(2)); 141 q.pollFirst(); 142 q.pollFirst(); 143 assertTrue(q.isEmpty()); 144 } 145 146 /** 147 * size changes when elements added and removed 148 */ 149 public void testSize() { 150 NavigableSet q = populatedSet(SIZE); 151 for (int i = 0; i < SIZE; ++i) { 152 assertEquals(SIZE - i, q.size()); 153 q.pollFirst(); 154 } 155 for (int i = 0; i < SIZE; ++i) { 156 assertEquals(i, q.size()); 157 q.add(new Integer(i)); 158 } 159 } 160 161 /** 162 * add(null) throws NPE 163 */ 164 public void testAddNull() { 165 NavigableSet q = set0(); 166 try { 167 q.add(null); 168 shouldThrow(); 169 } catch (NullPointerException success) {} 170 } 171 172 /** 173 * Add of comparable element succeeds 174 */ 175 public void testAdd() { 176 NavigableSet q = set0(); 177 assertTrue(q.add(six)); 178 } 179 180 /** 181 * Add of duplicate element fails 182 */ 183 public void testAddDup() { 184 NavigableSet q = set0(); 185 assertTrue(q.add(six)); 186 assertFalse(q.add(six)); 187 } 188 189 /** 190 * Add of non-Comparable throws CCE 191 */ 192 public void testAddNonComparable() { 193 NavigableSet q = set0(); 194 try { 195 q.add(new Object()); 196 q.add(new Object()); 197 shouldThrow(); 198 } catch (ClassCastException success) {} 199 } 200 201 /** 202 * addAll(null) throws NPE 203 */ 204 public void testAddAll1() { 205 NavigableSet q = set0(); 206 try { 207 q.addAll(null); 208 shouldThrow(); 209 } catch (NullPointerException success) {} 210 } 211 212 /** 213 * addAll of a collection with null elements throws NPE 214 */ 215 public void testAddAll2() { 216 NavigableSet q = set0(); 217 Integer[] ints = new Integer[SIZE]; 218 try { 219 q.addAll(Arrays.asList(ints)); 220 shouldThrow(); 221 } catch (NullPointerException success) {} 222 } 223 224 /** 225 * addAll of a collection with any null elements throws NPE after 226 * possibly adding some elements 227 */ 228 public void testAddAll3() { 229 NavigableSet q = set0(); 230 Integer[] ints = new Integer[SIZE]; 231 for (int i = 0; i < SIZE - 1; ++i) 232 ints[i] = new Integer(i + SIZE); 233 try { 234 q.addAll(Arrays.asList(ints)); 235 shouldThrow(); 236 } catch (NullPointerException success) {} 237 } 238 239 /** 240 * Set contains all elements of successful addAll 241 */ 242 public void testAddAll5() { 243 Integer[] empty = new Integer[0]; 244 Integer[] ints = new Integer[SIZE]; 245 for (int i = 0; i < SIZE; ++i) 246 ints[i] = new Integer(SIZE - 1 - i); 247 NavigableSet q = set0(); 248 assertFalse(q.addAll(Arrays.asList(empty))); 249 assertTrue(q.addAll(Arrays.asList(ints))); 250 for (int i = 0; i < SIZE; ++i) 251 assertEquals(new Integer(i), q.pollFirst()); 252 } 253 254 /** 255 * poll succeeds unless empty 256 */ 257 public void testPoll() { 258 NavigableSet q = populatedSet(SIZE); 259 for (int i = 0; i < SIZE; ++i) { 260 assertEquals(i, q.pollFirst()); 261 } 262 assertNull(q.pollFirst()); 263 } 264 265 /** 266 * remove(x) removes x and returns true if present 267 */ 268 public void testRemoveElement() { 269 NavigableSet q = populatedSet(SIZE); 270 for (int i = 1; i < SIZE; i += 2) { 271 assertTrue(q.contains(i)); 272 assertTrue(q.remove(i)); 273 assertFalse(q.contains(i)); 274 assertTrue(q.contains(i - 1)); 275 } 276 for (int i = 0; i < SIZE; i += 2) { 277 assertTrue(q.contains(i)); 278 assertTrue(q.remove(i)); 279 assertFalse(q.contains(i)); 280 assertFalse(q.remove(i + 1)); 281 assertFalse(q.contains(i + 1)); 282 } 283 assertTrue(q.isEmpty()); 284 } 285 286 /** 287 * contains(x) reports true when elements added but not yet removed 288 */ 289 public void testContains() { 290 NavigableSet q = populatedSet(SIZE); 291 for (int i = 0; i < SIZE; ++i) { 292 assertTrue(q.contains(new Integer(i))); 293 q.pollFirst(); 294 assertFalse(q.contains(new Integer(i))); 295 } 296 } 297 298 /** 299 * clear removes all elements 300 */ 301 public void testClear() { 302 NavigableSet q = populatedSet(SIZE); 303 q.clear(); 304 assertTrue(q.isEmpty()); 305 assertEquals(0, q.size()); 306 q.add(new Integer(1)); 307 assertFalse(q.isEmpty()); 308 q.clear(); 309 assertTrue(q.isEmpty()); 310 } 311 312 /** 313 * containsAll(c) is true when c contains a subset of elements 314 */ 315 public void testContainsAll() { 316 NavigableSet q = populatedSet(SIZE); 317 NavigableSet p = set0(); 318 for (int i = 0; i < SIZE; ++i) { 319 assertTrue(q.containsAll(p)); 320 assertFalse(p.containsAll(q)); 321 p.add(new Integer(i)); 322 } 323 assertTrue(p.containsAll(q)); 324 } 325 326 /** 327 * retainAll(c) retains only those elements of c and reports true if changed 328 */ 329 public void testRetainAll() { 330 NavigableSet q = populatedSet(SIZE); 331 NavigableSet p = populatedSet(SIZE); 332 for (int i = 0; i < SIZE; ++i) { 333 boolean changed = q.retainAll(p); 334 if (i == 0) 335 assertFalse(changed); 336 else 337 assertTrue(changed); 338 339 assertTrue(q.containsAll(p)); 340 assertEquals(SIZE - i, q.size()); 341 p.pollFirst(); 342 } 343 } 344 345 /** 346 * removeAll(c) removes only those elements of c and reports true if changed 347 */ 348 public void testRemoveAll() { 349 for (int i = 1; i < SIZE; ++i) { 350 NavigableSet q = populatedSet(SIZE); 351 NavigableSet p = populatedSet(i); 352 assertTrue(q.removeAll(p)); 353 assertEquals(SIZE - i, q.size()); 354 for (int j = 0; j < i; ++j) { 355 Integer x = (Integer)(p.pollFirst()); 356 assertFalse(q.contains(x)); 357 } 358 } 359 } 360 361 /** 362 * lower returns preceding element 363 */ 364 public void testLower() { 365 NavigableSet q = set5(); 366 Object e1 = q.lower(three); 367 assertEquals(two, e1); 368 369 Object e2 = q.lower(six); 370 assertEquals(five, e2); 371 372 Object e3 = q.lower(one); 373 assertNull(e3); 374 375 Object e4 = q.lower(zero); 376 assertNull(e4); 377 } 378 379 /** 380 * higher returns next element 381 */ 382 public void testHigher() { 383 NavigableSet q = set5(); 384 Object e1 = q.higher(three); 385 assertEquals(four, e1); 386 387 Object e2 = q.higher(zero); 388 assertEquals(one, e2); 389 390 Object e3 = q.higher(five); 391 assertNull(e3); 392 393 Object e4 = q.higher(six); 394 assertNull(e4); 395 } 396 397 /** 398 * floor returns preceding element 399 */ 400 public void testFloor() { 401 NavigableSet q = set5(); 402 Object e1 = q.floor(three); 403 assertEquals(three, e1); 404 405 Object e2 = q.floor(six); 406 assertEquals(five, e2); 407 408 Object e3 = q.floor(one); 409 assertEquals(one, e3); 410 411 Object e4 = q.floor(zero); 412 assertNull(e4); 413 } 414 415 /** 416 * ceiling returns next element 417 */ 418 public void testCeiling() { 419 NavigableSet q = set5(); 420 Object e1 = q.ceiling(three); 421 assertEquals(three, e1); 422 423 Object e2 = q.ceiling(zero); 424 assertEquals(one, e2); 425 426 Object e3 = q.ceiling(five); 427 assertEquals(five, e3); 428 429 Object e4 = q.ceiling(six); 430 assertNull(e4); 431 } 432 433 /** 434 * toArray contains all elements in sorted order 435 */ 436 public void testToArray() { 437 NavigableSet q = populatedSet(SIZE); 438 Object[] o = q.toArray(); 439 for (int i = 0; i < o.length; i++) 440 assertSame(o[i], q.pollFirst()); 441 } 442 443 /** 444 * toArray(a) contains all elements in sorted order 445 */ 446 public void testToArray2() { 447 NavigableSet<Integer> q = populatedSet(SIZE); 448 Integer[] ints = new Integer[SIZE]; 449 Integer[] array = q.toArray(ints); 450 assertSame(ints, array); 451 for (int i = 0; i < ints.length; i++) 452 assertSame(ints[i], q.pollFirst()); 453 } 454 455 /** 456 * iterator iterates through all elements 457 */ 458 public void testIterator() { 459 NavigableSet q = populatedSet(SIZE); 460 Iterator it = q.iterator(); 461 int i; 462 for (i = 0; it.hasNext(); i++) 463 assertTrue(q.contains(it.next())); 464 assertEquals(i, SIZE); 465 assertIteratorExhausted(it); 466 } 467 468 /** 469 * iterator of empty set has no elements 470 */ 471 public void testEmptyIterator() { 472 assertIteratorExhausted(set0().iterator()); 473 } 474 475 /** 476 * iterator.remove removes current element 477 */ 478 public void testIteratorRemove() { 479 final NavigableSet q = set0(); 480 q.add(new Integer(2)); 481 q.add(new Integer(1)); 482 q.add(new Integer(3)); 483 484 Iterator it = q.iterator(); 485 it.next(); 486 it.remove(); 487 488 it = q.iterator(); 489 assertEquals(it.next(), new Integer(2)); 490 assertEquals(it.next(), new Integer(3)); 491 assertFalse(it.hasNext()); 492 } 493 494 /** 495 * toString contains toStrings of elements 496 */ 497 public void testToString() { 498 NavigableSet q = populatedSet(SIZE); 499 String s = q.toString(); 500 for (int i = 0; i < SIZE; ++i) { 501 assertTrue(s.contains(String.valueOf(i))); 502 } 503 } 504 505 /** 506 * A deserialized serialized set has same elements 507 */ 508 public void testSerialization() throws Exception { 509 NavigableSet x = populatedSet(SIZE); 510 NavigableSet y = serialClone(x); 511 512 assertNotSame(y, x); 513 assertEquals(x.size(), y.size()); 514 assertEquals(x, y); 515 assertEquals(y, x); 516 while (!x.isEmpty()) { 517 assertFalse(y.isEmpty()); 518 assertEquals(x.pollFirst(), y.pollFirst()); 519 } 520 assertTrue(y.isEmpty()); 521 } 522 523 /** 524 * subSet returns set with keys in requested range 525 */ 526 public void testSubSetContents() { 527 NavigableSet set = set5(); 528 SortedSet sm = set.subSet(two, four); 529 assertEquals(two, sm.first()); 530 assertEquals(three, sm.last()); 531 assertEquals(2, sm.size()); 532 assertFalse(sm.contains(one)); 533 assertTrue(sm.contains(two)); 534 assertTrue(sm.contains(three)); 535 assertFalse(sm.contains(four)); 536 assertFalse(sm.contains(five)); 537 Iterator i = sm.iterator(); 538 Object k; 539 k = (Integer)(i.next()); 540 assertEquals(two, k); 541 k = (Integer)(i.next()); 542 assertEquals(three, k); 543 assertFalse(i.hasNext()); 544 Iterator j = sm.iterator(); 545 j.next(); 546 j.remove(); 547 assertFalse(set.contains(two)); 548 assertEquals(4, set.size()); 549 assertEquals(1, sm.size()); 550 assertEquals(three, sm.first()); 551 assertEquals(three, sm.last()); 552 assertTrue(sm.remove(three)); 553 assertTrue(sm.isEmpty()); 554 assertEquals(3, set.size()); 555 } 556 557 public void testSubSetContents2() { 558 NavigableSet set = set5(); 559 SortedSet sm = set.subSet(two, three); 560 assertEquals(1, sm.size()); 561 assertEquals(two, sm.first()); 562 assertEquals(two, sm.last()); 563 assertFalse(sm.contains(one)); 564 assertTrue(sm.contains(two)); 565 assertFalse(sm.contains(three)); 566 assertFalse(sm.contains(four)); 567 assertFalse(sm.contains(five)); 568 Iterator i = sm.iterator(); 569 Object k; 570 k = (Integer)(i.next()); 571 assertEquals(two, k); 572 assertFalse(i.hasNext()); 573 Iterator j = sm.iterator(); 574 j.next(); 575 j.remove(); 576 assertFalse(set.contains(two)); 577 assertEquals(4, set.size()); 578 assertEquals(0, sm.size()); 579 assertTrue(sm.isEmpty()); 580 assertFalse(sm.remove(three)); 581 assertEquals(4, set.size()); 582 } 583 584 /** 585 * headSet returns set with keys in requested range 586 */ 587 public void testHeadSetContents() { 588 NavigableSet set = set5(); 589 SortedSet sm = set.headSet(four); 590 assertTrue(sm.contains(one)); 591 assertTrue(sm.contains(two)); 592 assertTrue(sm.contains(three)); 593 assertFalse(sm.contains(four)); 594 assertFalse(sm.contains(five)); 595 Iterator i = sm.iterator(); 596 Object k; 597 k = (Integer)(i.next()); 598 assertEquals(one, k); 599 k = (Integer)(i.next()); 600 assertEquals(two, k); 601 k = (Integer)(i.next()); 602 assertEquals(three, k); 603 assertFalse(i.hasNext()); 604 sm.clear(); 605 assertTrue(sm.isEmpty()); 606 assertEquals(2, set.size()); 607 assertEquals(four, set.first()); 608 } 609 610 /** 611 * tailSet returns set with keys in requested range 612 */ 613 public void testTailSetContents() { 614 NavigableSet set = set5(); 615 SortedSet sm = set.tailSet(two); 616 assertFalse(sm.contains(one)); 617 assertTrue(sm.contains(two)); 618 assertTrue(sm.contains(three)); 619 assertTrue(sm.contains(four)); 620 assertTrue(sm.contains(five)); 621 Iterator i = sm.iterator(); 622 Object k; 623 k = (Integer)(i.next()); 624 assertEquals(two, k); 625 k = (Integer)(i.next()); 626 assertEquals(three, k); 627 k = (Integer)(i.next()); 628 assertEquals(four, k); 629 k = (Integer)(i.next()); 630 assertEquals(five, k); 631 assertFalse(i.hasNext()); 632 633 SortedSet ssm = sm.tailSet(four); 634 assertEquals(four, ssm.first()); 635 assertEquals(five, ssm.last()); 636 assertTrue(ssm.remove(four)); 637 assertEquals(1, ssm.size()); 638 assertEquals(3, sm.size()); 639 assertEquals(4, set.size()); 640 } 641 642 /** 643 * size changes when elements added and removed 644 */ 645 public void testDescendingSize() { 646 NavigableSet q = populatedSet(SIZE); 647 for (int i = 0; i < SIZE; ++i) { 648 assertEquals(SIZE - i, q.size()); 649 q.pollFirst(); 650 } 651 for (int i = 0; i < SIZE; ++i) { 652 assertEquals(i, q.size()); 653 q.add(new Integer(i)); 654 } 655 } 656 657 /** 658 * add(null) throws NPE 659 */ 660 public void testDescendingAddNull() { 661 NavigableSet q = dset0(); 662 try { 663 q.add(null); 664 shouldThrow(); 665 } catch (NullPointerException success) {} 666 } 667 668 /** 669 * Add of comparable element succeeds 670 */ 671 public void testDescendingAdd() { 672 NavigableSet q = dset0(); 673 assertTrue(q.add(m6)); 674 } 675 676 /** 677 * Add of duplicate element fails 678 */ 679 public void testDescendingAddDup() { 680 NavigableSet q = dset0(); 681 assertTrue(q.add(m6)); 682 assertFalse(q.add(m6)); 683 } 684 685 /** 686 * Add of non-Comparable throws CCE 687 */ 688 public void testDescendingAddNonComparable() { 689 NavigableSet q = dset0(); 690 try { 691 q.add(new Object()); 692 q.add(new Object()); 693 shouldThrow(); 694 } catch (ClassCastException success) {} 695 } 696 697 /** 698 * addAll(null) throws NPE 699 */ 700 public void testDescendingAddAll1() { 701 NavigableSet q = dset0(); 702 try { 703 q.addAll(null); 704 shouldThrow(); 705 } catch (NullPointerException success) {} 706 } 707 708 /** 709 * addAll of a collection with null elements throws NPE 710 */ 711 public void testDescendingAddAll2() { 712 NavigableSet q = dset0(); 713 Integer[] ints = new Integer[SIZE]; 714 try { 715 q.addAll(Arrays.asList(ints)); 716 shouldThrow(); 717 } catch (NullPointerException success) {} 718 } 719 720 /** 721 * addAll of a collection with any null elements throws NPE after 722 * possibly adding some elements 723 */ 724 public void testDescendingAddAll3() { 725 NavigableSet q = dset0(); 726 Integer[] ints = new Integer[SIZE]; 727 for (int i = 0; i < SIZE - 1; ++i) 728 ints[i] = new Integer(i + SIZE); 729 try { 730 q.addAll(Arrays.asList(ints)); 731 shouldThrow(); 732 } catch (NullPointerException success) {} 733 } 734 735 /** 736 * Set contains all elements of successful addAll 737 */ 738 public void testDescendingAddAll5() { 739 Integer[] empty = new Integer[0]; 740 Integer[] ints = new Integer[SIZE]; 741 for (int i = 0; i < SIZE; ++i) 742 ints[i] = new Integer(SIZE - 1 - i); 743 NavigableSet q = dset0(); 744 assertFalse(q.addAll(Arrays.asList(empty))); 745 assertTrue(q.addAll(Arrays.asList(ints))); 746 for (int i = 0; i < SIZE; ++i) 747 assertEquals(new Integer(i), q.pollFirst()); 748 } 749 750 /** 751 * poll succeeds unless empty 752 */ 753 public void testDescendingPoll() { 754 NavigableSet q = populatedSet(SIZE); 755 for (int i = 0; i < SIZE; ++i) { 756 assertEquals(i, q.pollFirst()); 757 } 758 assertNull(q.pollFirst()); 759 } 760 761 /** 762 * remove(x) removes x and returns true if present 763 */ 764 public void testDescendingRemoveElement() { 765 NavigableSet q = populatedSet(SIZE); 766 for (int i = 1; i < SIZE; i += 2) { 767 assertTrue(q.remove(new Integer(i))); 768 } 769 for (int i = 0; i < SIZE; i += 2 ) { 770 assertTrue(q.remove(new Integer(i))); 771 assertFalse(q.remove(new Integer(i + 1))); 772 } 773 assertTrue(q.isEmpty()); 774 } 775 776 /** 777 * contains(x) reports true when elements added but not yet removed 778 */ 779 public void testDescendingContains() { 780 NavigableSet q = populatedSet(SIZE); 781 for (int i = 0; i < SIZE; ++i) { 782 assertTrue(q.contains(new Integer(i))); 783 q.pollFirst(); 784 assertFalse(q.contains(new Integer(i))); 785 } 786 } 787 788 /** 789 * clear removes all elements 790 */ 791 public void testDescendingClear() { 792 NavigableSet q = populatedSet(SIZE); 793 q.clear(); 794 assertTrue(q.isEmpty()); 795 assertEquals(0, q.size()); 796 q.add(new Integer(1)); 797 assertFalse(q.isEmpty()); 798 q.clear(); 799 assertTrue(q.isEmpty()); 800 } 801 802 /** 803 * containsAll(c) is true when c contains a subset of elements 804 */ 805 public void testDescendingContainsAll() { 806 NavigableSet q = populatedSet(SIZE); 807 NavigableSet p = dset0(); 808 for (int i = 0; i < SIZE; ++i) { 809 assertTrue(q.containsAll(p)); 810 assertFalse(p.containsAll(q)); 811 p.add(new Integer(i)); 812 } 813 assertTrue(p.containsAll(q)); 814 } 815 816 /** 817 * retainAll(c) retains only those elements of c and reports true if changed 818 */ 819 public void testDescendingRetainAll() { 820 NavigableSet q = populatedSet(SIZE); 821 NavigableSet p = populatedSet(SIZE); 822 for (int i = 0; i < SIZE; ++i) { 823 boolean changed = q.retainAll(p); 824 if (i == 0) 825 assertFalse(changed); 826 else 827 assertTrue(changed); 828 829 assertTrue(q.containsAll(p)); 830 assertEquals(SIZE - i, q.size()); 831 p.pollFirst(); 832 } 833 } 834 835 /** 836 * removeAll(c) removes only those elements of c and reports true if changed 837 */ 838 public void testDescendingRemoveAll() { 839 for (int i = 1; i < SIZE; ++i) { 840 NavigableSet q = populatedSet(SIZE); 841 NavigableSet p = populatedSet(i); 842 assertTrue(q.removeAll(p)); 843 assertEquals(SIZE - i, q.size()); 844 for (int j = 0; j < i; ++j) { 845 Integer x = (Integer)(p.pollFirst()); 846 assertFalse(q.contains(x)); 847 } 848 } 849 } 850 851 /** 852 * lower returns preceding element 853 */ 854 public void testDescendingLower() { 855 NavigableSet q = dset5(); 856 Object e1 = q.lower(m3); 857 assertEquals(m2, e1); 858 859 Object e2 = q.lower(m6); 860 assertEquals(m5, e2); 861 862 Object e3 = q.lower(m1); 863 assertNull(e3); 864 865 Object e4 = q.lower(zero); 866 assertNull(e4); 867 } 868 869 /** 870 * higher returns next element 871 */ 872 public void testDescendingHigher() { 873 NavigableSet q = dset5(); 874 Object e1 = q.higher(m3); 875 assertEquals(m4, e1); 876 877 Object e2 = q.higher(zero); 878 assertEquals(m1, e2); 879 880 Object e3 = q.higher(m5); 881 assertNull(e3); 882 883 Object e4 = q.higher(m6); 884 assertNull(e4); 885 } 886 887 /** 888 * floor returns preceding element 889 */ 890 public void testDescendingFloor() { 891 NavigableSet q = dset5(); 892 Object e1 = q.floor(m3); 893 assertEquals(m3, e1); 894 895 Object e2 = q.floor(m6); 896 assertEquals(m5, e2); 897 898 Object e3 = q.floor(m1); 899 assertEquals(m1, e3); 900 901 Object e4 = q.floor(zero); 902 assertNull(e4); 903 } 904 905 /** 906 * ceiling returns next element 907 */ 908 public void testDescendingCeiling() { 909 NavigableSet q = dset5(); 910 Object e1 = q.ceiling(m3); 911 assertEquals(m3, e1); 912 913 Object e2 = q.ceiling(zero); 914 assertEquals(m1, e2); 915 916 Object e3 = q.ceiling(m5); 917 assertEquals(m5, e3); 918 919 Object e4 = q.ceiling(m6); 920 assertNull(e4); 921 } 922 923 /** 924 * toArray contains all elements 925 */ 926 public void testDescendingToArray() { 927 NavigableSet q = populatedSet(SIZE); 928 Object[] o = q.toArray(); 929 Arrays.sort(o); 930 for (int i = 0; i < o.length; i++) 931 assertEquals(o[i], q.pollFirst()); 932 } 933 934 /** 935 * toArray(a) contains all elements 936 */ 937 public void testDescendingToArray2() { 938 NavigableSet q = populatedSet(SIZE); 939 Integer[] ints = new Integer[SIZE]; 940 assertSame(ints, q.toArray(ints)); 941 Arrays.sort(ints); 942 for (int i = 0; i < ints.length; i++) 943 assertEquals(ints[i], q.pollFirst()); 944 } 945 946 /** 947 * iterator iterates through all elements 948 */ 949 public void testDescendingIterator() { 950 NavigableSet q = populatedSet(SIZE); 951 int i = 0; 952 Iterator it = q.iterator(); 953 while (it.hasNext()) { 954 assertTrue(q.contains(it.next())); 955 ++i; 956 } 957 assertEquals(i, SIZE); 958 } 959 960 /** 961 * iterator of empty set has no elements 962 */ 963 public void testDescendingEmptyIterator() { 964 NavigableSet q = dset0(); 965 int i = 0; 966 Iterator it = q.iterator(); 967 while (it.hasNext()) { 968 assertTrue(q.contains(it.next())); 969 ++i; 970 } 971 assertEquals(0, i); 972 } 973 974 /** 975 * iterator.remove removes current element 976 */ 977 public void testDescendingIteratorRemove() { 978 final NavigableSet q = dset0(); 979 q.add(new Integer(2)); 980 q.add(new Integer(1)); 981 q.add(new Integer(3)); 982 983 Iterator it = q.iterator(); 984 it.next(); 985 it.remove(); 986 987 it = q.iterator(); 988 assertEquals(it.next(), new Integer(2)); 989 assertEquals(it.next(), new Integer(3)); 990 assertFalse(it.hasNext()); 991 } 992 993 /** 994 * toString contains toStrings of elements 995 */ 996 public void testDescendingToString() { 997 NavigableSet q = populatedSet(SIZE); 998 String s = q.toString(); 999 for (int i = 0; i < SIZE; ++i) { 1000 assertTrue(s.contains(String.valueOf(i))); 1001 } 1002 } 1003 1004 /** 1005 * A deserialized serialized set has same elements 1006 */ 1007 public void testDescendingSerialization() throws Exception { 1008 NavigableSet x = dset5(); 1009 NavigableSet y = serialClone(x); 1010 1011 assertNotSame(y, x); 1012 assertEquals(x.size(), y.size()); 1013 assertEquals(x, y); 1014 assertEquals(y, x); 1015 while (!x.isEmpty()) { 1016 assertFalse(y.isEmpty()); 1017 assertEquals(x.pollFirst(), y.pollFirst()); 1018 } 1019 assertTrue(y.isEmpty()); 1020 } 1021 1022 /** 1023 * subSet returns set with keys in requested range 1024 */ 1025 public void testDescendingSubSetContents() { 1026 NavigableSet set = dset5(); 1027 SortedSet sm = set.subSet(m2, m4); 1028 assertEquals(m2, sm.first()); 1029 assertEquals(m3, sm.last()); 1030 assertEquals(2, sm.size()); 1031 assertFalse(sm.contains(m1)); 1032 assertTrue(sm.contains(m2)); 1033 assertTrue(sm.contains(m3)); 1034 assertFalse(sm.contains(m4)); 1035 assertFalse(sm.contains(m5)); 1036 Iterator i = sm.iterator(); 1037 Object k; 1038 k = (Integer)(i.next()); 1039 assertEquals(m2, k); 1040 k = (Integer)(i.next()); 1041 assertEquals(m3, k); 1042 assertFalse(i.hasNext()); 1043 Iterator j = sm.iterator(); 1044 j.next(); 1045 j.remove(); 1046 assertFalse(set.contains(m2)); 1047 assertEquals(4, set.size()); 1048 assertEquals(1, sm.size()); 1049 assertEquals(m3, sm.first()); 1050 assertEquals(m3, sm.last()); 1051 assertTrue(sm.remove(m3)); 1052 assertTrue(sm.isEmpty()); 1053 assertEquals(3, set.size()); 1054 } 1055 1056 public void testDescendingSubSetContents2() { 1057 NavigableSet set = dset5(); 1058 SortedSet sm = set.subSet(m2, m3); 1059 assertEquals(1, sm.size()); 1060 assertEquals(m2, sm.first()); 1061 assertEquals(m2, sm.last()); 1062 assertFalse(sm.contains(m1)); 1063 assertTrue(sm.contains(m2)); 1064 assertFalse(sm.contains(m3)); 1065 assertFalse(sm.contains(m4)); 1066 assertFalse(sm.contains(m5)); 1067 Iterator i = sm.iterator(); 1068 Object k; 1069 k = (Integer)(i.next()); 1070 assertEquals(m2, k); 1071 assertFalse(i.hasNext()); 1072 Iterator j = sm.iterator(); 1073 j.next(); 1074 j.remove(); 1075 assertFalse(set.contains(m2)); 1076 assertEquals(4, set.size()); 1077 assertEquals(0, sm.size()); 1078 assertTrue(sm.isEmpty()); 1079 assertFalse(sm.remove(m3)); 1080 assertEquals(4, set.size()); 1081 } 1082 1083 /** 1084 * headSet returns set with keys in requested range 1085 */ 1086 public void testDescendingHeadSetContents() { 1087 NavigableSet set = dset5(); 1088 SortedSet sm = set.headSet(m4); 1089 assertTrue(sm.contains(m1)); 1090 assertTrue(sm.contains(m2)); 1091 assertTrue(sm.contains(m3)); 1092 assertFalse(sm.contains(m4)); 1093 assertFalse(sm.contains(m5)); 1094 Iterator i = sm.iterator(); 1095 Object k; 1096 k = (Integer)(i.next()); 1097 assertEquals(m1, k); 1098 k = (Integer)(i.next()); 1099 assertEquals(m2, k); 1100 k = (Integer)(i.next()); 1101 assertEquals(m3, k); 1102 assertFalse(i.hasNext()); 1103 sm.clear(); 1104 assertTrue(sm.isEmpty()); 1105 assertEquals(2, set.size()); 1106 assertEquals(m4, set.first()); 1107 } 1108 1109 /** 1110 * tailSet returns set with keys in requested range 1111 */ 1112 public void testDescendingTailSetContents() { 1113 NavigableSet set = dset5(); 1114 SortedSet sm = set.tailSet(m2); 1115 assertFalse(sm.contains(m1)); 1116 assertTrue(sm.contains(m2)); 1117 assertTrue(sm.contains(m3)); 1118 assertTrue(sm.contains(m4)); 1119 assertTrue(sm.contains(m5)); 1120 Iterator i = sm.iterator(); 1121 Object k; 1122 k = (Integer)(i.next()); 1123 assertEquals(m2, k); 1124 k = (Integer)(i.next()); 1125 assertEquals(m3, k); 1126 k = (Integer)(i.next()); 1127 assertEquals(m4, k); 1128 k = (Integer)(i.next()); 1129 assertEquals(m5, k); 1130 assertFalse(i.hasNext()); 1131 1132 SortedSet ssm = sm.tailSet(m4); 1133 assertEquals(m4, ssm.first()); 1134 assertEquals(m5, ssm.last()); 1135 assertTrue(ssm.remove(m4)); 1136 assertEquals(1, ssm.size()); 1137 assertEquals(3, sm.size()); 1138 assertEquals(4, set.size()); 1139 } 1140 1141} 1142