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

Diff Legend

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