ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/TreeSetTest.java
(Generate patch)

Comparing jsr166/src/test/tck/TreeSetTest.java (file contents):
Revision 1.1 by dl, Tue Dec 28 16:15:59 2004 UTC vs.
Revision 1.48 by jsr166, Mon May 28 21:51:44 2018 UTC

# Line 1 | Line 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
4 > * http://creativecommons.org/publicdomain/zero/1.0/
5   */
6  
7 < import junit.framework.*;
8 < import java.util.*;
9 < import java.util.concurrent.*;
10 < import java.io.*;
7 > 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 >
19 > import junit.framework.Test;
20 > import junit.framework.TestSuite;
21  
22   public class TreeSetTest extends JSR166TestCase {
23      public static void main(String[] args) {
24 <        junit.textui.TestRunner.run (suite());  
24 >        main(suite(), args);
25      }
26      public static Test suite() {
27 <        return new TestSuite(TreeSetTest.class);
27 >        return new TestSuite(TreeSetTest.class);
28      }
29  
30 <    static class MyReverseComparator implements Comparator {
30 >    static class MyReverseComparator implements Comparator {
31          public int compare(Object x, Object y) {
32 <            int i = ((Integer)x).intValue();
23 <            int j = ((Integer)y).intValue();
24 <            if (i < j) return 1;
25 <            if (i > j) return -1;
26 <            return 0;
32 >            return ((Comparable)y).compareTo(x);
33          }
34      }
35  
# Line 33 | Line 39 | public class TreeSetTest extends JSR166T
39      static final int SIZE = 20;
40  
41      /**
42 <     * Create a set of given size containing consecutive
43 <     * Integers 0 ... n.
42 >     * Returns a new set of given size containing consecutive
43 >     * Integers 0 ... n - 1.
44       */
45 <    private TreeSet populatedSet(int n) {
46 <        TreeSet q = new TreeSet();
45 >    private static TreeSet<Integer> populatedSet(int n) {
46 >        TreeSet<Integer> q = new TreeSet<>();
47          assertTrue(q.isEmpty());
48 <        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)));
48 >        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          assertFalse(q.isEmpty());
53 <        assertEquals(n, q.size());
53 >        assertEquals(n, q.size());
54          return q;
55      }
56  
57      /**
58 <     * Create set of first 5 ints
58 >     * Returns a new set of first 5 ints.
59       */
60 <    private TreeSet set5() {
60 >    private static TreeSet set5() {
61          TreeSet q = new TreeSet();
62          assertTrue(q.isEmpty());
63          q.add(one);
# Line 59 | Line 65 | public class TreeSetTest extends JSR166T
65          q.add(three);
66          q.add(four);
67          q.add(five);
68 <        assertEquals(5, q.size());
68 >        assertEquals(5, q.size());
69          return q;
70      }
71 <
71 >
72      /**
73       * A new set has unbounded capacity
74       */
# Line 75 | Line 81 | public class TreeSetTest extends JSR166T
81       */
82      public void testConstructor3() {
83          try {
84 <            TreeSet q = new TreeSet((Collection)null);
84 >            new TreeSet((Collection)null);
85              shouldThrow();
86 <        }
81 <        catch (NullPointerException success) {}
86 >        } catch (NullPointerException success) {}
87      }
88  
89      /**
# Line 86 | Line 91 | public class TreeSetTest extends JSR166T
91       */
92      public void testConstructor4() {
93          try {
94 <            Integer[] ints = new Integer[SIZE];
90 <            TreeSet q = new TreeSet(Arrays.asList(ints));
94 >            new TreeSet(Arrays.asList(new Integer[SIZE]));
95              shouldThrow();
96 <        }
93 <        catch (NullPointerException success) {}
96 >        } catch (NullPointerException success) {}
97      }
98  
99      /**
100       * Initializing from Collection with some null elements throws NPE
101       */
102      public void testConstructor5() {
103 +        Integer[] ints = new Integer[SIZE];
104 +        for (int i = 0; i < SIZE - 1; ++i)
105 +            ints[i] = new Integer(i);
106          try {
107 <            Integer[] ints = new Integer[SIZE];
102 <            for (int i = 0; i < SIZE-1; ++i)
103 <                ints[i] = new Integer(i);
104 <            TreeSet q = new TreeSet(Arrays.asList(ints));
107 >            new TreeSet(Arrays.asList(ints));
108              shouldThrow();
109 <        }
107 <        catch (NullPointerException success) {}
109 >        } catch (NullPointerException success) {}
110      }
111  
112      /**
113       * Set contains all elements of collection used to initialize
114       */
115      public void testConstructor6() {
116 <        try {
117 <            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)
120 <                assertEquals(ints[i], q.pollFirst());
121 <        }
122 <        finally {}
116 >        Integer[] ints = new Integer[SIZE];
117 >        for (int i = 0; i < SIZE; ++i)
118 >            ints[i] = new Integer(i);
119 >        TreeSet q = new TreeSet(Arrays.asList(ints));
120 >        for (int i = 0; i < SIZE; ++i)
121 >            assertEquals(ints[i], q.pollFirst());
122      }
123  
124      /**
125       * The comparator used in constructor is used
126       */
127      public void testConstructor7() {
128 <        try {
129 <            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)
138 <                assertEquals(ints[i], q.pollFirst());
139 <        }
140 <        finally {}
128 >        MyReverseComparator cmp = new MyReverseComparator();
129 >        TreeSet q = new TreeSet(cmp);
130 >        assertEquals(cmp, q.comparator());
131 >        Integer[] ints = new Integer[SIZE];
132 >        for (int i = 0; i < SIZE; ++i)
133 >            ints[i] = new Integer(i);
134 >        q.addAll(Arrays.asList(ints));
135 >        for (int i = SIZE - 1; i >= 0; --i)
136 >            assertEquals(ints[i], q.pollFirst());
137      }
138  
139      /**
# Line 160 | Line 156 | public class TreeSetTest extends JSR166T
156      public void testSize() {
157          TreeSet q = populatedSet(SIZE);
158          for (int i = 0; i < SIZE; ++i) {
159 <            assertEquals(SIZE-i, q.size());
159 >            assertEquals(SIZE - i, q.size());
160              q.pollFirst();
161          }
162          for (int i = 0; i < SIZE; ++i) {
# Line 173 | Line 169 | public class TreeSetTest extends JSR166T
169       * add(null) throws NPE if nonempty
170       */
171      public void testAddNull() {
172 <        try {
173 <            TreeSet q = populatedSet(SIZE);
172 >        TreeSet q = populatedSet(SIZE);
173 >        try {
174              q.add(null);
175              shouldThrow();
176 <        } catch (NullPointerException success) { }  
176 >        } catch (NullPointerException success) {}
177      }
178  
179      /**
# Line 202 | Line 198 | public class TreeSetTest extends JSR166T
198       * Add of non-Comparable throws CCE
199       */
200      public void testAddNonComparable() {
201 +        TreeSet q = new TreeSet();
202          try {
206            TreeSet q = new TreeSet();
207            q.add(new Object());
203              q.add(new Object());
204              q.add(new Object());
205              shouldThrow();
206 <        }
212 <        catch(ClassCastException success) {}
206 >        } catch (ClassCastException success) {}
207      }
208  
209      /**
210       * addAll(null) throws NPE
211       */
212      public void testAddAll1() {
213 +        TreeSet q = new TreeSet();
214          try {
220            TreeSet q = new TreeSet();
215              q.addAll(null);
216              shouldThrow();
217 <        }
224 <        catch (NullPointerException success) {}
217 >        } catch (NullPointerException success) {}
218      }
219 +
220      /**
221       * addAll of a collection with null elements throws NPE
222       */
223      public void testAddAll2() {
224 +        TreeSet q = new TreeSet();
225 +        Integer[] ints = new Integer[SIZE];
226          try {
231            TreeSet q = new TreeSet();
232            Integer[] ints = new Integer[SIZE];
227              q.addAll(Arrays.asList(ints));
228              shouldThrow();
229 <        }
236 <        catch (NullPointerException success) {}
229 >        } catch (NullPointerException success) {}
230      }
231 +
232      /**
233       * addAll of a collection with any null elements throws NPE after
234       * possibly adding some elements
235       */
236      public void testAddAll3() {
237 +        TreeSet q = new TreeSet();
238 +        Integer[] ints = new Integer[SIZE];
239 +        for (int i = 0; i < SIZE - 1; ++i)
240 +            ints[i] = new Integer(i);
241          try {
244            TreeSet q = new TreeSet();
245            Integer[] ints = new Integer[SIZE];
246            for (int i = 0; i < SIZE-1; ++i)
247                ints[i] = new Integer(i);
242              q.addAll(Arrays.asList(ints));
243              shouldThrow();
244 <        }
251 <        catch (NullPointerException success) {}
244 >        } catch (NullPointerException success) {}
245      }
246  
247      /**
248       * Set contains all elements of successful addAll
249       */
250      public void testAddAll5() {
251 <        try {
252 <            Integer[] empty = new Integer[0];
253 <            Integer[] ints = new Integer[SIZE];
254 <            for (int i = 0; i < SIZE; ++i)
255 <                ints[i] = new Integer(SIZE-1-i);
256 <            TreeSet q = new TreeSet();
257 <            assertFalse(q.addAll(Arrays.asList(empty)));
258 <            assertTrue(q.addAll(Arrays.asList(ints)));
259 <            for (int i = 0; i < SIZE; ++i)
267 <                assertEquals(new Integer(i), q.pollFirst());
268 <        }
269 <        finally {}
251 >        Integer[] empty = new Integer[0];
252 >        Integer[] ints = new Integer[SIZE];
253 >        for (int i = 0; i < SIZE; ++i)
254 >            ints[i] = new Integer(SIZE - 1 - i);
255 >        TreeSet q = new TreeSet();
256 >        assertFalse(q.addAll(Arrays.asList(empty)));
257 >        assertTrue(q.addAll(Arrays.asList(ints)));
258 >        for (int i = 0; i < SIZE; ++i)
259 >            assertEquals(new Integer(i), q.pollFirst());
260      }
261  
262      /**
# Line 275 | Line 265 | public class TreeSetTest extends JSR166T
265      public void testPollFirst() {
266          TreeSet q = populatedSet(SIZE);
267          for (int i = 0; i < SIZE; ++i) {
268 <            assertEquals(i, ((Integer)q.pollFirst()).intValue());
268 >            assertEquals(i, q.pollFirst());
269          }
270 <        assertNull(q.pollFirst());
270 >        assertNull(q.pollFirst());
271      }
272  
273      /**
# Line 285 | Line 275 | public class TreeSetTest extends JSR166T
275       */
276      public void testPollLast() {
277          TreeSet q = populatedSet(SIZE);
278 <        for (int i = SIZE-1; i >= 0; --i) {
279 <            assertEquals(i, ((Integer)q.pollLast()).intValue());
278 >        for (int i = SIZE - 1; i >= 0; --i) {
279 >            assertEquals(i, q.pollLast());
280          }
281 <        assertNull(q.pollFirst());
281 >        assertNull(q.pollFirst());
282      }
283  
294
284      /**
285       * remove(x) removes x and returns true if present
286       */
287      public void testRemoveElement() {
288          TreeSet q = populatedSet(SIZE);
289 <        for (int i = 1; i < SIZE; i+=2) {
290 <            assertTrue(q.remove(new Integer(i)));
291 <        }
292 <        for (int i = 0; i < SIZE; i+=2) {
293 <            assertTrue(q.remove(new Integer(i)));
294 <            assertFalse(q.remove(new Integer(i+1)));
289 >        for (int i = 1; i < SIZE; i += 2) {
290 >            assertTrue(q.contains(i));
291 >            assertTrue(q.remove(i));
292 >            assertFalse(q.contains(i));
293 >            assertTrue(q.contains(i - 1));
294 >        }
295 >        for (int i = 0; i < SIZE; i += 2) {
296 >            assertTrue(q.contains(i));
297 >            assertTrue(q.remove(i));
298 >            assertFalse(q.contains(i));
299 >            assertFalse(q.remove(i + 1));
300 >            assertFalse(q.contains(i + 1));
301          }
302          assertTrue(q.isEmpty());
303      }
304 <        
304 >
305      /**
306       * contains(x) reports true when elements added but not yet removed
307       */
# Line 361 | Line 356 | public class TreeSetTest extends JSR166T
356                  assertTrue(changed);
357  
358              assertTrue(q.containsAll(p));
359 <            assertEquals(SIZE-i, q.size());
359 >            assertEquals(SIZE - i, q.size());
360              p.pollFirst();
361          }
362      }
# Line 374 | Line 369 | public class TreeSetTest extends JSR166T
369              TreeSet q = populatedSet(SIZE);
370              TreeSet p = populatedSet(i);
371              assertTrue(q.removeAll(p));
372 <            assertEquals(SIZE-i, q.size());
372 >            assertEquals(SIZE - i, q.size());
373              for (int j = 0; j < i; ++j) {
374 <                Integer I = (Integer)(p.pollFirst());
375 <                assertFalse(q.contains(I));
374 >                Integer x = (Integer)(p.pollFirst());
375 >                assertFalse(q.contains(x));
376              }
377          }
378      }
379  
385    
386
380      /**
381       * lower returns preceding element
382       */
# Line 400 | Line 393 | public class TreeSetTest extends JSR166T
393  
394          Object e4 = q.lower(zero);
395          assertNull(e4);
403
396      }
397  
398      /**
# Line 419 | Line 411 | public class TreeSetTest extends JSR166T
411  
412          Object e4 = q.higher(six);
413          assertNull(e4);
422
414      }
415  
416      /**
# Line 438 | Line 429 | public class TreeSetTest extends JSR166T
429  
430          Object e4 = q.floor(zero);
431          assertNull(e4);
441
432      }
433  
434      /**
# Line 457 | Line 447 | public class TreeSetTest extends JSR166T
447  
448          Object e4 = q.ceiling(six);
449          assertNull(e4);
460
450      }
451  
452      /**
453 <     * toArray contains all elements
453 >     * toArray contains all elements in sorted order
454       */
455      public void testToArray() {
456          TreeSet q = populatedSet(SIZE);
457 <        Object[] o = q.toArray();
458 <        Arrays.sort(o);
459 <        for(int i = 0; i < o.length; i++)
460 <            assertEquals(o[i], q.pollFirst());
457 >        Object[] a = q.toArray();
458 >        assertSame(Object[].class, a.getClass());
459 >        for (Object o : a)
460 >            assertSame(o, q.pollFirst());
461 >        assertTrue(q.isEmpty());
462      }
463  
464      /**
465 <     * toArray(a) contains all elements
465 >     * toArray(a) contains all elements in sorted order
466       */
467      public void testToArray2() {
468 <        TreeSet q = populatedSet(SIZE);
469 <        Integer[] ints = new Integer[SIZE];
470 <        ints = (Integer[])q.toArray(ints);
471 <        Arrays.sort(ints);
472 <        for(int i = 0; i < ints.length; i++)
473 <            assertEquals(ints[i], q.pollFirst());
468 >        TreeSet<Integer> q = populatedSet(SIZE);
469 >        Integer[] ints = new Integer[SIZE];
470 >        Integer[] array = q.toArray(ints);
471 >        assertSame(ints, array);
472 >        for (Integer o : ints)
473 >            assertSame(o, q.pollFirst());
474 >        assertTrue(q.isEmpty());
475      }
476 <    
476 >
477      /**
478       * iterator iterates through all elements
479       */
480      public void testIterator() {
481          TreeSet q = populatedSet(SIZE);
482 <        int i = 0;
483 <        Iterator it = q.iterator();
484 <        while(it.hasNext()) {
482 >        Iterator it = q.iterator();
483 >        int i;
484 >        for (i = 0; it.hasNext(); i++)
485              assertTrue(q.contains(it.next()));
495            ++i;
496        }
486          assertEquals(i, SIZE);
487 +        assertIteratorExhausted(it);
488      }
489  
490      /**
491       * iterator of empty set has no elements
492       */
493      public void testEmptyIterator() {
494 <        TreeSet q = new TreeSet();
505 <        int i = 0;
506 <        Iterator it = q.iterator();
507 <        while(it.hasNext()) {
508 <            assertTrue(q.contains(it.next()));
509 <            ++i;
510 <        }
511 <        assertEquals(i, 0);
494 >        assertIteratorExhausted(new TreeSet().iterator());
495      }
496  
497      /**
498       * iterator.remove removes current element
499       */
500 <    public void testIteratorRemove () {
500 >    public void testIteratorRemove() {
501          final TreeSet q = new TreeSet();
502          q.add(new Integer(2));
503          q.add(new Integer(1));
# Line 530 | Line 513 | public class TreeSetTest extends JSR166T
513          assertFalse(it.hasNext());
514      }
515  
533
516      /**
517       * toString contains toStrings of elements
518       */
# Line 538 | Line 520 | public class TreeSetTest extends JSR166T
520          TreeSet q = populatedSet(SIZE);
521          String s = q.toString();
522          for (int i = 0; i < SIZE; ++i) {
523 <            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
523 >            assertTrue(s.contains(String.valueOf(i)));
524          }
525 <    }        
525 >    }
526  
527      /**
528 <     * A deserialized serialized set has same elements
528 >     * A deserialized/reserialized set equals original
529       */
530 <    public void testSerialization() {
531 <        TreeSet q = populatedSet(SIZE);
532 <        try {
533 <            ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
534 <            ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
535 <            out.writeObject(q);
536 <            out.close();
537 <
538 <            ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
539 <            ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
540 <            TreeSet r = (TreeSet)in.readObject();
559 <            assertEquals(q.size(), r.size());
560 <            while (!q.isEmpty())
561 <                assertEquals(q.pollFirst(), r.pollFirst());
562 <        } catch(Exception e){
563 <            e.printStackTrace();
564 <            unexpectedException();
530 >    public void testSerialization() throws Exception {
531 >        NavigableSet x = populatedSet(SIZE);
532 >        NavigableSet y = serialClone(x);
533 >
534 >        assertNotSame(x, y);
535 >        assertEquals(x.size(), y.size());
536 >        assertEquals(x, y);
537 >        assertEquals(y, x);
538 >        while (!x.isEmpty()) {
539 >            assertFalse(y.isEmpty());
540 >            assertEquals(x.pollFirst(), y.pollFirst());
541          }
542 +        assertTrue(y.isEmpty());
543      }
544  
545      /**
# Line 684 | Line 661 | public class TreeSetTest extends JSR166T
661          assertEquals(4, set.size());
662      }
663  
664 +    Random rnd = new Random(666);
665 +    BitSet bs;
666 +
667 +    /**
668 +     * Subsets of subsets subdivide correctly
669 +     */
670 +    public void testRecursiveSubSets() throws Exception {
671 +        int setSize = expensiveTests ? 1000 : 100;
672 +        Class cl = TreeSet.class;
673 +
674 +        NavigableSet<Integer> set = newSet(cl);
675 +        bs = new BitSet(setSize);
676 +
677 +        populate(set, setSize);
678 +        check(set,                 0, setSize - 1, true);
679 +        check(set.descendingSet(), 0, setSize - 1, false);
680 +
681 +        mutateSet(set, 0, setSize - 1);
682 +        check(set,                 0, setSize - 1, true);
683 +        check(set.descendingSet(), 0, setSize - 1, false);
684 +
685 +        bashSubSet(set.subSet(0, true, setSize, false),
686 +                   0, setSize - 1, true);
687 +    }
688 +
689 +    /**
690 +     * addAll is idempotent
691 +     */
692 +    public void testAddAll_idempotent() throws Exception {
693 +        Set x = populatedSet(SIZE);
694 +        Set y = new TreeSet(x);
695 +        y.addAll(x);
696 +        assertEquals(x, y);
697 +        assertEquals(y, x);
698 +    }
699 +
700 +    static NavigableSet<Integer> newSet(Class cl) throws Exception {
701 +        NavigableSet<Integer> result =
702 +            (NavigableSet<Integer>) cl.getConstructor().newInstance();
703 +        assertEquals(0, result.size());
704 +        assertFalse(result.iterator().hasNext());
705 +        return result;
706 +    }
707 +
708 +    void populate(NavigableSet<Integer> set, int limit) {
709 +        for (int i = 0, n = 2 * limit / 3; i < n; i++) {
710 +            int element = rnd.nextInt(limit);
711 +            put(set, element);
712 +        }
713 +    }
714 +
715 +    void mutateSet(NavigableSet<Integer> set, int min, int max) {
716 +        int size = set.size();
717 +        int rangeSize = max - min + 1;
718 +
719 +        // Remove a bunch of entries directly
720 +        for (int i = 0, n = rangeSize / 2; i < n; i++) {
721 +            remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
722 +        }
723 +
724 +        // Remove a bunch of entries with iterator
725 +        for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
726 +            if (rnd.nextBoolean()) {
727 +                bs.clear(it.next());
728 +                it.remove();
729 +            }
730 +        }
731 +
732 +        // Add entries till we're back to original size
733 +        while (set.size() < size) {
734 +            int element = min + rnd.nextInt(rangeSize);
735 +            assertTrue(element >= min && element <= max);
736 +            put(set, element);
737 +        }
738 +    }
739 +
740 +    void mutateSubSet(NavigableSet<Integer> set, int min, int max) {
741 +        int size = set.size();
742 +        int rangeSize = max - min + 1;
743 +
744 +        // Remove a bunch of entries directly
745 +        for (int i = 0, n = rangeSize / 2; i < n; i++) {
746 +            remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
747 +        }
748 +
749 +        // Remove a bunch of entries with iterator
750 +        for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
751 +            if (rnd.nextBoolean()) {
752 +                bs.clear(it.next());
753 +                it.remove();
754 +            }
755 +        }
756 +
757 +        // Add entries till we're back to original size
758 +        while (set.size() < size) {
759 +            int element = min - 5 + rnd.nextInt(rangeSize + 10);
760 +            if (element >= min && element <= max) {
761 +                put(set, element);
762 +            } else {
763 +                try {
764 +                    set.add(element);
765 +                    shouldThrow();
766 +                } catch (IllegalArgumentException success) {}
767 +            }
768 +        }
769 +    }
770 +
771 +    void put(NavigableSet<Integer> set, int element) {
772 +        if (set.add(element))
773 +            bs.set(element);
774 +    }
775 +
776 +    void remove(NavigableSet<Integer> set, int element) {
777 +        if (set.remove(element))
778 +            bs.clear(element);
779 +    }
780 +
781 +    void bashSubSet(NavigableSet<Integer> set,
782 +                    int min, int max, boolean ascending) {
783 +        check(set, min, max, ascending);
784 +        check(set.descendingSet(), min, max, !ascending);
785 +
786 +        mutateSubSet(set, min, max);
787 +        check(set, min, max, ascending);
788 +        check(set.descendingSet(), min, max, !ascending);
789 +
790 +        // Recurse
791 +        if (max - min < 2)
792 +            return;
793 +        int midPoint = (min + max) / 2;
794 +
795 +        // headSet - pick direction and endpoint inclusion randomly
796 +        boolean incl = rnd.nextBoolean();
797 +        NavigableSet<Integer> hm = set.headSet(midPoint, incl);
798 +        if (ascending) {
799 +            if (rnd.nextBoolean())
800 +                bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true);
801 +            else
802 +                bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1),
803 +                           false);
804 +        } else {
805 +            if (rnd.nextBoolean())
806 +                bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false);
807 +            else
808 +                bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max,
809 +                           true);
810 +        }
811 +
812 +        // tailSet - pick direction and endpoint inclusion randomly
813 +        incl = rnd.nextBoolean();
814 +        NavigableSet<Integer> tm = set.tailSet(midPoint,incl);
815 +        if (ascending) {
816 +            if (rnd.nextBoolean())
817 +                bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true);
818 +            else
819 +                bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max,
820 +                           false);
821 +        } else {
822 +            if (rnd.nextBoolean()) {
823 +                bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false);
824 +            } else {
825 +                bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1),
826 +                           true);
827 +            }
828 +        }
829 +
830 +        // subSet - pick direction and endpoint inclusion randomly
831 +        int rangeSize = max - min + 1;
832 +        int[] endpoints = new int[2];
833 +        endpoints[0] = min + rnd.nextInt(rangeSize);
834 +        endpoints[1] = min + rnd.nextInt(rangeSize);
835 +        Arrays.sort(endpoints);
836 +        boolean lowIncl = rnd.nextBoolean();
837 +        boolean highIncl = rnd.nextBoolean();
838 +        if (ascending) {
839 +            NavigableSet<Integer> sm = set.subSet(
840 +                endpoints[0], lowIncl, endpoints[1], highIncl);
841 +            if (rnd.nextBoolean())
842 +                bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
843 +                           endpoints[1] - (highIncl ? 0 : 1), true);
844 +            else
845 +                bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
846 +                           endpoints[1] - (highIncl ? 0 : 1), false);
847 +        } else {
848 +            NavigableSet<Integer> sm = set.subSet(
849 +                endpoints[1], highIncl, endpoints[0], lowIncl);
850 +            if (rnd.nextBoolean())
851 +                bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
852 +                           endpoints[1] - (highIncl ? 0 : 1), false);
853 +            else
854 +                bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
855 +                           endpoints[1] - (highIncl ? 0 : 1), true);
856 +        }
857 +    }
858 +
859 +    /**
860 +     * min and max are both inclusive.  If max < min, interval is empty.
861 +     */
862 +    void check(NavigableSet<Integer> set,
863 +                      final int min, final int max, final boolean ascending) {
864 +        class ReferenceSet {
865 +            int lower(int element) {
866 +                return ascending ?
867 +                    lowerAscending(element) : higherAscending(element);
868 +            }
869 +            int floor(int element) {
870 +                return ascending ?
871 +                    floorAscending(element) : ceilingAscending(element);
872 +            }
873 +            int ceiling(int element) {
874 +                return ascending ?
875 +                    ceilingAscending(element) : floorAscending(element);
876 +            }
877 +            int higher(int element) {
878 +                return ascending ?
879 +                    higherAscending(element) : lowerAscending(element);
880 +            }
881 +            int first() {
882 +                return ascending ? firstAscending() : lastAscending();
883 +            }
884 +            int last() {
885 +                return ascending ? lastAscending() : firstAscending();
886 +            }
887 +            int lowerAscending(int element) {
888 +                return floorAscending(element - 1);
889 +            }
890 +            int floorAscending(int element) {
891 +                if (element < min)
892 +                    return -1;
893 +                else if (element > max)
894 +                    element = max;
895 +
896 +                // BitSet should support this! Test would run much faster
897 +                while (element >= min) {
898 +                    if (bs.get(element))
899 +                        return element;
900 +                    element--;
901 +                }
902 +                return -1;
903 +            }
904 +            int ceilingAscending(int element) {
905 +                if (element < min)
906 +                    element = min;
907 +                else if (element > max)
908 +                    return -1;
909 +                int result = bs.nextSetBit(element);
910 +                return (result > max) ? -1 : result;
911 +            }
912 +            int higherAscending(int element) {
913 +                return ceilingAscending(element + 1);
914 +            }
915 +            private int firstAscending() {
916 +                int result = ceilingAscending(min);
917 +                return (result > max) ? -1 : result;
918 +            }
919 +            private int lastAscending() {
920 +                int result = floorAscending(max);
921 +                return (result < min) ? -1 : result;
922 +            }
923 +        }
924 +        ReferenceSet rs = new ReferenceSet();
925 +
926 +        // Test contents using containsElement
927 +        int size = 0;
928 +        for (int i = min; i <= max; i++) {
929 +            boolean bsContainsI = bs.get(i);
930 +            assertEquals(bsContainsI, set.contains(i));
931 +            if (bsContainsI)
932 +                size++;
933 +        }
934 +        assertEquals(size, set.size());
935 +
936 +        // Test contents using contains elementSet iterator
937 +        int size2 = 0;
938 +        int previousElement = -1;
939 +        for (int element : set) {
940 +            assertTrue(bs.get(element));
941 +            size2++;
942 +            assertTrue(previousElement < 0 || (ascending ?
943 +                element - previousElement > 0 : element - previousElement < 0));
944 +            previousElement = element;
945 +        }
946 +        assertEquals(size2, size);
947 +
948 +        // Test navigation ops
949 +        for (int element = min - 1; element <= max + 1; element++) {
950 +            assertEq(set.lower(element), rs.lower(element));
951 +            assertEq(set.floor(element), rs.floor(element));
952 +            assertEq(set.higher(element), rs.higher(element));
953 +            assertEq(set.ceiling(element), rs.ceiling(element));
954 +        }
955 +
956 +        // Test extrema
957 +        if (set.size() != 0) {
958 +            assertEq(set.first(), rs.first());
959 +            assertEq(set.last(), rs.last());
960 +        } else {
961 +            assertEq(rs.first(), -1);
962 +            assertEq(rs.last(),  -1);
963 +            try {
964 +                set.first();
965 +                shouldThrow();
966 +            } catch (NoSuchElementException success) {}
967 +            try {
968 +                set.last();
969 +                shouldThrow();
970 +            } catch (NoSuchElementException success) {}
971 +        }
972 +    }
973 +
974 +    static void assertEq(Integer i, int j) {
975 +        if (i == null)
976 +            assertEquals(j, -1);
977 +        else
978 +            assertEquals((int) i, j);
979 +    }
980 +
981 +    static boolean eq(Integer i, int j) {
982 +        return (i == null) ? j == -1 : i == j;
983 +    }
984 +
985   }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines