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