ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/ConcurrentSkipListSubSetTest.java
Revision: 1.25
Committed: Wed Dec 31 16:44:01 2014 UTC (9 years, 4 months ago) by jsr166
Branch: MAIN
Changes since 1.24: +0 -5 lines
Log Message: 
remove unused imports

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