test/tck/PriorityQueueTest.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
 * Other contributors include Andrew Wright, Jeffrey Hayes, 
 * Pat Fisher, Mike Judd. 
 */

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

public class PriorityQueueTest extends JSR166TestCase {
    public static void main(String[] args) {
        junit.textui.TestRunner.run (suite());  
    }
    public static Test suite() {
        return new TestSuite(PriorityQueueTest.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 queue of given size containing consecutive
     * Integers 0 ... n.
     */
    private PriorityQueue populatedQueue(int n) {
        PriorityQueue q = new PriorityQueue(n);
        assertTrue(q.isEmpty());
        for(int i = n-1; i >= 0; i-=2)
            assertTrue(q.offer(new Integer(i)));
        for(int i = (n & 1); i < n; i+=2)
            assertTrue(q.offer(new Integer(i)));
        assertFalse(q.isEmpty());
        assertEquals(n, q.size());
        return q;
    }
 
    /**
     * A new queue has unbounded capacity
     */
    public void testConstructor1() {
        assertEquals(0, new PriorityQueue(SIZE).size());
    }

    /**
     * Constructor throws IAE if  capacity argument nonpositive
     */
    public void testConstructor2() {
        try {
            PriorityQueue q = new PriorityQueue(0);
            shouldThrow();
        }
        catch (IllegalArgumentException success) {}
    }

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

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

    /**
     * Queue 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);
            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
            for (int i = 0; i < SIZE; ++i)
                assertEquals(ints[i], q.poll());
        }
        finally {}
    }

    /**
     * The comparator used in constructor is used
     */
    public void testConstructor7() {
        try {
            MyReverseComparator cmp = new MyReverseComparator();
            PriorityQueue q = new PriorityQueue(SIZE, 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.poll());
        }
        finally {}
    }

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

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

    /**
     * offer(null) throws NPE
     */
    public void testOfferNull() {
        try {
            PriorityQueue q = new PriorityQueue(1);
            q.offer(null);
            shouldThrow();
        } catch (NullPointerException success) { }   
    }

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

    /**
     * Offer of comparable element succeeds
     */
    public void testOffer() {
        PriorityQueue q = new PriorityQueue(1);
        assertTrue(q.offer(zero));
        assertTrue(q.offer(one));
    }

    /**
     * Offer of non-Comparable throws CCE
     */
    public void testOfferNonComparable() {
        try {
            PriorityQueue q = new PriorityQueue(1);
            q.offer(new Object());
            q.offer(new Object());
            q.offer(new Object());
            shouldThrow();
        }
        catch(ClassCastException success) {}
    }

    /**
     * add of comparable succeeds
     */
    public void testAdd() {
        PriorityQueue q = new PriorityQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.size());
            assertTrue(q.add(new Integer(i)));
        }
    }

