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