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