    /**
     * addAll(null) throws NPE
     */
    public void testAddAll1() {
        try {
            PriorityQueue q = new PriorityQueue(1);
            q.addAll(null);
            shouldThrow();
        }
        catch (NullPointerException success) {}
    }
    /**
     * addAll of a collection with null elements throws NPE
     */
    public void testAddAll2() {
        try {
            PriorityQueue q = new PriorityQueue(SIZE);
            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 {
            PriorityQueue q = new PriorityQueue(SIZE);
            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) {}
    }

    /**
     * Queue 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);
            PriorityQueue q = new PriorityQueue(SIZE);
            assertFalse(q.addAll(Arrays.asList(empty)));
            assertTrue(q.addAll(Arrays.asList(ints)));
            for (int i = 0; i < SIZE; ++i)
                assertEquals(new Integer(i), q.poll());
        }
        finally {}
    }

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

    /**
     * peek returns next element, or null if empty
     */
    public void testPeek() {
        PriorityQueue q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.peek()).intValue());
            q.poll();
            assertTrue(q.peek() == null ||
                       i != ((Integer)q.peek()).intValue());
        }
        assertNull(q.peek());
    }

    /**
     * element returns next element, or throws NSEE if empty
     */
    public void testElement() {
        PriorityQueue q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.element()).intValue());
            q.poll();
        }
        try {
            q.element();
            shouldThrow();
        }
        catch (NoSuchElementException success) {}
    }

    /**
     * remove removes next element, or throws NSEE if empty
     */
    public void testRemove() {
        PriorityQueue q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.remove()).intValue());
        }
        try {
            q.remove();
            shouldThrow();
        } catch (NoSuchElementException success){
        }   
    }

    /**
     * remove(x) removes x and returns true if present
     */
    public void testRemoveElement() {
        PriorityQueue q = populatedQueue(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() {
        PriorityQueue q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertTrue(q.contains(new Integer(i)));
            q.poll();
            assertFalse(q.contains(new Integer(i)));
        }
    }

    /**
     * clear removes all elements
     */
    public void testClear() {
        PriorityQueue q = populatedQueue(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() {
        PriorityQueue q = populatedQueue(SIZE);
        PriorityQueue p = new PriorityQueue(SIZE);
        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() {
        PriorityQueue q = populatedQueue(SIZE);
        PriorityQueue p = populatedQueue(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.remove();
        }
    }

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

    /**
     * toArray contains all elements
     */
    public void testToArray() {
        PriorityQueue q = populatedQueue(SIZE);
        Object[] o = q.toArray();
        Arrays.sort(o);
        for(int i = 0; i < o.length; i++)
            assertEquals(o[i], q.poll());
    }

    /**
     * toArray(a) contains all elements
     */
    public void testToArray2() {
        PriorityQueue q = populatedQueue(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.poll());
    }
    
    /**
     * iterator iterates through all elements
     */
    public void testIterator() {
        PriorityQueue q = populatedQueue(SIZE);
        int i = 0;
        Iterator it = q.iterator();
        while(it.hasNext()) {
            assertTrue(q.contains(it.next()));
            ++i;
        }
        assertEquals(i, SIZE);
    }

    /**
     * iterator.remove removes current element
     */
    public void testIteratorRemove () {
        final PriorityQueue q = new PriorityQueue(3);
        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() {
        PriorityQueue q = populatedQueue(SIZE);
        String s = q.toString();
        for (int i = 0; i < SIZE; ++i) {
            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
        }
    }        

    /**
     * A deserialized serialized queue has same elements 
     */
    public void testSerialization() {
        PriorityQueue q = populatedQueue(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));
            PriorityQueue r = (PriorityQueue)in.readObject();
            assertEquals(q.size(), r.size());
            while (!q.isEmpty()) 
                assertEquals(q.remove(), r.remove());
        } catch(Exception e){
            unexpectedException();
        }
    }
}
Revision:	1.8
Committed:	Sat Dec 27 19:26:43 2003 UTC (20 years, 4 months ago) by dl
Branch:	MAIN
CVS Tags:	JSR166_PFD
Changes since 1.7:	+5 -4 lines
Log Message:	Headers reference Creative Commons
#	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	* Other contributors include Andrew Wright, Jeffrey Hayes,
6	* Pat Fisher, Mike Judd.
7	*/
8
9	import junit.framework.*;
10	import java.util.*;
11	import java.util.concurrent.*;
12	import java.io.*;
13
14	public class PriorityQueueTest extends JSR166TestCase {
15	public static void main(String[] args) {
16	junit.textui.TestRunner.run (suite());
17	}
18	public static Test suite() {
19	return new TestSuite(PriorityQueueTest.class);
20	}
21
22	static class MyReverseComparator implements Comparator {
23	public int compare(Object x, Object y) {
24	int i = ((Integer)x).intValue();
25	int j = ((Integer)y).intValue();
26	if (i < j) return 1;
27	if (i > j) return -1;
28	return 0;
29	}
30	}
31
32	/**
33	* Create a queue of given size containing consecutive
34	* Integers 0 ... n.
35	*/
36	private PriorityQueue populatedQueue(int n) {
37	PriorityQueue q = new PriorityQueue(n);
38	assertTrue(q.isEmpty());
39	for(int i = n-1; i >= 0; i-=2)
40	assertTrue(q.offer(new Integer(i)));
41	for(int i = (n & 1); i < n; i+=2)
42	assertTrue(q.offer(new Integer(i)));
43	assertFalse(q.isEmpty());
44	assertEquals(n, q.size());
45	return q;
46	}
47
48	/**
49	* A new queue has unbounded capacity
50	*/
51	public void testConstructor1() {
52	assertEquals(0, new PriorityQueue(SIZE).size());
53	}
54
55	/**
56	* Constructor throws IAE if capacity argument nonpositive
57	*/
58	public void testConstructor2() {
59	try {
60	PriorityQueue q = new PriorityQueue(0);
61	shouldThrow();
62	}
63	catch (IllegalArgumentException success) {}
64	}
65
66	/**
67	* Initializing from null Collection throws NPE
68	*/
69	public void testConstructor3() {
70	try {
71	PriorityQueue q = new PriorityQueue((Collection)null);
72	shouldThrow();
73	}
74	catch (NullPointerException success) {}
75	}
76
77	/**
78	* Initializing from Collection of null elements throws NPE
79	*/
80	public void testConstructor4() {
81	try {
82	Integer[] ints = new Integer[SIZE];
83	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
84	shouldThrow();
85	}
86	catch (NullPointerException success) {}
87	}
88
89	/**
90	* Initializing from Collection with some null elements throws NPE
91	*/
92	public void testConstructor5() {
93	try {
94	Integer[] ints = new Integer[SIZE];
95	for (int i = 0; i < SIZE-1; ++i)
96	ints[i] = new Integer(i);
97	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
98	shouldThrow();
99	}
100	catch (NullPointerException success) {}
101	}
102
103	/**
104	* Queue contains all elements of collection used to initialize
105	*/
106	public void testConstructor6() {
107	try {
108	Integer[] ints = new Integer[SIZE];
109	for (int i = 0; i < SIZE; ++i)
110	ints[i] = new Integer(i);
111	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
112	for (int i = 0; i < SIZE; ++i)
113	assertEquals(ints[i], q.poll());
114	}
115	finally {}
116	}
117
118	/**
119	* The comparator used in constructor is used
120	*/
121	public void testConstructor7() {
122	try {
123	MyReverseComparator cmp = new MyReverseComparator();
124	PriorityQueue q = new PriorityQueue(SIZE, cmp);
125	assertEquals(cmp, q.comparator());
126	Integer[] ints = new Integer[SIZE];
127	for (int i = 0; i < SIZE; ++i)
128	ints[i] = new Integer(i);
129	q.addAll(Arrays.asList(ints));
130	for (int i = SIZE-1; i >= 0; --i)
131	assertEquals(ints[i], q.poll());
132	}
133	finally {}
134	}
135
136	/**
137	* isEmpty is true before add, false after
138	*/
139	public void testEmpty() {
140	PriorityQueue q = new PriorityQueue(2);
141	assertTrue(q.isEmpty());
142	q.add(new Integer(1));
143	assertFalse(q.isEmpty());
144	q.add(new Integer(2));
145	q.remove();
146	q.remove();
147	assertTrue(q.isEmpty());
148	}
149
150	/**
151	* size changes when elements added and removed
152	*/
153	public void testSize() {
154	PriorityQueue q = populatedQueue(SIZE);
155	for (int i = 0; i < SIZE; ++i) {
156	assertEquals(SIZE-i, q.size());
157	q.remove();
158	}
159	for (int i = 0; i < SIZE; ++i) {
160	assertEquals(i, q.size());
161	q.add(new Integer(i));
162	}
163	}
164
165	/**
166	* offer(null) throws NPE
167	*/
168	public void testOfferNull() {
169	try {
170	PriorityQueue q = new PriorityQueue(1);
171	q.offer(null);
172	shouldThrow();
173	} catch (NullPointerException success) { }
174	}
175
176	/**
177	* add(null) throws NPE
178	*/
179	public void testAddNull() {
180	try {
181	PriorityQueue q = new PriorityQueue(1);
182	q.add(null);
183	shouldThrow();
184	} catch (NullPointerException success) { }
185	}
186
187	/**
188	* Offer of comparable element succeeds
189	*/
190	public void testOffer() {
191	PriorityQueue q = new PriorityQueue(1);
192	assertTrue(q.offer(zero));
193	assertTrue(q.offer(one));
194	}
195
196	/**
197	* Offer of non-Comparable throws CCE
198	*/
199	public void testOfferNonComparable() {
200	try {
201	PriorityQueue q = new PriorityQueue(1);
202	q.offer(new Object());
203	q.offer(new Object());
204	q.offer(new Object());
205	shouldThrow();
206	}
207	catch(ClassCastException success) {}
208	}
209
210	/**
211	* add of comparable succeeds
212	*/
213	public void testAdd() {
214	PriorityQueue q = new PriorityQueue(SIZE);
215	for (int i = 0; i < SIZE; ++i) {
216	assertEquals(i, q.size());
217	assertTrue(q.add(new Integer(i)));
218	}
219	}
220
221	/**
222	* addAll(null) throws NPE
223	*/
224	public void testAddAll1() {
225	try {
226	PriorityQueue q = new PriorityQueue(1);
227	q.addAll(null);
228	shouldThrow();
229	}
230	catch (NullPointerException success) {}
231	}
232	/**
233	* addAll of a collection with null elements throws NPE
234	*/
235	public void testAddAll2() {
236	try {
237	PriorityQueue q = new PriorityQueue(SIZE);
238	Integer[] ints = new Integer[SIZE];
239	q.addAll(Arrays.asList(ints));
240	shouldThrow();
241	}
242	catch (NullPointerException success) {}
243	}
244	/**
245	* addAll of a collection with any null elements throws NPE after
246	* possibly adding some elements
247	*/
248	public void testAddAll3() {
249	try {
250	PriorityQueue q = new PriorityQueue(SIZE);
251	Integer[] ints = new Integer[SIZE];
252	for (int i = 0; i < SIZE-1; ++i)
253	ints[i] = new Integer(i);
254	q.addAll(Arrays.asList(ints));
255	shouldThrow();
256	}
257	catch (NullPointerException success) {}
258	}
259
260	/**
261	* Queue contains all elements of successful addAll
262	*/
263	public void testAddAll5() {
264	try {
265	Integer[] empty = new Integer[0];
266	Integer[] ints = new Integer[SIZE];
267	for (int i = 0; i < SIZE; ++i)
268	ints[i] = new Integer(SIZE-1-i);
269	PriorityQueue q = new PriorityQueue(SIZE);
270	assertFalse(q.addAll(Arrays.asList(empty)));
271	assertTrue(q.addAll(Arrays.asList(ints)));
272	for (int i = 0; i < SIZE; ++i)
273	assertEquals(new Integer(i), q.poll());
274	}
275	finally {}
276	}
277
278	/**
279	* poll succeeds unless empty
280	*/
281	public void testPoll() {
282	PriorityQueue q = populatedQueue(SIZE);
283	for (int i = 0; i < SIZE; ++i) {
284	assertEquals(i, ((Integer)q.poll()).intValue());
285	}
286	assertNull(q.poll());
287	}
288
289	/**
290	* peek returns next element, or null if empty
291	*/
292	public void testPeek() {
293	PriorityQueue q = populatedQueue(SIZE);
294	for (int i = 0; i < SIZE; ++i) {
295	assertEquals(i, ((Integer)q.peek()).intValue());
296	q.poll();
297	assertTrue(q.peek() == null \|\|
298	i != ((Integer)q.peek()).intValue());
299	}
300	assertNull(q.peek());
301	}
302
303	/**
304	* element returns next element, or throws NSEE if empty
305	*/
306	public void testElement() {
307	PriorityQueue q = populatedQueue(SIZE);
308	for (int i = 0; i < SIZE; ++i) {
309	assertEquals(i, ((Integer)q.element()).intValue());
310	q.poll();
311	}
312	try {
313	q.element();
314	shouldThrow();
315	}
316	catch (NoSuchElementException success) {}
317	}
318
319	/**
320	* remove removes next element, or throws NSEE if empty
321	*/
322	public void testRemove() {
323	PriorityQueue q = populatedQueue(SIZE);
324	for (int i = 0; i < SIZE; ++i) {
325	assertEquals(i, ((Integer)q.remove()).intValue());
326	}
327	try {
328	q.remove();
329	shouldThrow();
330	} catch (NoSuchElementException success){
331	}
332	}
333
334	/**
335	* remove(x) removes x and returns true if present
336	*/
337	public void testRemoveElement() {
338	PriorityQueue q = populatedQueue(SIZE);
339	for (int i = 1; i < SIZE; i+=2) {
340	assertTrue(q.remove(new Integer(i)));
341	}
342	for (int i = 0; i < SIZE; i+=2) {
343	assertTrue(q.remove(new Integer(i)));
344	assertFalse(q.remove(new Integer(i+1)));
345	}
346	assertTrue(q.isEmpty());
347	}
348
349	/**
350	* contains(x) reports true when elements added but not yet removed
351	*/
352	public void testContains() {
353	PriorityQueue q = populatedQueue(SIZE);
354	for (int i = 0; i < SIZE; ++i) {
355	assertTrue(q.contains(new Integer(i)));
356	q.poll();
357	assertFalse(q.contains(new Integer(i)));
358	}
359	}
360
361	/**
362	* clear removes all elements
363	*/
364	public void testClear() {
365	PriorityQueue q = populatedQueue(SIZE);
366	q.clear();
367	assertTrue(q.isEmpty());
368	assertEquals(0, q.size());
369	q.add(new Integer(1));
370	assertFalse(q.isEmpty());
371	q.clear();
372	assertTrue(q.isEmpty());
373	}
374
375	/**
376	* containsAll(c) is true when c contains a subset of elements
377	*/
378	public void testContainsAll() {
379	PriorityQueue q = populatedQueue(SIZE);
380	PriorityQueue p = new PriorityQueue(SIZE);
381	for (int i = 0; i < SIZE; ++i) {
382	assertTrue(q.containsAll(p));
383	assertFalse(p.containsAll(q));
384	p.add(new Integer(i));
385	}
386	assertTrue(p.containsAll(q));
387	}
388
389	/**
390	* retainAll(c) retains only those elements of c and reports true if changed
391	*/
392	public void testRetainAll() {
393	PriorityQueue q = populatedQueue(SIZE);
394	PriorityQueue p = populatedQueue(SIZE);
395	for (int i = 0; i < SIZE; ++i) {
396	boolean changed = q.retainAll(p);
397	if (i == 0)
398	assertFalse(changed);
399	else
400	assertTrue(changed);
401
402	assertTrue(q.containsAll(p));
403	assertEquals(SIZE-i, q.size());
404	p.remove();
405	}
406	}
407
408	/**
409	* removeAll(c) removes only those elements of c and reports true if changed
410	*/
411	public void testRemoveAll() {
412	for (int i = 1; i < SIZE; ++i) {
413	PriorityQueue q = populatedQueue(SIZE);
414	PriorityQueue p = populatedQueue(i);
415	assertTrue(q.removeAll(p));
416	assertEquals(SIZE-i, q.size());
417	for (int j = 0; j < i; ++j) {
418	Integer I = (Integer)(p.remove());
419	assertFalse(q.contains(I));
420	}
421	}
422	}
423
424	/**
425	* toArray contains all elements
426	*/
427	public void testToArray() {
428	PriorityQueue q = populatedQueue(SIZE);
429	Object[] o = q.toArray();
430	Arrays.sort(o);
431	for(int i = 0; i < o.length; i++)
432	assertEquals(o[i], q.poll());
433	}
434
435	/**
436	* toArray(a) contains all elements
437	*/
438	public void testToArray2() {
439	PriorityQueue q = populatedQueue(SIZE);
440	Integer[] ints = new Integer[SIZE];
441	ints = (Integer[])q.toArray(ints);
442	Arrays.sort(ints);
443	for(int i = 0; i < ints.length; i++)
444	assertEquals(ints[i], q.poll());
445	}
446
447	/**
448	* iterator iterates through all elements
449	*/
450	public void testIterator() {
451	PriorityQueue q = populatedQueue(SIZE);
452	int i = 0;
453	Iterator it = q.iterator();
454	while(it.hasNext()) {
455	assertTrue(q.contains(it.next()));
456	++i;
457	}
458	assertEquals(i, SIZE);
459	}
460
461	/**
462	* iterator.remove removes current element
463	*/
464	public void testIteratorRemove () {
465	final PriorityQueue q = new PriorityQueue(3);
466	q.add(new Integer(2));
467	q.add(new Integer(1));
468	q.add(new Integer(3));
469
470	Iterator it = q.iterator();
471	it.next();
472	it.remove();
473
474	it = q.iterator();
475	assertEquals(it.next(), new Integer(2));
476	assertEquals(it.next(), new Integer(3));
477	assertFalse(it.hasNext());
478	}
479
480
481	/**
482	* toString contains toStrings of elements
483	*/
484	public void testToString() {
485	PriorityQueue q = populatedQueue(SIZE);
486	String s = q.toString();
487	for (int i = 0; i < SIZE; ++i) {
488	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
489	}
490	}
491
492	/**
493	* A deserialized serialized queue has same elements
494	*/
495	public void testSerialization() {
496	PriorityQueue q = populatedQueue(SIZE);
497	try {
498	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
499	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
500	out.writeObject(q);
501	out.close();
502
503	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
504	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
505	PriorityQueue r = (PriorityQueue)in.readObject();
506	assertEquals(q.size(), r.size());
507	while (!q.isEmpty())
508	assertEquals(q.remove(), r.remove());
509	} catch(Exception e){
510	unexpectedException();
511	}
512	}
513	}