--- jsr166/src/test/tck/ConcurrentSkipListSetTest.java	2004/12/28 16:15:59	1.1
+++ jsr166/src/test/tck/ConcurrentSkipListSetTest.java	2021/01/26 13:33:05	1.51
@@ -1,68 +1,75 @@
 /*
  * Written by Doug Lea with assistance from members of JCP JSR-166
  * Expert Group and released to the public domain, as explained at
- * http://creativecommons.org/licenses/publicdomain
+ * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
-import junit.framework.*;
-import java.util.*;
-import java.util.concurrent.*;
-import java.io.*;
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NavigableSet;
+import java.util.NoSuchElementException;
+import java.util.Random;
+import java.util.Set;
+import java.util.SortedSet;
+import java.util.concurrent.ConcurrentSkipListSet;
+
+import junit.framework.Test;
+import junit.framework.TestSuite;
 
 public class ConcurrentSkipListSetTest extends JSR166TestCase {
     public static void main(String[] args) {
-	junit.textui.TestRunner.run (suite());	
+        main(suite(), args);
     }
     public static Test suite() {
-	return new TestSuite(ConcurrentSkipListSetTest.class);
+        return new TestSuite(ConcurrentSkipListSetTest.class);
     }
 
-    static class MyReverseComparator implements Comparator { 
+    static class MyReverseComparator implements Comparator {
+        @SuppressWarnings("unchecked")
         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);
         }
     }
 
     /**
-     * Create a set of given size containing consecutive
-     * Integers 0 ... n.
+     * Returns a new set of given size containing consecutive
+     * Items 0 ... n - 1.
      */
-    private ConcurrentSkipListSet populatedSet(int n) {
-        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
+    private static ConcurrentSkipListSet<Item> populatedSet(int n) {
+        ConcurrentSkipListSet<Item> 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)
+            mustAdd(q, i);
+        for (int i = (n & 1); i < n; i += 2)
+            mustAdd(q, i);
         assertFalse(q.isEmpty());
-	assertEquals(n, q.size());
+        mustEqual(n, q.size());
         return q;
     }
 
     /**
-     * Create set of first 5 ints
+     * Returns a new set of first 5 ints.
      */
-    private ConcurrentSkipListSet set5() {
-        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
+    private static ConcurrentSkipListSet<Item> set5() {
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
         assertTrue(q.isEmpty());
         q.add(one);
         q.add(two);
         q.add(three);
         q.add(four);
         q.add(five);
-	assertEquals(5, q.size());
+        mustEqual(5, q.size());
         return q;
     }
- 
+
     /**
      * A new set has unbounded capacity
      */
     public void testConstructor1() {
-        assertEquals(0, new ConcurrentSkipListSet().size());
+        mustEqual(0, new ConcurrentSkipListSet<Item>().size());
     }
 
     /**
@@ -70,10 +77,9 @@ public class ConcurrentSkipListSetTest e
      */
     public void testConstructor3() {
         try {
-            ConcurrentSkipListSet q = new ConcurrentSkipListSet((Collection)null);
+            new ConcurrentSkipListSet<Item>((Collection<Item>)null);
             shouldThrow();
-        }
-        catch (NullPointerException success) {}
+        } catch (NullPointerException success) {}
     }
 
     /**
@@ -81,69 +87,56 @@ public class ConcurrentSkipListSetTest e
      */
     public void testConstructor4() {
         try {
-            Integer[] ints = new Integer[SIZE];
-            ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints));
+            new ConcurrentSkipListSet<Item>(Arrays.asList(new Item[SIZE]));
             shouldThrow();
-        }
-        catch (NullPointerException success) {}
+        } catch (NullPointerException success) {}
     }
 
     /**
      * Initializing from Collection with some null elements throws NPE
      */
     public void testConstructor5() {
+        Item[] items = new Item[2];
+        items[0] = zero;
         try {
-            Integer[] ints = new Integer[SIZE];
-            for (int i = 0; i < SIZE-1; ++i)
-                ints[i] = new Integer(i);
-            ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints));
+            new ConcurrentSkipListSet<Item>(Arrays.asList(items));
             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 {}
