test/tck/PriorityQueueTest.java

/*
 * Written by members of JCP JSR-166 Expert Group and released to the
 * public domain. Use, modify, and redistribute this code in any way
 * without acknowledgement. Other contributors include Andrew Wright,
 * Jeffrey Hayes, Pat Fischer, Mike Judd.
 */

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

public class PriorityQueueTest extends TestCase {

    private static final int N = 10;
    private static final long SHORT_DELAY_MS = 100; 
    private static final long MEDIUM_DELAY_MS = 1000;
    private static final long LONG_DELAY_MS = 10000; 

    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 fullQueue(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;
    }
 
    public void testConstructor1(){
        assertEquals(0, new PriorityQueue(N).size());
    }

    public void testConstructor2(){
        try {
            PriorityQueue q = new PriorityQueue(0);
            fail("Cannot make zero-sized");
        }
        catch (IllegalArgumentException success) {}
    }

    public void testConstructor3() {

        try {
            PriorityQueue q = new PriorityQueue((Collection)null);
            fail("Cannot make from null collection");
        }
        catch (NullPointerException success) {}
    }

    public void testConstructor4(){
        try {
            Integer[] ints = new Integer[N];
            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
            fail("Cannot make with null elements");
        }
        catch (NullPointerException success) {}
    }

