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