ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/TreeSubSetTest.java
Revision: 1.23
Committed: Tue Feb 21 02:04:17 2012 UTC (12 years, 2 months ago) by jsr166
Branch: MAIN
Changes since 1.22: +2 -2 lines
Log Message: 
slightly clearer javadoc

File Contents

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