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.12 by jsr166, Sat Nov 21 02:07:27 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");
61	>	shouldThrow();
62		}
63		catch (IllegalArgumentException success) {}
64		}
65
66	+	/**
67	+	* Initializing from null Collection throws NPE
68	+	*/
69		public void testConstructor3() {
68	–
70		try {
71		PriorityQueue q = new PriorityQueue((Collection)null);
72	<	fail("Cannot make from null collection");
72	>	shouldThrow();
73		}
74		catch (NullPointerException success) {}
75		}
76
77	<	public void testConstructor4(){
77	>	/**
78	>	* Initializing from Collection of null elements throws NPE
79	>	*/
80	>	public void testConstructor4() {
81		try {
82	<	Integer[] ints = new Integer[N];
82	>	Integer[] ints = new Integer[SIZE];
83		PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
84	<	fail("Cannot make with null elements");
84	>	shouldThrow();
85		}
86		catch (NullPointerException success) {}
87		}
88
89	<	public void testConstructor5(){
89	>	/**
90	>	* Initializing from Collection with some null elements throws NPE
91	>	*/
92	>	public void testConstructor5() {
93		try {
94	<	Integer[] ints = new Integer[N];
95	<	for (int i = 0; i < N-1; ++i)
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	<	fail("Cannot make with null elements");
98	>	shouldThrow();
99		}
100		catch (NullPointerException success) {}
101		}
102
103	<	public void testConstructor6(){
103	>	/**
104	>	* Queue contains all elements of collection used to initialize
105	>	*/
106	>	public void testConstructor6() {
107		try {
108	<	Integer[] ints = new Integer[N];
109	<	for (int i = 0; i < N; ++i)
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 < N; ++i)
112	>	for (int i = 0; i < SIZE; ++i)
113		assertEquals(ints[i], q.poll());
114		}
115		finally {}
116		}
117
118	<	public void testConstructor7(){
118	>	/**
119	>	* The comparator used in constructor is used
120	>	*/
121	>	public void testConstructor7() {
122		try {
123	<	PriorityQueue q = new PriorityQueue(N, new MyReverseComparator());
124	<	Integer[] ints = new Integer[N];
125	<	for (int i = 0; i < N; ++i)
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 = N-1; i >= 0; --i)
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());
#	Line 129 | Line 147 | public class PriorityQueueTest extends T
147		assertTrue(q.isEmpty());
148		}
149
150	+	/**
151	+	* size changes when elements added and removed
152	+	*/
153		public void testSize() {
154	<	PriorityQueue q = fullQueue(N);
155	<	for (int i = 0; i < N; ++i) {
156	<	assertEquals(N-i, q.size());
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 < N; ++i) {
159	>	for (int i = 0; i < SIZE; ++i) {
160		assertEquals(i, q.size());
161		q.add(new Integer(i));
162		}
163		}
164
165	<	public void testOfferNull(){
166	<	try {
165	>	/**
166	>	* offer(null) throws NPE
167	>	*/
168	>	public void testOfferNull() {
169	>	try {
170		PriorityQueue q = new PriorityQueue(1);
171		q.offer(null);
172	<	fail("should throw NPE");
173	<	} catch (NullPointerException success) { }
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(new Integer(0)));
193	<	assertTrue(q.offer(new Integer(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	<	fail("should throw CCE");
205	>	shouldThrow();
206		}
207	<	catch(ClassCastException success) {}
207	>	catch (ClassCastException success) {}
208		}
209
210	<	public void testAdd(){
211	<	PriorityQueue q = new PriorityQueue(N);
212	<	for (int i = 0; i < N; ++i) {
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	<	public void testAddAll1(){
221	>	/**
222	>	* addAll(null) throws NPE
223	>	*/
224	>	public void testAddAll1() {
225		try {
226		PriorityQueue q = new PriorityQueue(1);
227		q.addAll(null);
228	<	fail("Cannot add null collection");
228	>	shouldThrow();
229		}
230		catch (NullPointerException success) {}
231		}
232	<	public void testAddAll2(){
232	>	/**
233	>	* addAll of a collection with null elements throws NPE
234	>	*/
235	>	public void testAddAll2() {
236		try {
237	<	PriorityQueue q = new PriorityQueue(N);
238	<	Integer[] ints = new Integer[N];
237	>	PriorityQueue q = new PriorityQueue(SIZE);
238	>	Integer[] ints = new Integer[SIZE];
239		q.addAll(Arrays.asList(ints));
240	<	fail("Cannot add null elements");
240	>	shouldThrow();
241		}
242		catch (NullPointerException success) {}
243		}
244	<	public void testAddAll3(){
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(N);
251	<	Integer[] ints = new Integer[N];
252	<	for (int i = 0; i < N-1; ++i)
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	<	fail("Cannot add null elements");
255	>	shouldThrow();
256		}
257		catch (NullPointerException success) {}
258		}
259
260	<	public void testAddAll5(){
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[N];
267	<	for (int i = 0; i < N; ++i)
268	<	ints[i] = new Integer(N-1-i);
269	<	PriorityQueue q = new PriorityQueue(N);
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 < N; ++i)
272	>	for (int i = 0; i < SIZE; ++i)
273		assertEquals(new Integer(i), q.poll());
274		}
275		finally {}
276		}
277
278	<	public void testPoll(){
279	<	PriorityQueue q = fullQueue(N);
280	<	for (int i = 0; i < N; ++i) {
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());
286	>	assertNull(q.poll());
287		}
288
289	<	public void testPeek(){
290	<	PriorityQueue q = fullQueue(N);
291	<	for (int i = 0; i < N; ++i) {
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());
300	>	assertNull(q.peek());
301		}
302
303	<	public void testElement(){
304	<	PriorityQueue q = fullQueue(N);
305	<	for (int i = 0; i < N; ++i) {
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	<	fail("no such element");
314	>	shouldThrow();
315		}
316		catch (NoSuchElementException success) {}
317		}
318
319	<	public void testRemove(){
320	<	PriorityQueue q = fullQueue(N);
321	<	for (int i = 0; i < N; ++i) {
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	<	fail("remove should throw");
330	<	} catch (NoSuchElementException success){
331	<	}
329	>	shouldThrow();
330	>	} catch (NoSuchElementException success) {
331	>	}
332		}
333
334	<	public void testRemoveElement(){
335	<	PriorityQueue q = fullQueue(N);
336	<	for (int i = 1; i < N; i+=2) {
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 < N; i+=2) {
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	<	public void testContains(){
350	<	PriorityQueue q = fullQueue(N);
351	<	for (int i = 0; i < N; ++i) {
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	<	public void testClear(){
362	<	PriorityQueue q = fullQueue(N);
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());
#	Line 294 | Line 372 | public class PriorityQueueTest extends T
372		assertTrue(q.isEmpty());
373		}
374
375	<	public void testContainsAll(){
376	<	PriorityQueue q = fullQueue(N);
377	<	PriorityQueue p = new PriorityQueue(N);
378	<	for (int i = 0; i < N; ++i) {
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));
#	Line 305 | Line 386 | public class PriorityQueueTest extends T
386		assertTrue(p.containsAll(q));
387		}
388
389	<	public void testRetainAll(){
390	<	PriorityQueue q = fullQueue(N);
391	<	PriorityQueue p = fullQueue(N);
392	<	for (int i = 0; i < N; ++i) {
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);
#	Line 316 | Line 400 | public class PriorityQueueTest extends T
400		assertTrue(changed);
401
402		assertTrue(q.containsAll(p));
403	<	assertEquals(N-i, q.size());
403	>	assertEquals(SIZE-i, q.size());
404		p.remove();
405		}
406		}
407
408	<	public void testRemoveAll(){
409	<	for (int i = 1; i < N; ++i) {
410	<	PriorityQueue q = fullQueue(N);
411	<	PriorityQueue p = fullQueue(i);
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(N-i, q.size());
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));
#	Line 334 | Line 421 | public class PriorityQueueTest extends T
421		}
422		}
423
424	<	public void testToArray(){
425	<	PriorityQueue q = fullQueue(N);
426	<	Object[] o = q.toArray();
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());
431	>	for (int i = 0; i < o.length; i++)
432	>	assertEquals(o[i], q.poll());
433		}
434
435	<	public void testToArray2(){
436	<	PriorityQueue q = fullQueue(N);
437	<	Integer[] ints = new Integer[N];
438	<	ints = (Integer[])q.toArray(ints);
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++)
443	>	for (int i = 0; i < ints.length; i++)
444		assertEquals(ints[i], q.poll());
445		}
446	<
447	<	public void testIterator(){
448	<	PriorityQueue q = fullQueue(N);
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()) {
453	>	Iterator it = q.iterator();
454	>	while (it.hasNext()) {
455		assertTrue(q.contains(it.next()));
456		++i;
457		}
458	<	assertEquals(i, N);
458	>	assertEquals(i, SIZE);
459		}
460
461	+	/**
462	+	* iterator.remove removes current element
463	+	*/
464		public void testIteratorRemove () {
366	–
465		final PriorityQueue q = new PriorityQueue(3);
368	–
466		q.add(new Integer(2));
467		q.add(new Integer(1));
468		q.add(new Integer(3));
#	Line 381 | Line 478 | public class PriorityQueueTest extends T
478		}
479
480
481	<	public void testToString(){
482	<	PriorityQueue q = fullQueue(N);
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 < N; ++i) {
487	>	for (int i = 0; i < SIZE; ++i) {
488		assertTrue(s.indexOf(String.valueOf(i)) >= 0);
489		}
490	<	}
490	>	}
491
492	+	/**
493	+	* A deserialized serialized queue has same elements
494	+	*/
495		public void testSerialization() {
496	<	PriorityQueue q = fullQueue(N);
496	>	PriorityQueue q = populatedQueue(SIZE);
497		try {
498		ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
499		ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
#	Line 401 | Line 504 | public class PriorityQueueTest extends T
504		ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
505		PriorityQueue r = (PriorityQueue)in.readObject();
506		assertEquals(q.size(), r.size());
507	<	while (!q.isEmpty())
507	>	while (!q.isEmpty())
508		assertEquals(q.remove(), r.remove());
509	<	} catch(Exception e){
510	<	fail("unexpected exception");
509	>	} catch (Exception e) {
510	>	unexpectedException();
511		}
512		}
513		}

Diff Legend

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