ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/ConcurrentSkipListSubSetTest.java
Revision: 1.19
Committed: Fri May 27 19:21:27 2011 UTC (12 years, 11 months ago) by jsr166
Branch: MAIN
Changes since 1.18: +2 -11 lines
Log Message: 
indexOf => contains

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 jsr166 1.18 * http://creativecommons.org/publicdomain/zero/1.0/
5 dl 1.1 */
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 jsr166 1.16 private NavigableSet<Integer> populatedSet(int n) {
31     ConcurrentSkipListSet<Integer> q =
32     new ConcurrentSkipListSet<Integer>();
33 dl 1.1 assertTrue(q.isEmpty());
34    
35 jsr166 1.8 for (int i = n-1; i >= 0; i-=2)
36     assertTrue(q.add(new Integer(i)));
37     for (int i = (n & 1); i < n; i+=2)
38     assertTrue(q.add(new Integer(i)));
39 dl 1.1 assertTrue(q.add(new Integer(-n)));
40     assertTrue(q.add(new Integer(n)));
41 dl 1.4 NavigableSet s = q.subSet(new Integer(0), true, new Integer(n), false);
42 dl 1.1 assertFalse(s.isEmpty());
43 jsr166 1.8 assertEquals(n, s.size());
44 dl 1.1 return s;
45     }
46    
47     /**
48     * Create set of first 5 ints
49     */
50     private NavigableSet set5() {
51     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
52     assertTrue(q.isEmpty());
53     q.add(one);
54     q.add(two);
55     q.add(three);
56     q.add(four);
57     q.add(five);
58     q.add(zero);
59     q.add(seven);
60 dl 1.4 NavigableSet s = q.subSet(one, true, seven, false);
61 jsr166 1.8 assertEquals(5, s.size());
62 dl 1.4 return s;
63     }
64    
65     /**
66     * Create set of first 5 negative ints
67     */
68     private NavigableSet dset5() {
69     ConcurrentSkipListSet q = new ConcurrentSkipListSet();
70     assertTrue(q.isEmpty());
71     q.add(m1);
72     q.add(m2);
73     q.add(m3);
74     q.add(m4);
75     q.add(m5);
76     NavigableSet s = q.descendingSet();
77 jsr166 1.8 assertEquals(5, s.size());
78 dl 1.1 return s;
79     }
80    
81 jsr166 1.5 private static NavigableSet set0() {
82 jsr166 1.8 ConcurrentSkipListSet set = new ConcurrentSkipListSet();
83 dl 1.1 assertTrue(set.isEmpty());
84 dl 1.4 return set.tailSet(m1, true);
85     }
86    
87 jsr166 1.5 private static NavigableSet dset0() {
88 jsr166 1.8 ConcurrentSkipListSet set = new ConcurrentSkipListSet();
89 dl 1.4 assertTrue(set.isEmpty());
90     return set;
91 dl 1.1 }
92 jsr166 1.5
93 dl 1.1 /**
94     * A new set has unbounded capacity
95     */
96     public void testConstructor1() {
97     assertEquals(0, set0().size());
98     }
99    
100     /**
101     * 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     * addAll(null) throws NPE
172     */
173     public void testAddAll1() {
174     try {
175     NavigableSet q = set0();
176     q.addAll(null);
177     shouldThrow();
178 jsr166 1.9 } catch (NullPointerException success) {}
179 dl 1.1 }
180 jsr166 1.14
181 dl 1.1 /**
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 jsr166 1.14
193 dl 1.1 /**
194     * addAll of a collection with any null elements throws NPE after
195     * possibly adding some elements
196     */
197     public void testAddAll3() {
198     try {
199     NavigableSet q = set0();
200     Integer[] ints = new Integer[SIZE];
201     for (int i = 0; i < SIZE-1; ++i)
202     ints[i] = new Integer(i+SIZE);
203     q.addAll(Arrays.asList(ints));
204     shouldThrow();
205 jsr166 1.9 } catch (NullPointerException success) {}
206 dl 1.1 }
207    
208     /**
209     * Set contains all elements of successful addAll
210     */
211     public void testAddAll5() {
212 jsr166 1.10 Integer[] empty = new Integer[0];
213     Integer[] ints = new Integer[SIZE];
214     for (int i = 0; i < SIZE; ++i)
215     ints[i] = new Integer(SIZE-1- i);
216     NavigableSet q = set0();
217     assertFalse(q.addAll(Arrays.asList(empty)));
218     assertTrue(q.addAll(Arrays.asList(ints)));
219     for (int i = 0; i < SIZE; ++i)
220     assertEquals(new Integer(i), q.pollFirst());
221 dl 1.1 }
222    
223     /**
224     * poll succeeds unless empty
225     */
226     public void testPoll() {
227     NavigableSet q = populatedSet(SIZE);
228     for (int i = 0; i < SIZE; ++i) {
229 jsr166 1.11 assertEquals(i, q.pollFirst());
230 dl 1.1 }
231 jsr166 1.8 assertNull(q.pollFirst());
232 dl 1.1 }
233    
234     /**
235     * remove(x) removes x and returns true if present
236     */
237     public void testRemoveElement() {
238     NavigableSet q = populatedSet(SIZE);
239     for (int i = 1; i < SIZE; i+=2) {
240 jsr166 1.17 assertTrue(q.contains(i));
241     assertTrue(q.remove(i));
242     assertFalse(q.contains(i));
243     assertTrue(q.contains(i-1));
244 dl 1.1 }
245     for (int i = 0; i < SIZE; i+=2) {
246 jsr166 1.17 assertTrue(q.contains(i));
247     assertTrue(q.remove(i));
248     assertFalse(q.contains(i));
249     assertFalse(q.remove(i+1));
250     assertFalse(q.contains(i+1));
251 dl 1.1 }
252     assertTrue(q.isEmpty());
253     }
254 jsr166 1.5
255 dl 1.1 /**
256     * contains(x) reports true when elements added but not yet removed
257     */
258     public void testContains() {
259     NavigableSet q = populatedSet(SIZE);
260     for (int i = 0; i < SIZE; ++i) {
261     assertTrue(q.contains(new Integer(i)));
262     q.pollFirst();
263     assertFalse(q.contains(new Integer(i)));
264     }
265     }
266    
267     /**
268     * clear removes all elements
269     */
270     public void testClear() {
271     NavigableSet q = populatedSet(SIZE);
272     q.clear();
273     assertTrue(q.isEmpty());
274     assertEquals(0, q.size());
275     q.add(new Integer(1));
276     assertFalse(q.isEmpty());
277     q.clear();
278     assertTrue(q.isEmpty());
279     }
280    
281     /**
282     * containsAll(c) is true when c contains a subset of elements
283     */
284     public void testContainsAll() {
285     NavigableSet q = populatedSet(SIZE);
286     NavigableSet p = set0();
287     for (int i = 0; i < SIZE; ++i) {
288     assertTrue(q.containsAll(p));
289     assertFalse(p.containsAll(q));
290     p.add(new Integer(i));
291     }
292     assertTrue(p.containsAll(q));
293     }
294    
295     /**
296     * retainAll(c) retains only those elements of c and reports true if changed
297     */
298     public void testRetainAll() {
299     NavigableSet q = populatedSet(SIZE);
300     NavigableSet p = populatedSet(SIZE);
301     for (int i = 0; i < SIZE; ++i) {
302     boolean changed = q.retainAll(p);
303     if (i == 0)
304     assertFalse(changed);
305     else
306     assertTrue(changed);
307    
308     assertTrue(q.containsAll(p));
309     assertEquals(SIZE-i, q.size());
310     p.pollFirst();
311     }
312     }
313    
314     /**
315     * removeAll(c) removes only those elements of c and reports true if changed
316     */
317     public void testRemoveAll() {
318     for (int i = 1; i < SIZE; ++i) {
319     NavigableSet q = populatedSet(SIZE);
320     NavigableSet p = populatedSet(i);
321     assertTrue(q.removeAll(p));
322     assertEquals(SIZE-i, q.size());
323     for (int j = 0; j < i; ++j) {
324     Integer I = (Integer)(p.pollFirst());
325     assertFalse(q.contains(I));
326     }
327     }
328     }
329    
330     /**
331     * lower returns preceding element
332     */
333     public void testLower() {
334     NavigableSet q = set5();
335     Object e1 = q.lower(three);
336     assertEquals(two, e1);
337    
338     Object e2 = q.lower(six);
339     assertEquals(five, e2);
340    
341     Object e3 = q.lower(one);
342     assertNull(e3);
343    
344     Object e4 = q.lower(zero);
345     assertNull(e4);
346     }
347    
348     /**
349     * higher returns next element
350     */
351     public void testHigher() {
352     NavigableSet q = set5();
353     Object e1 = q.higher(three);
354     assertEquals(four, e1);
355    
356     Object e2 = q.higher(zero);
357     assertEquals(one, e2);
358    
359     Object e3 = q.higher(five);
360     assertNull(e3);
361    
362     Object e4 = q.higher(six);
363     assertNull(e4);
364     }
365    
366     /**
367     * floor returns preceding element
368     */
369     public void testFloor() {
370     NavigableSet q = set5();
371     Object e1 = q.floor(three);
372     assertEquals(three, e1);
373    
374     Object e2 = q.floor(six);
375     assertEquals(five, e2);
376    
377     Object e3 = q.floor(one);
378     assertEquals(one, e3);
379    
380     Object e4 = q.floor(zero);
381     assertNull(e4);
382     }
383    
384     /**
385     * ceiling returns next element
386     */
387     public void testCeiling() {
388     NavigableSet q = set5();
389     Object e1 = q.ceiling(three);
390     assertEquals(three, e1);
391    
392     Object e2 = q.ceiling(zero);
393     assertEquals(one, e2);
394    
395     Object e3 = q.ceiling(five);
396     assertEquals(five, e3);
397    
398     Object e4 = q.ceiling(six);
399     assertNull(e4);
400     }
401    
402     /**
403 jsr166 1.15 * toArray contains all elements in sorted order
404 dl 1.1 */
405     public void testToArray() {
406     NavigableSet q = populatedSet(SIZE);
407 jsr166 1.8 Object[] o = q.toArray();
408     for (int i = 0; i < o.length; i++)
409 jsr166 1.15 assertSame(o[i], q.pollFirst());
410 dl 1.1 }
411    
412     /**
413 jsr166 1.15 * toArray(a) contains all elements in sorted order
414 dl 1.1 */
415     public void testToArray2() {
416 jsr166 1.16 NavigableSet<Integer> q = populatedSet(SIZE);
417 jsr166 1.8 Integer[] ints = new Integer[SIZE];
418 jsr166 1.16 Integer[] array = q.toArray(ints);
419     assertSame(ints, array);
420 jsr166 1.6 for (int i = 0; i < ints.length; i++)
421 jsr166 1.15 assertSame(ints[i], q.pollFirst());
422 dl 1.1 }
423 jsr166 1.5
424 dl 1.1 /**
425     * iterator iterates through all elements
426     */
427     public void testIterator() {
428     NavigableSet q = populatedSet(SIZE);
429     int i = 0;
430 jsr166 1.8 Iterator it = q.iterator();
431 jsr166 1.6 while (it.hasNext()) {
432 dl 1.1 assertTrue(q.contains(it.next()));
433     ++i;
434     }
435     assertEquals(i, SIZE);
436     }
437    
438     /**
439     * iterator of empty set has no elements
440     */
441     public void testEmptyIterator() {
442     NavigableSet q = set0();
443     int i = 0;
444 jsr166 1.8 Iterator it = q.iterator();
445 jsr166 1.6 while (it.hasNext()) {
446 dl 1.1 assertTrue(q.contains(it.next()));
447     ++i;
448     }
449     assertEquals(i, 0);
450     }
451    
452     /**
453     * iterator.remove removes current element
454     */
455 jsr166 1.13 public void testIteratorRemove() {
456 dl 1.1 final NavigableSet q = set0();
457     q.add(new Integer(2));
458     q.add(new Integer(1));
459     q.add(new Integer(3));
460    
461     Iterator it = q.iterator();
462     it.next();
463     it.remove();
464    
465     it = q.iterator();
466     assertEquals(it.next(), new Integer(2));
467     assertEquals(it.next(), new Integer(3));
468     assertFalse(it.hasNext());
469     }
470    
471     /**
472     * toString contains toStrings of elements
473     */
474     public void testToString() {
475     NavigableSet q = populatedSet(SIZE);
476     String s = q.toString();
477     for (int i = 0; i < SIZE; ++i) {
478 jsr166 1.19 assertTrue(s.contains(String.valueOf(i)));
479 dl 1.1 }
480 jsr166 1.5 }
481 dl 1.1
482     /**
483 jsr166 1.5 * A deserialized serialized set has same elements
484 dl 1.1 */
485 jsr166 1.9 public void testSerialization() throws Exception {
486 dl 1.1 NavigableSet q = populatedSet(SIZE);
487 jsr166 1.9 ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
488     ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
489     out.writeObject(q);
490     out.close();
491    
492     ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
493     ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
494     NavigableSet r = (NavigableSet)in.readObject();
495     assertEquals(q.size(), r.size());
496     while (!q.isEmpty())
497     assertEquals(q.pollFirst(), r.pollFirst());
498 dl 1.1 }
499    
500     /**
501     * subSet returns set with keys in requested range
502     */
503     public void testSubSetContents() {
504     NavigableSet set = set5();
505     SortedSet sm = set.subSet(two, four);
506     assertEquals(two, sm.first());
507     assertEquals(three, sm.last());
508     assertEquals(2, sm.size());
509     assertFalse(sm.contains(one));
510     assertTrue(sm.contains(two));
511     assertTrue(sm.contains(three));
512     assertFalse(sm.contains(four));
513     assertFalse(sm.contains(five));
514     Iterator i = sm.iterator();
515     Object k;
516     k = (Integer)(i.next());
517     assertEquals(two, k);
518     k = (Integer)(i.next());
519     assertEquals(three, k);
520     assertFalse(i.hasNext());
521     Iterator j = sm.iterator();
522     j.next();
523     j.remove();
524     assertFalse(set.contains(two));
525     assertEquals(4, set.size());
526     assertEquals(1, sm.size());
527     assertEquals(three, sm.first());
528     assertEquals(three, sm.last());
529     assertTrue(sm.remove(three));
530     assertTrue(sm.isEmpty());
531     assertEquals(3, set.size());
532     }
533    
534     public void testSubSetContents2() {
535     NavigableSet set = set5();
536     SortedSet sm = set.subSet(two, three);
537     assertEquals(1, sm.size());
538     assertEquals(two, sm.first());
539     assertEquals(two, sm.last());
540     assertFalse(sm.contains(one));
541     assertTrue(sm.contains(two));
542     assertFalse(sm.contains(three));
543     assertFalse(sm.contains(four));
544     assertFalse(sm.contains(five));
545     Iterator i = sm.iterator();
546     Object k;
547     k = (Integer)(i.next());
548     assertEquals(two, k);
549     assertFalse(i.hasNext());
550     Iterator j = sm.iterator();
551     j.next();
552     j.remove();
553     assertFalse(set.contains(two));
554     assertEquals(4, set.size());
555     assertEquals(0, sm.size());
556     assertTrue(sm.isEmpty());
557     assertFalse(sm.remove(three));
558     assertEquals(4, set.size());
559     }
560    
561     /**
562     * headSet returns set with keys in requested range
563     */
564     public void testHeadSetContents() {
565     NavigableSet set = set5();
566     SortedSet sm = set.headSet(four);
567     assertTrue(sm.contains(one));
568     assertTrue(sm.contains(two));
569     assertTrue(sm.contains(three));
570     assertFalse(sm.contains(four));
571     assertFalse(sm.contains(five));
572     Iterator i = sm.iterator();
573     Object k;
574     k = (Integer)(i.next());
575     assertEquals(one, k);
576     k = (Integer)(i.next());
577     assertEquals(two, k);
578     k = (Integer)(i.next());
579     assertEquals(three, k);
580     assertFalse(i.hasNext());
581     sm.clear();
582     assertTrue(sm.isEmpty());
583     assertEquals(2, set.size());
584     assertEquals(four, set.first());
585     }
586    
587     /**
588     * tailSet returns set with keys in requested range
589     */
590     public void testTailSetContents() {
591     NavigableSet set = set5();
592     SortedSet sm = set.tailSet(two);
593     assertFalse(sm.contains(one));
594     assertTrue(sm.contains(two));
595     assertTrue(sm.contains(three));
596     assertTrue(sm.contains(four));
597     assertTrue(sm.contains(five));
598     Iterator i = sm.iterator();
599     Object k;
600     k = (Integer)(i.next());
601     assertEquals(two, k);
602     k = (Integer)(i.next());
603     assertEquals(three, k);
604     k = (Integer)(i.next());
605     assertEquals(four, k);
606     k = (Integer)(i.next());
607     assertEquals(five, k);
608     assertFalse(i.hasNext());
609    
610     SortedSet ssm = sm.tailSet(four);
611     assertEquals(four, ssm.first());
612     assertEquals(five, ssm.last());
613     assertTrue(ssm.remove(four));
614     assertEquals(1, ssm.size());
615     assertEquals(3, sm.size());
616     assertEquals(4, set.size());
617     }
618    
619 dl 1.4 /**
620     * size changes when elements added and removed
621     */
622     public void testDescendingSize() {
623     NavigableSet q = populatedSet(SIZE);
624     for (int i = 0; i < SIZE; ++i) {
625     assertEquals(SIZE-i, q.size());
626     q.pollFirst();
627     }
628     for (int i = 0; i < SIZE; ++i) {
629     assertEquals(i, q.size());
630     q.add(new Integer(i));
631     }
632     }
633    
634     /**
635     * add(null) throws NPE
636     */
637     public void testDescendingAddNull() {
638 jsr166 1.8 try {
639 dl 1.4 NavigableSet q = dset0();
640     q.add(null);
641     shouldThrow();
642 jsr166 1.9 } catch (NullPointerException success) {}
643 dl 1.4 }
644    
645     /**
646     * Add of comparable element succeeds
647     */
648     public void testDescendingAdd() {
649     NavigableSet q = dset0();
650     assertTrue(q.add(m6));
651     }
652    
653     /**
654     * Add of duplicate element fails
655     */
656     public void testDescendingAddDup() {
657     NavigableSet q = dset0();
658     assertTrue(q.add(m6));
659     assertFalse(q.add(m6));
660     }
661    
662     /**
663     * Add of non-Comparable throws CCE
664     */
665     public void testDescendingAddNonComparable() {
666     try {
667     NavigableSet q = dset0();
668     q.add(new Object());
669     q.add(new Object());
670     q.add(new Object());
671     shouldThrow();
672 jsr166 1.9 } catch (ClassCastException success) {}
673 dl 1.4 }
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     /**
830     * lower returns preceding element
831     */
832     public void testDescendingLower() {
833     NavigableSet q = dset5();
834     Object e1 = q.lower(m3);
835     assertEquals(m2, e1);
836    
837     Object e2 = q.lower(m6);
838     assertEquals(m5, e2);
839    
840     Object e3 = q.lower(m1);
841     assertNull(e3);
842    
843     Object e4 = q.lower(zero);
844     assertNull(e4);
845     }
846    
847     /**
848     * higher returns next element
849     */
850     public void testDescendingHigher() {
851     NavigableSet q = dset5();
852     Object e1 = q.higher(m3);
853     assertEquals(m4, e1);
854    
855     Object e2 = q.higher(zero);
856     assertEquals(m1, e2);
857    
858     Object e3 = q.higher(m5);
859     assertNull(e3);
860    
861     Object e4 = q.higher(m6);
862     assertNull(e4);
863     }
864    
865     /**
866     * floor returns preceding element
867     */
868     public void testDescendingFloor() {
869     NavigableSet q = dset5();
870     Object e1 = q.floor(m3);
871     assertEquals(m3, e1);
872    
873     Object e2 = q.floor(m6);
874     assertEquals(m5, e2);
875    
876     Object e3 = q.floor(m1);
877     assertEquals(m1, e3);
878    
879     Object e4 = q.floor(zero);
880     assertNull(e4);
881     }
882    
883     /**
884     * ceiling returns next element
885     */
886     public void testDescendingCeiling() {
887     NavigableSet q = dset5();
888     Object e1 = q.ceiling(m3);
889     assertEquals(m3, e1);
890    
891     Object e2 = q.ceiling(zero);
892     assertEquals(m1, e2);
893    
894     Object e3 = q.ceiling(m5);
895     assertEquals(m5, e3);
896    
897     Object e4 = q.ceiling(m6);
898     assertNull(e4);
899     }
900    
901     /**
902     * toArray contains all elements
903     */
904     public void testDescendingToArray() {
905     NavigableSet q = populatedSet(SIZE);
906 jsr166 1.8 Object[] o = q.toArray();
907 dl 1.4 Arrays.sort(o);
908 jsr166 1.8 for (int i = 0; i < o.length; i++)
909     assertEquals(o[i], q.pollFirst());
910 dl 1.4 }
911    
912     /**
913     * toArray(a) contains all elements
914     */
915     public void testDescendingToArray2() {
916     NavigableSet q = populatedSet(SIZE);
917 jsr166 1.8 Integer[] ints = new Integer[SIZE];
918 jsr166 1.15 assertSame(ints, q.toArray(ints));
919 dl 1.4 Arrays.sort(ints);
920 jsr166 1.6 for (int i = 0; i < ints.length; i++)
921 dl 1.4 assertEquals(ints[i], q.pollFirst());
922     }
923 jsr166 1.5
924 dl 1.4 /**
925     * iterator iterates through all elements
926     */
927     public void testDescendingIterator() {
928     NavigableSet q = populatedSet(SIZE);
929     int i = 0;
930 jsr166 1.8 Iterator it = q.iterator();
931 jsr166 1.6 while (it.hasNext()) {
932 dl 1.4 assertTrue(q.contains(it.next()));
933     ++i;
934     }
935     assertEquals(i, SIZE);
936     }
937    
938     /**
939     * iterator of empty set has no elements
940     */
941     public void testDescendingEmptyIterator() {
942     NavigableSet q = dset0();
943     int i = 0;
944 jsr166 1.8 Iterator it = q.iterator();
945 jsr166 1.6 while (it.hasNext()) {
946 dl 1.4 assertTrue(q.contains(it.next()));
947     ++i;
948     }
949     assertEquals(i, 0);
950     }
951    
952     /**
953     * iterator.remove removes current element
954     */
955 jsr166 1.13 public void testDescendingIteratorRemove() {
956 dl 1.4 final NavigableSet q = dset0();
957     q.add(new Integer(2));
958     q.add(new Integer(1));
959     q.add(new Integer(3));
960    
961     Iterator it = q.iterator();
962     it.next();
963     it.remove();
964    
965     it = q.iterator();
966     assertEquals(it.next(), new Integer(2));
967     assertEquals(it.next(), new Integer(3));
968     assertFalse(it.hasNext());
969     }
970    
971     /**
972     * toString contains toStrings of elements
973     */
974     public void testDescendingToString() {
975     NavigableSet q = populatedSet(SIZE);
976     String s = q.toString();
977     for (int i = 0; i < SIZE; ++i) {
978 jsr166 1.19 assertTrue(s.contains(String.valueOf(i)));
979 dl 1.4 }
980 jsr166 1.5 }
981 dl 1.4
982     /**
983 jsr166 1.5 * A deserialized serialized set has same elements
984 dl 1.4 */
985 jsr166 1.9 public void testDescendingSerialization() throws Exception {
986 dl 1.4 NavigableSet q = populatedSet(SIZE);
987 jsr166 1.9 ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
988     ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
989     out.writeObject(q);
990     out.close();
991    
992     ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
993     ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
994     NavigableSet r = (NavigableSet)in.readObject();
995     assertEquals(q.size(), r.size());
996     while (!q.isEmpty())
997     assertEquals(q.pollFirst(), r.pollFirst());
998 dl 1.4 }
999    
1000     /**
1001     * subSet returns set with keys in requested range
1002     */
1003     public void testDescendingSubSetContents() {
1004     NavigableSet set = dset5();
1005     SortedSet sm = set.subSet(m2, m4);
1006     assertEquals(m2, sm.first());
1007     assertEquals(m3, sm.last());
1008     assertEquals(2, sm.size());
1009     assertFalse(sm.contains(m1));
1010     assertTrue(sm.contains(m2));
1011     assertTrue(sm.contains(m3));
1012     assertFalse(sm.contains(m4));
1013     assertFalse(sm.contains(m5));
1014     Iterator i = sm.iterator();
1015     Object k;
1016     k = (Integer)(i.next());
1017     assertEquals(m2, k);
1018     k = (Integer)(i.next());
1019     assertEquals(m3, k);
1020     assertFalse(i.hasNext());
1021     Iterator j = sm.iterator();
1022     j.next();
1023     j.remove();
1024     assertFalse(set.contains(m2));
1025     assertEquals(4, set.size());
1026     assertEquals(1, sm.size());
1027     assertEquals(m3, sm.first());
1028     assertEquals(m3, sm.last());
1029     assertTrue(sm.remove(m3));
1030     assertTrue(sm.isEmpty());
1031     assertEquals(3, set.size());
1032     }
1033    
1034     public void testDescendingSubSetContents2() {
1035     NavigableSet set = dset5();
1036     SortedSet sm = set.subSet(m2, m3);
1037     assertEquals(1, sm.size());
1038     assertEquals(m2, sm.first());
1039     assertEquals(m2, sm.last());
1040     assertFalse(sm.contains(m1));
1041     assertTrue(sm.contains(m2));
1042     assertFalse(sm.contains(m3));
1043     assertFalse(sm.contains(m4));
1044     assertFalse(sm.contains(m5));
1045     Iterator i = sm.iterator();
1046     Object k;
1047     k = (Integer)(i.next());
1048     assertEquals(m2, k);
1049     assertFalse(i.hasNext());
1050     Iterator j = sm.iterator();
1051     j.next();
1052     j.remove();
1053     assertFalse(set.contains(m2));
1054     assertEquals(4, set.size());
1055     assertEquals(0, sm.size());
1056     assertTrue(sm.isEmpty());
1057     assertFalse(sm.remove(m3));
1058     assertEquals(4, set.size());
1059     }
1060    
1061     /**
1062     * headSet returns set with keys in requested range
1063     */
1064     public void testDescendingHeadSetContents() {
1065     NavigableSet set = dset5();
1066     SortedSet sm = set.headSet(m4);
1067     assertTrue(sm.contains(m1));
1068     assertTrue(sm.contains(m2));
1069     assertTrue(sm.contains(m3));
1070     assertFalse(sm.contains(m4));
1071     assertFalse(sm.contains(m5));
1072     Iterator i = sm.iterator();
1073     Object k;
1074     k = (Integer)(i.next());
1075     assertEquals(m1, k);
1076     k = (Integer)(i.next());
1077     assertEquals(m2, k);
1078     k = (Integer)(i.next());
1079     assertEquals(m3, k);
1080     assertFalse(i.hasNext());
1081     sm.clear();
1082     assertTrue(sm.isEmpty());
1083     assertEquals(2, set.size());
1084     assertEquals(m4, set.first());
1085     }
1086    
1087     /**
1088     * tailSet returns set with keys in requested range
1089     */
1090     public void testDescendingTailSetContents() {
1091     NavigableSet set = dset5();
1092     SortedSet sm = set.tailSet(m2);
1093     assertFalse(sm.contains(m1));
1094     assertTrue(sm.contains(m2));
1095     assertTrue(sm.contains(m3));
1096     assertTrue(sm.contains(m4));
1097     assertTrue(sm.contains(m5));
1098     Iterator i = sm.iterator();
1099     Object k;
1100     k = (Integer)(i.next());
1101     assertEquals(m2, k);
1102     k = (Integer)(i.next());
1103     assertEquals(m3, k);
1104     k = (Integer)(i.next());
1105     assertEquals(m4, k);
1106     k = (Integer)(i.next());
1107     assertEquals(m5, k);
1108     assertFalse(i.hasNext());
1109    
1110     SortedSet ssm = sm.tailSet(m4);
1111     assertEquals(m4, ssm.first());
1112     assertEquals(m5, ssm.last());
1113     assertTrue(ssm.remove(m4));
1114     assertEquals(1, ssm.size());
1115     assertEquals(3, sm.size());
1116     assertEquals(4, set.size());
1117     }
1118    
1119 dl 1.1 }