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