test/tck/TreeSetTest.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 TreeSetTest extends JSR166TestCase {
    public static void main(String[] args) {
        junit.textui.TestRunner.run (suite());  
    }
    public static Test suite() {
        return new TestSuite(TreeSetTest.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;
        }
    }

    /**
     * The number of elements to place in collections, arrays, etc.
     */
    static final int SIZE = 20;

    /**
     * Create a set of given size containing consecutive
     * Integers 0 ... n.
     */
    private TreeSet populatedSet(int n) {
        TreeSet q = new TreeSet();
        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 TreeSet set5() {
        TreeSet q = new TreeSet();
        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 TreeSet().size());
    }

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

    /**
     * Initializing from Collection of null elements throws NPE
     */
    public void testConstructor4() {
        try {
            Integer[] ints = new Integer[SIZE];
            TreeSet q = new TreeSet(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);
            TreeSet q = new TreeSet(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);
            TreeSet q = new TreeSet(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();
            TreeSet q = new TreeSet(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() {
        TreeSet q = new TreeSet();
        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() {
        TreeSet 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 if nonempty
     */
    public void testAddNull() {
        try {
            TreeSet q = populatedSet(SIZE);
            q.add(null);
            shouldThrow();
        } catch (NullPointerException success) { }   
    }

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

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

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

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