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