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