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