+        Item[] items = defaultItems;
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>(Arrays.asList(items));
+        for (int i = 0; i < SIZE; ++i)
+            mustEqual(items[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();
+        @SuppressWarnings("unchecked")
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>(cmp);
+        mustEqual(cmp, q.comparator());
+        Item[] items = defaultItems;
+        q.addAll(Arrays.asList(items));
+        for (int i = SIZE - 1; i >= 0; --i)
+            mustEqual(items[i], q.pollFirst());
     }
 
     /**
      * isEmpty is true before add, false after
      */
     public void testEmpty() {
-        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
         assertTrue(q.isEmpty());
-        q.add(new Integer(1));
+        mustAdd(q, one);
         assertFalse(q.isEmpty());
-        q.add(new Integer(2));
+        mustAdd(q, two);
         q.pollFirst();
         q.pollFirst();
         assertTrue(q.isEmpty());
@@ -153,14 +146,14 @@ public class ConcurrentSkipListSetTest e
      * size changes when elements added and removed
      */
     public void testSize() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(SIZE-i, q.size());
+            mustEqual(SIZE - i, q.size());
             q.pollFirst();
         }
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, q.size());
-            q.add(new Integer(i));
+            mustEqual(i, q.size());
+            mustAdd(q, i);
         }
     }
 
@@ -168,18 +161,18 @@ public class ConcurrentSkipListSetTest e
      * add(null) throws NPE
      */
     public void testAddNull() {
-	try {
-            ConcurrentSkipListSet q = new ConcurrentSkipListSet();
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
+        try {
             q.add(null);
             shouldThrow();
-        } catch (NullPointerException success) { }   
+        } catch (NullPointerException success) {}
     }
 
     /**
      * Add of comparable element succeeds
      */
     public void testAdd() {
-        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
         assertTrue(q.add(zero));
         assertTrue(q.add(one));
     }
@@ -188,7 +181,7 @@ public class ConcurrentSkipListSetTest e
      * Add of duplicate element fails
      */
     public void testAddDup() {
-        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
         assertTrue(q.add(zero));
         assertFalse(q.add(zero));
     }
@@ -197,120 +190,122 @@ public class ConcurrentSkipListSetTest e
      * Add of non-Comparable throws CCE
      */
     public void testAddNonComparable() {
+        ConcurrentSkipListSet<Object> q = new ConcurrentSkipListSet<Object>();
         try {
-            ConcurrentSkipListSet q = new ConcurrentSkipListSet();
-            q.add(new Object());
             q.add(new Object());
             q.add(new Object());
             shouldThrow();
+        } catch (ClassCastException success) {
+            assertTrue(q.size() < 2);
+            for (int i = 0, size = q.size(); i < size; i++)
+                assertSame(Object.class, q.pollFirst().getClass());
+            assertNull(q.pollFirst());
+            assertTrue(q.isEmpty());
+            mustEqual(0, q.size());
         }
-        catch(ClassCastException success) {}
     }
 
     /**
      * addAll(null) throws NPE
      */
     public void testAddAll1() {
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
         try {
-            ConcurrentSkipListSet q = new ConcurrentSkipListSet();
             q.addAll(null);
             shouldThrow();
-        }
-        catch (NullPointerException success) {}
+        } catch (NullPointerException success) {}
     }
+
     /**
      * addAll of a collection with null elements throws NPE
      */
     public void testAddAll2() {
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
+        Item[] items = new Item[SIZE];
         try {
-            ConcurrentSkipListSet q = new ConcurrentSkipListSet();
-            Integer[] ints = new Integer[SIZE];
-            q.addAll(Arrays.asList(ints));
+            q.addAll(Arrays.asList(items));
             shouldThrow();
-        }
-        catch (NullPointerException success) {}
+        } catch (NullPointerException success) {}
     }
+
     /**
      * addAll of a collection with any null elements throws NPE after
      * possibly adding some elements
      */
     public void testAddAll3() {
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
+        Item[] items = new Item[2]; items[0] = zero;
         try {
-            ConcurrentSkipListSet q = new ConcurrentSkipListSet();
-            Integer[] ints = new Integer[SIZE];
-            for (int i = 0; i < SIZE-1; ++i)
-                ints[i] = new Integer(i);
-            q.addAll(Arrays.asList(ints));
+            q.addAll(Arrays.asList(items));
             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 {}
+        Item[] empty = new Item[0];
+        Item[] items = defaultItems;
+        ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
+        assertFalse(q.addAll(Arrays.asList(empty)));
+        assertTrue(q.addAll(Arrays.asList(items)));
+        for (int i = 0; i < SIZE; ++i)
+            mustEqual(i, q.pollFirst());
     }
 
     /**
      * pollFirst succeeds unless empty
      */
     public void testPollFirst() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.pollFirst()).intValue());
+            mustEqual(i, q.pollFirst());
         }
