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