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