-	assertNull(q.pollFirst());
+        assertNull(q.pollFirst());
     }
 
     /**
      * pollLast succeeds unless empty
      */
     public void testPollLast() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
-        for (int i = SIZE-1; i >= 0; --i) {
-            assertEquals(i, ((Integer)q.pollLast()).intValue());
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
+        for (int i = SIZE - 1; i >= 0; --i) {
+            mustEqual(i, q.pollLast());
         }
-	assertNull(q.pollFirst());
+        assertNull(q.pollFirst());
     }
 
-
     /**
      * remove(x) removes x and returns true if present
      */
     public void testRemoveElement() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
-        for (int i = 1; i < SIZE; i+=2) {
-            assertTrue(q.remove(new Integer(i)));
-        }
-        for (int i = 0; i < SIZE; i+=2) {
-            assertTrue(q.remove(new Integer(i)));
-            assertFalse(q.remove(new Integer(i+1)));
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
+        for (int i = 1; i < SIZE; i += 2) {
+            mustContain(q, i);
+            mustRemove(q, i);
+            mustNotContain(q, i);
+            mustContain(q, i - 1);
+        }
+        for (int i = 0; i < SIZE; i += 2) {
+            mustContain(q, i);
+            mustRemove(q, i);
+            mustNotContain(q, i);
+            mustNotRemove(q, i + 1);
+            mustNotContain(q, i + 1);
         }
         assertTrue(q.isEmpty());
     }
-	
+
     /**
      * contains(x) reports true when elements added but not yet removed
      */
     public void testContains() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertTrue(q.contains(new Integer(i)));
+            mustContain(q, i);
             q.pollFirst();
-            assertFalse(q.contains(new Integer(i)));
+            mustNotContain(q, i);
         }
     }
 
@@ -318,11 +313,11 @@ public class ConcurrentSkipListSetTest e
      * clear removes all elements
      */
     public void testClear() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
         q.clear();
         assertTrue(q.isEmpty());
-        assertEquals(0, q.size());
-        q.add(new Integer(1));
+        mustEqual(0, q.size());
+        mustAdd(q, one);
         assertFalse(q.isEmpty());
         q.clear();
         assertTrue(q.isEmpty());
@@ -332,12 +327,12 @@ public class ConcurrentSkipListSetTest e
      * containsAll(c) is true when c contains a subset of elements
      */
     public void testContainsAll() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
-        ConcurrentSkipListSet p = new ConcurrentSkipListSet();
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
+        ConcurrentSkipListSet<Item> p = new ConcurrentSkipListSet<Item>();
         for (int i = 0; i < SIZE; ++i) {
             assertTrue(q.containsAll(p));
             assertFalse(p.containsAll(q));
-            p.add(new Integer(i));
+            mustAdd(p, i);
         }
         assertTrue(p.containsAll(q));
     }
@@ -346,8 +341,8 @@ public class ConcurrentSkipListSetTest e
      * retainAll(c) retains only those elements of c and reports true if changed
      */
     public void testRetainAll() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
-        ConcurrentSkipListSet p = populatedSet(SIZE);
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
+        ConcurrentSkipListSet<Item> p = populatedSet(SIZE);
         for (int i = 0; i < SIZE; ++i) {
             boolean changed = q.retainAll(p);
             if (i == 0)
@@ -356,7 +351,7 @@ public class ConcurrentSkipListSetTest e
                 assertTrue(changed);
 
             assertTrue(q.containsAll(p));
-            assertEquals(SIZE-i, q.size());
+            mustEqual(SIZE - i, q.size());
             p.pollFirst();
         }
     }
@@ -366,317 +361,639 @@ public class ConcurrentSkipListSetTest e
      */
     public void testRemoveAll() {
         for (int i = 1; i < SIZE; ++i) {
-            ConcurrentSkipListSet q = populatedSet(SIZE);
-            ConcurrentSkipListSet p = populatedSet(i);
+            ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
+            ConcurrentSkipListSet<Item> p = populatedSet(i);
             assertTrue(q.removeAll(p));
-            assertEquals(SIZE-i, q.size());
+            mustEqual(SIZE - i, q.size());
             for (int j = 0; j < i; ++j) {
-                Integer I = (Integer)(p.pollFirst());
-                assertFalse(q.contains(I));
+                mustNotContain(q, p.pollFirst());
             }
         }
     }
 