    public void testConstructor5(){
        try {
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N-1; ++i)
                ints[i] = new Integer(i);
            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
            fail("Cannot make with null elements");
        }
        catch (NullPointerException success) {}
    }

    public void testConstructor6(){
        try {
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N; ++i)
                ints[i] = new Integer(i);
            PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
            for (int i = 0; i < N; ++i)
                assertEquals(ints[i], q.poll());
        }
        finally {}
    }

    public void testConstructor7(){
        try {
            PriorityQueue q = new PriorityQueue(N, new MyReverseComparator());
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N; ++i)
                ints[i] = new Integer(i);
            q.addAll(Arrays.asList(ints));
            for (int i = N-1; i >= 0; --i)
                assertEquals(ints[i], q.poll());
        }
        finally {}
    }

    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());
    }

    public void testSize() {
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(N-i, q.size());
            q.remove();
        }
        for (int i = 0; i < N; ++i) {
            assertEquals(i, q.size());
            q.add(new Integer(i));
        }
    }

    public void testOfferNull(){
        try {
            PriorityQueue q = new PriorityQueue(1);
            q.offer(null);
            fail("should throw NPE");
        } catch (NullPointerException success) { }   
    }

    public void testOffer() {
        PriorityQueue q = new PriorityQueue(1);
        assertTrue(q.offer(new Integer(0)));
        assertTrue(q.offer(new Integer(1)));
    }

    public void testOfferNonComparable() {
        try {
            PriorityQueue q = new PriorityQueue(1);
            q.offer(new Object());
            q.offer(new Object());
            q.offer(new Object());
            fail("should throw CCE");
        }
        catch(ClassCastException success) {}
    }

    public void testAdd(){
        PriorityQueue q = new PriorityQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, q.size());
            assertTrue(q.add(new Integer(i)));
        }
    }

    public void testAddAll1(){
        try {
            PriorityQueue q = new PriorityQueue(1);
            q.addAll(null);
            fail("Cannot add null collection");
        }
        catch (NullPointerException success) {}
    }
    public void testAddAll2(){
        try {
            PriorityQueue q = new PriorityQueue(N);
            Integer[] ints = new Integer[N];
            q.addAll(Arrays.asList(ints));
            fail("Cannot add null elements");
        }
        catch (NullPointerException success) {}
    }
    public void testAddAll3(){
        try {
            PriorityQueue q = new PriorityQueue(N);
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N-1; ++i)
                ints[i] = new Integer(i);
            q.addAll(Arrays.asList(ints));
            fail("Cannot add null elements");
        }
        catch (NullPointerException success) {}
    }

    public void testAddAll5(){
        try {
            Integer[] empty = new Integer[0];
            Integer[] ints = new Integer[N];
            for (int i = 0; i < N; ++i)
                ints[i] = new Integer(N-1-i);
            PriorityQueue q = new PriorityQueue(N);
            assertFalse(q.addAll(Arrays.asList(empty)));
            assertTrue(q.addAll(Arrays.asList(ints)));
            for (int i = 0; i < N; ++i)
                assertEquals(new Integer(i), q.poll());
        }
        finally {}
    }

    public void testPoll(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, ((Integer)q.poll()).intValue());
        }
        assertNull(q.poll());
    }

    public void testPeek(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, ((Integer)q.peek()).intValue());
            q.poll();
            assertTrue(q.peek() == null ||
                       i != ((Integer)q.peek()).intValue());
        }
        assertNull(q.peek());
    }

    public void testElement(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, ((Integer)q.element()).intValue());
            q.poll();
        }
        try {
            q.element();
            fail("no such element");
        }
        catch (NoSuchElementException success) {}
    }

    public void testRemove(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertEquals(i, ((Integer)q.remove()).intValue());
        }
        try {
            q.remove();
            fail("remove should throw");
        } catch (NoSuchElementException success){
        }   
    }

    public void testRemoveElement(){
        PriorityQueue q = fullQueue(N);
        for (int i = 1; i < N; i+=2) {
            assertTrue(q.remove(new Integer(i)));
        }
        for (int i = 0; i < N; i+=2) {
            assertTrue(q.remove(new Integer(i)));
            assertFalse(q.remove(new Integer(i+1)));
        }
        assert(q.isEmpty());
    }
        
    public void testContains(){
        PriorityQueue q = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            assertTrue(q.contains(new Integer(i)));
            q.poll();
            assertFalse(q.contains(new Integer(i)));
        }
    }

    public void testClear(){
        PriorityQueue q = fullQueue(N);
        q.clear();
        assertTrue(q.isEmpty());
        assertEquals(0, q.size());
        q.add(new Integer(1));
        assertFalse(q.isEmpty());
        q.clear();
        assertTrue(q.isEmpty());
    }

    public void testContainsAll(){
        PriorityQueue q = fullQueue(N);
        PriorityQueue p = new PriorityQueue(N);
        for (int i = 0; i < N; ++i) {
            assertTrue(q.containsAll(p));
            assertFalse(p.containsAll(q));
            p.add(new Integer(i));
        }
        assertTrue(p.containsAll(q));
    }

    public void testRetainAll(){
        PriorityQueue q = fullQueue(N);
        PriorityQueue p = fullQueue(N);
        for (int i = 0; i < N; ++i) {
            boolean changed = q.retainAll(p);
            if (i == 0)
                assertFalse(changed);
            else
                assertTrue(changed);

            assertTrue(q.containsAll(p));
            assertEquals(N-i, q.size());
            p.remove();
        }
    }

    public void testRemoveAll(){
        for (int i = 1; i < N; ++i) {
            PriorityQueue q = fullQueue(N);
            PriorityQueue p = fullQueue(i);
            assertTrue(q.removeAll(p));
            assertEquals(N-i, q.size());
            for (int j = 0; j < i; ++j) {
                Integer I = (Integer)(p.remove());
                assertFalse(q.contains(I));
            }
        }
    }

    public void testToArray(){
        PriorityQueue q = fullQueue(N);
        Object[] o = q.toArray();
        Arrays.sort(o);
        for(int i = 0; i < o.length; i++)
            assertEquals(o[i], q.poll());
    }

    public void testToArray2(){
        PriorityQueue q = fullQueue(N);
        Integer[] ints = new Integer[N];
        ints = (Integer[])q.toArray(ints);
        Arrays.sort(ints);
        for(int i = 0; i < ints.length; i++)
            assertEquals(ints[i], q.poll());
    }
    
    public void testIterator(){
        PriorityQueue q = fullQueue(N);
        int i = 0;
        Iterator it = q.iterator();
        while(it.hasNext()) {
            assertTrue(q.contains(it.next()));
            ++i;
        }
        assertEquals(i, N);
    }

    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());
    }


    public void testToString(){
        PriorityQueue q = fullQueue(N);
        String s = q.toString();
        for (int i = 0; i < N; ++i) {
            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
        }
    }        

}
Revision:	1.1
Committed:	Sun Aug 31 19:24:55 2003 UTC (20 years, 8 months ago) by dl
Branch:	MAIN
Log Message:	First check-in of tests to be in tck
#	Content
1	/*
2	* Written by members of JCP JSR-166 Expert Group and released to the
3	* public domain. Use, modify, and redistribute this code in any way
4	* without acknowledgement. Other contributors include Andrew Wright,
5	* Jeffrey Hayes, Pat Fischer, Mike Judd.
6	*/
7
8	import junit.framework.*;
9	import java.util.*;
10	import java.util.concurrent.*;
11
12	public class PriorityQueueTest extends TestCase {
13
14	private static final int N = 10;
15	private static final long SHORT_DELAY_MS = 100;
16	private static final long MEDIUM_DELAY_MS = 1000;
17	private static final long LONG_DELAY_MS = 10000;
18
19	public static void main(String[] args) {
20	junit.textui.TestRunner.run (suite());
21	}
22
23	public static Test suite() {
24	return new TestSuite(PriorityQueueTest.class);
25	}
26
27	static class MyReverseComparator implements Comparator {
28	public int compare(Object x, Object y) {
29	int i = ((Integer)x).intValue();
30	int j = ((Integer)y).intValue();
31	if (i < j) return 1;
32	if (i > j) return -1;
33	return 0;
34	}
35	}
36
37
38	/**
39	* Create a queue of given size containing consecutive
40	* Integers 0 ... n.
41	*/
42	private PriorityQueue fullQueue(int n) {
43	PriorityQueue q = new PriorityQueue(n);
44	assertTrue(q.isEmpty());
45	for(int i = n-1; i >= 0; i-=2)
46	assertTrue(q.offer(new Integer(i)));
47	for(int i = (n & 1); i < n; i+=2)
48	assertTrue(q.offer(new Integer(i)));
49	assertFalse(q.isEmpty());
50	assertEquals(n, q.size());
51	return q;
52	}
53
54	public void testConstructor1(){
55	assertEquals(0, new PriorityQueue(N).size());
56	}
57
58	public void testConstructor2(){
59	try {
60	PriorityQueue q = new PriorityQueue(0);
61	fail("Cannot make zero-sized");
62	}
63	catch (IllegalArgumentException success) {}
64	}
65
66	public void testConstructor3() {
67
68	try {
69	PriorityQueue q = new PriorityQueue((Collection)null);
70	fail("Cannot make from null collection");
71	}
72	catch (NullPointerException success) {}
73	}
74
75	public void testConstructor4(){
76	try {
77	Integer[] ints = new Integer[N];
78	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
79	fail("Cannot make with null elements");
80	}
81	catch (NullPointerException success) {}
82	}
83
84	public void testConstructor5(){
85	try {
86	Integer[] ints = new Integer[N];
87	for (int i = 0; i < N-1; ++i)
88	ints[i] = new Integer(i);
89	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
90	fail("Cannot make with null elements");
91	}
92	catch (NullPointerException success) {}
93	}
94
95	public void testConstructor6(){
96	try {
97	Integer[] ints = new Integer[N];
98	for (int i = 0; i < N; ++i)
99	ints[i] = new Integer(i);
100	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
101	for (int i = 0; i < N; ++i)
102	assertEquals(ints[i], q.poll());
103	}
104	finally {}
105	}
106
107	public void testConstructor7(){
108	try {
109	PriorityQueue q = new PriorityQueue(N, new MyReverseComparator());
110	Integer[] ints = new Integer[N];
111	for (int i = 0; i < N; ++i)
112	ints[i] = new Integer(i);
113	q.addAll(Arrays.asList(ints));
114	for (int i = N-1; i >= 0; --i)
115	assertEquals(ints[i], q.poll());
116	}
117	finally {}
118	}
119
120	public void testEmpty() {
121	PriorityQueue q = new PriorityQueue(2);
122	assertTrue(q.isEmpty());
123	q.add(new Integer(1));
124	assertFalse(q.isEmpty());
125	q.add(new Integer(2));
126	q.remove();
127	q.remove();
128	assertTrue(q.isEmpty());
129	}
130
131	public void testSize() {
132	PriorityQueue q = fullQueue(N);
133	for (int i = 0; i < N; ++i) {
134	assertEquals(N-i, q.size());
135	q.remove();
136	}
137	for (int i = 0; i < N; ++i) {
138	assertEquals(i, q.size());
139	q.add(new Integer(i));
140	}
141	}
142
143	public void testOfferNull(){
144	try {
145	PriorityQueue q = new PriorityQueue(1);
146	q.offer(null);
147	fail("should throw NPE");
148	} catch (NullPointerException success) { }
149	}
150
151	public void testOffer() {
152	PriorityQueue q = new PriorityQueue(1);
153	assertTrue(q.offer(new Integer(0)));
154	assertTrue(q.offer(new Integer(1)));
155	}
156
157	public void testOfferNonComparable() {
158	try {
159	PriorityQueue q = new PriorityQueue(1);
160	q.offer(new Object());
161	q.offer(new Object());
162	q.offer(new Object());
163	fail("should throw CCE");
164	}
165	catch(ClassCastException success) {}
166	}
167
168	public void testAdd(){
169	PriorityQueue q = new PriorityQueue(N);
170	for (int i = 0; i < N; ++i) {
171	assertEquals(i, q.size());
172	assertTrue(q.add(new Integer(i)));
173	}
174	}
175
176	public void testAddAll1(){
177	try {
178	PriorityQueue q = new PriorityQueue(1);
179	q.addAll(null);
180	fail("Cannot add null collection");
181	}
182	catch (NullPointerException success) {}
183	}
184	public void testAddAll2(){
185	try {
186	PriorityQueue q = new PriorityQueue(N);
187	Integer[] ints = new Integer[N];
188	q.addAll(Arrays.asList(ints));
189	fail("Cannot add null elements");
190	}
191	catch (NullPointerException success) {}
192	}
193	public void testAddAll3(){
194	try {
195	PriorityQueue q = new PriorityQueue(N);
196	Integer[] ints = new Integer[N];
197	for (int i = 0; i < N-1; ++i)
198	ints[i] = new Integer(i);
199	q.addAll(Arrays.asList(ints));
200	fail("Cannot add null elements");
201	}
202	catch (NullPointerException success) {}
203	}
204
205	public void testAddAll5(){
206	try {
207	Integer[] empty = new Integer[0];
208	Integer[] ints = new Integer[N];
209	for (int i = 0; i < N; ++i)
210	ints[i] = new Integer(N-1-i);
211	PriorityQueue q = new PriorityQueue(N);
212	assertFalse(q.addAll(Arrays.asList(empty)));
213	assertTrue(q.addAll(Arrays.asList(ints)));
214	for (int i = 0; i < N; ++i)
215	assertEquals(new Integer(i), q.poll());
216	}
217	finally {}
218	}
219
220	public void testPoll(){
221	PriorityQueue q = fullQueue(N);
222	for (int i = 0; i < N; ++i) {
223	assertEquals(i, ((Integer)q.poll()).intValue());
224	}
225	assertNull(q.poll());
226	}
227
228	public void testPeek(){
229	PriorityQueue q = fullQueue(N);
230	for (int i = 0; i < N; ++i) {
231	assertEquals(i, ((Integer)q.peek()).intValue());
232	q.poll();
233	assertTrue(q.peek() == null \|\|
234	i != ((Integer)q.peek()).intValue());
235	}
236	assertNull(q.peek());
237	}
238
239	public void testElement(){
240	PriorityQueue q = fullQueue(N);
241	for (int i = 0; i < N; ++i) {
242	assertEquals(i, ((Integer)q.element()).intValue());
243	q.poll();
244	}
245	try {
246	q.element();
247	fail("no such element");
248	}
249	catch (NoSuchElementException success) {}
250	}
251
252	public void testRemove(){
253	PriorityQueue q = fullQueue(N);
254	for (int i = 0; i < N; ++i) {
255	assertEquals(i, ((Integer)q.remove()).intValue());
256	}
257	try {
258	q.remove();
259	fail("remove should throw");
260	} catch (NoSuchElementException success){
261	}
262	}
263
264	public void testRemoveElement(){
265	PriorityQueue q = fullQueue(N);
266	for (int i = 1; i < N; i+=2) {
267	assertTrue(q.remove(new Integer(i)));
268	}
269	for (int i = 0; i < N; i+=2) {
270	assertTrue(q.remove(new Integer(i)));
271	assertFalse(q.remove(new Integer(i+1)));
272	}
273	assert(q.isEmpty());
274	}
275
276	public void testContains(){
277	PriorityQueue q = fullQueue(N);
278	for (int i = 0; i < N; ++i) {
279	assertTrue(q.contains(new Integer(i)));
280	q.poll();
281	assertFalse(q.contains(new Integer(i)));
282	}
283	}
284
285	public void testClear(){
286	PriorityQueue q = fullQueue(N);
287	q.clear();
288	assertTrue(q.isEmpty());
289	assertEquals(0, q.size());
290	q.add(new Integer(1));
291	assertFalse(q.isEmpty());
292	q.clear();
293	assertTrue(q.isEmpty());
294	}
295
296	public void testContainsAll(){
297	PriorityQueue q = fullQueue(N);
298	PriorityQueue p = new PriorityQueue(N);
299	for (int i = 0; i < N; ++i) {
300	assertTrue(q.containsAll(p));
301	assertFalse(p.containsAll(q));
302	p.add(new Integer(i));
303	}
304	assertTrue(p.containsAll(q));
305	}
306
307	public void testRetainAll(){
308	PriorityQueue q = fullQueue(N);
309	PriorityQueue p = fullQueue(N);
310	for (int i = 0; i < N; ++i) {
311	boolean changed = q.retainAll(p);
312	if (i == 0)
313	assertFalse(changed);
314	else
315	assertTrue(changed);
316
317	assertTrue(q.containsAll(p));
318	assertEquals(N-i, q.size());
319	p.remove();
320	}
321	}
322
323	public void testRemoveAll(){
324	for (int i = 1; i < N; ++i) {
325	PriorityQueue q = fullQueue(N);
326	PriorityQueue p = fullQueue(i);
327	assertTrue(q.removeAll(p));
328	assertEquals(N-i, q.size());
329	for (int j = 0; j < i; ++j) {
330	Integer I = (Integer)(p.remove());
331	assertFalse(q.contains(I));
332	}
333	}
334	}
335
336	public void testToArray(){
337	PriorityQueue q = fullQueue(N);
338	Object[] o = q.toArray();
339	Arrays.sort(o);
340	for(int i = 0; i < o.length; i++)
341	assertEquals(o[i], q.poll());
342	}
343
344	public void testToArray2(){
345	PriorityQueue q = fullQueue(N);
346	Integer[] ints = new Integer[N];
347	ints = (Integer[])q.toArray(ints);
348	Arrays.sort(ints);
349	for(int i = 0; i < ints.length; i++)
350	assertEquals(ints[i], q.poll());
351	}
352
353	public void testIterator(){
354	PriorityQueue q = fullQueue(N);
355	int i = 0;
356	Iterator it = q.iterator();
357	while(it.hasNext()) {
358	assertTrue(q.contains(it.next()));
359	++i;
360	}
361	assertEquals(i, N);
362	}
363
364	public void testIteratorRemove () {
365
366	final PriorityQueue q = new PriorityQueue(3);
367
368	q.add(new Integer(2));
369	q.add(new Integer(1));
370	q.add(new Integer(3));
371
372	Iterator it = q.iterator();
373	it.next();
374	it.remove();
375
376	it = q.iterator();
377	assertEquals(it.next(), new Integer(2));
378	assertEquals(it.next(), new Integer(3));
379	assertFalse(it.hasNext());
380	}
381
382
383	public void testToString(){
384	PriorityQueue q = fullQueue(N);
385	String s = q.toString();
386	for (int i = 0; i < N; ++i) {
387	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
388	}
389	}
390
391	}