18f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle/*
28f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * Written by Doug Lea with assistance from members of JCP JSR-166
38f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * Expert Group and released to the public domain, as explained at
48f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * http://creativecommons.org/publicdomain/zero/1.0/
58f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */
68f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
78f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravlepackage jsr166;
88f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
98f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.Arrays;
108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.BitSet;
118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.Collection;
128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.Comparator;
138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.Iterator;
148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.NavigableSet;
158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.NoSuchElementException;
168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.Random;
178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.Set;
188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.SortedSet;
198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.TreeSet;
208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
218e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamathimport junit.framework.Test;
228e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamathimport junit.framework.TestSuite;
238e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath
248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravlepublic class TreeSetTest extends JSR166TestCase {
258e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath    // android-note: Removed because the CTS runner does a bad job of
268e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath    // retrying tests that have suite() declarations.
278e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath    //
288e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath    // public static void main(String[] args) {
298e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath    //     main(suite(), args);
308e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath    // }
318e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath    // public static Test suite() {
32e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak    //     return new TestSuite(TreeSetTest.class);
338e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath    // }
348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    static class MyReverseComparator implements Comparator {
368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        public int compare(Object x, Object y) {
378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            return ((Comparable)y).compareTo(x);
388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * The number of elements to place in collections, arrays, etc.
438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    static final int SIZE = 20;
458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Returns a new set of given size containing consecutive
488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Integers 0 ... n.
498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    private TreeSet<Integer> populatedSet(int n) {
518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet<Integer> q = new TreeSet<Integer>();
528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.isEmpty());
53e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak        for (int i = n - 1; i >= 0; i -= 2)
548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.add(new Integer(i)));
558e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        for (int i = (n & 1); i < n; i += 2)
568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.add(new Integer(i)));
578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(q.isEmpty());
588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(n, q.size());
598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        return q;
608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Returns a new set of first 5 ints.
648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    private TreeSet set5() {
668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = new TreeSet();
678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.isEmpty());
688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(one);
698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(two);
708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(three);
718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(four);
728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(five);
738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(5, q.size());
748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        return q;
758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * A new set has unbounded capacity
798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testConstructor1() {
818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(0, new TreeSet().size());
828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Initializing from null Collection throws NPE
868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testConstructor3() {
888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        try {
898e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath            new TreeSet((Collection)null);
908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            shouldThrow();
918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } catch (NullPointerException success) {}
928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Initializing from Collection of null elements throws NPE
968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testConstructor4() {
988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        try {
99e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak            new TreeSet(Arrays.asList(new Integer[SIZE]));
1008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            shouldThrow();
1018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } catch (NullPointerException success) {}
1028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
1038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
1048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
1058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Initializing from Collection with some null elements throws NPE
1068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
1078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testConstructor5() {
108e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak        Integer[] ints = new Integer[SIZE];
109e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak        for (int i = 0; i < SIZE - 1; ++i)
110e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak            ints[i] = new Integer(i);
1118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        try {
1128e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath            new TreeSet(Arrays.asList(ints));
1138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            shouldThrow();
1148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } catch (NullPointerException success) {}
1158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
1168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
1178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
1188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Set contains all elements of collection used to initialize
1198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
1208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testConstructor6() {
1218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Integer[] ints = new Integer[SIZE];
1228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i)
1238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            ints[i] = new Integer(i);
1248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = new TreeSet(Arrays.asList(ints));
1258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i)
1268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals(ints[i], q.pollFirst());
1278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
1288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
1298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
1308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * The comparator used in constructor is used
1318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
1328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testConstructor7() {
1338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        MyReverseComparator cmp = new MyReverseComparator();
1348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = new TreeSet(cmp);
1358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(cmp, q.comparator());
1368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Integer[] ints = new Integer[SIZE];
1378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i)
1388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            ints[i] = new Integer(i);
1398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.addAll(Arrays.asList(ints));
140e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak        for (int i = SIZE - 1; i >= 0; --i)
1418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals(ints[i], q.pollFirst());
1428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
1438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
1448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
1458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * isEmpty is true before add, false after
1468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
1478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testEmpty() {
1488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = new TreeSet();
1498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.isEmpty());
1508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(new Integer(1));
1518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(q.isEmpty());
1528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(new Integer(2));
1538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.pollFirst();
1548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.pollFirst();
1558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.isEmpty());
1568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
1578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
1588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
1598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * size changes when elements added and removed
1608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
1618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testSize() {
1628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
1638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i) {
164e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak            assertEquals(SIZE - i, q.size());
1658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            q.pollFirst();
1668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
1678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i) {
1688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals(i, q.size());
1698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            q.add(new Integer(i));
1708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
1718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
1728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
1738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
1748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * add(null) throws NPE if nonempty
1758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
1768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testAddNull() {
1778e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        TreeSet q = populatedSet(SIZE);
1788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        try {
1798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            q.add(null);
1808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            shouldThrow();
1818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } catch (NullPointerException success) {}
1828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
1838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
1848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
1858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Add of comparable element succeeds
1868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
1878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testAdd() {
1888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = new TreeSet();
1898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.add(zero));
1908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.add(one));
1918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
1928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
1938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
1948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Add of duplicate element fails
1958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
1968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testAddDup() {
1978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = new TreeSet();
1988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.add(zero));
1998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(q.add(zero));
2008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
2018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
2028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
2038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Add of non-Comparable throws CCE
2048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
2058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testAddNonComparable() {
2068e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        TreeSet q = new TreeSet();
2078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        try {
2088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            q.add(new Object());
2098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            q.add(new Object());
2108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            shouldThrow();
2118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } catch (ClassCastException success) {}
2128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
2138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
2148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
2158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * addAll(null) throws NPE
2168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
2178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testAddAll1() {
2188e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        TreeSet q = new TreeSet();
2198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        try {
2208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            q.addAll(null);
2218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            shouldThrow();
2228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } catch (NullPointerException success) {}
2238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
2248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
2258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
2268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * addAll of a collection with null elements throws NPE
2278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
2288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testAddAll2() {
2298e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        TreeSet q = new TreeSet();
2308e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        Integer[] ints = new Integer[SIZE];
2318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        try {
2328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            q.addAll(Arrays.asList(ints));
2338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            shouldThrow();
2348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } catch (NullPointerException success) {}
2358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
2368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
2378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
2388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * addAll of a collection with any null elements throws NPE after
2398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * possibly adding some elements
2408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
2418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testAddAll3() {
2428e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        TreeSet q = new TreeSet();
2438e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        Integer[] ints = new Integer[SIZE];
244e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak        for (int i = 0; i < SIZE - 1; ++i)
2458e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath            ints[i] = new Integer(i);
2468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        try {
2478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            q.addAll(Arrays.asList(ints));
2488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            shouldThrow();
2498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } catch (NullPointerException success) {}
2508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
2518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
2528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
2538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Set contains all elements of successful addAll
2548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
2558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testAddAll5() {
2568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Integer[] empty = new Integer[0];
2578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Integer[] ints = new Integer[SIZE];
2588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i)
259e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak            ints[i] = new Integer(SIZE - 1 - i);
2608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = new TreeSet();
2618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(q.addAll(Arrays.asList(empty)));
2628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.addAll(Arrays.asList(ints)));
2638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i)
2648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals(new Integer(i), q.pollFirst());
2658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
2668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
2678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
2688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * pollFirst succeeds unless empty
2698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
2708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testPollFirst() {
2718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
2728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i) {
2738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals(i, q.pollFirst());
2748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
2758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertNull(q.pollFirst());
2768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
2778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
2788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
2798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * pollLast succeeds unless empty
2808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
2818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testPollLast() {
2828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
283e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak        for (int i = SIZE - 1; i >= 0; --i) {
2848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals(i, q.pollLast());
2858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
2868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertNull(q.pollFirst());
2878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
2888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
2898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
2908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * remove(x) removes x and returns true if present
2918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
2928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testRemoveElement() {
2938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
2948e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        for (int i = 1; i < SIZE; i += 2) {
2958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.contains(i));
2968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.remove(i));
2978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertFalse(q.contains(i));
298e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak            assertTrue(q.contains(i - 1));
2998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
3008e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        for (int i = 0; i < SIZE; i += 2) {
3018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.contains(i));
3028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.remove(i));
3038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertFalse(q.contains(i));
304e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak            assertFalse(q.remove(i + 1));
305e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak            assertFalse(q.contains(i + 1));
3068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
3078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.isEmpty());
3088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
3098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
3118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * contains(x) reports true when elements added but not yet removed
3128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
3138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testContains() {
3148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
3158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i) {
3168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.contains(new Integer(i)));
3178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            q.pollFirst();
3188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertFalse(q.contains(new Integer(i)));
3198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
3208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
3218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
3238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * clear removes all elements
3248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
3258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testClear() {
3268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
3278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.clear();
3288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.isEmpty());
3298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(0, q.size());
3308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(new Integer(1));
3318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(q.isEmpty());
3328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.clear();
3338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(q.isEmpty());
3348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
3358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
3378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * containsAll(c) is true when c contains a subset of elements
3388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
3398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testContainsAll() {
3408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
3418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet p = new TreeSet();
3428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i) {
3438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.containsAll(p));
3448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertFalse(p.containsAll(q));
3458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            p.add(new Integer(i));
3468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
3478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(p.containsAll(q));
3488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
3498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
3518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * retainAll(c) retains only those elements of c and reports true if changed
3528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
3538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testRetainAll() {
3548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
3558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet p = populatedSet(SIZE);
3568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i) {
3578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            boolean changed = q.retainAll(p);
3588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (i == 0)
3598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                assertFalse(changed);
3608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            else
3618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                assertTrue(changed);
3628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.containsAll(p));
364e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak            assertEquals(SIZE - i, q.size());
3658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            p.pollFirst();
3668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
3678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
3688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
3708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * removeAll(c) removes only those elements of c and reports true if changed
3718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
3728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testRemoveAll() {
3738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 1; i < SIZE; ++i) {
3748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            TreeSet q = populatedSet(SIZE);
3758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            TreeSet p = populatedSet(i);
3768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.removeAll(p));
377e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak            assertEquals(SIZE - i, q.size());
3788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            for (int j = 0; j < i; ++j) {
3798e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath                Integer x = (Integer)(p.pollFirst());
3808e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath                assertFalse(q.contains(x));
3818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
3828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
3838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
3848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
3868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * lower returns preceding element
3878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
3888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testLower() {
3898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = set5();
3908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e1 = q.lower(three);
3918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(two, e1);
3928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e2 = q.lower(six);
3948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(five, e2);
3958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e3 = q.lower(one);
3978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertNull(e3);
3988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
3998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e4 = q.lower(zero);
4008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertNull(e4);
4018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
4028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
4048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * higher returns next element
4058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
4068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testHigher() {
4078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = set5();
4088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e1 = q.higher(three);
4098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(four, e1);
4108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e2 = q.higher(zero);
4128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(one, e2);
4138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e3 = q.higher(five);
4158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertNull(e3);
4168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e4 = q.higher(six);
4188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertNull(e4);
4198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
4208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
4228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * floor returns preceding element
4238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
4248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testFloor() {
4258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = set5();
4268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e1 = q.floor(three);
4278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(three, e1);
4288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e2 = q.floor(six);
4308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(five, e2);
4318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e3 = q.floor(one);
4338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(one, e3);
4348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e4 = q.floor(zero);
4368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertNull(e4);
4378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
4388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
4408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * ceiling returns next element
4418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
4428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testCeiling() {
4438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = set5();
4448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e1 = q.ceiling(three);
4458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(three, e1);
4468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e2 = q.ceiling(zero);
4488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(one, e2);
4498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e3 = q.ceiling(five);
4518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(five, e3);
4528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object e4 = q.ceiling(six);
4548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertNull(e4);
4558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
4568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
4588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * toArray contains all elements in sorted order
4598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
4608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testToArray() {
4618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
4628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object[] o = q.toArray();
4638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < o.length; i++)
4648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertSame(o[i], q.pollFirst());
4658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
4668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
4688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * toArray(a) contains all elements in sorted order
4698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
4708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testToArray2() {
4718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet<Integer> q = populatedSet(SIZE);
4728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Integer[] ints = new Integer[SIZE];
4738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Integer[] array = q.toArray(ints);
4748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertSame(ints, array);
4758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < ints.length; i++)
4768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertSame(ints[i], q.pollFirst());
4778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
4788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
4808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * iterator iterates through all elements
4818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
4828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testIterator() {
4838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
4848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Iterator it = q.iterator();
4858e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        int i;
4868e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        for (i = 0; it.hasNext(); i++)
4878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(q.contains(it.next()));
4888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(i, SIZE);
4898e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        assertIteratorExhausted(it);
4908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
4918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
4938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * iterator of empty set has no elements
4948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
4958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testEmptyIterator() {
4968e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath        assertIteratorExhausted(new TreeSet().iterator());
4978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
4988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
4998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
5008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * iterator.remove removes current element
5018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
5028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testIteratorRemove() {
5038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        final TreeSet q = new TreeSet();
5048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(new Integer(2));
5058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(new Integer(1));
5068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        q.add(new Integer(3));
5078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
5088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Iterator it = q.iterator();
5098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        it.next();
5108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        it.remove();
5118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
5128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        it = q.iterator();
5138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(it.next(), new Integer(2));
5148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(it.next(), new Integer(3));
5158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(it.hasNext());
5168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
5178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
5188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
5198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * toString contains toStrings of elements
5208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
5218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testToString() {
5228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet q = populatedSet(SIZE);
5238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        String s = q.toString();
5248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0; i < SIZE; ++i) {
5258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(s.contains(String.valueOf(i)));
5268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
5278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
5288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
5298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
5308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * A deserialized serialized set has same elements
5318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
5328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testSerialization() throws Exception {
5338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        NavigableSet x = populatedSet(SIZE);
5348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        NavigableSet y = serialClone(x);
5358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
5368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertNotSame(x, y);
5378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(x.size(), y.size());
5388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(x, y);
5398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(y, x);
5408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        while (!x.isEmpty()) {
5418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertFalse(y.isEmpty());
5428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals(x.pollFirst(), y.pollFirst());
5438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
5448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(y.isEmpty());
5458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
5468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
5478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
5488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * subSet returns set with keys in requested range
5498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
5508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testSubSetContents() {
5518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet set = set5();
5528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        SortedSet sm = set.subSet(two, four);
5538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(two, sm.first());
5548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(three, sm.last());
5558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(2, sm.size());
5568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(one));
5578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(two));
5588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(three));
5598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(four));
5608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(five));
5618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Iterator i = sm.iterator();
5628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object k;
5638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
5648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(two, k);
5658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
5668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(three, k);
5678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(i.hasNext());
5688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Iterator j = sm.iterator();
5698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        j.next();
5708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        j.remove();
5718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(set.contains(two));
5728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(4, set.size());
5738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(1, sm.size());
5748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(three, sm.first());
5758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(three, sm.last());
5768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.remove(three));
5778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.isEmpty());
5788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(3, set.size());
5798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
5808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
5818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testSubSetContents2() {
5828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet set = set5();
5838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        SortedSet sm = set.subSet(two, three);
5848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(1, sm.size());
5858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(two, sm.first());
5868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(two, sm.last());
5878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(one));
5888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(two));
5898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(three));
5908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(four));
5918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(five));
5928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Iterator i = sm.iterator();
5938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object k;
5948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
5958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(two, k);
5968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(i.hasNext());
5978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Iterator j = sm.iterator();
5988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        j.next();
5998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        j.remove();
6008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(set.contains(two));
6018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(4, set.size());
6028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(0, sm.size());
6038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.isEmpty());
6048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.remove(three));
6058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(4, set.size());
6068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
6078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
6098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * headSet returns set with keys in requested range
6108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
6118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testHeadSetContents() {
6128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet set = set5();
6138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        SortedSet sm = set.headSet(four);
6148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(one));
6158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(two));
6168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(three));
6178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(four));
6188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(five));
6198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Iterator i = sm.iterator();
6208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object k;
6218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
6228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(one, k);
6238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
6248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(two, k);
6258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
6268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(three, k);
6278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(i.hasNext());
6288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        sm.clear();
6298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.isEmpty());
6308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(2, set.size());
6318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(four, set.first());
6328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
6338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
6358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * tailSet returns set with keys in requested range
6368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
6378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testTailSetContents() {
6388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        TreeSet set = set5();
6398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        SortedSet sm = set.tailSet(two);
6408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(sm.contains(one));
6418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(two));
6428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(three));
6438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(four));
6448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(sm.contains(five));
6458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Iterator i = sm.iterator();
6468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Object k;
6478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
6488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(two, k);
6498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
6508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(three, k);
6518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
6528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(four, k);
6538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        k = (Integer)(i.next());
6548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(five, k);
6558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(i.hasNext());
6568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        SortedSet ssm = sm.tailSet(four);
6588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(four, ssm.first());
6598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(five, ssm.last());
6608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertTrue(ssm.remove(four));
6618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(1, ssm.size());
6628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(3, sm.size());
6638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(4, set.size());
6648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
6658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    Random rnd = new Random(666);
6678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    BitSet bs;
6688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
6708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * Subsets of subsets subdivide correctly
6718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
6728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testRecursiveSubSets() throws Exception {
6738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int setSize = expensiveTests ? 1000 : 100;
6748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Class cl = TreeSet.class;
6758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        NavigableSet<Integer> set = newSet(cl);
6778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        bs = new BitSet(setSize);
6788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        populate(set, setSize);
6808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        check(set,                 0, setSize - 1, true);
6818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        check(set.descendingSet(), 0, setSize - 1, false);
6828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        mutateSet(set, 0, setSize - 1);
6848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        check(set,                 0, setSize - 1, true);
6858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        check(set.descendingSet(), 0, setSize - 1, false);
6868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        bashSubSet(set.subSet(0, true, setSize, false),
6888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                   0, setSize - 1, true);
6898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
6908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
6918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
6928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * addAll is idempotent
6938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
6948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    public void testAddAll_idempotent() throws Exception {
6958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Set x = populatedSet(SIZE);
6968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Set y = new TreeSet(x);
6978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        y.addAll(x);
6988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(x, y);
6998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(y, x);
7008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
7018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    static NavigableSet<Integer> newSet(Class cl) throws Exception {
7038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        NavigableSet<Integer> result = (NavigableSet<Integer>) cl.newInstance();
7048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(0, result.size());
7058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertFalse(result.iterator().hasNext());
7068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        return result;
7078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
7088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    void populate(NavigableSet<Integer> set, int limit) {
7108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0, n = 2 * limit / 3; i < n; i++) {
7118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int element = rnd.nextInt(limit);
7128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            put(set, element);
7138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
7148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
7158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    void mutateSet(NavigableSet<Integer> set, int min, int max) {
7178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int size = set.size();
7188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int rangeSize = max - min + 1;
7198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Remove a bunch of entries directly
7218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0, n = rangeSize / 2; i < n; i++) {
7228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
7238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
7248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Remove a bunch of entries with iterator
7268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
7278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (rnd.nextBoolean()) {
7288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bs.clear(it.next());
7298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                it.remove();
7308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
7318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
7328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Add entries till we're back to original size
7348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        while (set.size() < size) {
7358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int element = min + rnd.nextInt(rangeSize);
7368e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath            assertTrue(element >= min && element <= max);
7378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            put(set, element);
7388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
7398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
7408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    void mutateSubSet(NavigableSet<Integer> set, int min, int max) {
7428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int size = set.size();
7438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int rangeSize = max - min + 1;
7448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Remove a bunch of entries directly
7468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = 0, n = rangeSize / 2; i < n; i++) {
7478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            remove(set, min - 5 + rnd.nextInt(rangeSize + 10));
7488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
7498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Remove a bunch of entries with iterator
7518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) {
7528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (rnd.nextBoolean()) {
7538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bs.clear(it.next());
7548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                it.remove();
7558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
7568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
7578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Add entries till we're back to original size
7598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        while (set.size() < size) {
7608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int element = min - 5 + rnd.nextInt(rangeSize + 10);
7618e9a0e92906742b17eb08d7fb83cca91965f9b8eNarayan Kamath            if (element >= min && element <= max) {
7628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                put(set, element);
7638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            } else {
7648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                try {
7658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    set.add(element);
7668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    shouldThrow();
7678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                } catch (IllegalArgumentException success) {}
7688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
7698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
7708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
7718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    void put(NavigableSet<Integer> set, int element) {
7738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        if (set.add(element))
7748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            bs.set(element);
7758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
7768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    void remove(NavigableSet<Integer> set, int element) {
7788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        if (set.remove(element))
7798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            bs.clear(element);
7808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
7818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    void bashSubSet(NavigableSet<Integer> set,
7838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    int min, int max, boolean ascending) {
7848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        check(set, min, max, ascending);
7858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        check(set.descendingSet(), min, max, !ascending);
7868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        mutateSubSet(set, min, max);
7888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        check(set, min, max, ascending);
7898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        check(set.descendingSet(), min, max, !ascending);
7908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Recurse
7928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        if (max - min < 2)
7938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            return;
7948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int midPoint = (min + max) / 2;
7958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
7968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // headSet - pick direction and endpoint inclusion randomly
7978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        boolean incl = rnd.nextBoolean();
7988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        NavigableSet<Integer> hm = set.headSet(midPoint, incl);
7998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        if (ascending) {
8008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (rnd.nextBoolean())
8018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true);
8028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            else
8038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1),
8048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                           false);
8058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } else {
8068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (rnd.nextBoolean())
8078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false);
8088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            else
8098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max,
8108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                           true);
8118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
8128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
8138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // tailSet - pick direction and endpoint inclusion randomly
8148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        incl = rnd.nextBoolean();
8158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        NavigableSet<Integer> tm = set.tailSet(midPoint,incl);
8168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        if (ascending) {
8178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (rnd.nextBoolean())
8188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true);
8198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            else
8208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max,
8218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                           false);
8228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } else {
8238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (rnd.nextBoolean()) {
8248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false);
8258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            } else {
8268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1),
8278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                           true);
8288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
8298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
8308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
8318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // subSet - pick direction and endpoint inclusion randomly
8328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int rangeSize = max - min + 1;
8338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int[] endpoints = new int[2];
8348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        endpoints[0] = min + rnd.nextInt(rangeSize);
8358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        endpoints[1] = min + rnd.nextInt(rangeSize);
8368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        Arrays.sort(endpoints);
8378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        boolean lowIncl = rnd.nextBoolean();
8388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        boolean highIncl = rnd.nextBoolean();
8398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        if (ascending) {
8408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            NavigableSet<Integer> sm = set.subSet(
8418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                endpoints[0], lowIncl, endpoints[1], highIncl);
8428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (rnd.nextBoolean())
8438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
8448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                           endpoints[1] - (highIncl ? 0 : 1), true);
8458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            else
8468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
8478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                           endpoints[1] - (highIncl ? 0 : 1), false);
8488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } else {
8498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            NavigableSet<Integer> sm = set.subSet(
8508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                endpoints[1], highIncl, endpoints[0], lowIncl);
8518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (rnd.nextBoolean())
8528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
8538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                           endpoints[1] - (highIncl ? 0 : 1), false);
8548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            else
8558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
8568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                           endpoints[1] - (highIncl ? 0 : 1), true);
8578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
8588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
8598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
8608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    /**
8618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     * min and max are both inclusive.  If max < min, interval is empty.
8628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle     */
8638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    void check(NavigableSet<Integer> set,
8648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                      final int min, final int max, final boolean ascending) {
8658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        class ReferenceSet {
8668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int lower(int element) {
8678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                return ascending ?
8688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    lowerAscending(element) : higherAscending(element);
8698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
8708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int floor(int element) {
8718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                return ascending ?
8728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    floorAscending(element) : ceilingAscending(element);
8738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
8748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int ceiling(int element) {
8758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                return ascending ?
8768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    ceilingAscending(element) : floorAscending(element);
8778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
8788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int higher(int element) {
8798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                return ascending ?
8808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    higherAscending(element) : lowerAscending(element);
8818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
8828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int first() {
8838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                return ascending ? firstAscending() : lastAscending();
8848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
8858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int last() {
8868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                return ascending ? lastAscending() : firstAscending();
8878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
8888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int lowerAscending(int element) {
8898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                return floorAscending(element - 1);
8908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
8918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int floorAscending(int element) {
8928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                if (element < min)
8938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    return -1;
8948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                else if (element > max)
8958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    element = max;
8968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
8978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                // BitSet should support this! Test would run much faster
8988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                while (element >= min) {
8998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    if (bs.get(element))
9008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                        return element;
9018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    element--;
9028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                }
9038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                return -1;
9048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
9058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int ceilingAscending(int element) {
9068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                if (element < min)
9078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    element = min;
9088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                else if (element > max)
9098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                    return -1;
9108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                int result = bs.nextSetBit(element);
911e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak                return (result > max) ? -1 : result;
9128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
9138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            int higherAscending(int element) {
9148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                return ceilingAscending(element + 1);
9158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
9168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            private int firstAscending() {
9178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                int result = ceilingAscending(min);
918e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak                return (result > max) ? -1 : result;
9198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
9208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            private int lastAscending() {
9218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                int result = floorAscending(max);
922e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak                return (result < min) ? -1 : result;
9238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            }
9248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
9258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        ReferenceSet rs = new ReferenceSet();
9268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
9278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Test contents using containsElement
9288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int size = 0;
9298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int i = min; i <= max; i++) {
9308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            boolean bsContainsI = bs.get(i);
9318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals(bsContainsI, set.contains(i));
9328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            if (bsContainsI)
9338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                size++;
9348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
9358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(size, set.size());
9368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
9378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Test contents using contains elementSet iterator
9388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int size2 = 0;
9398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        int previousElement = -1;
9408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int element : set) {
9418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(bs.get(element));
9428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            size2++;
9438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertTrue(previousElement < 0 || (ascending ?
9448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                element - previousElement > 0 : element - previousElement < 0));
9458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            previousElement = element;
9468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
9478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        assertEquals(size2, size);
9488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
9498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Test navigation ops
9508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        for (int element = min - 1; element <= max + 1; element++) {
9518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEq(set.lower(element), rs.lower(element));
9528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEq(set.floor(element), rs.floor(element));
9538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEq(set.higher(element), rs.higher(element));
9548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEq(set.ceiling(element), rs.ceiling(element));
9558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
9568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
9578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        // Test extrema
9588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        if (set.size() != 0) {
9598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEq(set.first(), rs.first());
9608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEq(set.last(), rs.last());
9618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        } else {
9628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEq(rs.first(), -1);
9638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEq(rs.last(),  -1);
9648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            try {
9658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                set.first();
9668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                shouldThrow();
9678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            } catch (NoSuchElementException success) {}
9688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            try {
9698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                set.last();
9708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle                shouldThrow();
9718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            } catch (NoSuchElementException success) {}
9728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        }
9738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
9748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
9758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    static void assertEq(Integer i, int j) {
9768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        if (i == null)
9778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals(j, -1);
9788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle        else
9798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle            assertEquals((int) i, j);
9808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
9818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
9828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    static boolean eq(Integer i, int j) {
983e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak        return (i == null) ? j == -1 : i == j;
9848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle    }
9858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle
9868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle}
987