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