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