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