test/tck/ConcurrentSkipListSubSetTest.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 ConcurrentSkipListSubSetTest extends JSR166TestCase {
    public static void main(String[] args) {
        junit.textui.TestRunner.run (suite());  
    }
    public static Test suite() {
        return new TestSuite(ConcurrentSkipListSubSetTest.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 NavigableSet 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)));
        assertTrue(q.add(new Integer(-n)));
        assertTrue(q.add(new Integer(n)));
        NavigableSet s = q.navigableSubSet(new Integer(0), true, new Integer(n), false);
        assertFalse(s.isEmpty());
        assertEquals(n, s.size());
        return s;
    }

    /**
     * Create set of first 5 ints
     */
    private NavigableSet set5() {
        ConcurrentSkipListSet q = new ConcurrentSkipListSet();
        assertTrue(q.isEmpty());
        q.add(one);
        q.add(two);
        q.add(three);
        q.add(four);
        q.add(five);
        q.add(zero);
        q.add(seven);
        NavigableSet s = q.navigableSubSet(one, true, seven, false);
        assertEquals(5, s.size());
        return s;
    }

    private static NavigableSet set0() {   
        ConcurrentSkipListSet set = new ConcurrentSkipListSet();
        assertTrue(set.isEmpty());
        return set.navigableTailSet(m1, true);
    }
 
    /**
     * A new set has unbounded capacity
     */
    public void testConstructor1() {
        assertEquals(0, set0().size());
    }


    /**
     * isEmpty is true before add, false after
     */
    public void testEmpty() {
        NavigableSet q = set0();
        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() {
        NavigableSet 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 {
            NavigableSet q = set0();
            q.add(null);
            shouldThrow();
        } catch (NullPointerException success) { }   
    }

    /**
     * Add of comparable element succeeds
     */
    public void testAdd() {
        NavigableSet q = set0();
        assertTrue(q.add(six));
    }

    /**
     * Add of duplicate element fails
     */
    public void testAddDup() {
        NavigableSet q = set0();
        assertTrue(q.add(six));
        assertFalse(q.add(six));
    }

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


    /**
     * addAll(null) throws NPE
     */
    public void testAddAll1() {
        try {
            NavigableSet q = set0();
            q.addAll(null);
            shouldThrow();
        }
        catch (NullPointerException success) {}
    }
    /**
     * addAll of a collection with null elements throws NPE
     */
    public void testAddAll2() {
        try {
            NavigableSet q = set0();
            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 {
            NavigableSet q = set0();
            Integer[] ints = new Integer[SIZE];
            for (int i = 0; i < SIZE-1; ++i)
                ints[i] = new Integer(i+SIZE);
            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);
            NavigableSet q = set0();
            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 {}
    }

    /**
     * poll succeeds unless empty
     */
    public void testPoll() {
        NavigableSet q = populatedSet(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.pollFirst()).intValue());
        }
        assertNull(q.pollFirst());
    }

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