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