ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/TreeSubSetTest.java
Revision: 1.15
Committed: Thu Nov 4 01:04:54 2010 UTC (13 years, 6 months ago) by jsr166
Branch: MAIN
Changes since 1.14: +6 -8 lines
Log Message: 
strengthen toArray tests

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.12 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 jsr166 1.13
179 dl 1.1 /**
180     * addAll of a collection with null elements throws NPE
181     */
182     public void testAddAll2() {
183     try {
184     NavigableSet q = set0();
185     Integer[] ints = new Integer[SIZE];
186     q.addAll(Arrays.asList(ints));
187     shouldThrow();
188 jsr166 1.7 } catch (NullPointerException success) {}
189 dl 1.1 }
190 jsr166 1.13
191 dl 1.1 /**
192     * addAll of a collection with any null elements throws NPE after
193     * possibly adding some elements
194     */
195     public void testAddAll3() {
196     try {
197     NavigableSet q = set0();
198     Integer[] ints = new Integer[SIZE];
199     for (int i = 0; i < SIZE-1; ++i)
200     ints[i] = new Integer(i+SIZE);
201     q.addAll(Arrays.asList(ints));
202     shouldThrow();
203 jsr166 1.7 } catch (NullPointerException success) {}
204 dl 1.1 }
205    
206     /**
207     * Set contains all elements of successful addAll
208     */
209     public void testAddAll5() {
210 jsr166 1.9 Integer[] empty = new Integer[0];
211     Integer[] ints = new Integer[SIZE];
212     for (int i = 0; i < SIZE; ++i)
213     ints[i] = new Integer(SIZE-1- i);
214     NavigableSet q = set0();
215     assertFalse(q.addAll(Arrays.asList(empty)));
216     assertTrue(q.addAll(Arrays.asList(ints)));
217     for (int i = 0; i < SIZE; ++i)
218     assertEquals(new Integer(i), q.pollFirst());
219 dl 1.1 }
220    
221     /**
222     * poll succeeds unless empty
223     */
224     public void testPoll() {
225     NavigableSet q = populatedSet(SIZE);
226     for (int i = 0; i < SIZE; ++i) {
227 jsr166 1.10 assertEquals(i, q.pollFirst());
228 dl 1.1 }
229 jsr166 1.8 assertNull(q.pollFirst());
230 dl 1.1 }
231    
232     /**
233     * remove(x) removes x and returns true if present
234     */
235     public void testRemoveElement() {
236     NavigableSet q = populatedSet(SIZE);
237     for (int i = 1; i < SIZE; i+=2) {
238     assertTrue(q.remove(new Integer(i)));
239     }
240     for (int i = 0; i < SIZE; i+=2) {
241     assertTrue(q.remove(new Integer(i)));
242     assertFalse(q.remove(new Integer(i+1)));
243     }
244     assertTrue(q.isEmpty());
245     }
246 jsr166 1.4
247 dl 1.1 /**
248     * contains(x) reports true when elements added but not yet removed
249     */
250     public void testContains() {
251     NavigableSet q = populatedSet(SIZE);
252     for (int i = 0; i < SIZE; ++i) {
253     assertTrue(q.contains(new Integer(i)));
254     q.pollFirst();
255     assertFalse(q.contains(new Integer(i)));
256     }
257     }
258    
259     /**
260     * clear removes all elements
261     */
262     public void testClear() {
263     NavigableSet q = populatedSet(SIZE);
264     q.clear();
265     assertTrue(q.isEmpty());
266     assertEquals(0, q.size());
267 jsr166 1.10 assertTrue(q.add(new Integer(1)));
268 dl 1.1 assertFalse(q.isEmpty());
269     q.clear();
270     assertTrue(q.isEmpty());
271     }
272    
273     /**
274     * containsAll(c) is true when c contains a subset of elements
275     */
276     public void testContainsAll() {
277     NavigableSet q = populatedSet(SIZE);
278     NavigableSet p = set0();
279     for (int i = 0; i < SIZE; ++i) {
280     assertTrue(q.containsAll(p));
281     assertFalse(p.containsAll(q));
282     p.add(new Integer(i));
283     }
284     assertTrue(p.containsAll(q));
285     }
286    
287     /**
288     * retainAll(c) retains only those elements of c and reports true if changed
289     */
290     public void testRetainAll() {
291     NavigableSet q = populatedSet(SIZE);
292     NavigableSet p = populatedSet(SIZE);
293     for (int i = 0; i < SIZE; ++i) {
294     boolean changed = q.retainAll(p);
295     if (i == 0)
296     assertFalse(changed);
297     else
298     assertTrue(changed);
299    
300     assertTrue(q.containsAll(p));
301     assertEquals(SIZE-i, q.size());
302     p.pollFirst();
303     }
304     }
305    
306     /**
307     * removeAll(c) removes only those elements of c and reports true if changed
308     */
309     public void testRemoveAll() {
310     for (int i = 1; i < SIZE; ++i) {
311     NavigableSet q = populatedSet(SIZE);
312     NavigableSet p = populatedSet(i);
313     assertTrue(q.removeAll(p));
314     assertEquals(SIZE-i, q.size());
315     for (int j = 0; j < i; ++j) {
316     Integer I = (Integer)(p.pollFirst());
317     assertFalse(q.contains(I));
318     }
319     }
320     }
321    
322 jsr166 1.4
323 dl 1.1
324     /**
325     * lower returns preceding element
326     */
327     public void testLower() {
328     NavigableSet q = set5();
329     Object e1 = q.lower(three);
330     assertEquals(two, e1);
331    
332     Object e2 = q.lower(six);
333     assertEquals(five, e2);
334    
335     Object e3 = q.lower(one);
336     assertNull(e3);
337    
338     Object e4 = q.lower(zero);
339     assertNull(e4);
340     }
341    
342     /**
343     * higher returns next element
344     */
345     public void testHigher() {
346     NavigableSet q = set5();
347     Object e1 = q.higher(three);
348     assertEquals(four, e1);
349    
350     Object e2 = q.higher(zero);
351     assertEquals(one, e2);
352    
353     Object e3 = q.higher(five);
354     assertNull(e3);
355    
356     Object e4 = q.higher(six);
357     assertNull(e4);
358     }
359    
360     /**
361     * floor returns preceding element
362     */
363     public void testFloor() {
364     NavigableSet q = set5();
365     Object e1 = q.floor(three);
366     assertEquals(three, e1);
367    
368     Object e2 = q.floor(six);
369     assertEquals(five, e2);
370    
371     Object e3 = q.floor(one);
372     assertEquals(one, e3);
373    
374     Object e4 = q.floor(zero);
375     assertNull(e4);
376     }
377    
378     /**
379     * ceiling returns next element
380     */
381     public void testCeiling() {
382     NavigableSet q = set5();
383     Object e1 = q.ceiling(three);
384     assertEquals(three, e1);
385    
386     Object e2 = q.ceiling(zero);
387     assertEquals(one, e2);
388    
389     Object e3 = q.ceiling(five);
390     assertEquals(five, e3);
391    
392     Object e4 = q.ceiling(six);
393     assertNull(e4);
394     }
395    
396     /**
397 jsr166 1.15 * toArray contains all elements in sorted order
398 dl 1.1 */
399     public void testToArray() {
400     NavigableSet q = populatedSet(SIZE);
401 jsr166 1.8 Object[] o = q.toArray();
402     for (int i = 0; i < o.length; i++)
403 jsr166 1.15 assertSame(o[i], q.pollFirst());
404 dl 1.1 }
405    
406     /**
407 jsr166 1.15 * toArray(a) contains all elements in sorted order
408 dl 1.1 */
409     public void testToArray2() {
410     NavigableSet q = populatedSet(SIZE);
411 jsr166 1.8 Integer[] ints = new Integer[SIZE];
412 jsr166 1.15 assertSame(ints, q.toArray(ints));
413 jsr166 1.5 for (int i = 0; i < ints.length; i++)
414 jsr166 1.15 assertSame(ints[i], q.pollFirst());
415 dl 1.1 }
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 jsr166 1.12 public void testIteratorRemove() {
449 dl 1.1 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 jsr166 1.13
670 dl 1.3 /**
671     * addAll of a collection with null elements throws NPE
672     */
673     public void testDescendingAddAll2() {
674     try {
675     NavigableSet q = dset0();
676     Integer[] ints = new Integer[SIZE];
677     q.addAll(Arrays.asList(ints));
678     shouldThrow();
679 jsr166 1.7 } catch (NullPointerException success) {}
680 dl 1.3 }
681 jsr166 1.14
682 dl 1.3 /**
683     * addAll of a collection with any null elements throws NPE after
684     * possibly adding some elements
685     */
686     public void testDescendingAddAll3() {
687     try {
688     NavigableSet q = dset0();
689     Integer[] ints = new Integer[SIZE];
690     for (int i = 0; i < SIZE-1; ++i)
691     ints[i] = new Integer(i+SIZE);
692     q.addAll(Arrays.asList(ints));
693     shouldThrow();
694 jsr166 1.7 } catch (NullPointerException success) {}
695 dl 1.3 }
696    
697     /**
698     * Set contains all elements of successful addAll
699     */
700     public void testDescendingAddAll5() {
701 jsr166 1.7 Integer[] empty = new Integer[0];
702     Integer[] ints = new Integer[SIZE];
703     for (int i = 0; i < SIZE; ++i)
704     ints[i] = new Integer(SIZE-1- i);
705     NavigableSet q = dset0();
706     assertFalse(q.addAll(Arrays.asList(empty)));
707     assertTrue(q.addAll(Arrays.asList(ints)));
708     for (int i = 0; i < SIZE; ++i)
709     assertEquals(new Integer(i), q.pollFirst());
710 dl 1.3 }
711    
712     /**
713     * poll succeeds unless empty
714     */
715     public void testDescendingPoll() {
716     NavigableSet q = populatedSet(SIZE);
717     for (int i = 0; i < SIZE; ++i) {
718 jsr166 1.10 assertEquals(i, q.pollFirst());
719 dl 1.3 }
720 jsr166 1.8 assertNull(q.pollFirst());
721 dl 1.3 }
722    
723     /**
724     * remove(x) removes x and returns true if present
725     */
726     public void testDescendingRemoveElement() {
727     NavigableSet q = populatedSet(SIZE);
728     for (int i = 1; i < SIZE; i+=2) {
729     assertTrue(q.remove(new Integer(i)));
730     }
731     for (int i = 0; i < SIZE; i+=2) {
732     assertTrue(q.remove(new Integer(i)));
733     assertFalse(q.remove(new Integer(i+1)));
734     }
735     assertTrue(q.isEmpty());
736     }
737 jsr166 1.4
738 dl 1.3 /**
739     * contains(x) reports true when elements added but not yet removed
740     */
741     public void testDescendingContains() {
742     NavigableSet q = populatedSet(SIZE);
743     for (int i = 0; i < SIZE; ++i) {
744     assertTrue(q.contains(new Integer(i)));
745     q.pollFirst();
746     assertFalse(q.contains(new Integer(i)));
747     }
748     }
749    
750     /**
751     * clear removes all elements
752     */
753     public void testDescendingClear() {
754     NavigableSet q = populatedSet(SIZE);
755     q.clear();
756     assertTrue(q.isEmpty());
757     assertEquals(0, q.size());
758 jsr166 1.10 assertTrue(q.add(new Integer(1)));
759 dl 1.3 assertFalse(q.isEmpty());
760     q.clear();
761     assertTrue(q.isEmpty());
762     }
763    
764     /**
765     * containsAll(c) is true when c contains a subset of elements
766     */
767     public void testDescendingContainsAll() {
768     NavigableSet q = populatedSet(SIZE);
769     NavigableSet p = dset0();
770     for (int i = 0; i < SIZE; ++i) {
771     assertTrue(q.containsAll(p));
772     assertFalse(p.containsAll(q));
773     p.add(new Integer(i));
774     }
775     assertTrue(p.containsAll(q));
776     }
777    
778     /**
779     * retainAll(c) retains only those elements of c and reports true if changed
780     */
781     public void testDescendingRetainAll() {
782     NavigableSet q = populatedSet(SIZE);
783     NavigableSet p = populatedSet(SIZE);
784     for (int i = 0; i < SIZE; ++i) {
785     boolean changed = q.retainAll(p);
786     if (i == 0)
787     assertFalse(changed);
788     else
789     assertTrue(changed);
790    
791     assertTrue(q.containsAll(p));
792     assertEquals(SIZE-i, q.size());
793     p.pollFirst();
794     }
795     }
796    
797     /**
798     * removeAll(c) removes only those elements of c and reports true if changed
799     */
800     public void testDescendingRemoveAll() {
801     for (int i = 1; i < SIZE; ++i) {
802     NavigableSet q = populatedSet(SIZE);
803     NavigableSet p = populatedSet(i);
804     assertTrue(q.removeAll(p));
805     assertEquals(SIZE-i, q.size());
806     for (int j = 0; j < i; ++j) {
807     Integer I = (Integer)(p.pollFirst());
808     assertFalse(q.contains(I));
809     }
810     }
811     }
812    
813 jsr166 1.4
814 dl 1.3
815     /**
816     * lower returns preceding element
817     */
818     public void testDescendingLower() {
819     NavigableSet q = dset5();
820     Object e1 = q.lower(m3);
821     assertEquals(m2, e1);
822    
823     Object e2 = q.lower(m6);
824     assertEquals(m5, e2);
825    
826     Object e3 = q.lower(m1);
827     assertNull(e3);
828    
829     Object e4 = q.lower(zero);
830     assertNull(e4);
831     }
832    
833     /**
834     * higher returns next element
835     */
836     public void testDescendingHigher() {
837     NavigableSet q = dset5();
838     Object e1 = q.higher(m3);
839     assertEquals(m4, e1);
840    
841     Object e2 = q.higher(zero);
842     assertEquals(m1, e2);
843    
844     Object e3 = q.higher(m5);
845     assertNull(e3);
846    
847     Object e4 = q.higher(m6);
848     assertNull(e4);
849     }
850    
851     /**
852     * floor returns preceding element
853     */
854     public void testDescendingFloor() {
855     NavigableSet q = dset5();
856     Object e1 = q.floor(m3);
857     assertEquals(m3, e1);
858    
859     Object e2 = q.floor(m6);
860     assertEquals(m5, e2);
861    
862     Object e3 = q.floor(m1);
863     assertEquals(m1, e3);
864    
865     Object e4 = q.floor(zero);
866     assertNull(e4);
867     }
868    
869     /**
870     * ceiling returns next element
871     */
872     public void testDescendingCeiling() {
873     NavigableSet q = dset5();
874     Object e1 = q.ceiling(m3);
875     assertEquals(m3, e1);
876    
877     Object e2 = q.ceiling(zero);
878     assertEquals(m1, e2);
879    
880     Object e3 = q.ceiling(m5);
881     assertEquals(m5, e3);
882    
883     Object e4 = q.ceiling(m6);
884     assertNull(e4);
885     }
886    
887     /**
888     * toArray contains all elements
889     */
890     public void testDescendingToArray() {
891     NavigableSet q = populatedSet(SIZE);
892 jsr166 1.8 Object[] o = q.toArray();
893 dl 1.3 Arrays.sort(o);
894 jsr166 1.8 for (int i = 0; i < o.length; i++)
895     assertEquals(o[i], q.pollFirst());
896 dl 1.3 }
897    
898     /**
899     * toArray(a) contains all elements
900     */
901     public void testDescendingToArray2() {
902     NavigableSet q = populatedSet(SIZE);
903 jsr166 1.8 Integer[] ints = new Integer[SIZE];
904 jsr166 1.15 assertSame(ints, q.toArray(ints));
905 dl 1.3 Arrays.sort(ints);
906 jsr166 1.5 for (int i = 0; i < ints.length; i++)
907 dl 1.3 assertEquals(ints[i], q.pollFirst());
908     }
909 jsr166 1.4
910 dl 1.3 /**
911     * iterator iterates through all elements
912     */
913     public void testDescendingIterator() {
914     NavigableSet q = populatedSet(SIZE);
915     int i = 0;
916 jsr166 1.8 Iterator it = q.iterator();
917 jsr166 1.5 while (it.hasNext()) {
918 dl 1.3 assertTrue(q.contains(it.next()));
919     ++i;
920     }
921     assertEquals(i, SIZE);
922     }
923    
924     /**
925     * iterator of empty set has no elements
926     */
927     public void testDescendingEmptyIterator() {
928     NavigableSet q = dset0();
929     int i = 0;
930 jsr166 1.8 Iterator it = q.iterator();
931 jsr166 1.5 while (it.hasNext()) {
932 dl 1.3 assertTrue(q.contains(it.next()));
933     ++i;
934     }
935     assertEquals(i, 0);
936     }
937    
938     /**
939     * iterator.remove removes current element
940     */
941 jsr166 1.12 public void testDescendingIteratorRemove() {
942 dl 1.3 final NavigableSet q = dset0();
943     q.add(new Integer(2));
944     q.add(new Integer(1));
945     q.add(new Integer(3));
946    
947     Iterator it = q.iterator();
948     it.next();
949     it.remove();
950    
951     it = q.iterator();
952 jsr166 1.10 assertEquals(it.next(), 2);
953     assertEquals(it.next(), 3);
954 dl 1.3 assertFalse(it.hasNext());
955     }
956    
957    
958     /**
959     * toString contains toStrings of elements
960     */
961     public void testDescendingToString() {
962     NavigableSet q = populatedSet(SIZE);
963     String s = q.toString();
964     for (int i = 0; i < SIZE; ++i) {
965     assertTrue(s.indexOf(String.valueOf(i)) >= 0);
966     }
967 jsr166 1.4 }
968 dl 1.3
969     /**
970 jsr166 1.4 * A deserialized serialized set has same elements
971 dl 1.3 */
972 jsr166 1.7 public void testDescendingSerialization() throws Exception {
973 dl 1.3 NavigableSet q = populatedSet(SIZE);
974 jsr166 1.7 ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
975     ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
976     out.writeObject(q);
977     out.close();
978    
979     ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
980     ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
981     NavigableSet r = (NavigableSet)in.readObject();
982     assertEquals(q.size(), r.size());
983     while (!q.isEmpty())
984     assertEquals(q.pollFirst(), r.pollFirst());
985 dl 1.3 }
986    
987     /**
988     * subSet returns set with keys in requested range
989     */
990     public void testDescendingSubSetContents() {
991     NavigableSet set = dset5();
992     SortedSet sm = set.subSet(m2, m4);
993     assertEquals(m2, sm.first());
994     assertEquals(m3, sm.last());
995     assertEquals(2, sm.size());
996     assertFalse(sm.contains(m1));
997     assertTrue(sm.contains(m2));
998     assertTrue(sm.contains(m3));
999     assertFalse(sm.contains(m4));
1000     assertFalse(sm.contains(m5));
1001     Iterator i = sm.iterator();
1002     Object k;
1003     k = (Integer)(i.next());
1004     assertEquals(m2, k);
1005     k = (Integer)(i.next());
1006     assertEquals(m3, k);
1007     assertFalse(i.hasNext());
1008     Iterator j = sm.iterator();
1009     j.next();
1010     j.remove();
1011     assertFalse(set.contains(m2));
1012     assertEquals(4, set.size());
1013     assertEquals(1, sm.size());
1014     assertEquals(m3, sm.first());
1015     assertEquals(m3, sm.last());
1016     assertTrue(sm.remove(m3));
1017     assertTrue(sm.isEmpty());
1018     assertEquals(3, set.size());
1019     }
1020    
1021     public void testDescendingSubSetContents2() {
1022     NavigableSet set = dset5();
1023     SortedSet sm = set.subSet(m2, m3);
1024     assertEquals(1, sm.size());
1025     assertEquals(m2, sm.first());
1026     assertEquals(m2, sm.last());
1027     assertFalse(sm.contains(m1));
1028     assertTrue(sm.contains(m2));
1029     assertFalse(sm.contains(m3));
1030     assertFalse(sm.contains(m4));
1031     assertFalse(sm.contains(m5));
1032     Iterator i = sm.iterator();
1033     Object k;
1034     k = (Integer)(i.next());
1035     assertEquals(m2, k);
1036     assertFalse(i.hasNext());
1037     Iterator j = sm.iterator();
1038     j.next();
1039     j.remove();
1040     assertFalse(set.contains(m2));
1041     assertEquals(4, set.size());
1042     assertEquals(0, sm.size());
1043     assertTrue(sm.isEmpty());
1044     assertFalse(sm.remove(m3));
1045     assertEquals(4, set.size());
1046     }
1047    
1048     /**
1049     * headSet returns set with keys in requested range
1050     */
1051     public void testDescendingHeadSetContents() {
1052     NavigableSet set = dset5();
1053     SortedSet sm = set.headSet(m4);
1054     assertTrue(sm.contains(m1));
1055     assertTrue(sm.contains(m2));
1056     assertTrue(sm.contains(m3));
1057     assertFalse(sm.contains(m4));
1058     assertFalse(sm.contains(m5));
1059     Iterator i = sm.iterator();
1060     Object k;
1061     k = (Integer)(i.next());
1062     assertEquals(m1, k);
1063     k = (Integer)(i.next());
1064     assertEquals(m2, k);
1065     k = (Integer)(i.next());
1066     assertEquals(m3, k);
1067     assertFalse(i.hasNext());
1068     sm.clear();
1069     assertTrue(sm.isEmpty());
1070     assertEquals(2, set.size());
1071     assertEquals(m4, set.first());
1072     }
1073    
1074     /**
1075     * tailSet returns set with keys in requested range
1076     */
1077     public void testDescendingTailSetContents() {
1078     NavigableSet set = dset5();
1079     SortedSet sm = set.tailSet(m2);
1080     assertFalse(sm.contains(m1));
1081     assertTrue(sm.contains(m2));
1082     assertTrue(sm.contains(m3));
1083     assertTrue(sm.contains(m4));
1084     assertTrue(sm.contains(m5));
1085     Iterator i = sm.iterator();
1086     Object k;
1087     k = (Integer)(i.next());
1088     assertEquals(m2, k);
1089     k = (Integer)(i.next());
1090     assertEquals(m3, k);
1091     k = (Integer)(i.next());
1092     assertEquals(m4, k);
1093     k = (Integer)(i.next());
1094     assertEquals(m5, k);
1095     assertFalse(i.hasNext());
1096    
1097     SortedSet ssm = sm.tailSet(m4);
1098     assertEquals(m4, ssm.first());
1099     assertEquals(m5, ssm.last());
1100     assertTrue(ssm.remove(m4));
1101     assertEquals(1, ssm.size());
1102     assertEquals(3, sm.size());
1103     assertEquals(4, set.size());
1104     }
1105    
1106 dl 1.1 }