ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/tck/PriorityQueueTest.java

Comparing jsr166/src/test/tck/PriorityQueueTest.java (file contents):
Revision 1.2 by dl, Sun Sep 7 20:39:11 2003 UTC vs.
Revision 1.13 by jsr166, Sat Nov 21 10:25:05 2009 UTC

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

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines