ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/TreeSetTest.java
Revision: 1.30
Committed: Wed Dec 31 19:05:43 2014 UTC (9 years, 4 months ago) by jsr166
Branch: MAIN
Changes since 1.29: +3 -1 lines
Log Message:
no wildcard imports

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.20 * http://creativecommons.org/publicdomain/zero/1.0/
5 dl 1.1 */
6    
7 jsr166 1.23 import java.util.Arrays;
8     import java.util.BitSet;
9     import java.util.Collection;
10     import java.util.Comparator;
11     import java.util.Iterator;
12     import java.util.NavigableSet;
13     import java.util.NoSuchElementException;
14     import java.util.Random;
15     import java.util.Set;
16     import java.util.SortedSet;
17     import java.util.TreeSet;
18 dl 1.1
19 jsr166 1.30 import junit.framework.Test;
20     import junit.framework.TestSuite;
21    
22 dl 1.1 public class TreeSetTest extends JSR166TestCase {
23     public static void main(String[] args) {
24 jsr166 1.13 junit.textui.TestRunner.run(suite());
25 dl 1.1 }
26     public static Test suite() {
27 jsr166 1.7 return new TestSuite(TreeSetTest.class);
28 dl 1.1 }
29    
30 jsr166 1.4 static class MyReverseComparator implements Comparator {
31 dl 1.1 public int compare(Object x, Object y) {
32 jsr166 1.11 return ((Comparable)y).compareTo(x);
33 dl 1.1 }
34     }
35    
36     /**
37     * The number of elements to place in collections, arrays, etc.
38     */
39     static final int SIZE = 20;
40    
41     /**
42 jsr166 1.27 * Returns a new set of given size containing consecutive
43 dl 1.1 * Integers 0 ... n.
44     */
45 jsr166 1.18 private TreeSet<Integer> populatedSet(int n) {
46     TreeSet<Integer> q = new TreeSet<Integer>();
47 dl 1.1 assertTrue(q.isEmpty());
48 jsr166 1.7 for (int i = n-1; i >= 0; i-=2)
49     assertTrue(q.add(new Integer(i)));
50     for (int i = (n & 1); i < n; i+=2)
51     assertTrue(q.add(new Integer(i)));
52 dl 1.1 assertFalse(q.isEmpty());
53 jsr166 1.7 assertEquals(n, q.size());
54 dl 1.1 return q;
55     }
56    
57     /**
58 jsr166 1.27 * Returns a new set of first 5 ints.
59 dl 1.1 */
60     private TreeSet set5() {
61     TreeSet q = new TreeSet();
62     assertTrue(q.isEmpty());
63     q.add(one);
64     q.add(two);
65     q.add(three);
66     q.add(four);
67     q.add(five);
68 jsr166 1.7 assertEquals(5, q.size());
69 dl 1.1 return q;
70     }
71 jsr166 1.4
72 dl 1.1 /**
73     * A new set has unbounded capacity
74     */
75     public void testConstructor1() {
76     assertEquals(0, new TreeSet().size());
77     }
78    
79     /**
80     * Initializing from null Collection throws NPE
81     */
82     public void testConstructor3() {
83     try {
84     TreeSet q = new TreeSet((Collection)null);
85     shouldThrow();
86 jsr166 1.8 } catch (NullPointerException success) {}
87 dl 1.1 }
88    
89     /**
90     * Initializing from Collection of null elements throws NPE
91     */
92     public void testConstructor4() {
93     try {
94     Integer[] ints = new Integer[SIZE];
95     TreeSet q = new TreeSet(Arrays.asList(ints));
96     shouldThrow();
97 jsr166 1.8 } catch (NullPointerException success) {}
98 dl 1.1 }
99    
100     /**
101     * Initializing from Collection with some null elements throws NPE
102     */
103     public void testConstructor5() {
104     try {
105     Integer[] ints = new Integer[SIZE];
106     for (int i = 0; i < SIZE-1; ++i)
107     ints[i] = new Integer(i);
108     TreeSet q = new TreeSet(Arrays.asList(ints));
109     shouldThrow();
110 jsr166 1.8 } catch (NullPointerException success) {}
111 dl 1.1 }
112    
113     /**
114     * Set contains all elements of collection used to initialize
115     */
116     public void testConstructor6() {
117 jsr166 1.9 Integer[] ints = new Integer[SIZE];
118     for (int i = 0; i < SIZE; ++i)
119     ints[i] = new Integer(i);
120     TreeSet q = new TreeSet(Arrays.asList(ints));
121     for (int i = 0; i < SIZE; ++i)
122     assertEquals(ints[i], q.pollFirst());
123 dl 1.1 }
124    
125     /**
126     * The comparator used in constructor is used
127     */
128     public void testConstructor7() {
129 jsr166 1.9 MyReverseComparator cmp = new MyReverseComparator();
130     TreeSet q = new TreeSet(cmp);
131     assertEquals(cmp, q.comparator());
132     Integer[] ints = new Integer[SIZE];
133     for (int i = 0; i < SIZE; ++i)
134     ints[i] = new Integer(i);
135     q.addAll(Arrays.asList(ints));
136     for (int i = SIZE-1; i >= 0; --i)
137     assertEquals(ints[i], q.pollFirst());
138 dl 1.1 }
139    
140     /**
141     * isEmpty is true before add, false after
142     */
143     public void testEmpty() {
144     TreeSet q = new TreeSet();
145     assertTrue(q.isEmpty());
146     q.add(new Integer(1));
147     assertFalse(q.isEmpty());
148     q.add(new Integer(2));
149     q.pollFirst();
150     q.pollFirst();
151     assertTrue(q.isEmpty());
152     }
153    
154     /**
155     * size changes when elements added and removed
156     */
157     public void testSize() {
158     TreeSet q = populatedSet(SIZE);
159     for (int i = 0; i < SIZE; ++i) {
160     assertEquals(SIZE-i, q.size());
161     q.pollFirst();
162     }
163     for (int i = 0; i < SIZE; ++i) {
164     assertEquals(i, q.size());
165     q.add(new Integer(i));
166     }
167     }
168    
169     /**
170     * add(null) throws NPE if nonempty
171     */
172     public void testAddNull() {
173 jsr166 1.7 try {
174 dl 1.1 TreeSet q = populatedSet(SIZE);
175     q.add(null);
176     shouldThrow();
177 jsr166 1.8 } catch (NullPointerException success) {}
178 dl 1.1 }
179    
180     /**
181     * Add of comparable element succeeds
182     */
183     public void testAdd() {
184     TreeSet q = new TreeSet();
185     assertTrue(q.add(zero));
186     assertTrue(q.add(one));
187     }
188    
189     /**
190     * Add of duplicate element fails
191     */
192     public void testAddDup() {
193     TreeSet q = new TreeSet();
194     assertTrue(q.add(zero));
195     assertFalse(q.add(zero));
196     }
197    
198     /**
199     * Add of non-Comparable throws CCE
200     */
201     public void testAddNonComparable() {
202     try {
203     TreeSet q = new TreeSet();
204     q.add(new Object());
205     q.add(new Object());
206     q.add(new Object());
207     shouldThrow();
208 jsr166 1.8 } catch (ClassCastException success) {}
209 dl 1.1 }
210    
211     /**
212     * addAll(null) throws NPE
213     */
214     public void testAddAll1() {
215     try {
216     TreeSet q = new TreeSet();
217     q.addAll(null);
218     shouldThrow();
219 jsr166 1.8 } catch (NullPointerException success) {}
220 dl 1.1 }
221 jsr166 1.14
222 dl 1.1 /**
223     * addAll of a collection with null elements throws NPE
224     */
225     public void testAddAll2() {
226     try {
227     TreeSet q = new TreeSet();
228     Integer[] ints = new Integer[SIZE];
229     q.addAll(Arrays.asList(ints));
230     shouldThrow();
231 jsr166 1.8 } catch (NullPointerException success) {}
232 dl 1.1 }
233 jsr166 1.14
234 dl 1.1 /**
235     * addAll of a collection with any null elements throws NPE after
236     * possibly adding some elements
237     */
238     public void testAddAll3() {
239     try {
240     TreeSet q = new TreeSet();
241     Integer[] ints = new Integer[SIZE];
242     for (int i = 0; i < SIZE-1; ++i)
243     ints[i] = new Integer(i);
244     q.addAll(Arrays.asList(ints));
245     shouldThrow();
246 jsr166 1.8 } catch (NullPointerException success) {}
247 dl 1.1 }
248    
249     /**
250     * Set contains all elements of successful addAll
251     */
252     public void testAddAll5() {
253 jsr166 1.9 Integer[] empty = new Integer[0];
254     Integer[] ints = new Integer[SIZE];
255     for (int i = 0; i < SIZE; ++i)
256     ints[i] = new Integer(SIZE-1-i);
257     TreeSet q = new TreeSet();
258     assertFalse(q.addAll(Arrays.asList(empty)));
259     assertTrue(q.addAll(Arrays.asList(ints)));
260     for (int i = 0; i < SIZE; ++i)
261     assertEquals(new Integer(i), q.pollFirst());
262 dl 1.1 }
263    
264     /**
265     * pollFirst succeeds unless empty
266     */
267     public void testPollFirst() {
268     TreeSet q = populatedSet(SIZE);
269     for (int i = 0; i < SIZE; ++i) {
270 jsr166 1.11 assertEquals(i, q.pollFirst());
271 dl 1.1 }
272 jsr166 1.7 assertNull(q.pollFirst());
273 dl 1.1 }
274    
275     /**
276     * pollLast succeeds unless empty
277     */
278     public void testPollLast() {
279     TreeSet q = populatedSet(SIZE);
280     for (int i = SIZE-1; i >= 0; --i) {
281 jsr166 1.11 assertEquals(i, q.pollLast());
282 dl 1.1 }
283 jsr166 1.7 assertNull(q.pollFirst());
284 dl 1.1 }
285    
286     /**
287     * remove(x) removes x and returns true if present
288     */
289     public void testRemoveElement() {
290     TreeSet q = populatedSet(SIZE);
291     for (int i = 1; i < SIZE; i+=2) {
292 jsr166 1.19 assertTrue(q.contains(i));
293     assertTrue(q.remove(i));
294     assertFalse(q.contains(i));
295     assertTrue(q.contains(i-1));
296 dl 1.1 }
297     for (int i = 0; i < SIZE; i+=2) {
298 jsr166 1.19 assertTrue(q.contains(i));
299     assertTrue(q.remove(i));
300     assertFalse(q.contains(i));
301     assertFalse(q.remove(i+1));
302     assertFalse(q.contains(i+1));
303 dl 1.1 }
304     assertTrue(q.isEmpty());
305     }
306 jsr166 1.4
307 dl 1.1 /**
308     * contains(x) reports true when elements added but not yet removed
309     */
310     public void testContains() {
311     TreeSet q = populatedSet(SIZE);
312     for (int i = 0; i < SIZE; ++i) {
313     assertTrue(q.contains(new Integer(i)));
314     q.pollFirst();
315     assertFalse(q.contains(new Integer(i)));
316     }
317     }
318    
319     /**
320     * clear removes all elements
321     */
322     public void testClear() {
323     TreeSet q = populatedSet(SIZE);
324     q.clear();
325     assertTrue(q.isEmpty());
326     assertEquals(0, q.size());
327     q.add(new Integer(1));
328     assertFalse(q.isEmpty());
329     q.clear();
330     assertTrue(q.isEmpty());
331     }
332    
333     /**
334     * containsAll(c) is true when c contains a subset of elements
335     */
336     public void testContainsAll() {
337     TreeSet q = populatedSet(SIZE);
338     TreeSet p = new TreeSet();
339     for (int i = 0; i < SIZE; ++i) {
340     assertTrue(q.containsAll(p));
341     assertFalse(p.containsAll(q));
342     p.add(new Integer(i));
343     }
344     assertTrue(p.containsAll(q));
345     }
346    
347     /**
348     * retainAll(c) retains only those elements of c and reports true if changed
349     */
350     public void testRetainAll() {
351     TreeSet q = populatedSet(SIZE);
352     TreeSet p = populatedSet(SIZE);
353     for (int i = 0; i < SIZE; ++i) {
354     boolean changed = q.retainAll(p);
355     if (i == 0)
356     assertFalse(changed);
357     else
358     assertTrue(changed);
359    
360     assertTrue(q.containsAll(p));
361     assertEquals(SIZE-i, q.size());
362     p.pollFirst();
363     }
364     }
365    
366     /**
367     * removeAll(c) removes only those elements of c and reports true if changed
368     */
369     public void testRemoveAll() {
370     for (int i = 1; i < SIZE; ++i) {
371     TreeSet q = populatedSet(SIZE);
372     TreeSet p = populatedSet(i);
373     assertTrue(q.removeAll(p));
374     assertEquals(SIZE-i, q.size());
375     for (int j = 0; j < i; ++j) {
376     Integer I = (Integer)(p.pollFirst());
377     assertFalse(q.contains(I));
378     }
379     }
380     }
381    
382     /**
383     * lower returns preceding element
384     */
385     public void testLower() {
386     TreeSet q = set5();
387     Object e1 = q.lower(three);
388     assertEquals(two, e1);
389    
390     Object e2 = q.lower(six);
391     assertEquals(five, e2);
392    
393     Object e3 = q.lower(one);
394     assertNull(e3);
395    
396     Object e4 = q.lower(zero);
397     assertNull(e4);
398     }
399    
400     /**
401     * higher returns next element
402     */
403     public void testHigher() {
404     TreeSet q = set5();
405     Object e1 = q.higher(three);
406     assertEquals(four, e1);
407    
408     Object e2 = q.higher(zero);
409     assertEquals(one, e2);
410    
411     Object e3 = q.higher(five);
412     assertNull(e3);
413    
414     Object e4 = q.higher(six);
415     assertNull(e4);
416     }
417    
418     /**
419     * floor returns preceding element
420     */
421     public void testFloor() {
422     TreeSet q = set5();
423     Object e1 = q.floor(three);
424     assertEquals(three, e1);
425    
426     Object e2 = q.floor(six);
427     assertEquals(five, e2);
428    
429     Object e3 = q.floor(one);
430     assertEquals(one, e3);
431    
432     Object e4 = q.floor(zero);
433     assertNull(e4);
434     }
435    
436     /**
437     * ceiling returns next element
438     */
439     public void testCeiling() {
440     TreeSet q = set5();
441     Object e1 = q.ceiling(three);
442     assertEquals(three, e1);
443    
444     Object e2 = q.ceiling(zero);
445     assertEquals(one, e2);
446    
447     Object e3 = q.ceiling(five);
448     assertEquals(five, e3);
449    
450     Object e4 = q.ceiling(six);
451     assertNull(e4);
452     }
453    
454     /**
455 jsr166 1.17 * toArray contains all elements in sorted order
456 dl 1.1 */
457     public void testToArray() {
458     TreeSet q = populatedSet(SIZE);
459 jsr166 1.7 Object[] o = q.toArray();
460     for (int i = 0; i < o.length; i++)
461 jsr166 1.17 assertSame(o[i], q.pollFirst());
462 dl 1.1 }
463    
464     /**
465 jsr166 1.17 * toArray(a) contains all elements in sorted order
466 dl 1.1 */
467     public void testToArray2() {
468 jsr166 1.18 TreeSet<Integer> q = populatedSet(SIZE);
469 jsr166 1.7 Integer[] ints = new Integer[SIZE];
470 jsr166 1.18 Integer[] array = q.toArray(ints);
471     assertSame(ints, array);
472 jsr166 1.5 for (int i = 0; i < ints.length; i++)
473 jsr166 1.17 assertSame(ints[i], q.pollFirst());
474 dl 1.1 }
475 jsr166 1.4
476 dl 1.1 /**
477     * iterator iterates through all elements
478     */
479     public void testIterator() {
480     TreeSet q = populatedSet(SIZE);
481     int i = 0;
482 jsr166 1.7 Iterator it = q.iterator();
483 jsr166 1.5 while (it.hasNext()) {
484 dl 1.1 assertTrue(q.contains(it.next()));
485     ++i;
486     }
487     assertEquals(i, SIZE);
488     }
489    
490     /**
491     * iterator of empty set has no elements
492     */
493     public void testEmptyIterator() {
494     TreeSet q = new TreeSet();
495     int i = 0;
496 jsr166 1.7 Iterator it = q.iterator();
497 jsr166 1.5 while (it.hasNext()) {
498 dl 1.1 assertTrue(q.contains(it.next()));
499     ++i;
500     }
501 jsr166 1.24 assertEquals(0, i);
502 dl 1.1 }
503    
504     /**
505     * iterator.remove removes current element
506     */
507 jsr166 1.13 public void testIteratorRemove() {
508 dl 1.1 final TreeSet q = new TreeSet();
509     q.add(new Integer(2));
510     q.add(new Integer(1));
511     q.add(new Integer(3));
512    
513     Iterator it = q.iterator();
514     it.next();
515     it.remove();
516    
517     it = q.iterator();
518     assertEquals(it.next(), new Integer(2));
519     assertEquals(it.next(), new Integer(3));
520     assertFalse(it.hasNext());
521     }
522    
523     /**
524     * toString contains toStrings of elements
525     */
526     public void testToString() {
527     TreeSet q = populatedSet(SIZE);
528     String s = q.toString();
529     for (int i = 0; i < SIZE; ++i) {
530 jsr166 1.22 assertTrue(s.contains(String.valueOf(i)));
531 dl 1.1 }
532 jsr166 1.4 }
533 dl 1.1
534     /**
535 jsr166 1.4 * A deserialized serialized set has same elements
536 dl 1.1 */
537 jsr166 1.8 public void testSerialization() throws Exception {
538 jsr166 1.23 NavigableSet x = populatedSet(SIZE);
539     NavigableSet y = serialClone(x);
540    
541 jsr166 1.29 assertNotSame(x, y);
542 jsr166 1.23 assertEquals(x.size(), y.size());
543     assertEquals(x, y);
544     assertEquals(y, x);
545     while (!x.isEmpty()) {
546     assertFalse(y.isEmpty());
547     assertEquals(x.pollFirst(), y.pollFirst());
548     }
549     assertTrue(y.isEmpty());
550 dl 1.1 }
551    
552     /**
553     * subSet returns set with keys in requested range
554     */
555     public void testSubSetContents() {
556     TreeSet set = set5();
557     SortedSet sm = set.subSet(two, four);
558     assertEquals(two, sm.first());
559     assertEquals(three, sm.last());
560     assertEquals(2, sm.size());
561     assertFalse(sm.contains(one));
562     assertTrue(sm.contains(two));
563     assertTrue(sm.contains(three));
564     assertFalse(sm.contains(four));
565     assertFalse(sm.contains(five));
566     Iterator i = sm.iterator();
567     Object k;
568     k = (Integer)(i.next());
569     assertEquals(two, k);
570     k = (Integer)(i.next());
571     assertEquals(three, k);
572     assertFalse(i.hasNext());
573     Iterator j = sm.iterator();
574     j.next();
575     j.remove();
576     assertFalse(set.contains(two));
577     assertEquals(4, set.size());
578     assertEquals(1, sm.size());
579     assertEquals(three, sm.first());
580     assertEquals(three, sm.last());
581     assertTrue(sm.remove(three));
582     assertTrue(sm.isEmpty());
583     assertEquals(3, set.size());
584     }
585    
586     public void testSubSetContents2() {
587     TreeSet set = set5();
588     SortedSet sm = set.subSet(two, three);
589     assertEquals(1, sm.size());
590     assertEquals(two, sm.first());
591     assertEquals(two, sm.last());
592     assertFalse(sm.contains(one));
593     assertTrue(sm.contains(two));
594     assertFalse(sm.contains(three));
595     assertFalse(sm.contains(four));
596     assertFalse(sm.contains(five));
597     Iterator i = sm.iterator();
598     Object k;
599     k = (Integer)(i.next());
600     assertEquals(two, k);
601     assertFalse(i.hasNext());
602     Iterator j = sm.iterator();
603     j.next();
604     j.remove();
605     assertFalse(set.contains(two));
606     assertEquals(4, set.size());
607     assertEquals(0, sm.size());
608     assertTrue(sm.isEmpty());
609     assertFalse(sm.remove(three));
610     assertEquals(4, set.size());
611     }
612    
613     /**
614     * headSet returns set with keys in requested range
615     */
616     public void testHeadSetContents() {
617     TreeSet set = set5();
618     SortedSet sm = set.headSet(four);
619     assertTrue(sm.contains(one));
620     assertTrue(sm.contains(two));
621     assertTrue(sm.contains(three));
622     assertFalse(sm.contains(four));
623     assertFalse(sm.contains(five));
624     Iterator i = sm.iterator();
625     Object k;
626     k = (Integer)(i.next());
627     assertEquals(one, k);
628     k = (Integer)(i.next());
629     assertEquals(two, k);
630     k = (Integer)(i.next());
631     assertEquals(three, k);
632     assertFalse(i.hasNext());
633     sm.clear();
634     assertTrue(sm.isEmpty());
635     assertEquals(2, set.size());
636     assertEquals(four, set.first());
637     }
638    
639     /**
640     * tailSet returns set with keys in requested range
641     */
642     public void testTailSetContents() {
643     TreeSet set = set5();
644     SortedSet sm = set.tailSet(two);
645     assertFalse(sm.contains(one));
646     assertTrue(sm.contains(two));
647     assertTrue(sm.contains(three));
648     assertTrue(sm.contains(four));
649     assertTrue(sm.contains(five));
650     Iterator i = sm.iterator();
651     Object k;
652     k = (Integer)(i.next());
653     assertEquals(two, k);
654     k = (Integer)(i.next());
655     assertEquals(three, k);
656     k = (Integer)(i.next());
657     assertEquals(four, k);
658     k = (Integer)(i.next());
659     assertEquals(five, k);
660     assertFalse(i.hasNext());
661    
662     SortedSet ssm = sm.tailSet(four);
663     assertEquals(four, ssm.first());
664     assertEquals(five, ssm.last());
665     assertTrue(ssm.remove(four));
666     assertEquals(1, ssm.size());
667     assertEquals(3, sm.size());
668     assertEquals(4, set.size());
669     }
670    
671 dl 1.2 Random rnd = new Random(666);
672     BitSet bs;
673    
674     /**
675     * Subsets of subsets subdivide correctly
676     */
677 jsr166 1.10 public void testRecursiveSubSets() throws Exception {
678 jsr166 1.16 int setSize = expensiveTests ? 1000 : 100;
679 jsr166 1.7 Class cl = TreeSet.class;
680 dl 1.2
681     NavigableSet<Integer> set = newSet(cl);
682     bs = new BitSet(setSize);
683    
684     populate(set, setSize);
685     check(set, 0, setSize - 1, true);
686     check(set.descendingSet(), 0, setSize - 1, false);
687    
688     mutateSet(set, 0, setSize - 1);
689     check(set, 0, setSize - 1, true);
690     check(set.descendingSet(), 0, setSize - 1, false);
691    
692 dl 1.3 bashSubSet(set.subSet(0, true, setSize, false),
693 dl 1.2 0, setSize - 1, true);
694     }
695    
696 jsr166 1.28 /**
697     * addAll is idempotent
698     */
699     public void testAddAll_idempotent() throws Exception {
700     Set x = populatedSet(SIZE);
701     Set y = new TreeSet(x);
702     y.addAll(x);
703     assertEquals(x, y);
704     assertEquals(y, x);
705     }
706    
707 jsr166 1.10 static NavigableSet<Integer> newSet(Class cl) throws Exception {
708     NavigableSet<Integer> result = (NavigableSet<Integer>) cl.newInstance();
709 jsr166 1.24 assertEquals(0, result.size());
710 dl 1.2 assertFalse(result.iterator().hasNext());
711     return result;
712     }
713    
714     void populate(NavigableSet<Integer> set, int limit) {
715     for (int i = 0, n = 2 * limit / 3; i < n; i++) {
716     int element = rnd.nextInt(limit);
717     put(set, element);
718     }
719     }
720    
721     void mutateSet(NavigableSet<Integer> set, int min, int max) {
722     int size = set.size();
723     int rangeSize = max - min + 1;
724    
725     // Remove a bunch of entries directly
726     for (int i = 0, n = rangeSize / 2; i < n; i++) {
727     remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
728     }
729    
730     // Remove a bunch of entries with iterator
731 jsr166 1.5 for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
732 dl 1.2 if (rnd.nextBoolean()) {
733     bs.clear(it.next());
734     it.remove();
735     }
736     }
737    
738     // Add entries till we're back to original size
739     while (set.size() < size) {
740     int element = min + rnd.nextInt(rangeSize);
741     assertTrue(element >= min && element<= max);
742     put(set, element);
743     }
744     }
745    
746     void mutateSubSet(NavigableSet<Integer> set, int min, int max) {
747     int size = set.size();
748     int rangeSize = max - min + 1;
749    
750     // Remove a bunch of entries directly
751     for (int i = 0, n = rangeSize / 2; i < n; i++) {
752     remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
753     }
754    
755     // Remove a bunch of entries with iterator
756 jsr166 1.5 for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
757 dl 1.2 if (rnd.nextBoolean()) {
758     bs.clear(it.next());
759     it.remove();
760     }
761     }
762    
763     // Add entries till we're back to original size
764     while (set.size() < size) {
765     int element = min - 5 + rnd.nextInt(rangeSize + 10);
766     if (element >= min && element<= max) {
767     put(set, element);
768     } else {
769     try {
770     set.add(element);
771 jsr166 1.10 shouldThrow();
772     } catch (IllegalArgumentException success) {}
773 dl 1.2 }
774     }
775     }
776    
777     void put(NavigableSet<Integer> set, int element) {
778     if (set.add(element))
779     bs.set(element);
780     }
781    
782     void remove(NavigableSet<Integer> set, int element) {
783     if (set.remove(element))
784     bs.clear(element);
785     }
786    
787     void bashSubSet(NavigableSet<Integer> set,
788     int min, int max, boolean ascending) {
789     check(set, min, max, ascending);
790     check(set.descendingSet(), min, max, !ascending);
791    
792     mutateSubSet(set, min, max);
793     check(set, min, max, ascending);
794     check(set.descendingSet(), min, max, !ascending);
795    
796     // Recurse
797     if (max - min < 2)
798     return;
799     int midPoint = (min + max) / 2;
800    
801     // headSet - pick direction and endpoint inclusion randomly
802     boolean incl = rnd.nextBoolean();
803 dl 1.3 NavigableSet<Integer> hm = set.headSet(midPoint, incl);
804 dl 1.2 if (ascending) {
805     if (rnd.nextBoolean())
806     bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true);
807     else
808     bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1),
809     false);
810     } else {
811     if (rnd.nextBoolean())
812     bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false);
813     else
814     bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max,
815     true);
816     }
817    
818     // tailSet - pick direction and endpoint inclusion randomly
819     incl = rnd.nextBoolean();
820 dl 1.3 NavigableSet<Integer> tm = set.tailSet(midPoint,incl);
821 dl 1.2 if (ascending) {
822     if (rnd.nextBoolean())
823     bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true);
824     else
825     bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max,
826     false);
827     } else {
828     if (rnd.nextBoolean()) {
829     bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false);
830     } else {
831     bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1),
832     true);
833     }
834     }
835    
836     // subSet - pick direction and endpoint inclusion randomly
837     int rangeSize = max - min + 1;
838     int[] endpoints = new int[2];
839     endpoints[0] = min + rnd.nextInt(rangeSize);
840     endpoints[1] = min + rnd.nextInt(rangeSize);
841     Arrays.sort(endpoints);
842     boolean lowIncl = rnd.nextBoolean();
843     boolean highIncl = rnd.nextBoolean();
844     if (ascending) {
845 dl 1.3 NavigableSet<Integer> sm = set.subSet(
846 dl 1.2 endpoints[0], lowIncl, endpoints[1], highIncl);
847     if (rnd.nextBoolean())
848     bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
849     endpoints[1] - (highIncl ? 0 : 1), true);
850     else
851     bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
852     endpoints[1] - (highIncl ? 0 : 1), false);
853     } else {
854 dl 1.3 NavigableSet<Integer> sm = set.subSet(
855 dl 1.2 endpoints[1], highIncl, endpoints[0], lowIncl);
856     if (rnd.nextBoolean())
857     bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
858     endpoints[1] - (highIncl ? 0 : 1), false);
859     else
860     bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
861     endpoints[1] - (highIncl ? 0 : 1), true);
862     }
863     }
864    
865     /**
866     * min and max are both inclusive. If max < min, interval is empty.
867     */
868     void check(NavigableSet<Integer> set,
869     final int min, final int max, final boolean ascending) {
870 jsr166 1.21 class ReferenceSet {
871 dl 1.2 int lower(int element) {
872     return ascending ?
873     lowerAscending(element) : higherAscending(element);
874     }
875     int floor(int element) {
876     return ascending ?
877     floorAscending(element) : ceilingAscending(element);
878     }
879     int ceiling(int element) {
880     return ascending ?
881     ceilingAscending(element) : floorAscending(element);
882     }
883     int higher(int element) {
884     return ascending ?
885     higherAscending(element) : lowerAscending(element);
886     }
887     int first() {
888     return ascending ? firstAscending() : lastAscending();
889     }
890     int last() {
891     return ascending ? lastAscending() : firstAscending();
892     }
893     int lowerAscending(int element) {
894     return floorAscending(element - 1);
895     }
896     int floorAscending(int element) {
897     if (element < min)
898     return -1;
899     else if (element > max)
900     element = max;
901    
902     // BitSet should support this! Test would run much faster
903     while (element >= min) {
904     if (bs.get(element))
905 jsr166 1.15 return element;
906 dl 1.2 element--;
907     }
908     return -1;
909     }
910     int ceilingAscending(int element) {
911     if (element < min)
912     element = min;
913     else if (element > max)
914     return -1;
915     int result = bs.nextSetBit(element);
916     return result > max ? -1 : result;
917     }
918     int higherAscending(int element) {
919     return ceilingAscending(element + 1);
920     }
921     private int firstAscending() {
922     int result = ceilingAscending(min);
923     return result > max ? -1 : result;
924     }
925     private int lastAscending() {
926     int result = floorAscending(max);
927     return result < min ? -1 : result;
928     }
929     }
930     ReferenceSet rs = new ReferenceSet();
931    
932     // Test contents using containsElement
933     int size = 0;
934     for (int i = min; i <= max; i++) {
935     boolean bsContainsI = bs.get(i);
936     assertEquals(bsContainsI, set.contains(i));
937     if (bsContainsI)
938     size++;
939     }
940 jsr166 1.25 assertEquals(size, set.size());
941 dl 1.2
942     // Test contents using contains elementSet iterator
943     int size2 = 0;
944     int previousElement = -1;
945     for (int element : set) {
946     assertTrue(bs.get(element));
947     size2++;
948     assertTrue(previousElement < 0 || (ascending ?
949     element - previousElement > 0 : element - previousElement < 0));
950     previousElement = element;
951     }
952     assertEquals(size2, size);
953    
954     // Test navigation ops
955     for (int element = min - 1; element <= max + 1; element++) {
956     assertEq(set.lower(element), rs.lower(element));
957     assertEq(set.floor(element), rs.floor(element));
958     assertEq(set.higher(element), rs.higher(element));
959     assertEq(set.ceiling(element), rs.ceiling(element));
960     }
961    
962     // Test extrema
963     if (set.size() != 0) {
964     assertEq(set.first(), rs.first());
965     assertEq(set.last(), rs.last());
966     } else {
967     assertEq(rs.first(), -1);
968     assertEq(rs.last(), -1);
969     try {
970     set.first();
971 jsr166 1.10 shouldThrow();
972     } catch (NoSuchElementException success) {}
973 dl 1.2 try {
974     set.last();
975 jsr166 1.10 shouldThrow();
976     } catch (NoSuchElementException success) {}
977 dl 1.2 }
978     }
979    
980     static void assertEq(Integer i, int j) {
981     if (i == null)
982     assertEquals(j, -1);
983     else
984     assertEquals((int) i, j);
985     }
986    
987     static boolean eq(Integer i, int j) {
988     return i == null ? j == -1 : i == j;
989     }
990    
991 dl 1.1 }