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.*; 118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravleimport java.util.concurrent.ConcurrentSkipListMap; 128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravlepublic class ConcurrentSkipListMapTest extends JSR166TestCase { 148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * Returns a new map from Integers 1-5 to Strings "A"-"E". 178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle private static ConcurrentSkipListMap map5() { 198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = new ConcurrentSkipListMap(); 208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.isEmpty()); 218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.put(one, "A"); 228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.put(five, "E"); 238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.put(three, "C"); 248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.put(two, "B"); 258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.put(four, "D"); 268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.isEmpty()); 278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, map.size()); 288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return map; 298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * clear removes all pairs 338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testClear() { 358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.clear(); 378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(0, map.size()); 388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * copy constructor creates map equal to source map 428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testConstructFromSorted() { 448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map2 = new ConcurrentSkipListMap(map); 468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(map, map2); 478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * Maps with same contents are equal 518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testEquals() { 538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map1 = map5(); 548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map2 = map5(); 558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(map1, map2); 568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(map2, map1); 578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map1.clear(); 588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map1.equals(map2)); 598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map2.equals(map1)); 608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * containsKey returns true for contained key 648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testContainsKey() { 668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.containsKey(one)); 688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.containsKey(zero)); 698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * containsValue returns true for held values 738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testContainsValue() { 758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.containsValue("A")); 778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.containsValue("Z")); 788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * get returns the correct element at the given key, 828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * or null if not present 838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testGet() { 858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("A", (String)map.get(one)); 878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap empty = new ConcurrentSkipListMap(); 888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(empty.get(one)); 898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * isEmpty is true of empty map and false for non-empty 938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testIsEmpty() { 958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap empty = new ConcurrentSkipListMap(); 968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(empty.isEmpty()); 988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.isEmpty()); 998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 1018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 1028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * firstKey returns first key 1038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 1048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testFirstKey() { 1058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 1068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, map.firstKey()); 1078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 1098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 1108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * lastKey returns last key 1118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 1128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testLastKey() { 1138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 1148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, map.lastKey()); 1158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 1178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 1188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * keySet.toArray returns contains all keys 1198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 1208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testKeySetToArray() { 1218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 1228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Set s = map.keySet(); 1238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object[] ar = s.toArray(); 1248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.containsAll(Arrays.asList(ar))); 1258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, ar.length); 1268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ar[0] = m10; 1278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(s.containsAll(Arrays.asList(ar))); 1288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 1308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 1318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * descendingkeySet.toArray returns contains all keys 1328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 1338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testDescendingKeySetToArray() { 1348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 1358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Set s = map.descendingKeySet(); 1368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object[] ar = s.toArray(); 1378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, ar.length); 1388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.containsAll(Arrays.asList(ar))); 1398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ar[0] = m10; 1408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(s.containsAll(Arrays.asList(ar))); 1418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 1438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 1448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * keySet returns a Set containing all the keys 1458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 1468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testKeySet() { 1478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 1488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Set s = map.keySet(); 1498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, s.size()); 1508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains(one)); 1518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains(two)); 1528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains(three)); 1538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains(four)); 1548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains(five)); 1558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 1578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 1588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * keySet is ordered 1598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 1608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testKeySetOrder() { 1618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 1628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Set s = map.keySet(); 1638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator i = s.iterator(); 1648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Integer last = (Integer)i.next(); 1658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(last, one); 1668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int count = 1; 1678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle while (i.hasNext()) { 1688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Integer k = (Integer)i.next(); 1698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(last.compareTo(k) < 0); 1708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle last = k; 1718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ++count; 1728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, count); 1748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 1768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 1778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * descending iterator of key set is inverse ordered 1788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 1798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testKeySetDescendingIteratorOrder() { 1808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 1818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableSet s = map.navigableKeySet(); 1828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator i = s.descendingIterator(); 1838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Integer last = (Integer)i.next(); 1848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(last, five); 1858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int count = 1; 1868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle while (i.hasNext()) { 1878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Integer k = (Integer)i.next(); 1888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(last.compareTo(k) > 0); 1898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle last = k; 1908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ++count; 1918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, count); 1938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 1948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 1958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 1968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * descendingKeySet is ordered 1978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 1988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testDescendingKeySetOrder() { 1998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 2008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Set s = map.descendingKeySet(); 2018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator i = s.iterator(); 2028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Integer last = (Integer)i.next(); 2038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(last, five); 2048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int count = 1; 2058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle while (i.hasNext()) { 2068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Integer k = (Integer)i.next(); 2078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(last.compareTo(k) > 0); 2088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle last = k; 2098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ++count; 2108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 2118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, count); 2128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 2138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 2148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 2158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * descending iterator of descendingKeySet is ordered 2168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 2178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testDescendingKeySetDescendingIteratorOrder() { 2188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 2198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableSet s = map.descendingKeySet(); 2208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator i = s.descendingIterator(); 2218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Integer last = (Integer)i.next(); 2228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(last, one); 2238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int count = 1; 2248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle while (i.hasNext()) { 2258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Integer k = (Integer)i.next(); 2268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(last.compareTo(k) < 0); 2278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle last = k; 2288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ++count; 2298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 2308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, count); 2318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 2328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 2338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 2348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * Values.toArray contains all values 2358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 2368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testValuesToArray() { 2378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 2388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Collection v = map.values(); 2398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object[] ar = v.toArray(); 2408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ArrayList s = new ArrayList(Arrays.asList(ar)); 2418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, ar.length); 2428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("A")); 2438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("B")); 2448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("C")); 2458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("D")); 2468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("E")); 2478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 2488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 2498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 2508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * values collection contains all values 2518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 2528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testValues() { 2538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 2548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Collection s = map.values(); 2558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, s.size()); 2568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("A")); 2578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("B")); 2588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("C")); 2598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("D")); 2608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains("E")); 2618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 2628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 2638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 2648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * entrySet contains all pairs 2658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 2668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testEntrySet() { 2678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 2688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Set s = map.entrySet(); 2698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, s.size()); 2708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator it = s.iterator(); 2718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle while (it.hasNext()) { 2728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e = (Map.Entry) it.next(); 2738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue( 2748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(one) && e.getValue().equals("A")) || 2758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(two) && e.getValue().equals("B")) || 2768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(three) && e.getValue().equals("C")) || 2778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(four) && e.getValue().equals("D")) || 2788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(five) && e.getValue().equals("E"))); 2798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 2808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 2818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 2828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 2838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * descendingEntrySet contains all pairs 2848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 2858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testDescendingEntrySet() { 2868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 2878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Set s = map.descendingMap().entrySet(); 2888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, s.size()); 2898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator it = s.iterator(); 2908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle while (it.hasNext()) { 2918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e = (Map.Entry) it.next(); 2928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue( 2938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(one) && e.getValue().equals("A")) || 2948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(two) && e.getValue().equals("B")) || 2958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(three) && e.getValue().equals("C")) || 2968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(four) && e.getValue().equals("D")) || 2978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (e.getKey().equals(five) && e.getValue().equals("E"))); 2988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 2998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 3028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * entrySet.toArray contains all entries 3038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 3048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testEntrySetToArray() { 3058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 3068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Set s = map.entrySet(); 3078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object[] ar = s.toArray(); 3088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, ar.length); 3098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (int i = 0; i < 5; ++i) { 3108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey())); 3118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue())); 3128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 3168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * descendingEntrySet.toArray contains all entries 3178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 3188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testDescendingEntrySetToArray() { 3198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 3208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Set s = map.descendingMap().entrySet(); 3218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object[] ar = s.toArray(); 3228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, ar.length); 3238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (int i = 0; i < 5; ++i) { 3248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.containsKey(((Map.Entry)(ar[i])).getKey())); 3258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.containsValue(((Map.Entry)(ar[i])).getValue())); 3268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 3308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * putAll adds all key-value pairs from the given map 3318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 3328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testPutAll() { 3338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap empty = new ConcurrentSkipListMap(); 3348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 3358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle empty.putAll(map); 3368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, empty.size()); 3378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(empty.containsKey(one)); 3388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(empty.containsKey(two)); 3398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(empty.containsKey(three)); 3408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(empty.containsKey(four)); 3418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(empty.containsKey(five)); 3428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 3458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * putIfAbsent works when the given key is not present 3468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 3478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testPutIfAbsent() { 3488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 3498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.putIfAbsent(six, "Z"); 3508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.containsKey(six)); 3518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 3548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * putIfAbsent does not add the pair if the key is already present 3558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 3568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testPutIfAbsent2() { 3578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 3588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("A", map.putIfAbsent(one, "Z")); 3598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 3628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * replace fails when the given key is not present 3638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 3648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testReplace() { 3658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 3668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(map.replace(six, "Z")); 3678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.containsKey(six)); 3688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 3718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * replace succeeds if the key is already present 3728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 3738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testReplace2() { 3748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 3758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNotNull(map.replace(one, "Z")); 3768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("Z", map.get(one)); 3778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 3808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * replace value fails when the given key not mapped to expected value 3818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 3828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testReplaceValue() { 3838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 3848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("A", map.get(one)); 3858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.replace(one, "Z", "Z")); 3868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("A", map.get(one)); 3878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 3908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * replace value succeeds when the given key mapped to expected value 3918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 3928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testReplaceValue2() { 3938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 3948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("A", map.get(one)); 3958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.replace(one, "A", "Z")); 3968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("Z", map.get(one)); 3978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 3988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 3998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 4008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * remove removes the correct key-value pair from the map 4018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 4028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testRemove() { 4038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 4048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.remove(five); 4058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(4, map.size()); 4068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.containsKey(five)); 4078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 4088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 4108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * remove(key,value) removes only if pair present 4118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 4128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testRemove2() { 4138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 4148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.containsKey(five)); 4158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("E", map.get(five)); 4168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.remove(five, "E"); 4178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(4, map.size()); 4188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.containsKey(five)); 4198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.remove(four, "A"); 4208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(4, map.size()); 4218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(map.containsKey(four)); 4228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 4238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 4258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * lowerEntry returns preceding entry. 4268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 4278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testLowerEntry() { 4288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 4298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e1 = map.lowerEntry(three); 4308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, e1.getKey()); 4318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e2 = map.lowerEntry(six); 4338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e2.getKey()); 4348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e3 = map.lowerEntry(one); 4368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e3); 4378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e4 = map.lowerEntry(zero); 4398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e4); 4408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 4418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 4438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * higherEntry returns next entry. 4448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 4458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testHigherEntry() { 4468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 4478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e1 = map.higherEntry(three); 4488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(four, e1.getKey()); 4498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e2 = map.higherEntry(zero); 4518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e2.getKey()); 4528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e3 = map.higherEntry(five); 4548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e3); 4558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e4 = map.higherEntry(six); 4578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e4); 4588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 4598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 4618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * floorEntry returns preceding entry. 4628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 4638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testFloorEntry() { 4648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 4658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e1 = map.floorEntry(three); 4668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, e1.getKey()); 4678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e2 = map.floorEntry(six); 4698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e2.getKey()); 4708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e3 = map.floorEntry(one); 4728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e3.getKey()); 4738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e4 = map.floorEntry(zero); 4758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e4); 4768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 4778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 4798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * ceilingEntry returns next entry. 4808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 4818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testCeilingEntry() { 4828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 4838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e1 = map.ceilingEntry(three); 4848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, e1.getKey()); 4858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e2 = map.ceilingEntry(zero); 4878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e2.getKey()); 4888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e3 = map.ceilingEntry(five); 4908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e3.getKey()); 4918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e4 = map.ceilingEntry(six); 4938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e4); 4948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 4958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 4968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 4978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * lowerEntry, higherEntry, ceilingEntry, and floorEntry return 4988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * immutable entries 4998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 5008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testEntryImmutability() { 5018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 5028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e = map.lowerEntry(three); 5038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, e.getKey()); 5048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 5058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e.setValue("X"); 5068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 5078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (UnsupportedOperationException success) {} 5088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.higherEntry(zero); 5098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e.getKey()); 5108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 5118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e.setValue("X"); 5128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 5138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (UnsupportedOperationException success) {} 5148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.floorEntry(one); 5158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e.getKey()); 5168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 5178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e.setValue("X"); 5188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 5198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (UnsupportedOperationException success) {} 5208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.ceilingEntry(five); 5218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e.getKey()); 5228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 5238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e.setValue("X"); 5248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 5258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (UnsupportedOperationException success) {} 5268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 5278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 5298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * lowerKey returns preceding element 5308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 5318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testLowerKey() { 5328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap q = map5(); 5338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e1 = q.lowerKey(three); 5348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, e1); 5358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e2 = q.lowerKey(six); 5378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e2); 5388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e3 = q.lowerKey(one); 5408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e3); 5418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e4 = q.lowerKey(zero); 5438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e4); 5448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 5458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 5478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * higherKey returns next element 5488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 5498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testHigherKey() { 5508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap q = map5(); 5518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e1 = q.higherKey(three); 5528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(four, e1); 5538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e2 = q.higherKey(zero); 5558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e2); 5568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e3 = q.higherKey(five); 5588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e3); 5598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e4 = q.higherKey(six); 5618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e4); 5628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 5638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 5658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * floorKey returns preceding element 5668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 5678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testFloorKey() { 5688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap q = map5(); 5698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e1 = q.floorKey(three); 5708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, e1); 5718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e2 = q.floorKey(six); 5738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e2); 5748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e3 = q.floorKey(one); 5768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e3); 5778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e4 = q.floorKey(zero); 5798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e4); 5808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 5818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 5838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * ceilingKey returns next element 5848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 5858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testCeilingKey() { 5868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap q = map5(); 5878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e1 = q.ceilingKey(three); 5888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, e1); 5898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e2 = q.ceilingKey(zero); 5918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e2); 5928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e3 = q.ceilingKey(five); 5948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e3); 5958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 5968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object e4 = q.ceilingKey(six); 5978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e4); 5988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 5998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 6008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 6018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * pollFirstEntry returns entries in order 6028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 6038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testPollFirstEntry() { 6048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 6058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e = map.pollFirstEntry(); 6068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e.getKey()); 6078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("A", e.getValue()); 6088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollFirstEntry(); 6098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, e.getKey()); 6108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.put(one, "A"); 6118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollFirstEntry(); 6128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e.getKey()); 6138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("A", e.getValue()); 6148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollFirstEntry(); 6158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, e.getKey()); 6168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.remove(four); 6178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollFirstEntry(); 6188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e.getKey()); 6198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 6208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e.setValue("A"); 6218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 6228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (UnsupportedOperationException success) {} 6238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollFirstEntry(); 6248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e); 6258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 6268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 6278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 6288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * pollLastEntry returns entries in order 6298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 6308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testPollLastEntry() { 6318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 6328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e = map.pollLastEntry(); 6338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e.getKey()); 6348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("E", e.getValue()); 6358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollLastEntry(); 6368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(four, e.getKey()); 6378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.put(five, "E"); 6388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollLastEntry(); 6398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e.getKey()); 6408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("E", e.getValue()); 6418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollLastEntry(); 6428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, e.getKey()); 6438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.remove(two); 6448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollLastEntry(); 6458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, e.getKey()); 6468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 6478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e.setValue("E"); 6488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 6498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (UnsupportedOperationException success) {} 6508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = map.pollLastEntry(); 6518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNull(e); 6528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 6538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 6548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 6558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * size returns the correct values 6568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 6578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testSize() { 6588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 6598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap empty = new ConcurrentSkipListMap(); 6608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(0, empty.size()); 6618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(5, map.size()); 6628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 6638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 6648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 6658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * toString contains toString of elements 6668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 6678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testToString() { 6688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 6698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle String s = map.toString(); 6708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (int i = 1; i <= 5; ++i) { 6718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(s.contains(String.valueOf(i))); 6728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 6738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 6748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 6758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Exception tests 6768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 6778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 6788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * get(null) of nonempty map throws NPE 6798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 6808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testGet_NullPointerException() { 6818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 6828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = map5(); 6838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.get(null); 6848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 6858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NullPointerException success) {} 6868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 6878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 6888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 6898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * containsKey(null) of nonempty map throws NPE 6908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 6918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testContainsKey_NullPointerException() { 6928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 6938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = map5(); 6948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.containsKey(null); 6958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 6968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NullPointerException success) {} 6978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 6988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 6998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 7008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * containsValue(null) throws NPE 7018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 7028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testContainsValue_NullPointerException() { 7038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 7048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = new ConcurrentSkipListMap(); 7058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.containsValue(null); 7068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 7078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NullPointerException success) {} 7088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 7098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 7108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 7118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * put(null,x) throws NPE 7128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 7138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testPut1_NullPointerException() { 7148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 7158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = map5(); 7168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.put(null, "whatever"); 7178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 7188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NullPointerException success) {} 7198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 7208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 7218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 7228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * putIfAbsent(null, x) throws NPE 7238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 7248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testPutIfAbsent1_NullPointerException() { 7258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 7268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = map5(); 7278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.putIfAbsent(null, "whatever"); 7288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 7298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NullPointerException success) {} 7308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 7318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 7328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 7338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * replace(null, x) throws NPE 7348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 7358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testReplace_NullPointerException() { 7368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 7378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = map5(); 7388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.replace(null, "whatever"); 7398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 7408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NullPointerException success) {} 7418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 7428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 7438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 7448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * replace(null, x, y) throws NPE 7458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 7468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testReplaceValue_NullPointerException() { 7478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 7488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = map5(); 7498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.replace(null, one, "whatever"); 7508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 7518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NullPointerException success) {} 7528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 7538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 7548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 7558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * remove(null) throws NPE 7568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 7578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testRemove1_NullPointerException() { 7588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 7598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = new ConcurrentSkipListMap(); 7608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.put("sadsdf", "asdads"); 7618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.remove(null); 7628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 7638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NullPointerException success) {} 7648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 7658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 7668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 7678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * remove(null, x) throws NPE 7688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 7698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testRemove2_NullPointerException() { 7708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 7718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = new ConcurrentSkipListMap(); 7728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.put("sadsdf", "asdads"); 7738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.remove(null, "whatever"); 7748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 7758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NullPointerException success) {} 7768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 7778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 7788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 7798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * remove(x, null) returns false 7808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 7818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testRemove3() { 7828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap c = new ConcurrentSkipListMap(); 7838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle c.put("sadsdf", "asdads"); 7848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(c.remove("sadsdf", null)); 7858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 7868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 7878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 7888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * A deserialized map equals original 7898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 7908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testSerialization() throws Exception { 7918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap x = map5(); 7928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap y = serialClone(x); 7938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 7948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertNotSame(x, y); 7958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(x.size(), y.size()); 7968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(x.toString(), y.toString()); 7978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(x, y); 7988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(y, x); 7998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 8008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 8018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 8028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * subMap returns map with keys in requested range 8038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 8048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testSubMapContents() { 8058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 8068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap sm = map.subMap(two, true, four, false); 8078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, sm.firstKey()); 8088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, sm.lastKey()); 8098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(2, sm.size()); 8108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(one)); 8118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(two)); 8128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(three)); 8138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(four)); 8148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(five)); 8158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator i = sm.keySet().iterator(); 8168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object k; 8178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 8188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, k); 8198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 8208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, k); 8218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(i.hasNext()); 8228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator r = sm.descendingKeySet().iterator(); 8238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(r.next()); 8248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, k); 8258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(r.next()); 8268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, k); 8278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(r.hasNext()); 8288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 8298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator j = sm.keySet().iterator(); 8308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle j.next(); 8318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle j.remove(); 8328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.containsKey(two)); 8338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(4, map.size()); 8348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(1, sm.size()); 8358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, sm.firstKey()); 8368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, sm.lastKey()); 8378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("C", sm.remove(three)); 8388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.isEmpty()); 8398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(3, map.size()); 8408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 8418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 8428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testSubMapContents2() { 8438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 8448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap sm = map.subMap(two, true, three, false); 8458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(1, sm.size()); 8468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, sm.firstKey()); 8478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, sm.lastKey()); 8488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(one)); 8498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(two)); 8508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(three)); 8518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(four)); 8528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(five)); 8538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator i = sm.keySet().iterator(); 8548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object k; 8558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 8568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, k); 8578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(i.hasNext()); 8588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator r = sm.descendingKeySet().iterator(); 8598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(r.next()); 8608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, k); 8618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(r.hasNext()); 8628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 8638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator j = sm.keySet().iterator(); 8648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle j.next(); 8658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle j.remove(); 8668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(map.containsKey(two)); 8678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(4, map.size()); 8688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(0, sm.size()); 8698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.isEmpty()); 8708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertSame(sm.remove(three), null); 8718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(4, map.size()); 8728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 8738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 8748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 8758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * headMap returns map with keys in requested range 8768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 8778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testHeadMapContents() { 8788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 8798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap sm = map.headMap(four, false); 8808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(one)); 8818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(two)); 8828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(three)); 8838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(four)); 8848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(five)); 8858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator i = sm.keySet().iterator(); 8868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object k; 8878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 8888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(one, k); 8898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 8908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, k); 8918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 8928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, k); 8938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(i.hasNext()); 8948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle sm.clear(); 8958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.isEmpty()); 8968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(2, map.size()); 8978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(four, map.firstKey()); 8988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 8998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 9018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * tailMap returns map with keys in requested range 9028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 9038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testTailMapContents() { 9048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ConcurrentSkipListMap map = map5(); 9058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap sm = map.tailMap(two, true); 9068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(sm.containsKey(one)); 9078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(two)); 9088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(three)); 9098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(four)); 9108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(sm.containsKey(five)); 9118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator i = sm.keySet().iterator(); 9128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Object k; 9138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 9148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, k); 9158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 9168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, k); 9178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 9188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(four, k); 9198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(i.next()); 9208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, k); 9218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(i.hasNext()); 9228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator r = sm.descendingKeySet().iterator(); 9238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(r.next()); 9248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, k); 9258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(r.next()); 9268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(four, k); 9278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(r.next()); 9288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, k); 9298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle k = (Integer)(r.next()); 9308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, k); 9318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(r.hasNext()); 9328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Iterator ei = sm.entrySet().iterator(); 9348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Map.Entry e; 9358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = (Map.Entry)(ei.next()); 9368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(two, e.getKey()); 9378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("B", e.getValue()); 9388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = (Map.Entry)(ei.next()); 9398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(three, e.getKey()); 9408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("C", e.getValue()); 9418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = (Map.Entry)(ei.next()); 9428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(four, e.getKey()); 9438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("D", e.getValue()); 9448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle e = (Map.Entry)(ei.next()); 9458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, e.getKey()); 9468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("E", e.getValue()); 9478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(i.hasNext()); 9488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap ssm = sm.tailMap(four, true); 9508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(four, ssm.firstKey()); 9518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(five, ssm.lastKey()); 9528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals("D", ssm.remove(four)); 9538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(1, ssm.size()); 9548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(3, sm.size()); 9558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(4, map.size()); 9568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 9578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Random rnd = new Random(666); 9598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle BitSet bs; 9608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 9628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * Submaps of submaps subdivide correctly 9638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 9648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle public void testRecursiveSubMaps() throws Exception { 9658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int mapSize = expensiveTests ? 1000 : 100; 9668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Class cl = ConcurrentSkipListMap.class; 9678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap<Integer, Integer> map = newMap(cl); 9688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bs = new BitSet(mapSize); 9698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle populate(map, mapSize); 9718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle check(map, 0, mapSize - 1, true); 9728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle check(map.descendingMap(), 0, mapSize - 1, false); 9738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle mutateMap(map, 0, mapSize - 1); 9758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle check(map, 0, mapSize - 1, true); 9768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle check(map.descendingMap(), 0, mapSize - 1, false); 9778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(map.subMap(0, true, mapSize, false), 9798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 0, mapSize - 1, true); 9808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 9818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception { 9838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap<Integer, Integer> result = 9848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (NavigableMap<Integer, Integer>) cl.newInstance(); 9858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(0, result.size()); 9868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertFalse(result.keySet().iterator().hasNext()); 9878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return result; 9888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 9898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle void populate(NavigableMap<Integer, Integer> map, int limit) { 9918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (int i = 0, n = 2 * limit / 3; i < n; i++) { 9928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int key = rnd.nextInt(limit); 9938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle put(map, key); 9948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 9958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 9968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 9978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) { 9988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int size = map.size(); 9998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int rangeSize = max - min + 1; 10008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Remove a bunch of entries directly 10028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (int i = 0, n = rangeSize / 2; i < n; i++) { 10038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle remove(map, min - 5 + rnd.nextInt(rangeSize + 10)); 10048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Remove a bunch of entries with iterator 10078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) { 10088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (rnd.nextBoolean()) { 10098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bs.clear(it.next()); 10108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle it.remove(); 10118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Add entries till we're back to original size 10158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle while (map.size() < size) { 10168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int key = min + rnd.nextInt(rangeSize); 10178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(key >= min && key<= max); 10188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle put(map, key); 10198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) { 10238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int size = map.size(); 10248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int rangeSize = max - min + 1; 10258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Remove a bunch of entries directly 10278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (int i = 0, n = rangeSize / 2; i < n; i++) { 10288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle remove(map, min - 5 + rnd.nextInt(rangeSize + 10)); 10298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Remove a bunch of entries with iterator 10328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) { 10338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (rnd.nextBoolean()) { 10348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bs.clear(it.next()); 10358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle it.remove(); 10368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Add entries till we're back to original size 10408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle while (map.size() < size) { 10418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int key = min - 5 + rnd.nextInt(rangeSize + 10); 10428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (key >= min && key<= max) { 10438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle put(map, key); 10448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } else { 10458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 10468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.put(key, 2 * key); 10478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 10488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (IllegalArgumentException success) {} 10498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle void put(NavigableMap<Integer, Integer> map, int key) { 10548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (map.put(key, 2 * key) == null) 10558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bs.set(key); 10568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle void remove(NavigableMap<Integer, Integer> map, int key) { 10598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (map.remove(key) != null) 10608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bs.clear(key); 10618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle void bashSubMap(NavigableMap<Integer, Integer> map, 10648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int min, int max, boolean ascending) { 10658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle check(map, min, max, ascending); 10668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle check(map.descendingMap(), min, max, !ascending); 10678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle mutateSubMap(map, min, max); 10698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle check(map, min, max, ascending); 10708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle check(map.descendingMap(), min, max, !ascending); 10718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Recurse 10738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (max - min < 2) 10748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return; 10758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int midPoint = (min + max) / 2; 10768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // headMap - pick direction and endpoint inclusion randomly 10788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle boolean incl = rnd.nextBoolean(); 10798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl); 10808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (ascending) { 10818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (rnd.nextBoolean()) 10828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true); 10838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle else 10848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1), 10858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle false); 10868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } else { 10878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (rnd.nextBoolean()) 10888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false); 10898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle else 10908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max, 10918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle true); 10928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 10938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 10948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // tailMap - pick direction and endpoint inclusion randomly 10958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle incl = rnd.nextBoolean(); 10968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl); 10978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (ascending) { 10988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (rnd.nextBoolean()) 10998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true); 11008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle else 11018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max, 11028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle false); 11038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } else { 11048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (rnd.nextBoolean()) { 11058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false); 11068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } else { 11078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1), 11088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle true); 11098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 11128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // subMap - pick direction and endpoint inclusion randomly 11138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int rangeSize = max - min + 1; 11148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int[] endpoints = new int[2]; 11158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle endpoints[0] = min + rnd.nextInt(rangeSize); 11168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle endpoints[1] = min + rnd.nextInt(rangeSize); 11178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle Arrays.sort(endpoints); 11188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle boolean lowIncl = rnd.nextBoolean(); 11198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle boolean highIncl = rnd.nextBoolean(); 11208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (ascending) { 11218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap<Integer,Integer> sm = map.subMap( 11228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle endpoints[0], lowIncl, endpoints[1], highIncl); 11238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (rnd.nextBoolean()) 11248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1), 11258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle endpoints[1] - (highIncl ? 0 : 1), true); 11268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle else 11278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1), 11288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle endpoints[1] - (highIncl ? 0 : 1), false); 11298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } else { 11308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle NavigableMap<Integer,Integer> sm = map.subMap( 11318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle endpoints[1], highIncl, endpoints[0], lowIncl); 11328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (rnd.nextBoolean()) 11338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1), 11348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle endpoints[1] - (highIncl ? 0 : 1), false); 11358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle else 11368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1), 11378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle endpoints[1] - (highIncl ? 0 : 1), true); 11388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 11418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle /** 11428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle * min and max are both inclusive. If max < min, interval is empty. 11438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle */ 11448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle void check(NavigableMap<Integer, Integer> map, 11458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle final int min, final int max, final boolean ascending) { 11468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle class ReferenceSet { 11478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int lower(int key) { 11488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return ascending ? lowerAscending(key) : higherAscending(key); 11498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int floor(int key) { 11518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return ascending ? floorAscending(key) : ceilingAscending(key); 11528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int ceiling(int key) { 11548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return ascending ? ceilingAscending(key) : floorAscending(key); 11558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int higher(int key) { 11578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return ascending ? higherAscending(key) : lowerAscending(key); 11588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int first() { 11608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return ascending ? firstAscending() : lastAscending(); 11618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int last() { 11638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return ascending ? lastAscending() : firstAscending(); 11648f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11658f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int lowerAscending(int key) { 11668f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return floorAscending(key - 1); 11678f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11688f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int floorAscending(int key) { 11698f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (key < min) 11708f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return -1; 11718f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle else if (key > max) 11728f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle key = max; 11738f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 11748f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // BitSet should support this! Test would run much faster 11758f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle while (key >= min) { 11768f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (bs.get(key)) 11778f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return key; 11788f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle key--; 11798f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11808f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return -1; 11818f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11828f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int ceilingAscending(int key) { 11838f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (key < min) 11848f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle key = min; 11858f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle else if (key > max) 11868f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return -1; 11878f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int result = bs.nextSetBit(key); 11888f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return result > max ? -1 : result; 11898f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11908f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int higherAscending(int key) { 11918f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return ceilingAscending(key + 1); 11928f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11938f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle private int firstAscending() { 11948f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int result = ceilingAscending(min); 11958f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return result > max ? -1 : result; 11968f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 11978f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle private int lastAscending() { 11988f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int result = floorAscending(max); 11998f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return result < min ? -1 : result; 12008f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 12018f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 12028f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle ReferenceSet rs = new ReferenceSet(); 12038f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 12048f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Test contents using containsKey 12058f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int size = 0; 12068f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (int i = min; i <= max; i++) { 12078f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle boolean bsContainsI = bs.get(i); 12088f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(bsContainsI, map.containsKey(i)); 12098f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (bsContainsI) 12108f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle size++; 12118f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 12128f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(size, map.size()); 12138f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 12148f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Test contents using contains keySet iterator 12158f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int size2 = 0; 12168f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle int previousKey = -1; 12178f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (int key : map.keySet()) { 12188f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(bs.get(key)); 12198f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle size2++; 12208f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertTrue(previousKey < 0 || 12218f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle (ascending ? key - previousKey > 0 : key - previousKey < 0)); 12228f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle previousKey = key; 12238f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 12248f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(size2, size); 12258f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 12268f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Test navigation ops 12278f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle for (int key = min - 1; key <= max + 1; key++) { 12288f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEq(map.lowerKey(key), rs.lower(key)); 12298f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEq(map.floorKey(key), rs.floor(key)); 12308f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEq(map.higherKey(key), rs.higher(key)); 12318f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEq(map.ceilingKey(key), rs.ceiling(key)); 12328f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 12338f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 12348f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle // Test extrema 12358f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (map.size() != 0) { 12368f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEq(map.firstKey(), rs.first()); 12378f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEq(map.lastKey(), rs.last()); 12388f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } else { 12398f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEq(rs.first(), -1); 12408f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEq(rs.last(), -1); 12418f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 12428f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.firstKey(); 12438f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 12448f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NoSuchElementException success) {} 12458f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle try { 12468f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle map.lastKey(); 12478f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle shouldThrow(); 12488f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } catch (NoSuchElementException success) {} 12498f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 12508f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 12518f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 12528f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle static void assertEq(Integer i, int j) { 12538f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle if (i == null) 12548f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals(j, -1); 12558f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle else 12568f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle assertEquals((int) i, j); 12578f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 12588f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 12598f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle static boolean eq(Integer i, int j) { 12608f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle return i == null ? j == -1 : i == j; 12618f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle } 12628f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle 12638f0d92bba199d906c70a5e40d7f3516c1a424117Calin Juravle} 1264