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