test/tck/ConcurrentSkipListSetTest.java

/*
 * 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
 */

import junit.framework.*;
import java.util.*;
import java.util.concurrent.*;
import java.io.*;

public class ConcurrentSkipListSetTest extends JSR166TestCase {
    public static void main(String[] args) {
        junit.textui.TestRunner.run (suite());  
    }
    public static Test suite() {
        return new TestSuite(ConcurrentSkipListSetTest.class);
    }

    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;
        }
    }

    /**
     * Create a set of given size containing consecutive
     * Integers 0 ... n.
     */
    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)));
        assertFalse(q.isEmpty());
        assertEquals(n, q.size());
        return q;
    }

    /**
     * Create set of first 5 ints
     */
    private ConcurrentSkipListSet set5() {
        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
        assertTrue(q.isEmpty());
        q.add(one);
        q.add(two);
        q.add(three);
        q.add(four);
        q.add(five);
        assertEquals(5, q.size());
        return q;
    }
 
    /**
     * A new set has unbounded capacity
     */
    public void testConstructor1() {
        assertEquals(0, new ConcurrentSkipListSet().size());
    }

    /**
     * Initializing from null Collection throws NPE
     */
    public void testConstructor3() {
        try {
            ConcurrentSkipListSet q = new ConcurrentSkipListSet((Collection)null);
            shouldThrow();
        }
        catch (NullPointerException success) {}
    }

    /**
     * Initializing from Collection of null elements throws NPE
     */
    public void testConstructor4() {
        try {
            Integer[] ints = new Integer[SIZE];
            ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints));
            shouldThrow();
        }
        catch (NullPointerException success) {}
    }

    /**
     * Initializing from Collection with some null elements throws NPE
     */
    public void testConstructor5() {
        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));
            shouldThrow();
        }
        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 {}
    }

    /**
     * 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 {}
    }

    /**
     * isEmpty is true before add, false after
     */
    public void testEmpty() {
        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
        assertTrue(q.isEmpty());
        q.add(new Integer(1));
        assertFalse(q.isEmpty());
        q.add(new Integer(2));
        q.pollFirst();
        q.pollFirst();
        assertTrue(q.isEmpty());
    }

    /**
     * size changes when elements added and removed
     */
    public void testSize() {
        ConcurrentSkipListSet q = populatedSet(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(SIZE-i, q.size());
            q.pollFirst();
        }
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.size());
            q.add(new Integer(i));
        }
    }

    /**
     * add(null) throws NPE
     */
    public void testAddNull() {
        try {
            ConcurrentSkipListSet q = new ConcurrentSkipListSet();
            q.add(null);
            shouldThrow();
        } catch (NullPointerException success) { }   
    }

    /**
     * Add of comparable element succeeds
     */
    public void testAdd() {
        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
        assertTrue(q.add(zero));
        assertTrue(q.add(one));
    }

    /**
     * Add of duplicate element fails
     */
    public void testAddDup() {
        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
        assertTrue(q.add(zero));
        assertFalse(q.add(zero));
    }

    /**
     * Add of non-Comparable throws CCE
     */
    public void testAddNonComparable() {
        try {
            ConcurrentSkipListSet q = new ConcurrentSkipListSet();
            q.add(new Object());
            q.add(new Object());
            q.add(new Object());
            shouldThrow();
        }
        catch(ClassCastException success) {}
    }

    /**
     * addAll(null) throws NPE
     */
    public void testAddAll1() {
        try {
            ConcurrentSkipListSet q = new ConcurrentSkipListSet();
            q.addAll(null);
            shouldThrow();
        }
        catch (NullPointerException success) {}
    }
    /**
     * addAll of a collection with null elements throws NPE
     */
    public void testAddAll2() {
        try {
            ConcurrentSkipListSet q = new ConcurrentSkipListSet();
            Integer[] ints = new Integer[SIZE];
            q.addAll(Arrays.asList(ints));
            shouldThrow();
        }
        catch (NullPointerException success) {}
    }
    /**
     * addAll of a collection with any null elements throws NPE after
     * possibly adding some elements
     */
    public void testAddAll3() {
        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));
            shouldThrow();
        }
        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 {}
    }

    /**
     * pollFirst succeeds unless empty
     */
    public void testPollFirst() {
        ConcurrentSkipListSet q = populatedSet(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.pollFirst()).intValue());
        }
        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());
        }
        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)));
        }
        assertTrue(q.isEmpty());
    }
        
    /**
     * contains(x) reports true when elements added but not yet removed
     */
    public void testContains() {
        ConcurrentSkipListSet q = populatedSet(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertTrue(q.contains(new Integer(i)));
            q.pollFirst();
            assertFalse(q.contains(new Integer(i)));
        }
    }

    /**
     * clear removes all elements
     */
    public void testClear() {
        ConcurrentSkipListSet q = populatedSet(SIZE);
        q.clear();
        assertTrue(q.isEmpty());
        assertEquals(0, q.size());
        q.add(new Integer(1));
        assertFalse(q.isEmpty());
        q.clear();
        assertTrue(q.isEmpty());
    }

    /**
     * containsAll(c) is true when c contains a subset of elements
     */
    public void testContainsAll() {
        ConcurrentSkipListSet q = populatedSet(SIZE);
        ConcurrentSkipListSet p = new ConcurrentSkipListSet();
        for (int i = 0; i < SIZE; ++i) {
            assertTrue(q.containsAll(p));
            assertFalse(p.containsAll(q));
            p.add(new Integer(i));
        }
        assertTrue(p.containsAll(q));
    }

    /**
     * retainAll(c) retains only those elements of c and reports true if changed
     */
    public void testRetainAll() {
        ConcurrentSkipListSet q = populatedSet(SIZE);
        ConcurrentSkipListSet p = populatedSet(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            boolean changed = q.retainAll(p);
            if (i == 0)
                assertFalse(changed);
            else
                assertTrue(changed);

            assertTrue(q.containsAll(p));
            assertEquals(SIZE-i, q.size());
            p.pollFirst();
        }
    }

    /**
     * removeAll(c) removes only those elements of c and reports true if changed
     */
    public void testRemoveAll() {
        for (int i = 1; i < SIZE; ++i) {
            ConcurrentSkipListSet q = populatedSet(SIZE);
            ConcurrentSkipListSet p = populatedSet(i);
            assertTrue(q.removeAll(p));
            assertEquals(SIZE-i, q.size());
            for (int j = 0; j < i; ++j) {
                Integer I = (Integer)(p.pollFirst());
                assertFalse(q.contains(I));
            }
        }
    }

    
    /**
     * lower returns preceding element
     */
    public void testLower() {
        ConcurrentSkipListSet q = set5();
        Object e1 = q.lower(three);
        assertEquals(two, e1);

        Object e2 = q.lower(six);
        assertEquals(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();
        Object e1 = q.higher(three);
        assertEquals(four, e1);

        Object e2 = q.higher(zero);
        assertEquals(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();
        Object e1 = q.floor(three);
        assertEquals(three, e1);

        Object e2 = q.floor(six);
        assertEquals(five, e2);

        Object e3 = q.floor(one);
        assertEquals(one, e3);

        Object e4 = q.floor(zero);
        assertNull(e4);

    }

    /**
     * ceiling returns next element
     */
    public void testCeiling() {
        ConcurrentSkipListSet q = set5();
        Object e1 = q.ceiling(three);
        assertEquals(three, e1);

        Object e2 = q.ceiling(zero);
        assertEquals(one, e2);

        Object e3 = q.ceiling(five);
        assertEquals(five, e3);

        Object e4 = q.ceiling(six);
        assertNull(e4);

    }

    /**
     * toArray contains all elements
     */
    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());
    }

    /**
     * toArray(a) contains all elements
     */
    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());
    }
    
    /**
     * 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);
    }

    /**
     * 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);
    }

    /**
     * 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));

        Iterator it = q.iterator();
        it.next();
        it.remove();

        it = q.iterator();
        assertEquals(it.next(), new Integer(2));
        assertEquals(it.next(), new Integer(3));
        assertFalse(it.hasNext());
    }


    /**
     * toString contains toStrings of elements
     */
    public void testToString() {
        ConcurrentSkipListSet q = populatedSet(SIZE);
        String s = q.toString();
        for (int i = 0; i < SIZE; ++i) {
            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
        }
    }        

    /**
     * A deserialized serialized set has same elements 
     */
    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();
        }
    }

    /**
     * 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);
        assertFalse(i.hasNext());
        Iterator 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));
        assertTrue(sm.isEmpty());
        assertEquals(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);
        assertFalse(i.hasNext());
        Iterator j = sm.iterator();
        j.next();
        j.remove();
        assertFalse(set.contains(two));
        assertEquals(4, set.size());
        assertEquals(0, sm.size());
        assertTrue(sm.isEmpty());
        assertFalse(sm.remove(three));
        assertEquals(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);
        assertFalse(i.hasNext());
        sm.clear();
        assertTrue(sm.isEmpty());
        assertEquals(2, set.size());
        assertEquals(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);
        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());
    }

}
Revision:	1.1
Committed:	Tue Dec 28 16:15:59 2004 UTC (19 years, 4 months ago) by dl
Branch:	MAIN
Log Message:	Integrate tests for jsr166x classes
#	Content
1	/*
2	* Written by Doug Lea with assistance from members of JCP JSR-166
3	* Expert Group and released to the public domain, as explained at
4	* http://creativecommons.org/licenses/publicdomain
5	*/
6
7	import junit.framework.*;
8	import java.util.*;
9	import java.util.concurrent.*;
10	import java.io.*;
11
12	public class ConcurrentSkipListSetTest extends JSR166TestCase {
13	public static void main(String[] args) {
14	junit.textui.TestRunner.run (suite());
15	}
16	public static Test suite() {
17	return new TestSuite(ConcurrentSkipListSetTest.class);
18	}
19
20	static class MyReverseComparator implements Comparator {
21	public int compare(Object x, Object y) {
22	int i = ((Integer)x).intValue();
23	int j = ((Integer)y).intValue();
24	if (i < j) return 1;
25	if (i > j) return -1;
26	return 0;
27	}
28	}
29
30	/**
31	* Create a set of given size containing consecutive
32	* Integers 0 ... n.
33	*/
34	private ConcurrentSkipListSet populatedSet(int n) {
35	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
36	assertTrue(q.isEmpty());
37	for(int i = n-1; i >= 0; i-=2)
38	assertTrue(q.add(new Integer(i)));
39	for(int i = (n & 1); i < n; i+=2)
40	assertTrue(q.add(new Integer(i)));
41	assertFalse(q.isEmpty());
42	assertEquals(n, q.size());
43	return q;
44	}
45
46	/**
47	* Create set of first 5 ints
48	*/
49	private ConcurrentSkipListSet set5() {
50	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
51	assertTrue(q.isEmpty());
52	q.add(one);
53	q.add(two);
54	q.add(three);
55	q.add(four);
56	q.add(five);
57	assertEquals(5, q.size());
58	return q;
59	}
60
61	/**
62	* A new set has unbounded capacity
63	*/
64	public void testConstructor1() {
65	assertEquals(0, new ConcurrentSkipListSet().size());
66	}
67
68	/**
69	* Initializing from null Collection throws NPE
70	*/
71	public void testConstructor3() {
72	try {
73	ConcurrentSkipListSet q = new ConcurrentSkipListSet((Collection)null);
74	shouldThrow();
75	}
76	catch (NullPointerException success) {}
77	}
78
79	/**
80	* Initializing from Collection of null elements throws NPE
81	*/
82	public void testConstructor4() {
83	try {
84	Integer[] ints = new Integer[SIZE];
85	ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints));
86	shouldThrow();
87	}
88	catch (NullPointerException success) {}
89	}
90
91	/**
92	* Initializing from Collection with some null elements throws NPE
93	*/
94	public void testConstructor5() {
95	try {
96	Integer[] ints = new Integer[SIZE];
97	for (int i = 0; i < SIZE-1; ++i)
98	ints[i] = new Integer(i);
99	ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints));
100	shouldThrow();
101	}
102	catch (NullPointerException success) {}
103	}
104
105	/**
106	* Set contains all elements of collection used to initialize
107	*/
108	public void testConstructor6() {
109	try {
110	Integer[] ints = new Integer[SIZE];
111	for (int i = 0; i < SIZE; ++i)
112	ints[i] = new Integer(i);
113	ConcurrentSkipListSet q = new ConcurrentSkipListSet(Arrays.asList(ints));
114	for (int i = 0; i < SIZE; ++i)
115	assertEquals(ints[i], q.pollFirst());
116	}
117	finally {}
118	}
119
120	/**
121	* The comparator used in constructor is used
122	*/
123	public void testConstructor7() {
124	try {
125	MyReverseComparator cmp = new MyReverseComparator();
126	ConcurrentSkipListSet q = new ConcurrentSkipListSet(cmp);
127	assertEquals(cmp, q.comparator());
128	Integer[] ints = new Integer[SIZE];
129	for (int i = 0; i < SIZE; ++i)
130	ints[i] = new Integer(i);
131	q.addAll(Arrays.asList(ints));
132	for (int i = SIZE-1; i >= 0; --i)
133	assertEquals(ints[i], q.pollFirst());
134	}
135	finally {}
136	}
137
138	/**
139	* isEmpty is true before add, false after
140	*/
141	public void testEmpty() {
142	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
143	assertTrue(q.isEmpty());
144	q.add(new Integer(1));
145	assertFalse(q.isEmpty());
146	q.add(new Integer(2));
147	q.pollFirst();
148	q.pollFirst();
149	assertTrue(q.isEmpty());
150	}
151
152	/**
153	* size changes when elements added and removed
154	*/
155	public void testSize() {
156	ConcurrentSkipListSet q = populatedSet(SIZE);
157	for (int i = 0; i < SIZE; ++i) {
158	assertEquals(SIZE-i, q.size());
159	q.pollFirst();
160	}
161	for (int i = 0; i < SIZE; ++i) {
162	assertEquals(i, q.size());
163	q.add(new Integer(i));
164	}
165	}
166
167	/**
168	* add(null) throws NPE
169	*/
170	public void testAddNull() {
171	try {
172	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
173	q.add(null);
174	shouldThrow();
175	} catch (NullPointerException success) { }
176	}
177
178	/**
179	* Add of comparable element succeeds
180	*/
181	public void testAdd() {
182	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
183	assertTrue(q.add(zero));
184	assertTrue(q.add(one));
185	}
186
187	/**
188	* Add of duplicate element fails
189	*/
190	public void testAddDup() {
191	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
192	assertTrue(q.add(zero));
193	assertFalse(q.add(zero));
194	}
195
196	/**
197	* Add of non-Comparable throws CCE
198	*/
199	public void testAddNonComparable() {
200	try {
201	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
202	q.add(new Object());
203	q.add(new Object());
204	q.add(new Object());
205	shouldThrow();
206	}
207	catch(ClassCastException success) {}
208	}
209
210	/**
211	* addAll(null) throws NPE
212	*/
213	public void testAddAll1() {
214	try {
215	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
216	q.addAll(null);
217	shouldThrow();
218	}
219	catch (NullPointerException success) {}
220	}
221	/**
222	* addAll of a collection with null elements throws NPE
223	*/
224	public void testAddAll2() {
225	try {
226	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
227	Integer[] ints = new Integer[SIZE];
228	q.addAll(Arrays.asList(ints));
229	shouldThrow();
230	}
231	catch (NullPointerException success) {}
232	}
233	/**
234	* addAll of a collection with any null elements throws NPE after
235	* possibly adding some elements
236	*/
237	public void testAddAll3() {
238	try {
239	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
240	Integer[] ints = new Integer[SIZE];
241	for (int i = 0; i < SIZE-1; ++i)
242	ints[i] = new Integer(i);
243	q.addAll(Arrays.asList(ints));
244	shouldThrow();
245	}
246	catch (NullPointerException success) {}
247	}
248
249	/**
250	* Set contains all elements of successful addAll
251	*/
252	public void testAddAll5() {
253	try {
254	Integer[] empty = new Integer[0];
255	Integer[] ints = new Integer[SIZE];
256	for (int i = 0; i < SIZE; ++i)
257	ints[i] = new Integer(SIZE-1-i);
258	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
259	assertFalse(q.addAll(Arrays.asList(empty)));
260	assertTrue(q.addAll(Arrays.asList(ints)));
261	for (int i = 0; i < SIZE; ++i)
262	assertEquals(new Integer(i), q.pollFirst());
263	}
264	finally {}
265	}
266
267	/**
268	* pollFirst succeeds unless empty
269	*/
270	public void testPollFirst() {
271	ConcurrentSkipListSet q = populatedSet(SIZE);
272	for (int i = 0; i < SIZE; ++i) {
273	assertEquals(i, ((Integer)q.pollFirst()).intValue());
274	}
275	assertNull(q.pollFirst());
276	}
277
278	/**
279	* pollLast succeeds unless empty
280	*/
281	public void testPollLast() {
282	ConcurrentSkipListSet q = populatedSet(SIZE);
283	for (int i = SIZE-1; i >= 0; --i) {
284	assertEquals(i, ((Integer)q.pollLast()).intValue());
285	}
286	assertNull(q.pollFirst());
287	}
288
289
290	/**
291	* remove(x) removes x and returns true if present
292	*/
293	public void testRemoveElement() {
294	ConcurrentSkipListSet q = populatedSet(SIZE);
295	for (int i = 1; i < SIZE; i+=2) {
296	assertTrue(q.remove(new Integer(i)));
297	}
298	for (int i = 0; i < SIZE; i+=2) {
299	assertTrue(q.remove(new Integer(i)));
300	assertFalse(q.remove(new Integer(i+1)));
301	}
302	assertTrue(q.isEmpty());
303	}
304
305	/**
306	* contains(x) reports true when elements added but not yet removed
307	*/
308	public void testContains() {
309	ConcurrentSkipListSet q = populatedSet(SIZE);
310	for (int i = 0; i < SIZE; ++i) {
311	assertTrue(q.contains(new Integer(i)));
312	q.pollFirst();
313	assertFalse(q.contains(new Integer(i)));
314	}
315	}
316
317	/**
318	* clear removes all elements
319	*/
320	public void testClear() {
321	ConcurrentSkipListSet q = populatedSet(SIZE);
322	q.clear();
323	assertTrue(q.isEmpty());
324	assertEquals(0, q.size());
325	q.add(new Integer(1));
326	assertFalse(q.isEmpty());
327	q.clear();
328	assertTrue(q.isEmpty());
329	}
330
331	/**
332	* containsAll(c) is true when c contains a subset of elements
333	*/
334	public void testContainsAll() {
335	ConcurrentSkipListSet q = populatedSet(SIZE);
336	ConcurrentSkipListSet p = new ConcurrentSkipListSet();
337	for (int i = 0; i < SIZE; ++i) {
338	assertTrue(q.containsAll(p));
339	assertFalse(p.containsAll(q));
340	p.add(new Integer(i));
341	}
342	assertTrue(p.containsAll(q));
343	}
344
345	/**
346	* retainAll(c) retains only those elements of c and reports true if changed
347	*/
348	public void testRetainAll() {
349	ConcurrentSkipListSet q = populatedSet(SIZE);
350	ConcurrentSkipListSet p = populatedSet(SIZE);
351	for (int i = 0; i < SIZE; ++i) {
352	boolean changed = q.retainAll(p);
353	if (i == 0)
354	assertFalse(changed);
355	else
356	assertTrue(changed);
357
358	assertTrue(q.containsAll(p));
359	assertEquals(SIZE-i, q.size());
360	p.pollFirst();
361	}
362	}
363
364	/**
365	* removeAll(c) removes only those elements of c and reports true if changed
366	*/
367	public void testRemoveAll() {
368	for (int i = 1; i < SIZE; ++i) {
369	ConcurrentSkipListSet q = populatedSet(SIZE);
370	ConcurrentSkipListSet p = populatedSet(i);
371	assertTrue(q.removeAll(p));
372	assertEquals(SIZE-i, q.size());
373	for (int j = 0; j < i; ++j) {
374	Integer I = (Integer)(p.pollFirst());
375	assertFalse(q.contains(I));
376	}
377	}
378	}
379
380
381
382	/**
383	* lower returns preceding element
384	*/
385	public void testLower() {
386	ConcurrentSkipListSet q = set5();
387	Object e1 = q.lower(three);
388	assertEquals(two, e1);
389
390	Object e2 = q.lower(six);
391	assertEquals(five, e2);
392
393	Object e3 = q.lower(one);
394	assertNull(e3);
395
396	Object e4 = q.lower(zero);
397	assertNull(e4);
398
399	}
400
401	/**
402	* higher returns next element
403	*/
404	public void testHigher() {
405	ConcurrentSkipListSet q = set5();
406	Object e1 = q.higher(three);
407	assertEquals(four, e1);
408
409	Object e2 = q.higher(zero);
410	assertEquals(one, e2);
411
412	Object e3 = q.higher(five);
413	assertNull(e3);
414
415	Object e4 = q.higher(six);
416	assertNull(e4);
417
418	}
419
420	/**
421	* floor returns preceding element
422	*/
423	public void testFloor() {
424	ConcurrentSkipListSet q = set5();
425	Object e1 = q.floor(three);
426	assertEquals(three, e1);
427
428	Object e2 = q.floor(six);
429	assertEquals(five, e2);
430
431	Object e3 = q.floor(one);
432	assertEquals(one, e3);
433
434	Object e4 = q.floor(zero);
435	assertNull(e4);
436
437	}
438
439	/**
440	* ceiling returns next element
441	*/
442	public void testCeiling() {
443	ConcurrentSkipListSet q = set5();
444	Object e1 = q.ceiling(three);
445	assertEquals(three, e1);
446
447	Object e2 = q.ceiling(zero);
448	assertEquals(one, e2);
449
450	Object e3 = q.ceiling(five);
451	assertEquals(five, e3);
452
453	Object e4 = q.ceiling(six);
454	assertNull(e4);
455
456	}
457
458	/**
459	* toArray contains all elements
460	*/
461	public void testToArray() {
462	ConcurrentSkipListSet q = populatedSet(SIZE);
463	Object[] o = q.toArray();
464	Arrays.sort(o);
465	for(int i = 0; i < o.length; i++)
466	assertEquals(o[i], q.pollFirst());
467	}
468
469	/**
470	* toArray(a) contains all elements
471	*/
472	public void testToArray2() {
473	ConcurrentSkipListSet q = populatedSet(SIZE);
474	Integer[] ints = new Integer[SIZE];
475	ints = (Integer[])q.toArray(ints);
476	Arrays.sort(ints);
477	for(int i = 0; i < ints.length; i++)
478	assertEquals(ints[i], q.pollFirst());
479	}
480
481	/**
482	* iterator iterates through all elements
483	*/
484	public void testIterator() {
485	ConcurrentSkipListSet q = populatedSet(SIZE);
486	int i = 0;
487	Iterator it = q.iterator();
488	while(it.hasNext()) {
489	assertTrue(q.contains(it.next()));
490	++i;
491	}
492	assertEquals(i, SIZE);
493	}
494
495	/**
496	* iterator of empty set has no elements
497	*/
498	public void testEmptyIterator() {
499	ConcurrentSkipListSet q = new ConcurrentSkipListSet();
500	int i = 0;
501	Iterator it = q.iterator();
502	while(it.hasNext()) {
503	assertTrue(q.contains(it.next()));
504	++i;
505	}
506	assertEquals(i, 0);
507	}
508
509	/**
510	* iterator.remove removes current element
511	*/
512	public void testIteratorRemove () {
513	final ConcurrentSkipListSet q = new ConcurrentSkipListSet();
514	q.add(new Integer(2));
515	q.add(new Integer(1));
516	q.add(new Integer(3));
517
518	Iterator it = q.iterator();
519	it.next();
520	it.remove();
521
522	it = q.iterator();
523	assertEquals(it.next(), new Integer(2));
524	assertEquals(it.next(), new Integer(3));
525	assertFalse(it.hasNext());
526	}
527
528
529	/**
530	* toString contains toStrings of elements
531	*/
532	public void testToString() {
533	ConcurrentSkipListSet q = populatedSet(SIZE);
534	String s = q.toString();
535	for (int i = 0; i < SIZE; ++i) {
536	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
537	}
538	}
539
540	/**
541	* A deserialized serialized set has same elements
542	*/
543	public void testSerialization() {
544	ConcurrentSkipListSet q = populatedSet(SIZE);
545	try {
546	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
547	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
548	out.writeObject(q);
549	out.close();
550
551	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
552	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
553	ConcurrentSkipListSet r = (ConcurrentSkipListSet)in.readObject();
554	assertEquals(q.size(), r.size());
555	while (!q.isEmpty())
556	assertEquals(q.pollFirst(), r.pollFirst());
557	} catch(Exception e){
558	e.printStackTrace();
559	unexpectedException();
560	}
561	}
562
563	/**
564	* subSet returns set with keys in requested range
565	*/
566	public void testSubSetContents() {
567	ConcurrentSkipListSet set = set5();
568	SortedSet sm = set.subSet(two, four);
569	assertEquals(two, sm.first());
570	assertEquals(three, sm.last());
571	assertEquals(2, sm.size());
572	assertFalse(sm.contains(one));
573	assertTrue(sm.contains(two));
574	assertTrue(sm.contains(three));
575	assertFalse(sm.contains(four));
576	assertFalse(sm.contains(five));
577	Iterator i = sm.iterator();
578	Object k;
579	k = (Integer)(i.next());
580	assertEquals(two, k);
581	k = (Integer)(i.next());
582	assertEquals(three, k);
583	assertFalse(i.hasNext());
584	Iterator j = sm.iterator();
585	j.next();
586	j.remove();
587	assertFalse(set.contains(two));
588	assertEquals(4, set.size());
589	assertEquals(1, sm.size());
590	assertEquals(three, sm.first());
591	assertEquals(three, sm.last());
592	assertTrue(sm.remove(three));
593	assertTrue(sm.isEmpty());
594	assertEquals(3, set.size());
595	}
596
597	public void testSubSetContents2() {
598	ConcurrentSkipListSet set = set5();
599	SortedSet sm = set.subSet(two, three);
600	assertEquals(1, sm.size());
601	assertEquals(two, sm.first());
602	assertEquals(two, sm.last());
603	assertFalse(sm.contains(one));
604	assertTrue(sm.contains(two));
605	assertFalse(sm.contains(three));
606	assertFalse(sm.contains(four));
607	assertFalse(sm.contains(five));
608	Iterator i = sm.iterator();
609	Object k;
610	k = (Integer)(i.next());
611	assertEquals(two, k);
612	assertFalse(i.hasNext());
613	Iterator j = sm.iterator();
614	j.next();
615	j.remove();
616	assertFalse(set.contains(two));
617	assertEquals(4, set.size());
618	assertEquals(0, sm.size());
619	assertTrue(sm.isEmpty());
620	assertFalse(sm.remove(three));
621	assertEquals(4, set.size());
622	}
623
624	/**
625	* headSet returns set with keys in requested range
626	*/
627	public void testHeadSetContents() {
628	ConcurrentSkipListSet set = set5();
629	SortedSet sm = set.headSet(four);
630	assertTrue(sm.contains(one));
631	assertTrue(sm.contains(two));
632	assertTrue(sm.contains(three));
633	assertFalse(sm.contains(four));
634	assertFalse(sm.contains(five));
635	Iterator i = sm.iterator();
636	Object k;
637	k = (Integer)(i.next());
638	assertEquals(one, k);
639	k = (Integer)(i.next());
640	assertEquals(two, k);
641	k = (Integer)(i.next());
642	assertEquals(three, k);
643	assertFalse(i.hasNext());
644	sm.clear();
645	assertTrue(sm.isEmpty());
646	assertEquals(2, set.size());
647	assertEquals(four, set.first());
648	}
649
650	/**
651	* tailSet returns set with keys in requested range
652	*/
653	public void testTailSetContents() {
654	ConcurrentSkipListSet set = set5();
655	SortedSet sm = set.tailSet(two);
656	assertFalse(sm.contains(one));
657	assertTrue(sm.contains(two));
658	assertTrue(sm.contains(three));
659	assertTrue(sm.contains(four));
660	assertTrue(sm.contains(five));
661	Iterator i = sm.iterator();
662	Object k;
663	k = (Integer)(i.next());
664	assertEquals(two, k);
665	k = (Integer)(i.next());
666	assertEquals(three, k);
667	k = (Integer)(i.next());
668	assertEquals(four, k);
669	k = (Integer)(i.next());
670	assertEquals(five, k);
671	assertFalse(i.hasNext());
672
673	SortedSet ssm = sm.tailSet(four);
674	assertEquals(four, ssm.first());
675	assertEquals(five, ssm.last());
676	assertTrue(ssm.remove(four));
677	assertEquals(1, ssm.size());
678	assertEquals(3, sm.size());
679	assertEquals(4, set.size());
680	}
681
682	}