-    
-
     /**
      * lower returns preceding element
      */
     public void testLower() {
-        ConcurrentSkipListSet q = set5();
+        ConcurrentSkipListSet<Item> q = set5();
         Object e1 = q.lower(three);
-        assertEquals(two, e1);
+        mustEqual(two, e1);
 
         Object e2 = q.lower(six);
-        assertEquals(five, e2);
+        mustEqual(five, e2);
 
         Object e3 = q.lower(one);
         assertNull(e3);
 
         Object e4 = q.lower(zero);
         assertNull(e4);
-
     }
 
     /**
      * higher returns next element
      */
     public void testHigher() {
-        ConcurrentSkipListSet q = set5();
+        ConcurrentSkipListSet<Item> q = set5();
         Object e1 = q.higher(three);
-        assertEquals(four, e1);
+        mustEqual(four, e1);
 
         Object e2 = q.higher(zero);
-        assertEquals(one, e2);
+        mustEqual(one, e2);
 
         Object e3 = q.higher(five);
         assertNull(e3);
 
         Object e4 = q.higher(six);
         assertNull(e4);
-
     }
 
     /**
      * floor returns preceding element
      */
     public void testFloor() {
-        ConcurrentSkipListSet q = set5();
+        ConcurrentSkipListSet<Item> q = set5();
         Object e1 = q.floor(three);
-        assertEquals(three, e1);
+        mustEqual(three, e1);
 
         Object e2 = q.floor(six);
-        assertEquals(five, e2);
+        mustEqual(five, e2);
 
         Object e3 = q.floor(one);
-        assertEquals(one, e3);
+        mustEqual(one, e3);
 
         Object e4 = q.floor(zero);
         assertNull(e4);
-
     }
 
     /**
      * ceiling returns next element
      */
     public void testCeiling() {
-        ConcurrentSkipListSet q = set5();
+        ConcurrentSkipListSet<Item> q = set5();
         Object e1 = q.ceiling(three);
-        assertEquals(three, e1);
+        mustEqual(three, e1);
 
         Object e2 = q.ceiling(zero);
-        assertEquals(one, e2);
+        mustEqual(one, e2);
 
         Object e3 = q.ceiling(five);
-        assertEquals(five, e3);
+        mustEqual(five, e3);
 
         Object e4 = q.ceiling(six);
         assertNull(e4);
-
     }
 
     /**
-     * toArray contains all elements
+     * toArray contains all elements in sorted order
      */
     public void testToArray() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
-	Object[] o = q.toArray();
-        Arrays.sort(o);
-	for(int i = 0; i < o.length; i++)
-	    assertEquals(o[i], q.pollFirst());
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
+        Object[] a = q.toArray();
+        assertSame(Object[].class, a.getClass());
+        for (Object o : a)
+            assertSame(o, q.pollFirst());
+        assertTrue(q.isEmpty());
     }
 
     /**
-     * toArray(a) contains all elements
+     * toArray(a) contains all elements in sorted order
      */
     public void testToArray2() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
-	Integer[] ints = new Integer[SIZE];
-	ints = (Integer[])q.toArray(ints);
-        Arrays.sort(ints);
-        for(int i = 0; i < ints.length; i++)
-            assertEquals(ints[i], q.pollFirst());
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
+        Item[] items = new Item[SIZE];
+        assertSame(items, q.toArray(items));
+        for (Item o : items)
+            assertSame(o, q.pollFirst());
+        assertTrue(q.isEmpty());
     }
-    
+
     /**
      * iterator iterates through all elements
      */
     public void testIterator() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
-        int i = 0;
-	Iterator it = q.iterator();
-        while(it.hasNext()) {
-            assertTrue(q.contains(it.next()));
-            ++i;
-        }
-        assertEquals(i, SIZE);
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
+        Iterator<? extends Item> it = q.iterator();
+        int i;
+        for (i = 0; it.hasNext(); i++)
+            mustContain(q, it.next());
+        mustEqual(i, SIZE);
+        assertIteratorExhausted(it);
     }
 
     /**
      * iterator of empty set has no elements
      */
     public void testEmptyIterator() {
-        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
-        int i = 0;
-	Iterator it = q.iterator();
-        while(it.hasNext()) {
-            assertTrue(q.contains(it.next()));
-            ++i;
-        }
-        assertEquals(i, 0);
+        NavigableSet<Item> s = new ConcurrentSkipListSet<Item>();
+        assertIteratorExhausted(s.iterator());
+        assertIteratorExhausted(s.descendingSet().iterator());
     }
 
     /**
      * iterator.remove removes current element
      */
