ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/TreeSubSetTest.java
Revision: 1.11
Committed: Tue Dec 1 09:43:19 2009 UTC (14 years, 5 months ago) by jsr166
Branch: MAIN
Changes since 1.10: +0 -8 lines
Log Message: 
whitespace

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