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