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