ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/TreeSubSetTest.java
Revision: 1.40
Committed: Wed Jan 27 01:57:25 2021 UTC (3 years, 3 months ago) by jsr166
Branch: MAIN
CVS Tags: HEAD
Changes since 1.39: +7 -7 lines
Log Message: 
use diamond <> pervasively

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