-    public void testIteratorRemove () {
-        final ConcurrentSkipListSet q = new ConcurrentSkipListSet();
-        q.add(new Integer(2));
-        q.add(new Integer(1));
-        q.add(new Integer(3));
+    public void testIteratorRemove() {
+        final ConcurrentSkipListSet<Item> q = new ConcurrentSkipListSet<Item>();
+        q.add(two);
+        q.add(one);
+        q.add(three);
 
-        Iterator it = q.iterator();
+        Iterator<? extends Item> it = q.iterator();
         it.next();
         it.remove();
 
         it = q.iterator();
-        assertEquals(it.next(), new Integer(2));
-        assertEquals(it.next(), new Integer(3));
+        mustEqual(it.next(), two);
+        mustEqual(it.next(), three);
         assertFalse(it.hasNext());
     }
 
-
     /**
      * toString contains toStrings of elements
      */
     public void testToString() {
-        ConcurrentSkipListSet q = populatedSet(SIZE);
+        ConcurrentSkipListSet<Item> q = populatedSet(SIZE);
         String s = q.toString();
         for (int i = 0; i < SIZE; ++i) {
-            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
+            assertTrue(s.contains(String.valueOf(i)));
         }
-    }        
+    }
 
     /**
-     * A deserialized serialized set has same elements 
+     * A cloned set equals original
      */
