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 
7 package jsr166;
8 
9 import java.util.Arrays;
10 import java.util.Comparator;
11 import java.util.Iterator;
12 import java.util.NavigableSet;
13 import java.util.SortedSet;
14 import java.util.concurrent.ConcurrentSkipListSet;
15 
16 import junit.framework.Test;
17 import junit.framework.TestSuite;
18 
19 public 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 {
compare(Object x, Object y)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      */
populatedSet(int n)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      */
set5()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      */
dset5()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 
set0()91     private static NavigableSet set0() {
92         ConcurrentSkipListSet set = new ConcurrentSkipListSet();
93         assertTrue(set.isEmpty());
94         return set.tailSet(m1, true);
95     }
96 
dset0()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      */
testConstructor1()106     public void testConstructor1() {
107         assertEquals(0, set0().size());
108     }
109 
110     /**
111      * isEmpty is true before add, false after
112      */
testEmpty()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      */
testSize()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      */
testAddNull()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      */
testAdd()153     public void testAdd() {
154         NavigableSet q = set0();
155         assertTrue(q.add(six));
156     }
157 
158     /**
159      * Add of duplicate element fails
160      */
testAddDup()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      */
testAddNonComparable()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      */
testAddAll1()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      */
testAddAll2()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      */
testAddAll3()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      */
testAddAll5()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      */
testPoll()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      */
testRemoveElement()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      */
testContains()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      */
testClear()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      */
testContainsAll()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      */
testRetainAll()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      */
testRemoveAll()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      */
testLower()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      */
testHigher()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      */
testFloor()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      */
testCeiling()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      */
testToArray()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      */
testToArray2()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      */
testIterator()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      */
testEmptyIterator()449     public void testEmptyIterator() {
450         assertIteratorExhausted(set0().iterator());
451     }
452 
453     /**
454      * iterator.remove removes current element
455      */
testIteratorRemove()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      */
testToString()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      */
testSerialization()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      */
testSubSetContents()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 
testSubSetContents2()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      */
testHeadSetContents()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      */
testTailSetContents()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      */
testDescendingSize()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      */
testDescendingAddNull()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      */
testDescendingAdd()649     public void testDescendingAdd() {
650         NavigableSet q = dset0();
651         assertTrue(q.add(m6));
652     }
653 
654     /**
655      * Add of duplicate element fails
656      */
testDescendingAddDup()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      */
testDescendingAddNonComparable()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      */
testDescendingAddAll1()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      */
testDescendingAddAll2()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      */
testDescendingAddAll3()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      */
testDescendingAddAll5()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      */
testDescendingPoll()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      */
testDescendingRemoveElement()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      */
testDescendingContains()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      */
testDescendingClear()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      */
testDescendingContainsAll()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      */
testDescendingRetainAll()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      */
testDescendingRemoveAll()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      */
testDescendingLower()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      */
testDescendingHigher()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      */
testDescendingFloor()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      */
testDescendingCeiling()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      */
testDescendingToArray()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      */
testDescendingToArray2()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      */
testDescendingIterator()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      */
testDescendingEmptyIterator()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      */
testDescendingIteratorRemove()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      */
testDescendingToString()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      */
testDescendingSerialization()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      */
testDescendingSubSetContents()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 
testDescendingSubSetContents2()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      */
testDescendingHeadSetContents()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      */
testDescendingTailSetContents()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