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.Comparator;
11import java.util.Iterator;
12import java.util.NavigableSet;
13import java.util.Set;
14import java.util.SortedSet;
15import java.util.TreeSet;
16
17import junit.framework.Test;
18import junit.framework.TestSuite;
19
20public class TreeSubSetTest extends JSR166TestCase {
21    // android-note: Removed because the CTS runner does a bad job of
22    // retrying tests that have suite() declarations.
23    //
24    // public static void main(String[] args) {
25    //     main(suite(), args);
26    // }
27    // public static Test suite() {
28    //     return new TestSuite(TreeSubSetTest.class);
29    // }
30
31    static class MyReverseComparator implements Comparator {
32        public int compare(Object x, Object y) {
33            return ((Comparable)y).compareTo(x);
34        }
35    }
36
37    /**
38     * Returns a new set of given size containing consecutive
39     * Integers 0 ... n.
40     */
41    private NavigableSet<Integer> populatedSet(int n) {
42        TreeSet<Integer> q = new TreeSet<Integer>();
43        assertTrue(q.isEmpty());
44
45        for (int i = n - 1; i >= 0; i -= 2)
46            assertTrue(q.add(new Integer(i)));
47        for (int i = (n & 1); i < n; i += 2)
48            assertTrue(q.add(new Integer(i)));
49        assertTrue(q.add(new Integer(-n)));
50        assertTrue(q.add(new Integer(n)));
51        NavigableSet s = q.subSet(new Integer(0), true, new Integer(n), false);
52        assertFalse(s.isEmpty());
53        assertEquals(n, s.size());
54        return s;
55    }
56
57    /**
58     * Returns a new set of first 5 ints.
59     */
60    private NavigableSet set5() {
61        TreeSet q = new TreeSet();
62        assertTrue(q.isEmpty());
63        q.add(one);
64        q.add(two);
65        q.add(three);
66        q.add(four);
67        q.add(five);
68        q.add(zero);
69        q.add(seven);
70        NavigableSet s = q.subSet(one, true, seven, false);
71        assertEquals(5, s.size());
72        return s;
73    }
74
75    private NavigableSet dset5() {
76        TreeSet q = new TreeSet();
77        assertTrue(q.isEmpty());
78        q.add(m1);
79        q.add(m2);
80        q.add(m3);
81        q.add(m4);
82        q.add(m5);
83        NavigableSet s = q.descendingSet();
84        assertEquals(5, s.size());
85        return s;
86    }
87
88    private static NavigableSet set0() {
89        TreeSet set = new TreeSet();
90        assertTrue(set.isEmpty());
91        return set.tailSet(m1, false);
92    }
93
94    private static NavigableSet dset0() {
95        TreeSet set = new TreeSet();
96        assertTrue(set.isEmpty());
97        return set;
98    }
99
100    /**
101     * A new set has unbounded capacity
102     */
103    public void testConstructor1() {
104        assertEquals(0, set0().size());
105    }
106
107    /**
108     * isEmpty is true before add, false after
109     */
110    public void testEmpty() {
111        NavigableSet q = set0();
112        assertTrue(q.isEmpty());
113        assertTrue(q.add(new Integer(1)));
114        assertFalse(q.isEmpty());
115        assertTrue(q.add(new Integer(2)));
116        q.pollFirst();
117        q.pollFirst();
118        assertTrue(q.isEmpty());
119    }
120
121    /**
122     * size changes when elements added and removed
123     */
124    public void testSize() {
125        NavigableSet q = populatedSet(SIZE);
126        for (int i = 0; i < SIZE; ++i) {
127            assertEquals(SIZE - i, q.size());
128            q.pollFirst();
129        }
130        for (int i = 0; i < SIZE; ++i) {
131            assertEquals(i, q.size());
132            q.add(new Integer(i));
133        }
134    }
135
136    /**
137     * add(null) throws NPE
138     */
139    public void testAddNull() {
140        NavigableSet q = set0();
141        try {
142            q.add(null);
143            shouldThrow();
144        } catch (NullPointerException success) {}
145    }
146
147    /**
148     * Add of comparable element succeeds
149     */
150    public void testAdd() {
151        NavigableSet q = set0();
152        assertTrue(q.add(six));
153    }
154
155    /**
156     * Add of duplicate element fails
157     */
158    public void testAddDup() {
159        NavigableSet q = set0();
160        assertTrue(q.add(six));
161        assertFalse(q.add(six));
162    }
163
164    /**
165     * Add of non-Comparable throws CCE
166     */
167    public void testAddNonComparable() {
168        NavigableSet q = set0();
169        try {
170            q.add(new Object());
171            q.add(new Object());
172            shouldThrow();
173        } catch (ClassCastException success) {}
174    }
175
176    /**
177     * addAll(null) throws NPE
178     */
179    public void testAddAll1() {
180        NavigableSet q = set0();
181        try {
182            q.addAll(null);
183            shouldThrow();
184        } catch (NullPointerException success) {}
185    }
186
187    /**
188     * addAll of a collection with null elements throws NPE
189     */
190    public void testAddAll2() {
191        NavigableSet q = set0();
192        Integer[] ints = new Integer[SIZE];
193        try {
194            q.addAll(Arrays.asList(ints));
195            shouldThrow();
196        } catch (NullPointerException success) {}
197    }
198
199    /**
200     * addAll of a collection with any null elements throws NPE after
201     * possibly adding some elements
202     */
203    public void testAddAll3() {
204        NavigableSet q = set0();
205        Integer[] ints = new Integer[SIZE];
206        for (int i = 0; i < SIZE - 1; ++i)
207            ints[i] = new Integer(i + SIZE);
208        try {
209            q.addAll(Arrays.asList(ints));
210            shouldThrow();
211        } catch (NullPointerException success) {}
212    }
213
214    /**
215     * Set contains all elements of successful addAll
216     */
217    public void testAddAll5() {
218        Integer[] empty = new Integer[0];
219        Integer[] ints = new Integer[SIZE];
220        for (int i = 0; i < SIZE; ++i)
221            ints[i] = new Integer(SIZE - 1 - i);
222        NavigableSet q = set0();
223        assertFalse(q.addAll(Arrays.asList(empty)));
224        assertTrue(q.addAll(Arrays.asList(ints)));
225        for (int i = 0; i < SIZE; ++i)
226            assertEquals(new Integer(i), q.pollFirst());
227    }
228
229    /**
230     * poll succeeds unless empty
231     */
232    public void testPoll() {
233        NavigableSet q = populatedSet(SIZE);
234        for (int i = 0; i < SIZE; ++i) {
235            assertEquals(i, q.pollFirst());
236        }
237        assertNull(q.pollFirst());
238    }
239
240    /**
241     * remove(x) removes x and returns true if present
242     */
243    public void testRemoveElement() {
244        NavigableSet q = populatedSet(SIZE);
245        for (int i = 1; i < SIZE; i += 2) {
246            assertTrue(q.contains(i));
247            assertTrue(q.remove(i));
248            assertFalse(q.contains(i));
249            assertTrue(q.contains(i - 1));
250        }
251        for (int i = 0; i < SIZE; i += 2) {
252            assertTrue(q.contains(i));
253            assertTrue(q.remove(i));
254            assertFalse(q.contains(i));
255            assertFalse(q.remove(i + 1));
256            assertFalse(q.contains(i + 1));
257        }
258        assertTrue(q.isEmpty());
259    }
260
261    /**
262     * contains(x) reports true when elements added but not yet removed
263     */
264    public void testContains() {
265        NavigableSet q = populatedSet(SIZE);
266        for (int i = 0; i < SIZE; ++i) {
267            assertTrue(q.contains(new Integer(i)));
268            q.pollFirst();
269            assertFalse(q.contains(new Integer(i)));
270        }
271    }
272
273    /**
274     * clear removes all elements
275     */
276    public void testClear() {
277        NavigableSet q = populatedSet(SIZE);
278        q.clear();
279        assertTrue(q.isEmpty());
280        assertEquals(0, q.size());
281        assertTrue(q.add(new Integer(1)));
282        assertFalse(q.isEmpty());
283        q.clear();
284        assertTrue(q.isEmpty());
285    }
286
287    /**
288     * containsAll(c) is true when c contains a subset of elements
289     */
290    public void testContainsAll() {
291        NavigableSet q = populatedSet(SIZE);
292        NavigableSet p = set0();
293        for (int i = 0; i < SIZE; ++i) {
294            assertTrue(q.containsAll(p));
295            assertFalse(p.containsAll(q));
296            p.add(new Integer(i));
297        }
298        assertTrue(p.containsAll(q));
299    }
300
301    /**
302     * retainAll(c) retains only those elements of c and reports true if changed
303     */
304    public void testRetainAll() {
305        NavigableSet q = populatedSet(SIZE);
306        NavigableSet p = populatedSet(SIZE);
307        for (int i = 0; i < SIZE; ++i) {
308            boolean changed = q.retainAll(p);
309            if (i == 0)
310                assertFalse(changed);
311            else
312                assertTrue(changed);
313
314            assertTrue(q.containsAll(p));
315            assertEquals(SIZE - i, q.size());
316            p.pollFirst();
317        }
318    }
319
320    /**
321     * removeAll(c) removes only those elements of c and reports true if changed
322     */
323    public void testRemoveAll() {
324        for (int i = 1; i < SIZE; ++i) {
325            NavigableSet q = populatedSet(SIZE);
326            NavigableSet p = populatedSet(i);
327            assertTrue(q.removeAll(p));
328            assertEquals(SIZE - i, q.size());
329            for (int j = 0; j < i; ++j) {
330                Integer x = (Integer)(p.pollFirst());
331                assertFalse(q.contains(x));
332            }
333        }
334    }
335
336    /**
337     * lower returns preceding element
338     */
339    public void testLower() {
340        NavigableSet q = set5();
341        Object e1 = q.lower(three);
342        assertEquals(two, e1);
343
344        Object e2 = q.lower(six);
345        assertEquals(five, e2);
346
347        Object e3 = q.lower(one);
348        assertNull(e3);
349
350        Object e4 = q.lower(zero);
351        assertNull(e4);
352    }
353
354    /**
355     * higher returns next element
356     */
357    public void testHigher() {
358        NavigableSet q = set5();
359        Object e1 = q.higher(three);
360        assertEquals(four, e1);
361
362        Object e2 = q.higher(zero);
363        assertEquals(one, e2);
364
365        Object e3 = q.higher(five);
366        assertNull(e3);
367
368        Object e4 = q.higher(six);
369        assertNull(e4);
370    }
371
372    /**
373     * floor returns preceding element
374     */
375    public void testFloor() {
376        NavigableSet q = set5();
377        Object e1 = q.floor(three);
378        assertEquals(three, e1);
379
380        Object e2 = q.floor(six);
381        assertEquals(five, e2);
382
383        Object e3 = q.floor(one);
384        assertEquals(one, e3);
385
386        Object e4 = q.floor(zero);
387        assertNull(e4);
388    }
389
390    /**
391     * ceiling returns next element
392     */
393    public void testCeiling() {
394        NavigableSet q = set5();
395        Object e1 = q.ceiling(three);
396        assertEquals(three, e1);
397
398        Object e2 = q.ceiling(zero);
399        assertEquals(one, e2);
400
401        Object e3 = q.ceiling(five);
402        assertEquals(five, e3);
403
404        Object e4 = q.ceiling(six);
405        assertNull(e4);
406    }
407
408    /**
409     * toArray contains all elements in sorted order
410     */
411    public void testToArray() {
412        NavigableSet q = populatedSet(SIZE);
413        Object[] o = q.toArray();
414        for (int i = 0; i < o.length; i++)
415            assertSame(o[i], q.pollFirst());
416    }
417
418    /**
419     * toArray(a) contains all elements in sorted order
420     */
421    public void testToArray2() {
422        NavigableSet<Integer> q = populatedSet(SIZE);
423        Integer[] ints = new Integer[SIZE];
424        Integer[] array = q.toArray(ints);
425        assertSame(ints, array);
426        for (int i = 0; i < ints.length; i++)
427            assertSame(ints[i], q.pollFirst());
428    }
429
430    /**
431     * iterator iterates through all elements
432     */
433    public void testIterator() {
434        NavigableSet q = populatedSet(SIZE);
435        Iterator it = q.iterator();
436        int i;
437        for (i = 0; it.hasNext(); i++)
438            assertTrue(q.contains(it.next()));
439        assertEquals(i, SIZE);
440        assertIteratorExhausted(it);
441    }
442
443    /**
444     * iterator of empty set has no elements
445     */
446    public void testEmptyIterator() {
447        assertIteratorExhausted(set0().iterator());
448    }
449
450    /**
451     * iterator.remove removes current element
452     */
453    public void testIteratorRemove() {
454        final NavigableSet q = set0();
455        q.add(new Integer(2));
456        q.add(new Integer(1));
457        q.add(new Integer(3));
458
459        Iterator it = q.iterator();
460        it.next();
461        it.remove();
462
463        it = q.iterator();
464        assertEquals(2, it.next());
465        assertEquals(3, it.next());
466        assertFalse(it.hasNext());
467    }
468
469    /**
470     * toString contains toStrings of elements
471     */
472    public void testToString() {
473        NavigableSet q = populatedSet(SIZE);
474        String s = q.toString();
475        for (int i = 0; i < SIZE; ++i) {
476            assertTrue(s.contains(String.valueOf(i)));
477        }
478    }
479
480    /**
481     * A deserialized serialized set has same elements
482     */
483    public void testSerialization() throws Exception {
484        NavigableSet x = populatedSet(SIZE);
485        NavigableSet y = serialClone(x);
486
487        assertNotSame(x, y);
488        assertEquals(x.size(), y.size());
489        assertEquals(x, y);
490        assertEquals(y, x);
491        while (!x.isEmpty()) {
492            assertFalse(y.isEmpty());
493            assertEquals(x.pollFirst(), y.pollFirst());
494        }
495        assertTrue(y.isEmpty());
496    }
497
498    /**
499     * subSet returns set with keys in requested range
500     */
501    public void testSubSetContents() {
502        NavigableSet set = set5();
503        SortedSet sm = set.subSet(two, four);
504        assertEquals(two, sm.first());
505        assertEquals(three, sm.last());
506        assertEquals(2, sm.size());
507        assertFalse(sm.contains(one));
508        assertTrue(sm.contains(two));
509        assertTrue(sm.contains(three));
510        assertFalse(sm.contains(four));
511        assertFalse(sm.contains(five));
512        Iterator i = sm.iterator();
513        Object k;
514        k = (Integer)(i.next());
515        assertEquals(two, k);
516        k = (Integer)(i.next());
517        assertEquals(three, k);
518        assertFalse(i.hasNext());
519        Iterator j = sm.iterator();
520        j.next();
521        j.remove();
522        assertFalse(set.contains(two));
523        assertEquals(4, set.size());
524        assertEquals(1, sm.size());
525        assertEquals(three, sm.first());
526        assertEquals(three, sm.last());
527        assertTrue(sm.remove(three));
528        assertTrue(sm.isEmpty());
529        assertEquals(3, set.size());
530    }
531
532    public void testSubSetContents2() {
533        NavigableSet set = set5();
534        SortedSet sm = set.subSet(two, three);
535        assertEquals(1, sm.size());
536        assertEquals(two, sm.first());
537        assertEquals(two, sm.last());
538        assertFalse(sm.contains(one));
539        assertTrue(sm.contains(two));
540        assertFalse(sm.contains(three));
541        assertFalse(sm.contains(four));
542        assertFalse(sm.contains(five));
543        Iterator i = sm.iterator();
544        Object k;
545        k = (Integer)(i.next());
546        assertEquals(two, k);
547        assertFalse(i.hasNext());
548        Iterator j = sm.iterator();
549        j.next();
550        j.remove();
551        assertFalse(set.contains(two));
552        assertEquals(4, set.size());
553        assertEquals(0, sm.size());
554        assertTrue(sm.isEmpty());
555        assertFalse(sm.remove(three));
556        assertEquals(4, set.size());
557    }
558
559    /**
560     * headSet returns set with keys in requested range
561     */
562    public void testHeadSetContents() {
563        NavigableSet set = set5();
564        SortedSet sm = set.headSet(four);
565        assertTrue(sm.contains(one));
566        assertTrue(sm.contains(two));
567        assertTrue(sm.contains(three));
568        assertFalse(sm.contains(four));
569        assertFalse(sm.contains(five));
570        Iterator i = sm.iterator();
571        Object k;
572        k = (Integer)(i.next());
573        assertEquals(one, k);
574        k = (Integer)(i.next());
575        assertEquals(two, k);
576        k = (Integer)(i.next());
577        assertEquals(three, k);
578        assertFalse(i.hasNext());
579        sm.clear();
580        assertTrue(sm.isEmpty());
581        assertEquals(2, set.size());
582        assertEquals(four, set.first());
583    }
584
585    /**
586     * tailSet returns set with keys in requested range
587     */
588    public void testTailSetContents() {
589        NavigableSet set = set5();
590        SortedSet sm = set.tailSet(two);
591        assertFalse(sm.contains(one));
592        assertTrue(sm.contains(two));
593        assertTrue(sm.contains(three));
594        assertTrue(sm.contains(four));
595        assertTrue(sm.contains(five));
596        Iterator i = sm.iterator();
597        Object k;
598        k = (Integer)(i.next());
599        assertEquals(two, k);
600        k = (Integer)(i.next());
601        assertEquals(three, k);
602        k = (Integer)(i.next());
603        assertEquals(four, k);
604        k = (Integer)(i.next());
605        assertEquals(five, k);
606        assertFalse(i.hasNext());
607
608        SortedSet ssm = sm.tailSet(four);
609        assertEquals(four, ssm.first());
610        assertEquals(five, ssm.last());
611        assertTrue(ssm.remove(four));
612        assertEquals(1, ssm.size());
613        assertEquals(3, sm.size());
614        assertEquals(4, set.size());
615    }
616
617    /**
618     * size changes when elements added and removed
619     */
620    public void testDescendingSize() {
621        NavigableSet q = populatedSet(SIZE);
622        for (int i = 0; i < SIZE; ++i) {
623            assertEquals(SIZE - i, q.size());
624            q.pollFirst();
625        }
626        for (int i = 0; i < SIZE; ++i) {
627            assertEquals(i, q.size());
628            q.add(new Integer(i));
629        }
630    }
631
632    /**
633     * Add of comparable element succeeds
634     */
635    public void testDescendingAdd() {
636        NavigableSet q = dset0();
637        assertTrue(q.add(m6));
638    }
639
640    /**
641     * Add of duplicate element fails
642     */
643    public void testDescendingAddDup() {
644        NavigableSet q = dset0();
645        assertTrue(q.add(m6));
646        assertFalse(q.add(m6));
647    }
648
649    /**
650     * Add of non-Comparable throws CCE
651     */
652    public void testDescendingAddNonComparable() {
653        NavigableSet q = dset0();
654        try {
655            q.add(new Object());
656            q.add(new Object());
657            shouldThrow();
658        } catch (ClassCastException success) {}
659    }
660
661    /**
662     * addAll(null) throws NPE
663     */
664    public void testDescendingAddAll1() {
665        NavigableSet q = dset0();
666        try {
667            q.addAll(null);
668            shouldThrow();
669        } catch (NullPointerException success) {}
670    }
671
672    /**
673     * addAll of a collection with null elements throws NPE
674     */
675    public void testDescendingAddAll2() {
676        NavigableSet q = dset0();
677        Integer[] ints = new Integer[SIZE];
678        try {
679            q.addAll(Arrays.asList(ints));
680            shouldThrow();
681        } catch (NullPointerException success) {}
682    }
683
684    /**
685     * addAll of a collection with any null elements throws NPE after
686     * possibly adding some elements
687     */
688    public void testDescendingAddAll3() {
689        NavigableSet q = dset0();
690        Integer[] ints = new Integer[SIZE];
691        for (int i = 0; i < SIZE - 1; ++i)
692            ints[i] = new Integer(i + SIZE);
693        try {
694            q.addAll(Arrays.asList(ints));
695            shouldThrow();
696        } catch (NullPointerException success) {}
697    }
698
699    /**
700     * Set contains all elements of successful addAll
701     */
702    public void testDescendingAddAll5() {
703        Integer[] empty = new Integer[0];
704        Integer[] ints = new Integer[SIZE];
705        for (int i = 0; i < SIZE; ++i)
706            ints[i] = new Integer(SIZE - 1 - i);
707        NavigableSet q = dset0();
708        assertFalse(q.addAll(Arrays.asList(empty)));
709        assertTrue(q.addAll(Arrays.asList(ints)));
710        for (int i = 0; i < SIZE; ++i)
711            assertEquals(new Integer(i), q.pollFirst());
712    }
713
714    /**
715     * poll succeeds unless empty
716     */
717    public void testDescendingPoll() {
718        NavigableSet q = populatedSet(SIZE);
719        for (int i = 0; i < SIZE; ++i) {
720            assertEquals(i, q.pollFirst());
721        }
722        assertNull(q.pollFirst());
723    }
724
725    /**
726     * remove(x) removes x and returns true if present
727     */
728    public void testDescendingRemoveElement() {
729        NavigableSet q = populatedSet(SIZE);
730        for (int i = 1; i < SIZE; i += 2) {
731            assertTrue(q.remove(new Integer(i)));
732        }
733        for (int i = 0; i < SIZE; i += 2) {
734            assertTrue(q.remove(new Integer(i)));
735            assertFalse(q.remove(new Integer(i + 1)));
736        }
737        assertTrue(q.isEmpty());
738    }
739
740    /**
741     * contains(x) reports true when elements added but not yet removed
742     */
743    public void testDescendingContains() {
744        NavigableSet q = populatedSet(SIZE);
745        for (int i = 0; i < SIZE; ++i) {
746            assertTrue(q.contains(new Integer(i)));
747            q.pollFirst();
748            assertFalse(q.contains(new Integer(i)));
749        }
750    }
751
752    /**
753     * clear removes all elements
754     */
755    public void testDescendingClear() {
756        NavigableSet q = populatedSet(SIZE);
757        q.clear();
758        assertTrue(q.isEmpty());
759        assertEquals(0, q.size());
760        assertTrue(q.add(new Integer(1)));
761        assertFalse(q.isEmpty());
762        q.clear();
763        assertTrue(q.isEmpty());
764    }
765
766    /**
767     * containsAll(c) is true when c contains a subset of elements
768     */
769    public void testDescendingContainsAll() {
770        NavigableSet q = populatedSet(SIZE);
771        NavigableSet p = dset0();
772        for (int i = 0; i < SIZE; ++i) {
773            assertTrue(q.containsAll(p));
774            assertFalse(p.containsAll(q));
775            p.add(new Integer(i));
776        }
777        assertTrue(p.containsAll(q));
778    }
779
780    /**
781     * retainAll(c) retains only those elements of c and reports true if changed
782     */
783    public void testDescendingRetainAll() {
784        NavigableSet q = populatedSet(SIZE);
785        NavigableSet p = populatedSet(SIZE);
786        for (int i = 0; i < SIZE; ++i) {
787            boolean changed = q.retainAll(p);
788            if (i == 0)
789                assertFalse(changed);
790            else
791                assertTrue(changed);
792
793            assertTrue(q.containsAll(p));
794            assertEquals(SIZE - i, q.size());
795            p.pollFirst();
796        }
797    }
798
799    /**
800     * removeAll(c) removes only those elements of c and reports true if changed
801     */
802    public void testDescendingRemoveAll() {
803        for (int i = 1; i < SIZE; ++i) {
804            NavigableSet q = populatedSet(SIZE);
805            NavigableSet p = populatedSet(i);
806            assertTrue(q.removeAll(p));
807            assertEquals(SIZE - i, q.size());
808            for (int j = 0; j < i; ++j) {
809                Integer x = (Integer)(p.pollFirst());
810                assertFalse(q.contains(x));
811            }
812        }
813    }
814
815    /**
816     * lower returns preceding element
817     */
818    public void testDescendingLower() {
819        NavigableSet q = dset5();
820        Object e1 = q.lower(m3);
821        assertEquals(m2, e1);
822
823        Object e2 = q.lower(m6);
824        assertEquals(m5, e2);
825
826        Object e3 = q.lower(m1);
827        assertNull(e3);
828
829        Object e4 = q.lower(zero);
830        assertNull(e4);
831    }
832
833    /**
834     * higher returns next element
835     */
836    public void testDescendingHigher() {
837        NavigableSet q = dset5();
838        Object e1 = q.higher(m3);
839        assertEquals(m4, e1);
840
841        Object e2 = q.higher(zero);
842        assertEquals(m1, e2);
843
844        Object e3 = q.higher(m5);
845        assertNull(e3);
846
847        Object e4 = q.higher(m6);
848        assertNull(e4);
849    }
850
851    /**
852     * floor returns preceding element
853     */
854    public void testDescendingFloor() {
855        NavigableSet q = dset5();
856        Object e1 = q.floor(m3);
857        assertEquals(m3, e1);
858
859        Object e2 = q.floor(m6);
860        assertEquals(m5, e2);
861
862        Object e3 = q.floor(m1);
863        assertEquals(m1, e3);
864
865        Object e4 = q.floor(zero);
866        assertNull(e4);
867    }
868
869    /**
870     * ceiling returns next element
871     */
872    public void testDescendingCeiling() {
873        NavigableSet q = dset5();
874        Object e1 = q.ceiling(m3);
875        assertEquals(m3, e1);
876
877        Object e2 = q.ceiling(zero);
878        assertEquals(m1, e2);
879
880        Object e3 = q.ceiling(m5);
881        assertEquals(m5, e3);
882
883        Object e4 = q.ceiling(m6);
884        assertNull(e4);
885    }
886
887    /**
888     * toArray contains all elements
889     */
890    public void testDescendingToArray() {
891        NavigableSet q = populatedSet(SIZE);
892        Object[] o = q.toArray();
893        Arrays.sort(o);
894        for (int i = 0; i < o.length; i++)
895            assertEquals(o[i], q.pollFirst());
896    }
897
898    /**
899     * toArray(a) contains all elements
900     */
901    public void testDescendingToArray2() {
902        NavigableSet q = populatedSet(SIZE);
903        Integer[] ints = new Integer[SIZE];
904        assertSame(ints, q.toArray(ints));
905        Arrays.sort(ints);
906        for (int i = 0; i < ints.length; i++)
907            assertEquals(ints[i], q.pollFirst());
908    }
909
910    /**
911     * iterator iterates through all elements
912     */
913    public void testDescendingIterator() {
914        NavigableSet q = populatedSet(SIZE);
915        int i = 0;
916        Iterator it = q.iterator();
917        while (it.hasNext()) {
918            assertTrue(q.contains(it.next()));
919            ++i;
920        }
921        assertEquals(i, SIZE);
922    }
923
924    /**
925     * iterator of empty set has no elements
926     */
927    public void testDescendingEmptyIterator() {
928        NavigableSet q = dset0();
929        int i = 0;
930        Iterator it = q.iterator();
931        while (it.hasNext()) {
932            assertTrue(q.contains(it.next()));
933            ++i;
934        }
935        assertEquals(0, i);
936    }
937
938    /**
939     * iterator.remove removes current element
940     */
941    public void testDescendingIteratorRemove() {
942        final NavigableSet q = dset0();
943        q.add(new Integer(2));
944        q.add(new Integer(1));
945        q.add(new Integer(3));
946
947        Iterator it = q.iterator();
948        it.next();
949        it.remove();
950
951        it = q.iterator();
952        assertEquals(2, it.next());
953        assertEquals(3, it.next());
954        assertFalse(it.hasNext());
955    }
956
957    /**
958     * toString contains toStrings of elements
959     */
960    public void testDescendingToString() {
961        NavigableSet q = populatedSet(SIZE);
962        String s = q.toString();
963        for (int i = 0; i < SIZE; ++i) {
964            assertTrue(s.contains(String.valueOf(i)));
965        }
966    }
967
968    /**
969     * A deserialized serialized set has same elements
970     */
971    public void testDescendingSerialization() throws Exception {
972        NavigableSet x = dset5();
973        NavigableSet y = serialClone(x);
974
975        assertNotSame(x, y);
976        assertEquals(x.size(), y.size());
977        assertEquals(x.toString(), y.toString());
978        assertEquals(x, y);
979        assertEquals(y, x);
980        while (!x.isEmpty()) {
981            assertFalse(y.isEmpty());
982            assertEquals(x.pollFirst(), y.pollFirst());
983        }
984        assertTrue(y.isEmpty());
985    }
986
987    /**
988     * subSet returns set with keys in requested range
989     */
990    public void testDescendingSubSetContents() {
991        NavigableSet set = dset5();
992        SortedSet sm = set.subSet(m2, m4);
993        assertEquals(m2, sm.first());
994        assertEquals(m3, sm.last());
995        assertEquals(2, sm.size());
996        assertFalse(sm.contains(m1));
997        assertTrue(sm.contains(m2));
998        assertTrue(sm.contains(m3));
999        assertFalse(sm.contains(m4));
1000        assertFalse(sm.contains(m5));
1001        Iterator i = sm.iterator();
1002        Object k;
1003        k = (Integer)(i.next());
1004        assertEquals(m2, k);
1005        k = (Integer)(i.next());
1006        assertEquals(m3, k);
1007        assertFalse(i.hasNext());
1008        Iterator j = sm.iterator();
1009        j.next();
1010        j.remove();
1011        assertFalse(set.contains(m2));
1012        assertEquals(4, set.size());
1013        assertEquals(1, sm.size());
1014        assertEquals(m3, sm.first());
1015        assertEquals(m3, sm.last());
1016        assertTrue(sm.remove(m3));
1017        assertTrue(sm.isEmpty());
1018        assertEquals(3, set.size());
1019    }
1020
1021    public void testDescendingSubSetContents2() {
1022        NavigableSet set = dset5();
1023        SortedSet sm = set.subSet(m2, m3);
1024        assertEquals(1, sm.size());
1025        assertEquals(m2, sm.first());
1026        assertEquals(m2, sm.last());
1027        assertFalse(sm.contains(m1));
1028        assertTrue(sm.contains(m2));
1029        assertFalse(sm.contains(m3));
1030        assertFalse(sm.contains(m4));
1031        assertFalse(sm.contains(m5));
1032        Iterator i = sm.iterator();
1033        Object k;
1034        k = (Integer)(i.next());
1035        assertEquals(m2, k);
1036        assertFalse(i.hasNext());
1037        Iterator j = sm.iterator();
1038        j.next();
1039        j.remove();
1040        assertFalse(set.contains(m2));
1041        assertEquals(4, set.size());
1042        assertEquals(0, sm.size());
1043        assertTrue(sm.isEmpty());
1044        assertFalse(sm.remove(m3));
1045        assertEquals(4, set.size());
1046    }
1047
1048    /**
1049     * headSet returns set with keys in requested range
1050     */
1051    public void testDescendingHeadSetContents() {
1052        NavigableSet set = dset5();
1053        SortedSet sm = set.headSet(m4);
1054        assertTrue(sm.contains(m1));
1055        assertTrue(sm.contains(m2));
1056        assertTrue(sm.contains(m3));
1057        assertFalse(sm.contains(m4));
1058        assertFalse(sm.contains(m5));
1059        Iterator i = sm.iterator();
1060        Object k;
1061        k = (Integer)(i.next());
1062        assertEquals(m1, k);
1063        k = (Integer)(i.next());
1064        assertEquals(m2, k);
1065        k = (Integer)(i.next());
1066        assertEquals(m3, k);
1067        assertFalse(i.hasNext());
1068        sm.clear();
1069        assertTrue(sm.isEmpty());
1070        assertEquals(2, set.size());
1071        assertEquals(m4, set.first());
1072    }
1073
1074    /**
1075     * tailSet returns set with keys in requested range
1076     */
1077    public void testDescendingTailSetContents() {
1078        NavigableSet set = dset5();
1079        SortedSet sm = set.tailSet(m2);
1080        assertFalse(sm.contains(m1));
1081        assertTrue(sm.contains(m2));
1082        assertTrue(sm.contains(m3));
1083        assertTrue(sm.contains(m4));
1084        assertTrue(sm.contains(m5));
1085        Iterator i = sm.iterator();
1086        Object k;
1087        k = (Integer)(i.next());
1088        assertEquals(m2, k);
1089        k = (Integer)(i.next());
1090        assertEquals(m3, k);
1091        k = (Integer)(i.next());
1092        assertEquals(m4, k);
1093        k = (Integer)(i.next());
1094        assertEquals(m5, k);
1095        assertFalse(i.hasNext());
1096
1097        SortedSet ssm = sm.tailSet(m4);
1098        assertEquals(m4, ssm.first());
1099        assertEquals(m5, ssm.last());
1100        assertTrue(ssm.remove(m4));
1101        assertEquals(1, ssm.size());
1102        assertEquals(3, sm.size());
1103        assertEquals(4, set.size());
1104    }
1105
1106    /**
1107     * addAll is idempotent
1108     */
1109    public void testAddAll_idempotent() throws Exception {
1110        Set x = populatedSet(SIZE);
1111        Set y = new TreeSet(x);
1112        y.addAll(x);
1113        assertEquals(x, y);
1114        assertEquals(y, x);
1115    }
1116
1117}
1118