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