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.subSet(new Integer(0), new Integer(n));
        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.subSet(one, seven);
        assertEquals(5, s.size());
        return s;
    }

    private static NavigableSet set0() {   
        ConcurrentSkipListSet set = new ConcurrentSkipListSet();
        assertTrue(set.isEmpty());
        return set.tailSet(m1);
    }
 
    /**
     * 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.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
#	User	Rev	Content
1	dl	1.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.subSet(new Integer(0), new Integer(n));
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.subSet(one, seven);
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.tailSet(m1);
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			}