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