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