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