ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/ConcurrentSkipListSubSetTest.java
Revision: 1.39
Committed: Mon May 28 21:19:50 2018 UTC (5 years, 11 months ago) by jsr166
Branch: MAIN
Changes since 1.38: +8 -5 lines
Log Message: 
improve toArray tests

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