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