--- jsr166/src/test/tck/ConcurrentSkipListSetTest.java 2004/12/28 16:15:59 1.1 +++ jsr166/src/test/tck/ConcurrentSkipListSetTest.java 2010/08/25 01:44:48 1.14 @@ -11,19 +11,15 @@ import java.io.*; public class ConcurrentSkipListSetTest extends JSR166TestCase { public static void main(String[] args) { - junit.textui.TestRunner.run (suite()); + junit.textui.TestRunner.run(suite()); } public static Test suite() { - return new TestSuite(ConcurrentSkipListSetTest.class); + return new TestSuite(ConcurrentSkipListSetTest.class); } - static class MyReverseComparator implements Comparator { + static class MyReverseComparator implements Comparator { public int compare(Object x, Object y) { - int i = ((Integer)x).intValue(); - int j = ((Integer)y).intValue(); - if (i < j) return 1; - if (i > j) return -1; - return 0; + return ((Comparable)y).compareTo(x); } } @@ -34,12 +30,12 @@ public class ConcurrentSkipListSetTest e private ConcurrentSkipListSet populatedSet(int n) { ConcurrentSkipListSet q = new ConcurrentSkipListSet(); assertTrue(q.isEmpty()); - for(int i = n-1; i >= 0; i-=2) - assertTrue(q.add(new Integer(i))); - for(int i = (n & 1); i < n; i+=2) - assertTrue(q.add(new Integer(i))); + for (int i = n-1; i >= 0; i-=2) + assertTrue(q.add(new Integer(i))); + for (int i = (n & 1); i < n; i+=2) + assertTrue(q.add(new Integer(i))); assertFalse(q.isEmpty()); - assertEquals(n, q.size()); + assertEquals(n, q.size()); return q; } @@ -54,10 +50,10 @@ public class ConcurrentSkipListSetTest e q.add(three); q.add(four); q.add(five); - assertEquals(5, q.size()); + assertEquals(5, q.size()); return q; } - + /** * A new set has unbounded capacity */ @@ -72,8 +68,7 @@ public class ConcurrentSkipListSetTest e try { ConcurrentSkipListSet q = new ConcurrentSkipListSet((Collection)null); shouldThrow(); - } - catch (NullPointerException success) {} + } catch (NullPointerException success) {} } /** @@ -84,8 +79,7 @@ public class ConcurrentSkipListSetTest e Integer[] ints = new Integer[SIZE]; ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints)); shouldThrow(); - } - catch (NullPointerException success) {} + } catch (NullPointerException success) {} } /** @@ -98,41 +92,34 @@ public class ConcurrentSkipListSetTest e ints[i] = new Integer(i); ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints)); shouldThrow(); - } - catch (NullPointerException success) {} + } catch (NullPointerException success) {} } /** * Set contains all elements of collection used to initialize */ public void testConstructor6() { - try { - Integer[] ints = new Integer[SIZE]; - for (int i = 0; i < SIZE; ++i) - ints[i] = new Integer(i); - ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints)); - for (int i = 0; i < SIZE; ++i) - assertEquals(ints[i], q.pollFirst()); - } - finally {} + Integer[] ints = new Integer[SIZE]; + for (int i = 0; i < SIZE; ++i) + ints[i] = new Integer(i); + ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints)); + for (int i = 0; i < SIZE; ++i) + assertEquals(ints[i], q.pollFirst()); } /** * The comparator used in constructor is used */ public void testConstructor7() { - try { - MyReverseComparator cmp = new MyReverseComparator(); - ConcurrentSkipListSet q = new ConcurrentSkipListSet(cmp); - assertEquals(cmp, q.comparator()); - Integer[] ints = new Integer[SIZE]; - for (int i = 0; i < SIZE; ++i) - ints[i] = new Integer(i); - q.addAll(Arrays.asList(ints)); - for (int i = SIZE-1; i >= 0; --i) - assertEquals(ints[i], q.pollFirst()); - } - finally {} + MyReverseComparator cmp = new MyReverseComparator(); + ConcurrentSkipListSet q = new ConcurrentSkipListSet(cmp); + assertEquals(cmp, q.comparator()); + Integer[] ints = new Integer[SIZE]; + for (int i = 0; i < SIZE; ++i) + ints[i] = new Integer(i); + q.addAll(Arrays.asList(ints)); + for (int i = SIZE-1; i >= 0; --i) + assertEquals(ints[i], q.pollFirst()); } /** @@ -168,11 +155,11 @@ public class ConcurrentSkipListSetTest e * add(null) throws NPE */ public void testAddNull() { - try { + try { ConcurrentSkipListSet q = new ConcurrentSkipListSet(); q.add(null); shouldThrow(); - } catch (NullPointerException success) { } + } catch (NullPointerException success) {} } /** @@ -203,8 +190,7 @@ public class ConcurrentSkipListSetTest e q.add(new Object()); q.add(new Object()); shouldThrow(); - } - catch(ClassCastException success) {} + } catch (ClassCastException success) {} } /** @@ -215,9 +201,9 @@ public class ConcurrentSkipListSetTest e ConcurrentSkipListSet q = new ConcurrentSkipListSet(); q.addAll(null); shouldThrow(); - } - catch (NullPointerException success) {} + } catch (NullPointerException success) {} } + /** * addAll of a collection with null elements throws NPE */ @@ -227,9 +213,9 @@ public class ConcurrentSkipListSetTest e Integer[] ints = new Integer[SIZE]; q.addAll(Arrays.asList(ints)); shouldThrow(); - } - catch (NullPointerException success) {} + } catch (NullPointerException success) {} } + /** * addAll of a collection with any null elements throws NPE after * possibly adding some elements @@ -242,26 +228,22 @@ public class ConcurrentSkipListSetTest e ints[i] = new Integer(i); q.addAll(Arrays.asList(ints)); shouldThrow(); - } - catch (NullPointerException success) {} + } catch (NullPointerException success) {} } /** * Set contains all elements of successful addAll */ public void testAddAll5() { - try { - Integer[] empty = new Integer[0]; - Integer[] ints = new Integer[SIZE]; - for (int i = 0; i < SIZE; ++i) - ints[i] = new Integer(SIZE-1-i); - ConcurrentSkipListSet q = new ConcurrentSkipListSet(); - assertFalse(q.addAll(Arrays.asList(empty))); - assertTrue(q.addAll(Arrays.asList(ints))); - for (int i = 0; i < SIZE; ++i) - assertEquals(new Integer(i), q.pollFirst()); - } - finally {} + Integer[] empty = new Integer[0]; + Integer[] ints = new Integer[SIZE]; + for (int i = 0; i < SIZE; ++i) + ints[i] = new Integer(SIZE-1-i); + ConcurrentSkipListSet q = new ConcurrentSkipListSet(); + assertFalse(q.addAll(Arrays.asList(empty))); + assertTrue(q.addAll(Arrays.asList(ints))); + for (int i = 0; i < SIZE; ++i) + assertEquals(i, q.pollFirst()); } /** @@ -270,9 +252,9 @@ public class ConcurrentSkipListSetTest e public void testPollFirst() { ConcurrentSkipListSet q = populatedSet(SIZE); for (int i = 0; i < SIZE; ++i) { - assertEquals(i, ((Integer)q.pollFirst()).intValue()); + assertEquals(i, q.pollFirst()); } - assertNull(q.pollFirst()); + assertNull(q.pollFirst()); } /** @@ -281,9 +263,9 @@ public class ConcurrentSkipListSetTest e public void testPollLast() { ConcurrentSkipListSet q = populatedSet(SIZE); for (int i = SIZE-1; i >= 0; --i) { - assertEquals(i, ((Integer)q.pollLast()).intValue()); + assertEquals(i, q.pollLast()); } - assertNull(q.pollFirst()); + assertNull(q.pollFirst()); } @@ -301,7 +283,7 @@ public class ConcurrentSkipListSetTest e } assertTrue(q.isEmpty()); } - + /** * contains(x) reports true when elements added but not yet removed */ @@ -377,7 +359,7 @@ public class ConcurrentSkipListSetTest e } } - + /** * lower returns preceding element @@ -395,7 +377,6 @@ public class ConcurrentSkipListSetTest e Object e4 = q.lower(zero); assertNull(e4); - } /** @@ -414,7 +395,6 @@ public class ConcurrentSkipListSetTest e Object e4 = q.higher(six); assertNull(e4); - } /** @@ -433,7 +413,6 @@ public class ConcurrentSkipListSetTest e Object e4 = q.floor(zero); assertNull(e4); - } /** @@ -452,7 +431,6 @@ public class ConcurrentSkipListSetTest e Object e4 = q.ceiling(six); assertNull(e4); - } /** @@ -460,10 +438,10 @@ public class ConcurrentSkipListSetTest e */ public void testToArray() { ConcurrentSkipListSet q = populatedSet(SIZE); - Object[] o = q.toArray(); + Object[] o = q.toArray(); Arrays.sort(o); - for(int i = 0; i < o.length; i++) - assertEquals(o[i], q.pollFirst()); + for (int i = 0; i < o.length; i++) + assertEquals(o[i], q.pollFirst()); } /** @@ -471,21 +449,21 @@ public class ConcurrentSkipListSetTest e */ public void testToArray2() { ConcurrentSkipListSet q = populatedSet(SIZE); - Integer[] ints = new Integer[SIZE]; - ints = (Integer[])q.toArray(ints); + Integer[] ints = new Integer[SIZE]; + ints = (Integer[])q.toArray(ints); Arrays.sort(ints); - for(int i = 0; i < ints.length; i++) + for (int i = 0; i < ints.length; i++) assertEquals(ints[i], q.pollFirst()); } - + /** * iterator iterates through all elements */ public void testIterator() { ConcurrentSkipListSet q = populatedSet(SIZE); int i = 0; - Iterator it = q.iterator(); - while(it.hasNext()) { + Iterator it = q.iterator(); + while (it.hasNext()) { assertTrue(q.contains(it.next())); ++i; } @@ -498,8 +476,8 @@ public class ConcurrentSkipListSetTest e public void testEmptyIterator() { ConcurrentSkipListSet q = new ConcurrentSkipListSet(); int i = 0; - Iterator it = q.iterator(); - while(it.hasNext()) { + Iterator it = q.iterator(); + while (it.hasNext()) { assertTrue(q.contains(it.next())); ++i; } @@ -509,7 +487,7 @@ public class ConcurrentSkipListSetTest e /** * iterator.remove removes current element */ - public void testIteratorRemove () { + public void testIteratorRemove() { final ConcurrentSkipListSet q = new ConcurrentSkipListSet(); q.add(new Integer(2)); q.add(new Integer(1)); @@ -535,29 +513,24 @@ public class ConcurrentSkipListSetTest e for (int i = 0; i < SIZE; ++i) { assertTrue(s.indexOf(String.valueOf(i)) >= 0); } - } + } /** - * A deserialized serialized set has same elements + * A deserialized serialized set has same elements */ - public void testSerialization() { + public void testSerialization() throws Exception { ConcurrentSkipListSet q = populatedSet(SIZE); - try { - ByteArrayOutputStream bout = new ByteArrayOutputStream(10000); - ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout)); - out.writeObject(q); - out.close(); - - ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray()); - ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin)); - ConcurrentSkipListSet r = (ConcurrentSkipListSet)in.readObject(); - assertEquals(q.size(), r.size()); - while (!q.isEmpty()) - assertEquals(q.pollFirst(), r.pollFirst()); - } catch(Exception e){ - e.printStackTrace(); - unexpectedException(); - } + ByteArrayOutputStream bout = new ByteArrayOutputStream(10000); + ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout)); + out.writeObject(q); + out.close(); + + ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray()); + ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin)); + ConcurrentSkipListSet r = (ConcurrentSkipListSet)in.readObject(); + assertEquals(q.size(), r.size()); + while (!q.isEmpty()) + assertEquals(q.pollFirst(), r.pollFirst()); } /** @@ -679,4 +652,313 @@ public class ConcurrentSkipListSetTest e assertEquals(4, set.size()); } + Random rnd = new Random(666); + BitSet bs; + + /** + * Subsets of subsets subdivide correctly + */ + public void testRecursiveSubSets() throws Exception { + int setSize = 1000; + Class cl = ConcurrentSkipListSet.class; + + NavigableSet set = newSet(cl); + bs = new BitSet(setSize); + + populate(set, setSize); + check(set, 0, setSize - 1, true); + check(set.descendingSet(), 0, setSize - 1, false); + + mutateSet(set, 0, setSize - 1); + check(set, 0, setSize - 1, true); + check(set.descendingSet(), 0, setSize - 1, false); + + bashSubSet(set.subSet(0, true, setSize, false), + 0, setSize - 1, true); + } + + static NavigableSet newSet(Class cl) throws Exception { + NavigableSet result = (NavigableSet) cl.newInstance(); + assertEquals(result.size(), 0); + assertFalse(result.iterator().hasNext()); + return result; + } + + void populate(NavigableSet set, int limit) { + for (int i = 0, n = 2 * limit / 3; i < n; i++) { + int element = rnd.nextInt(limit); + put(set, element); + } + } + + void mutateSet(NavigableSet set, int min, int max) { + int size = set.size(); + int rangeSize = max - min + 1; + + // Remove a bunch of entries directly + for (int i = 0, n = rangeSize / 2; i < n; i++) { + remove(set, min - 5 + rnd.nextInt(rangeSize + 10)); + } + + // Remove a bunch of entries with iterator + for (Iterator it = set.iterator(); it.hasNext(); ) { + if (rnd.nextBoolean()) { + bs.clear(it.next()); + it.remove(); + } + } + + // Add entries till we're back to original size + while (set.size() < size) { + int element = min + rnd.nextInt(rangeSize); + assertTrue(element >= min && element<= max); + put(set, element); + } + } + + void mutateSubSet(NavigableSet set, int min, int max) { + int size = set.size(); + int rangeSize = max - min + 1; + + // Remove a bunch of entries directly + for (int i = 0, n = rangeSize / 2; i < n; i++) { + remove(set, min - 5 + rnd.nextInt(rangeSize + 10)); + } + + // Remove a bunch of entries with iterator + for (Iterator it = set.iterator(); it.hasNext(); ) { + if (rnd.nextBoolean()) { + bs.clear(it.next()); + it.remove(); + } + } + + // Add entries till we're back to original size + while (set.size() < size) { + int element = min - 5 + rnd.nextInt(rangeSize + 10); + if (element >= min && element<= max) { + put(set, element); + } else { + try { + set.add(element); + shouldThrow(); + } catch (IllegalArgumentException success) {} + } + } + } + + void put(NavigableSet set, int element) { + if (set.add(element)) + bs.set(element); + } + + void remove(NavigableSet set, int element) { + if (set.remove(element)) + bs.clear(element); + } + + void bashSubSet(NavigableSet set, + int min, int max, boolean ascending) { + check(set, min, max, ascending); + check(set.descendingSet(), min, max, !ascending); + + mutateSubSet(set, min, max); + check(set, min, max, ascending); + check(set.descendingSet(), min, max, !ascending); + + // Recurse + if (max - min < 2) + return; + int midPoint = (min + max) / 2; + + // headSet - pick direction and endpoint inclusion randomly + boolean incl = rnd.nextBoolean(); + NavigableSet hm = set.headSet(midPoint, incl); + if (ascending) { + if (rnd.nextBoolean()) + bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true); + else + bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1), + false); + } else { + if (rnd.nextBoolean()) + bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false); + else + bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max, + true); + } + + // tailSet - pick direction and endpoint inclusion randomly + incl = rnd.nextBoolean(); + NavigableSet tm = set.tailSet(midPoint,incl); + if (ascending) { + if (rnd.nextBoolean()) + bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true); + else + bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max, + false); + } else { + if (rnd.nextBoolean()) { + bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false); + } else { + bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1), + true); + } + } + + // subSet - pick direction and endpoint inclusion randomly + int rangeSize = max - min + 1; + int[] endpoints = new int[2]; + endpoints[0] = min + rnd.nextInt(rangeSize); + endpoints[1] = min + rnd.nextInt(rangeSize); + Arrays.sort(endpoints); + boolean lowIncl = rnd.nextBoolean(); + boolean highIncl = rnd.nextBoolean(); + if (ascending) { + NavigableSet sm = set.subSet( + endpoints[0], lowIncl, endpoints[1], highIncl); + if (rnd.nextBoolean()) + bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1), + endpoints[1] - (highIncl ? 0 : 1), true); + else + bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1), + endpoints[1] - (highIncl ? 0 : 1), false); + } else { + NavigableSet sm = set.subSet( + endpoints[1], highIncl, endpoints[0], lowIncl); + if (rnd.nextBoolean()) + bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1), + endpoints[1] - (highIncl ? 0 : 1), false); + else + bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1), + endpoints[1] - (highIncl ? 0 : 1), true); + } + } + + /** + * min and max are both inclusive. If max < min, interval is empty. + */ + void check(NavigableSet set, + final int min, final int max, final boolean ascending) { + class ReferenceSet { + int lower(int element) { + return ascending ? + lowerAscending(element) : higherAscending(element); + } + int floor(int element) { + return ascending ? + floorAscending(element) : ceilingAscending(element); + } + int ceiling(int element) { + return ascending ? + ceilingAscending(element) : floorAscending(element); + } + int higher(int element) { + return ascending ? + higherAscending(element) : lowerAscending(element); + } + int first() { + return ascending ? firstAscending() : lastAscending(); + } + int last() { + return ascending ? lastAscending() : firstAscending(); + } + int lowerAscending(int element) { + return floorAscending(element - 1); + } + int floorAscending(int element) { + if (element < min) + return -1; + else if (element > max) + element = max; + + // BitSet should support this! Test would run much faster + while (element >= min) { + if (bs.get(element)) + return(element); + element--; + } + return -1; + } + int ceilingAscending(int element) { + if (element < min) + element = min; + else if (element > max) + return -1; + int result = bs.nextSetBit(element); + return result > max ? -1 : result; + } + int higherAscending(int element) { + return ceilingAscending(element + 1); + } + private int firstAscending() { + int result = ceilingAscending(min); + return result > max ? -1 : result; + } + private int lastAscending() { + int result = floorAscending(max); + return result < min ? -1 : result; + } + } + ReferenceSet rs = new ReferenceSet(); + + // Test contents using containsElement + int size = 0; + for (int i = min; i <= max; i++) { + boolean bsContainsI = bs.get(i); + assertEquals(bsContainsI, set.contains(i)); + if (bsContainsI) + size++; + } + assertEquals(set.size(), size); + + // Test contents using contains elementSet iterator + int size2 = 0; + int previousElement = -1; + for (int element : set) { + assertTrue(bs.get(element)); + size2++; + assertTrue(previousElement < 0 || (ascending ? + element - previousElement > 0 : element - previousElement < 0)); + previousElement = element; + } + assertEquals(size2, size); + + // Test navigation ops + for (int element = min - 1; element <= max + 1; element++) { + assertEq(set.lower(element), rs.lower(element)); + assertEq(set.floor(element), rs.floor(element)); + assertEq(set.higher(element), rs.higher(element)); + assertEq(set.ceiling(element), rs.ceiling(element)); + } + + // Test extrema + if (set.size() != 0) { + assertEq(set.first(), rs.first()); + assertEq(set.last(), rs.last()); + } else { + assertEq(rs.first(), -1); + assertEq(rs.last(), -1); + try { + set.first(); + shouldThrow(); + } catch (NoSuchElementException success) {} + try { + set.last(); + shouldThrow(); + } catch (NoSuchElementException success) {} + } + } + + static void assertEq(Integer i, int j) { + if (i == null) + assertEquals(j, -1); + else + assertEquals((int) i, j); + } + + static boolean eq(Integer i, int j) { + return i == null ? j == -1 : i == j; + } + }