ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/ConcurrentSkipListSubSetTest.java
Revision: 1.38
Committed: Sun Jan 7 22:59:18 2018 UTC (6 years, 3 months ago) by jsr166
Branch: MAIN
Changes since 1.37: +1 -2 lines
Log Message: 
use <>

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.32 main(suite(), args);
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 jsr166 1.35 * Integers 0 ... n - 1.
34 dl 1.1 */
35 jsr166 1.36 private static NavigableSet<Integer> populatedSet(int n) {
36 jsr166 1.38 ConcurrentSkipListSet<Integer> q = new ConcurrentSkipListSet<>();
37 dl 1.1 assertTrue(q.isEmpty());
38    
39 jsr166 1.34 for (int i = n - 1; i >= 0; i -= 2)
40 jsr166 1.8 assertTrue(q.add(new Integer(i)));
41 jsr166 1.27 for (int i = (n & 1); i < n; i += 2)
42 jsr166 1.8 assertTrue(q.add(new Integer(i)));
43 dl 1.1 assertTrue(q.add(new Integer(-n)));
44     assertTrue(q.add(new Integer(n)));
45 dl 1.4 NavigableSet s = q.subSet(new Integer(0), true, new Integer(n), false);
46 dl 1.1 assertFalse(s.isEmpty());
47 jsr166 1.8 assertEquals(n, s.size());
48 dl 1.1 return s;
49     }
50    
51     /**
52 jsr166 1.23 * Returns a new set of first 5 ints.
53 dl 1.1 */
54 jsr166 1.36 private static NavigableSet set5() {
55 dl 1.1 ConcurrentSkipListSet q = new ConcurrentSkipListSet();
56     assertTrue(q.isEmpty());
57     q.add(one);
58     q.add(two);
59     q.add(three);
60     q.add(four);
61     q.add(five);
62     q.add(zero);
63     q.add(seven);
64 dl 1.4 NavigableSet s = q.subSet(one, true, seven, false);
65 jsr166 1.8 assertEquals(5, s.size());
66 dl 1.4 return s;
67     }
68    
69     /**
70 jsr166 1.23 * Returns a new set of first 5 negative ints.
71 dl 1.4 */
72 jsr166 1.36 private static NavigableSet dset5() {
73 dl 1.4 ConcurrentSkipListSet q = new ConcurrentSkipListSet();
74     assertTrue(q.isEmpty());
75     q.add(m1);
76     q.add(m2);
77     q.add(m3);
78     q.add(m4);
79     q.add(m5);
80     NavigableSet s = q.descendingSet();
81 jsr166 1.8 assertEquals(5, s.size());
82 dl 1.1 return s;
83     }
84    
85 jsr166 1.5 private static NavigableSet set0() {
86 jsr166 1.8 ConcurrentSkipListSet set = new ConcurrentSkipListSet();
87 dl 1.1 assertTrue(set.isEmpty());
88 dl 1.4 return set.tailSet(m1, true);
89     }
90    
91 jsr166 1.5 private static NavigableSet dset0() {
92 jsr166 1.8 ConcurrentSkipListSet set = new ConcurrentSkipListSet();
93 dl 1.4 assertTrue(set.isEmpty());
94     return set;
95 dl 1.1 }
96 jsr166 1.5
97 dl 1.1 /**
98     * A new set has unbounded capacity
99     */
100     public void testConstructor1() {
101     assertEquals(0, set0().size());
102     }
103    
104     /**
105     * isEmpty is true before add, false after
106     */
107     public void testEmpty() {
108     NavigableSet q = set0();
109     assertTrue(q.isEmpty());
110     q.add(new Integer(1));
111     assertFalse(q.isEmpty());
112     q.add(new Integer(2));
113     q.pollFirst();
114     q.pollFirst();
115     assertTrue(q.isEmpty());
116     }
117    
118     /**
119     * size changes when elements added and removed
120     */
121     public void testSize() {
122     NavigableSet q = populatedSet(SIZE);
123     for (int i = 0; i < SIZE; ++i) {
124 jsr166 1.33 assertEquals(SIZE - i, q.size());
125 dl 1.1 q.pollFirst();
126     }
127     for (int i = 0; i < SIZE; ++i) {
128     assertEquals(i, q.size());
129     q.add(new Integer(i));
130     }
131     }
132    
133     /**
134     * add(null) throws NPE
135     */
136     public void testAddNull() {
137 jsr166 1.30 NavigableSet q = set0();
138 jsr166 1.8 try {
139 dl 1.1 q.add(null);
140     shouldThrow();
141 jsr166 1.9 } catch (NullPointerException success) {}
142 dl 1.1 }
143    
144     /**
145     * Add of comparable element succeeds
146     */
147     public void testAdd() {
148     NavigableSet q = set0();
149     assertTrue(q.add(six));
150     }
151    
152     /**
153     * Add of duplicate element fails
154     */
155     public void testAddDup() {
156     NavigableSet q = set0();
157     assertTrue(q.add(six));
158     assertFalse(q.add(six));
159     }
160    
161     /**
162     * Add of non-Comparable throws CCE
163     */
164     public void testAddNonComparable() {
165 jsr166 1.30 NavigableSet q = set0();
166 dl 1.1 try {
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 jsr166 1.30 NavigableSet q = set0();
178 dl 1.1 try {
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 jsr166 1.30 NavigableSet q = set0();
189     Integer[] ints = new Integer[SIZE];
190 dl 1.1 try {
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 jsr166 1.30 NavigableSet q = set0();
202     Integer[] ints = new Integer[SIZE];
203 jsr166 1.33 for (int i = 0; i < SIZE - 1; ++i)
204     ints[i] = new Integer(i + SIZE);
205 dl 1.1 try {
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 jsr166 1.33 ints[i] = new Integer(SIZE - 1 - i);
219 jsr166 1.10 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 jsr166 1.27 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 jsr166 1.34 assertTrue(q.contains(i - 1));
247 dl 1.1 }
248 jsr166 1.27 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 jsr166 1.34 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 jsr166 1.33 assertEquals(SIZE - i, q.size());
313 dl 1.1 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 jsr166 1.33 assertEquals(SIZE - i, q.size());
326 dl 1.1 for (int j = 0; j < i; ++j) {
327 jsr166 1.28 Integer x = (Integer)(p.pollFirst());
328     assertFalse(q.contains(x));
329 dl 1.1 }
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 jsr166 1.8 Iterator it = q.iterator();
433 jsr166 1.29 int i;
434     for (i = 0; it.hasNext(); i++)
435 dl 1.1 assertTrue(q.contains(it.next()));
436     assertEquals(i, SIZE);
437 jsr166 1.29 assertIteratorExhausted(it);
438 dl 1.1 }
439    
440     /**
441     * iterator of empty set has no elements
442     */
443     public void testEmptyIterator() {
444 jsr166 1.29 assertIteratorExhausted(set0().iterator());
445 dl 1.1 }
446    
447     /**
448     * iterator.remove removes current element
449     */
450 jsr166 1.13 public void testIteratorRemove() {
451 dl 1.1 final NavigableSet q = set0();
452     q.add(new Integer(2));
453     q.add(new Integer(1));
454     q.add(new Integer(3));
455    
456     Iterator it = q.iterator();
457     it.next();
458     it.remove();
459    
460     it = q.iterator();
461     assertEquals(it.next(), new Integer(2));
462     assertEquals(it.next(), new Integer(3));
463     assertFalse(it.hasNext());
464     }
465    
466     /**
467     * toString contains toStrings of elements
468     */
469     public void testToString() {
470     NavigableSet q = populatedSet(SIZE);
471     String s = q.toString();
472     for (int i = 0; i < SIZE; ++i) {
473 jsr166 1.19 assertTrue(s.contains(String.valueOf(i)));
474 dl 1.1 }
475 jsr166 1.5 }
476 dl 1.1
477     /**
478 jsr166 1.37 * A deserialized/reserialized set equals original
479 dl 1.1 */
480 jsr166 1.9 public void testSerialization() throws Exception {
481 jsr166 1.20 NavigableSet x = populatedSet(SIZE);
482     NavigableSet y = serialClone(x);
483    
484 jsr166 1.24 assertNotSame(y, x);
485 jsr166 1.20 assertEquals(x.size(), y.size());
486     assertEquals(x, y);
487     assertEquals(y, x);
488     while (!x.isEmpty()) {
489     assertFalse(y.isEmpty());
490     assertEquals(x.pollFirst(), y.pollFirst());
491     }
492     assertTrue(y.isEmpty());
493 dl 1.1 }
494    
495     /**
496     * subSet returns set with keys in requested range
497     */
498     public void testSubSetContents() {
499     NavigableSet set = set5();
500     SortedSet sm = set.subSet(two, four);
501     assertEquals(two, sm.first());
502     assertEquals(three, sm.last());
503     assertEquals(2, sm.size());
504     assertFalse(sm.contains(one));
505     assertTrue(sm.contains(two));
506     assertTrue(sm.contains(three));
507     assertFalse(sm.contains(four));
508     assertFalse(sm.contains(five));
509     Iterator i = sm.iterator();
510     Object k;
511     k = (Integer)(i.next());
512     assertEquals(two, k);
513     k = (Integer)(i.next());
514     assertEquals(three, k);
515     assertFalse(i.hasNext());
516     Iterator j = sm.iterator();
517     j.next();
518     j.remove();
519     assertFalse(set.contains(two));
520     assertEquals(4, set.size());
521     assertEquals(1, sm.size());
522     assertEquals(three, sm.first());
523     assertEquals(three, sm.last());
524     assertTrue(sm.remove(three));
525     assertTrue(sm.isEmpty());
526     assertEquals(3, set.size());
527     }
528    
529     public void testSubSetContents2() {
530     NavigableSet set = set5();
531     SortedSet sm = set.subSet(two, three);
532     assertEquals(1, sm.size());
533     assertEquals(two, sm.first());
534     assertEquals(two, sm.last());
535     assertFalse(sm.contains(one));
536     assertTrue(sm.contains(two));
537     assertFalse(sm.contains(three));
538     assertFalse(sm.contains(four));
539     assertFalse(sm.contains(five));
540     Iterator i = sm.iterator();
541     Object k;
542     k = (Integer)(i.next());
543     assertEquals(two, k);
544     assertFalse(i.hasNext());
545     Iterator j = sm.iterator();
546     j.next();
547     j.remove();
548     assertFalse(set.contains(two));
549     assertEquals(4, set.size());
550     assertEquals(0, sm.size());
551     assertTrue(sm.isEmpty());
552     assertFalse(sm.remove(three));
553     assertEquals(4, set.size());
554     }
555    
556     /**
557     * headSet returns set with keys in requested range
558     */
559     public void testHeadSetContents() {
560     NavigableSet set = set5();
561     SortedSet sm = set.headSet(four);
562     assertTrue(sm.contains(one));
563     assertTrue(sm.contains(two));
564     assertTrue(sm.contains(three));
565     assertFalse(sm.contains(four));
566     assertFalse(sm.contains(five));
567     Iterator i = sm.iterator();
568     Object k;
569     k = (Integer)(i.next());
570     assertEquals(one, k);
571     k = (Integer)(i.next());
572     assertEquals(two, k);
573     k = (Integer)(i.next());
574     assertEquals(three, k);
575     assertFalse(i.hasNext());
576     sm.clear();
577     assertTrue(sm.isEmpty());
578     assertEquals(2, set.size());
579     assertEquals(four, set.first());
580     }
581    
582     /**
583     * tailSet returns set with keys in requested range
584     */
585     public void testTailSetContents() {
586     NavigableSet set = set5();
587     SortedSet sm = set.tailSet(two);
588     assertFalse(sm.contains(one));
589     assertTrue(sm.contains(two));
590     assertTrue(sm.contains(three));
591     assertTrue(sm.contains(four));
592     assertTrue(sm.contains(five));
593     Iterator i = sm.iterator();
594     Object k;
595     k = (Integer)(i.next());
596     assertEquals(two, k);
597     k = (Integer)(i.next());
598     assertEquals(three, k);
599     k = (Integer)(i.next());
600     assertEquals(four, k);
601     k = (Integer)(i.next());
602     assertEquals(five, k);
603     assertFalse(i.hasNext());
604    
605     SortedSet ssm = sm.tailSet(four);
606     assertEquals(four, ssm.first());
607     assertEquals(five, ssm.last());
608     assertTrue(ssm.remove(four));
609     assertEquals(1, ssm.size());
610     assertEquals(3, sm.size());
611     assertEquals(4, set.size());
612     }
613    
614 dl 1.4 /**
615     * size changes when elements added and removed
616     */
617     public void testDescendingSize() {
618     NavigableSet q = populatedSet(SIZE);
619     for (int i = 0; i < SIZE; ++i) {
620 jsr166 1.33 assertEquals(SIZE - i, q.size());
621 dl 1.4 q.pollFirst();
622     }
623     for (int i = 0; i < SIZE; ++i) {
624     assertEquals(i, q.size());
625     q.add(new Integer(i));
626     }
627     }
628    
629     /**
630     * add(null) throws NPE
631     */
632     public void testDescendingAddNull() {
633 jsr166 1.30 NavigableSet q = dset0();
634 jsr166 1.8 try {
635 dl 1.4 q.add(null);
636     shouldThrow();
637 jsr166 1.9 } catch (NullPointerException success) {}
638 dl 1.4 }
639    
640     /**
641     * Add of comparable element succeeds
642     */
643     public void testDescendingAdd() {
644     NavigableSet q = dset0();
645     assertTrue(q.add(m6));
646     }
647    
648     /**
649     * Add of duplicate element fails
650     */
651     public void testDescendingAddDup() {
652     NavigableSet q = dset0();
653     assertTrue(q.add(m6));
654     assertFalse(q.add(m6));
655     }
656    
657     /**
658     * Add of non-Comparable throws CCE
659     */
660     public void testDescendingAddNonComparable() {
661 jsr166 1.30 NavigableSet q = dset0();
662 dl 1.4 try {
663     q.add(new Object());
664     q.add(new Object());
665     shouldThrow();
666 jsr166 1.9 } catch (ClassCastException success) {}
667 dl 1.4 }
668    
669     /**
670     * addAll(null) throws NPE
671     */
672     public void testDescendingAddAll1() {
673 jsr166 1.30 NavigableSet q = dset0();
674 dl 1.4 try {
675     q.addAll(null);
676     shouldThrow();
677 jsr166 1.9 } catch (NullPointerException success) {}
678 dl 1.4 }
679 jsr166 1.14
680 dl 1.4 /**
681     * addAll of a collection with null elements throws NPE
682     */
683     public void testDescendingAddAll2() {
684 jsr166 1.30 NavigableSet q = dset0();
685     Integer[] ints = new Integer[SIZE];
686 dl 1.4 try {
687     q.addAll(Arrays.asList(ints));
688     shouldThrow();
689 jsr166 1.9 } catch (NullPointerException success) {}
690 dl 1.4 }
691 jsr166 1.14
692 dl 1.4 /**
693     * addAll of a collection with any null elements throws NPE after
694     * possibly adding some elements
695     */
696     public void testDescendingAddAll3() {
697 jsr166 1.30 NavigableSet q = dset0();
698     Integer[] ints = new Integer[SIZE];
699 jsr166 1.33 for (int i = 0; i < SIZE - 1; ++i)
700     ints[i] = new Integer(i + SIZE);
701 dl 1.4 try {
702     q.addAll(Arrays.asList(ints));
703     shouldThrow();
704 jsr166 1.9 } catch (NullPointerException success) {}
705 dl 1.4 }
706    
707     /**
708     * Set contains all elements of successful addAll
709     */
710     public void testDescendingAddAll5() {
711 jsr166 1.10 Integer[] empty = new Integer[0];
712     Integer[] ints = new Integer[SIZE];
713     for (int i = 0; i < SIZE; ++i)
714 jsr166 1.33 ints[i] = new Integer(SIZE - 1 - i);
715 jsr166 1.10 NavigableSet q = dset0();
716     assertFalse(q.addAll(Arrays.asList(empty)));
717     assertTrue(q.addAll(Arrays.asList(ints)));
718     for (int i = 0; i < SIZE; ++i)
719     assertEquals(new Integer(i), q.pollFirst());
720 dl 1.4 }
721    
722     /**
723     * poll succeeds unless empty
724     */
725     public void testDescendingPoll() {
726     NavigableSet q = populatedSet(SIZE);
727     for (int i = 0; i < SIZE; ++i) {
728 jsr166 1.11 assertEquals(i, q.pollFirst());
729 dl 1.4 }
730 jsr166 1.8 assertNull(q.pollFirst());
731 dl 1.4 }
732    
733     /**
734     * remove(x) removes x and returns true if present
735     */
736     public void testDescendingRemoveElement() {
737     NavigableSet q = populatedSet(SIZE);
738 jsr166 1.27 for (int i = 1; i < SIZE; i += 2) {
739 dl 1.4 assertTrue(q.remove(new Integer(i)));
740     }
741 jsr166 1.27 for (int i = 0; i < SIZE; i += 2 ) {
742 dl 1.4 assertTrue(q.remove(new Integer(i)));
743 jsr166 1.34 assertFalse(q.remove(new Integer(i + 1)));
744 dl 1.4 }
745     assertTrue(q.isEmpty());
746     }
747 jsr166 1.5
748 dl 1.4 /**
749     * contains(x) reports true when elements added but not yet removed
750     */
751     public void testDescendingContains() {
752     NavigableSet q = populatedSet(SIZE);
753     for (int i = 0; i < SIZE; ++i) {
754     assertTrue(q.contains(new Integer(i)));
755     q.pollFirst();
756     assertFalse(q.contains(new Integer(i)));
757     }
758     }
759    
760     /**
761     * clear removes all elements
762     */
763     public void testDescendingClear() {
764     NavigableSet q = populatedSet(SIZE);
765     q.clear();
766     assertTrue(q.isEmpty());
767     assertEquals(0, q.size());
768     q.add(new Integer(1));
769     assertFalse(q.isEmpty());
770     q.clear();
771     assertTrue(q.isEmpty());
772     }
773    
774     /**
775     * containsAll(c) is true when c contains a subset of elements
776     */
777     public void testDescendingContainsAll() {
778     NavigableSet q = populatedSet(SIZE);
779     NavigableSet p = dset0();
780     for (int i = 0; i < SIZE; ++i) {
781     assertTrue(q.containsAll(p));
782     assertFalse(p.containsAll(q));
783     p.add(new Integer(i));
784     }
785     assertTrue(p.containsAll(q));
786     }
787    
788     /**
789     * retainAll(c) retains only those elements of c and reports true if changed
790     */
791     public void testDescendingRetainAll() {
792     NavigableSet q = populatedSet(SIZE);
793     NavigableSet p = populatedSet(SIZE);
794     for (int i = 0; i < SIZE; ++i) {
795     boolean changed = q.retainAll(p);
796     if (i == 0)
797     assertFalse(changed);
798     else
799     assertTrue(changed);
800    
801     assertTrue(q.containsAll(p));
802 jsr166 1.33 assertEquals(SIZE - i, q.size());
803 dl 1.4 p.pollFirst();
804     }
805     }
806    
807     /**
808     * removeAll(c) removes only those elements of c and reports true if changed
809     */
810     public void testDescendingRemoveAll() {
811     for (int i = 1; i < SIZE; ++i) {
812     NavigableSet q = populatedSet(SIZE);
813     NavigableSet p = populatedSet(i);
814     assertTrue(q.removeAll(p));
815 jsr166 1.33 assertEquals(SIZE - i, q.size());
816 dl 1.4 for (int j = 0; j < i; ++j) {
817 jsr166 1.28 Integer x = (Integer)(p.pollFirst());
818     assertFalse(q.contains(x));
819 dl 1.4 }
820     }
821     }
822    
823     /**
824     * lower returns preceding element
825     */
826     public void testDescendingLower() {
827     NavigableSet q = dset5();
828     Object e1 = q.lower(m3);
829     assertEquals(m2, e1);
830    
831     Object e2 = q.lower(m6);
832     assertEquals(m5, e2);
833    
834     Object e3 = q.lower(m1);
835     assertNull(e3);
836    
837     Object e4 = q.lower(zero);
838     assertNull(e4);
839     }
840    
841     /**
842     * higher returns next element
843     */
844     public void testDescendingHigher() {
845     NavigableSet q = dset5();
846     Object e1 = q.higher(m3);
847     assertEquals(m4, e1);
848    
849     Object e2 = q.higher(zero);
850     assertEquals(m1, e2);
851    
852     Object e3 = q.higher(m5);
853     assertNull(e3);
854    
855     Object e4 = q.higher(m6);
856     assertNull(e4);
857     }
858    
859     /**
860     * floor returns preceding element
861     */
862     public void testDescendingFloor() {
863     NavigableSet q = dset5();
864     Object e1 = q.floor(m3);
865     assertEquals(m3, e1);
866    
867     Object e2 = q.floor(m6);
868     assertEquals(m5, e2);
869    
870     Object e3 = q.floor(m1);
871     assertEquals(m1, e3);
872    
873     Object e4 = q.floor(zero);
874     assertNull(e4);
875     }
876    
877     /**
878     * ceiling returns next element
879     */
880     public void testDescendingCeiling() {
881     NavigableSet q = dset5();
882     Object e1 = q.ceiling(m3);
883     assertEquals(m3, e1);
884    
885     Object e2 = q.ceiling(zero);
886     assertEquals(m1, e2);
887    
888     Object e3 = q.ceiling(m5);
889     assertEquals(m5, e3);
890    
891     Object e4 = q.ceiling(m6);
892     assertNull(e4);
893     }
894    
895     /**
896     * toArray contains all elements
897     */
898     public void testDescendingToArray() {
899     NavigableSet q = populatedSet(SIZE);
900 jsr166 1.8 Object[] o = q.toArray();
901 dl 1.4 Arrays.sort(o);
902 jsr166 1.8 for (int i = 0; i < o.length; i++)
903     assertEquals(o[i], q.pollFirst());
904 dl 1.4 }
905    
906     /**
907     * toArray(a) contains all elements
908     */
909     public void testDescendingToArray2() {
910     NavigableSet q = populatedSet(SIZE);
911 jsr166 1.8 Integer[] ints = new Integer[SIZE];
912 jsr166 1.15 assertSame(ints, q.toArray(ints));
913 dl 1.4 Arrays.sort(ints);
914 jsr166 1.6 for (int i = 0; i < ints.length; i++)
915 dl 1.4 assertEquals(ints[i], q.pollFirst());
916     }
917 jsr166 1.5
918 dl 1.4 /**
919     * iterator iterates through all elements
920     */
921     public void testDescendingIterator() {
922     NavigableSet q = populatedSet(SIZE);
923     int i = 0;
924 jsr166 1.8 Iterator it = q.iterator();
925 jsr166 1.6 while (it.hasNext()) {
926 dl 1.4 assertTrue(q.contains(it.next()));
927     ++i;
928     }
929     assertEquals(i, SIZE);
930     }
931    
932     /**
933     * iterator of empty set has no elements
934     */
935     public void testDescendingEmptyIterator() {
936     NavigableSet q = dset0();
937     int i = 0;
938 jsr166 1.8 Iterator it = q.iterator();
939 jsr166 1.6 while (it.hasNext()) {
940 dl 1.4 assertTrue(q.contains(it.next()));
941     ++i;
942     }
943 jsr166 1.21 assertEquals(0, i);
944 dl 1.4 }
945    
946     /**
947     * iterator.remove removes current element
948     */
949 jsr166 1.13 public void testDescendingIteratorRemove() {
950 dl 1.4 final NavigableSet q = dset0();
951     q.add(new Integer(2));
952     q.add(new Integer(1));
953     q.add(new Integer(3));
954    
955     Iterator it = q.iterator();
956     it.next();
957     it.remove();
958    
959     it = q.iterator();
960     assertEquals(it.next(), new Integer(2));
961     assertEquals(it.next(), new Integer(3));
962     assertFalse(it.hasNext());
963     }
964    
965     /**
966     * toString contains toStrings of elements
967     */
968     public void testDescendingToString() {
969     NavigableSet q = populatedSet(SIZE);
970     String s = q.toString();
971     for (int i = 0; i < SIZE; ++i) {
972 jsr166 1.19 assertTrue(s.contains(String.valueOf(i)));
973 dl 1.4 }
974 jsr166 1.5 }
975 dl 1.4
976     /**
977 jsr166 1.37 * A deserialized/reserialized set equals original
978 dl 1.4 */
979 jsr166 1.9 public void testDescendingSerialization() throws Exception {
980 jsr166 1.20 NavigableSet x = dset5();
981     NavigableSet y = serialClone(x);
982    
983 jsr166 1.24 assertNotSame(y, x);
984 jsr166 1.20 assertEquals(x.size(), y.size());
985     assertEquals(x, y);
986     assertEquals(y, x);
987     while (!x.isEmpty()) {
988     assertFalse(y.isEmpty());
989     assertEquals(x.pollFirst(), y.pollFirst());
990     }
991     assertTrue(y.isEmpty());
992 dl 1.4 }
993    
994     /**
995     * subSet returns set with keys in requested range
996     */
997     public void testDescendingSubSetContents() {
998     NavigableSet set = dset5();
999     SortedSet sm = set.subSet(m2, m4);
1000     assertEquals(m2, sm.first());
1001     assertEquals(m3, sm.last());
1002     assertEquals(2, sm.size());
1003     assertFalse(sm.contains(m1));
1004     assertTrue(sm.contains(m2));
1005     assertTrue(sm.contains(m3));
1006     assertFalse(sm.contains(m4));
1007     assertFalse(sm.contains(m5));
1008     Iterator i = sm.iterator();
1009     Object k;
1010     k = (Integer)(i.next());
1011     assertEquals(m2, k);
1012     k = (Integer)(i.next());
1013     assertEquals(m3, k);
1014     assertFalse(i.hasNext());
1015     Iterator j = sm.iterator();
1016     j.next();
1017     j.remove();
1018     assertFalse(set.contains(m2));
1019     assertEquals(4, set.size());
1020     assertEquals(1, sm.size());
1021     assertEquals(m3, sm.first());
1022     assertEquals(m3, sm.last());
1023     assertTrue(sm.remove(m3));
1024     assertTrue(sm.isEmpty());
1025     assertEquals(3, set.size());
1026     }
1027    
1028     public void testDescendingSubSetContents2() {
1029     NavigableSet set = dset5();
1030     SortedSet sm = set.subSet(m2, m3);
1031     assertEquals(1, sm.size());
1032     assertEquals(m2, sm.first());
1033     assertEquals(m2, sm.last());
1034     assertFalse(sm.contains(m1));
1035     assertTrue(sm.contains(m2));
1036     assertFalse(sm.contains(m3));
1037     assertFalse(sm.contains(m4));
1038     assertFalse(sm.contains(m5));
1039     Iterator i = sm.iterator();
1040     Object k;
1041     k = (Integer)(i.next());
1042     assertEquals(m2, k);
1043     assertFalse(i.hasNext());
1044     Iterator j = sm.iterator();
1045     j.next();
1046     j.remove();
1047     assertFalse(set.contains(m2));
1048     assertEquals(4, set.size());
1049     assertEquals(0, sm.size());
1050     assertTrue(sm.isEmpty());
1051     assertFalse(sm.remove(m3));
1052     assertEquals(4, set.size());
1053     }
1054    
1055     /**
1056     * headSet returns set with keys in requested range
1057     */
1058     public void testDescendingHeadSetContents() {
1059     NavigableSet set = dset5();
1060     SortedSet sm = set.headSet(m4);
1061     assertTrue(sm.contains(m1));
1062     assertTrue(sm.contains(m2));
1063     assertTrue(sm.contains(m3));
1064     assertFalse(sm.contains(m4));
1065     assertFalse(sm.contains(m5));
1066     Iterator i = sm.iterator();
1067     Object k;
1068     k = (Integer)(i.next());
1069     assertEquals(m1, k);
1070     k = (Integer)(i.next());
1071     assertEquals(m2, k);
1072     k = (Integer)(i.next());
1073     assertEquals(m3, k);
1074     assertFalse(i.hasNext());
1075     sm.clear();
1076     assertTrue(sm.isEmpty());
1077     assertEquals(2, set.size());
1078     assertEquals(m4, set.first());
1079     }
1080    
1081     /**
1082     * tailSet returns set with keys in requested range
1083     */
1084     public void testDescendingTailSetContents() {
1085     NavigableSet set = dset5();
1086     SortedSet sm = set.tailSet(m2);
1087     assertFalse(sm.contains(m1));
1088     assertTrue(sm.contains(m2));
1089     assertTrue(sm.contains(m3));
1090     assertTrue(sm.contains(m4));
1091     assertTrue(sm.contains(m5));
1092     Iterator i = sm.iterator();
1093     Object k;
1094     k = (Integer)(i.next());
1095     assertEquals(m2, k);
1096     k = (Integer)(i.next());
1097     assertEquals(m3, k);
1098     k = (Integer)(i.next());
1099     assertEquals(m4, k);
1100     k = (Integer)(i.next());
1101     assertEquals(m5, k);
1102     assertFalse(i.hasNext());
1103    
1104     SortedSet ssm = sm.tailSet(m4);
1105     assertEquals(m4, ssm.first());
1106     assertEquals(m5, ssm.last());
1107     assertTrue(ssm.remove(m4));
1108     assertEquals(1, ssm.size());
1109     assertEquals(3, sm.size());
1110     assertEquals(4, set.size());
1111     }
1112    
1113 dl 1.1 }