-    public void testSerialization() {
-        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();
+    public void testClone() {
+        ConcurrentSkipListSet<Item> x = populatedSet(SIZE);
+        ConcurrentSkipListSet<Item> y = x.clone();
+
+        assertNotSame(x, y);
+        mustEqual(x.size(), y.size());
+        mustEqual(x, y);
+        mustEqual(y, x);
+        while (!x.isEmpty()) {
+            assertFalse(y.isEmpty());
+            mustEqual(x.pollFirst(), y.pollFirst());
         }
+        assertTrue(y.isEmpty());
+    }
+
+    /**
+     * A deserialized/reserialized set equals original
+     */
+    public void testSerialization() throws Exception {
+        NavigableSet<Item> x = populatedSet(SIZE);
+        NavigableSet<Item> y = serialClone(x);
+
+        assertNotSame(x, y);
+        mustEqual(x.size(), y.size());
+        mustEqual(x, y);
+        mustEqual(y, x);
+        while (!x.isEmpty()) {
+            assertFalse(y.isEmpty());
+            mustEqual(x.pollFirst(), y.pollFirst());
+        }
+        assertTrue(y.isEmpty());
     }
 
     /**
      * subSet returns set with keys in requested range
      */
     public void testSubSetContents() {
-        ConcurrentSkipListSet set = set5();
-        SortedSet sm = set.subSet(two, four);
-        assertEquals(two, sm.first());
-        assertEquals(three, sm.last());
-        assertEquals(2, sm.size());
-        assertFalse(sm.contains(one));
-        assertTrue(sm.contains(two));
-        assertTrue(sm.contains(three));
-        assertFalse(sm.contains(four));
-        assertFalse(sm.contains(five));
-        Iterator i = sm.iterator();
-        Object k;
-        k = (Integer)(i.next());
-        assertEquals(two, k);
-        k = (Integer)(i.next());
-        assertEquals(three, k);
+        ConcurrentSkipListSet<Item> set = set5();
+        SortedSet<Item> sm = set.subSet(two, four);
+        mustEqual(two, sm.first());
+        mustEqual(three, sm.last());
+        mustEqual(2, sm.size());
+        mustNotContain(sm, one);
+        mustContain(sm, two);
+        mustContain(sm, three);
+        mustNotContain(sm, four);
+        mustNotContain(sm, five);
+        Iterator<? extends Item> i = sm.iterator();
+        Item k = i.next();
+        mustEqual(two, k);
+        k = i.next();
+        mustEqual(three, k);
         assertFalse(i.hasNext());
-        Iterator j = sm.iterator();
+        Iterator<? extends Item> j = sm.iterator();
         j.next();
         j.remove();
-        assertFalse(set.contains(two));
-        assertEquals(4, set.size());
-        assertEquals(1, sm.size());
-        assertEquals(three, sm.first());
-        assertEquals(three, sm.last());
-        assertTrue(sm.remove(three));
+        mustNotContain(set, two);
+        mustEqual(4, set.size());
+        mustEqual(1, sm.size());
+        mustEqual(three, sm.first());
+        mustEqual(three, sm.last());
+        mustRemove(sm, three);
         assertTrue(sm.isEmpty());
-        assertEquals(3, set.size());
+        mustEqual(3, set.size());
     }
 
     public void testSubSetContents2() {
-        ConcurrentSkipListSet set = set5();
-        SortedSet sm = set.subSet(two, three);
-        assertEquals(1, sm.size());
-        assertEquals(two, sm.first());
-        assertEquals(two, sm.last());
-        assertFalse(sm.contains(one));
-        assertTrue(sm.contains(two));
-        assertFalse(sm.contains(three));
-        assertFalse(sm.contains(four));
-        assertFalse(sm.contains(five));
-        Iterator i = sm.iterator();
-        Object k;
-        k = (Integer)(i.next());
-        assertEquals(two, k);
+        ConcurrentSkipListSet<Item> set = set5();
+        SortedSet<Item> sm = set.subSet(two, three);
+        mustEqual(1, sm.size());
+        mustEqual(two, sm.first());
+        mustEqual(two, sm.last());
+        mustNotContain(sm, one);
+        mustContain(sm, two);
+        mustNotContain(sm, three);
+        mustNotContain(sm, four);
+        mustNotContain(sm, five);
+        Iterator<? extends Item> i = sm.iterator();
+        Item k = i.next();
+        mustEqual(two, k);
         assertFalse(i.hasNext());
-        Iterator j = sm.iterator();
+        Iterator<? extends Item> j = sm.iterator();
         j.next();
         j.remove();
-        assertFalse(set.contains(two));
-        assertEquals(4, set.size());
-        assertEquals(0, sm.size());
+        mustNotContain(set, two);
+        mustEqual(4, set.size());
+        mustEqual(0, sm.size());
         assertTrue(sm.isEmpty());
-        assertFalse(sm.remove(three));
-        assertEquals(4, set.size());
+        mustNotRemove(sm, three);
+        mustEqual(4, set.size());
     }
 
     /**
      * headSet returns set with keys in requested range
      */
     public void testHeadSetContents() {
-        ConcurrentSkipListSet set = set5();
-        SortedSet sm = set.headSet(four);
-        assertTrue(sm.contains(one));
-        assertTrue(sm.contains(two));
-        assertTrue(sm.contains(three));
-        assertFalse(sm.contains(four));
-        assertFalse(sm.contains(five));
-        Iterator i = sm.iterator();
-        Object k;
-        k = (Integer)(i.next());
-        assertEquals(one, k);
-        k = (Integer)(i.next());
-        assertEquals(two, k);
-        k = (Integer)(i.next());
-        assertEquals(three, k);
+        ConcurrentSkipListSet<Item> set = set5();
+        SortedSet<Item> sm = set.headSet(four);
+        mustContain(sm, one);
+        mustContain(sm, two);
+        mustContain(sm, three);
+        mustNotContain(sm, four);
+        mustNotContain(sm, five);
+        Iterator<? extends Item> i = sm.iterator();
+        Item k = i.next();
+        mustEqual(one, k);
+        k = i.next();
+        mustEqual(two, k);
+        k = i.next();
+        mustEqual(three, k);
         assertFalse(i.hasNext());
         sm.clear();
         assertTrue(sm.isEmpty());
-        assertEquals(2, set.size());
-        assertEquals(four, set.first());
+        mustEqual(2, set.size());
+        mustEqual(four, set.first());
     }
 
     /**
      * tailSet returns set with keys in requested range
      */
     public void testTailSetContents() {
-        ConcurrentSkipListSet set = set5();
-        SortedSet sm = set.tailSet(two);
-        assertFalse(sm.contains(one));
-        assertTrue(sm.contains(two));
-        assertTrue(sm.contains(three));
-        assertTrue(sm.contains(four));
-        assertTrue(sm.contains(five));
-        Iterator i = sm.iterator();
-        Object k;
-        k = (Integer)(i.next());
-        assertEquals(two, k);
-        k = (Integer)(i.next());
-        assertEquals(three, k);
-        k = (Integer)(i.next());
-        assertEquals(four, k);
-        k = (Integer)(i.next());
-        assertEquals(five, k);
+        ConcurrentSkipListSet<Item> set = set5();
+        SortedSet<Item> sm = set.tailSet(two);
+        mustNotContain(sm, one);
+        mustContain(sm, two);
+        mustContain(sm, three);
+        mustContain(sm, four);
+        mustContain(sm, five);
+        mustContain(sm, two);
+        Iterator<? extends Item> i = sm.iterator();
+        Item k = i.next();
+        mustEqual(two, k);
+        k = i.next();
+        mustEqual(three, k);
+        k = i.next();
+        mustEqual(four, k);
+        k = i.next();
+        mustEqual(five, k);
         assertFalse(i.hasNext());
 
-        SortedSet ssm = sm.tailSet(four);
-        assertEquals(four, ssm.first());
-        assertEquals(five, ssm.last());
-        assertTrue(ssm.remove(four));
-        assertEquals(1, ssm.size());
-        assertEquals(3, sm.size());
-        assertEquals(4, set.size());
+        SortedSet<Item> ssm = sm.tailSet(four);
+        mustEqual(four, ssm.first());
+        mustEqual(five, ssm.last());
+        mustRemove(ssm, four);
+        mustEqual(1, ssm.size());
+        mustEqual(3, sm.size());
+        mustEqual(4, set.size());
+    }
+
+    Random rnd = new Random(666);
+
+    /**
+     * Subsets of subsets subdivide correctly
+     */
+    public void testRecursiveSubSets() throws Exception {
+        int setSize = expensiveTests ? 1000 : 100;
+        Class<?> cl = ConcurrentSkipListSet.class;
+
+        NavigableSet<Item> set = newSet(cl);
+        BitSet bs = new BitSet(setSize);
+
+        populate(set, setSize, bs);
+        check(set,                 0, setSize - 1, true, bs);
+        check(set.descendingSet(), 0, setSize - 1, false, bs);
+
+        mutateSet(set, 0, setSize - 1, bs);
+        check(set,                 0, setSize - 1, true, bs);
+        check(set.descendingSet(), 0, setSize - 1, false, bs);
+
+        bashSubSet(set.subSet(zero, true, itemFor(setSize), false),
+                   0, setSize - 1, true, bs);
+    }
+
+    /**
+     * addAll is idempotent
+     */
+    public void testAddAll_idempotent() throws Exception {
+        Set<Item> x = populatedSet(SIZE);
+        Set<Item> y = new ConcurrentSkipListSet<Item>(x);
+        y.addAll(x);
+        mustEqual(x, y);
+        mustEqual(y, x);
+    }
+
+    static NavigableSet<Item> newSet(Class<?> cl) throws Exception {
+        @SuppressWarnings("unchecked")
+        NavigableSet<Item> result =
+            (NavigableSet<Item>) cl.getConstructor().newInstance();
+        mustEqual(0, result.size());
+        assertFalse(result.iterator().hasNext());
+        return result;
+    }
+
+    void populate(NavigableSet<Item> set, int limit, BitSet bs) {
+        for (int i = 0, n = 2 * limit / 3; i < n; i++) {
+            int element = rnd.nextInt(limit);
+            put(set, element, bs);
+        }
+    }
+
+    void mutateSet(NavigableSet<Item> set, int min, int max, BitSet bs) {
+        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), bs);
+        }
+
+        // Remove a bunch of entries with iterator
+        for (Iterator<Item> it = set.iterator(); it.hasNext(); ) {
+            if (rnd.nextBoolean()) {
+                bs.clear(it.next().value);
+                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, bs);
+        }
+    }
+
+    void mutateSubSet(NavigableSet<Item> set, int min, int max,
+                      BitSet bs) {
+        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), bs);
+        }
+
+        // Remove a bunch of entries with iterator
+        for (Iterator<Item> it = set.iterator(); it.hasNext(); ) {
+            if (rnd.nextBoolean()) {
+                bs.clear(it.next().value);
+                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, bs);
+            } else {
+                try {
+                    set.add(itemFor(element));
+                    shouldThrow();
+                } catch (IllegalArgumentException success) {}
+            }
+        }
+    }
+
+    void put(NavigableSet<Item> set, int element, BitSet bs) {
+        if (set.add(itemFor(element)))
+            bs.set(element);
+    }
+
+    void remove(NavigableSet<Item> set, int element, BitSet bs) {
+        if (set.remove(itemFor(element)))
+            bs.clear(element);
+    }
+
+    void bashSubSet(NavigableSet<Item> set,
+                    int min, int max, boolean ascending,
+                    BitSet bs) {
+        check(set, min, max, ascending, bs);
+        check(set.descendingSet(), min, max, !ascending, bs);
+
+        mutateSubSet(set, min, max, bs);
+        check(set, min, max, ascending, bs);
+        check(set.descendingSet(), min, max, !ascending, bs);
+
+        // Recurse
+        if (max - min < 2)
+            return;
+        int midPoint = (min + max) / 2;
+
+        // headSet - pick direction and endpoint inclusion randomly
+        boolean incl = rnd.nextBoolean();
+        NavigableSet<Item> hm = set.headSet(itemFor(midPoint), incl);
+        if (ascending) {
+            if (rnd.nextBoolean())
+                bashSubSet(hm, min, midPoint - (incl ? 0 : 1), true, bs);
+            else
+                bashSubSet(hm.descendingSet(), min, midPoint - (incl ? 0 : 1),
+                           false, bs);
+        } else {
+            if (rnd.nextBoolean())
+                bashSubSet(hm, midPoint + (incl ? 0 : 1), max, false, bs);
+            else
+                bashSubSet(hm.descendingSet(), midPoint + (incl ? 0 : 1), max,
+                           true, bs);
+        }
+
+        // tailSet - pick direction and endpoint inclusion randomly
+        incl = rnd.nextBoolean();
+        NavigableSet<Item> tm = set.tailSet(itemFor(midPoint),incl);
+        if (ascending) {
+            if (rnd.nextBoolean())
+                bashSubSet(tm, midPoint + (incl ? 0 : 1), max, true, bs);
+            else
+                bashSubSet(tm.descendingSet(), midPoint + (incl ? 0 : 1), max,
+                           false, bs);
+        } else {
+            if (rnd.nextBoolean()) {
+                bashSubSet(tm, min, midPoint - (incl ? 0 : 1), false, bs);
+            } else {
+                bashSubSet(tm.descendingSet(), min, midPoint - (incl ? 0 : 1),
+                           true, bs);
+            }
+        }
+
+        // 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<Item> sm = set.subSet(
+                itemFor(endpoints[0]), lowIncl, itemFor(endpoints[1]), highIncl);
+            if (rnd.nextBoolean())
+                bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
+                           endpoints[1] - (highIncl ? 0 : 1), true, bs);
+            else
+                bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
+                           endpoints[1] - (highIncl ? 0 : 1), false, bs);
+        } else {
+            NavigableSet<Item> sm = set.subSet(
+                itemFor(endpoints[1]), highIncl, itemFor(endpoints[0]), lowIncl);
+            if (rnd.nextBoolean())
+                bashSubSet(sm, endpoints[0] + (lowIncl ? 0 : 1),
+                           endpoints[1] - (highIncl ? 0 : 1), false, bs);
+            else
+                bashSubSet(sm.descendingSet(), endpoints[0] + (lowIncl ? 0 : 1),
+                           endpoints[1] - (highIncl ? 0 : 1), true, bs);
+        }
+    }
+
+    /**
+     * min and max are both inclusive.  If max < min, interval is empty.
+     */
+    void check(NavigableSet<Item> set,
+               final int min, final int max, final boolean ascending,
+               final BitSet bs) {
+        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);
+            mustEqual(bsContainsI, set.contains(itemFor(i)));
+            if (bsContainsI)
+                size++;
+        }
+        mustEqual(size, set.size());
+
+        // Test contents using contains elementSet iterator
+        int size2 = 0;
+        int previousElement = -1;
+        for (Item element : set) {
+            assertTrue(bs.get(element.value));
+            size2++;
+            assertTrue(previousElement < 0 || (ascending ?
+                element.value - previousElement > 0 : element.value - previousElement < 0));
+            previousElement = element.value;
+        }
+        mustEqual(size2, size);
+
+        // Test navigation ops
+        for (int element = min - 1; element <= max + 1; element++) {
+            Item e = itemFor(element);
+            assertEq(set.lower(e), rs.lower(element));
+            assertEq(set.floor(e), rs.floor(element));
+            assertEq(set.higher(e), rs.higher(element));
+            assertEq(set.ceiling(e), rs.ceiling(element));
+        }
+
+        // Test extrema
+        if (set.size() != 0) {
+            assertEq(set.first(), rs.first());
+            assertEq(set.last(), rs.last());
+        } else {
+            mustEqual(rs.first(), -1);
+            mustEqual(rs.last(),  -1);
+            try {
+                set.first();
+                shouldThrow();
+            } catch (NoSuchElementException success) {}
+            try {
+                set.last();
+                shouldThrow();
+            } catch (NoSuchElementException success) {}
+        }
+    }
+
+    static void assertEq(Item i, int j) {
+        if (i == null)
+            mustEqual(j, -1);
+        else
+            mustEqual(i, j);
+    }
+
+    static boolean eq(Item i, int j) {
+        return (i == null) ? j == -1 : i.value == j;
     }
 
 }