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