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