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.6 by dl, Thu Sep 25 11:02:41 2003 UTC vs.
Revision 1.46 by jsr166, Sun May 6 22:26:24 2018 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.*;
9	>	import java.util.Arrays;
10	>	import java.util.Collection;
11	>	import java.util.Comparator;
12	>	import java.util.Iterator;
13	>	import java.util.NoSuchElementException;
14	>	import java.util.PriorityQueue;
15	>	import java.util.Queue;
16	>
17	>	import junit.framework.Test;
18
19		public class PriorityQueueTest extends JSR166TestCase {
20		public static void main(String[] args) {
21	<	junit.textui.TestRunner.run (suite());
21	>	main(suite(), args);
22		}
23		public static Test suite() {
24	<	return new TestSuite(PriorityQueueTest.class);
24	>	class Implementation implements CollectionImplementation {
25	>	public Class<?> klazz() { return PriorityQueue.class; }
26	>	public Collection emptyCollection() { return new PriorityQueue(); }
27	>	public Object makeElement(int i) { return i; }
28	>	public boolean isConcurrent() { return false; }
29	>	public boolean permitsNulls() { return false; }
30	>	}
31	>	class ComparatorImplementation implements CollectionImplementation {
32	>	public Class<?> klazz() { return PriorityQueue.class; }
33	>	public Collection emptyCollection() {
34	>	return new PriorityQueue(new MyReverseComparator());
35	>	}
36	>	public Object makeElement(int i) { return i; }
37	>	public boolean isConcurrent() { return false; }
38	>	public boolean permitsNulls() { return false; }
39	>	}
40	>	return newTestSuite(
41	>	PriorityQueueTest.class,
42	>	CollectionTest.testSuite(new Implementation()),
43	>	CollectionTest.testSuite(new ComparatorImplementation()));
44		}
45
46	<	static class MyReverseComparator implements Comparator {
46	>	static class MyReverseComparator implements Comparator, java.io.Serializable {
47		public int compare(Object x, Object y) {
48	<	int i = ((Integer)x).intValue();
24	<	int j = ((Integer)y).intValue();
25	<	if (i < j) return 1;
26	<	if (i > j) return -1;
27	<	return 0;
48	>	return ((Comparable)y).compareTo(x);
49		}
50		}
51
52		/**
53	<	* Create a queue of given size containing consecutive
54	<	* Integers 0 ... n.
53	>	* Returns a new queue of given size containing consecutive
54	>	* Integers 0 ... n - 1.
55		*/
56	<	private PriorityQueue populatedQueue(int n) {
57	<	PriorityQueue q = new PriorityQueue(n);
56	>	private static PriorityQueue<Integer> populatedQueue(int n) {
57	>	PriorityQueue<Integer> q = new PriorityQueue<>(n);
58		assertTrue(q.isEmpty());
59	<	for(int i = n-1; i >= 0; i-=2)
60	<	assertTrue(q.offer(new Integer(i)));
61	<	for(int i = (n & 1); i < n; i+=2)
62	<	assertTrue(q.offer(new Integer(i)));
59	>	for (int i = n - 1; i >= 0; i -= 2)
60	>	assertTrue(q.offer(new Integer(i)));
61	>	for (int i = (n & 1); i < n; i += 2)
62	>	assertTrue(q.offer(new Integer(i)));
63		assertFalse(q.isEmpty());
64	<	assertEquals(n, q.size());
64	>	assertEquals(n, q.size());
65	>	assertEquals((Integer) 0, q.peek());
66		return q;
67		}
68	<
68	>
69		/**
70		* A new queue has unbounded capacity
71		*/
#	Line 52 | Line 74 | public class PriorityQueueTest extends J
74		}
75
76		/**
77	<	* Constructor throws IAE if  capacity argument nonpositive
77	>	* Constructor throws IllegalArgumentException if capacity argument nonpositive
78		*/
79		public void testConstructor2() {
80		try {
81	<	PriorityQueue q = new PriorityQueue(0);
81	>	new PriorityQueue(0);
82		shouldThrow();
83	<	}
62	<	catch (IllegalArgumentException success) {}
83	>	} catch (IllegalArgumentException success) {}
84		}
85
86		/**
#	Line 67 | Line 88 | public class PriorityQueueTest extends J
88		*/
89		public void testConstructor3() {
90		try {
91	<	PriorityQueue q = new PriorityQueue((Collection)null);
91	>	new PriorityQueue((Collection)null);
92		shouldThrow();
93	<	}
73	<	catch (NullPointerException success) {}
93	>	} catch (NullPointerException success) {}
94		}
95
96		/**
#	Line 78 | Line 98 | public class PriorityQueueTest extends J
98		*/
99		public void testConstructor4() {
100		try {
101	<	Integer[] ints = new Integer[SIZE];
82	<	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
101	>	new PriorityQueue(Arrays.asList(new Integer[SIZE]));
102		shouldThrow();
103	<	}
85	<	catch (NullPointerException success) {}
103	>	} catch (NullPointerException success) {}
104		}
105
106		/**
107		* Initializing from Collection with some null elements throws NPE
108		*/
109		public void testConstructor5() {
110	+	Integer[] ints = new Integer[SIZE];
111	+	for (int i = 0; i < SIZE - 1; ++i)
112	+	ints[i] = new Integer(i);
113		try {
114	<	Integer[] ints = new Integer[SIZE];
94	<	for (int i = 0; i < SIZE-1; ++i)
95	<	ints[i] = new Integer(i);
96	<	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
114	>	new PriorityQueue(Arrays.asList(ints));
115		shouldThrow();
116	<	}
99	<	catch (NullPointerException success) {}
116	>	} catch (NullPointerException success) {}
117		}
118
119		/**
120		* Queue contains all elements of collection used to initialize
121		*/
122		public void testConstructor6() {
123	<	try {
124	<	Integer[] ints = new Integer[SIZE];
125	<	for (int i = 0; i < SIZE; ++i)
126	<	ints[i] = new Integer(i);
127	<	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
128	<	for (int i = 0; i < SIZE; ++i)
112	<	assertEquals(ints[i], q.poll());
113	<	}
114	<	finally {}
123	>	Integer[] ints = new Integer[SIZE];
124	>	for (int i = 0; i < SIZE; ++i)
125	>	ints[i] = new Integer(i);
126	>	PriorityQueue q = new PriorityQueue(Arrays.asList(ints));
127	>	for (int i = 0; i < SIZE; ++i)
128	>	assertEquals(ints[i], q.poll());
129		}
130
131		/**
132		* The comparator used in constructor is used
133		*/
134		public void testConstructor7() {
135	<	try {
136	<	MyReverseComparator cmp = new MyReverseComparator();
137	<	PriorityQueue q = new PriorityQueue(SIZE, cmp);
138	<	assertEquals(cmp, q.comparator());
139	<	Integer[] ints = new Integer[SIZE];
140	<	for (int i = 0; i < SIZE; ++i)
141	<	ints[i] = new Integer(i);
142	<	q.addAll(Arrays.asList(ints));
143	<	for (int i = SIZE-1; i >= 0; --i)
130	<	assertEquals(ints[i], q.poll());
131	<	}
132	<	finally {}
135	>	MyReverseComparator cmp = new MyReverseComparator();
136	>	PriorityQueue q = new PriorityQueue(SIZE, cmp);
137	>	assertEquals(cmp, q.comparator());
138	>	Integer[] ints = new Integer[SIZE];
139	>	for (int i = 0; i < SIZE; ++i)
140	>	ints[i] = new Integer(i);
141	>	q.addAll(Arrays.asList(ints));
142	>	for (int i = SIZE - 1; i >= 0; --i)
143	>	assertEquals(ints[i], q.poll());
144		}
145
146		/**
#	Line 152 | Line 163 | public class PriorityQueueTest extends J
163		public void testSize() {
164		PriorityQueue q = populatedQueue(SIZE);
165		for (int i = 0; i < SIZE; ++i) {
166	<	assertEquals(SIZE-i, q.size());
166	>	assertEquals(SIZE - i, q.size());
167		q.remove();
168		}
169		for (int i = 0; i < SIZE; ++i) {
#	Line 165 | Line 176 | public class PriorityQueueTest extends J
176		* offer(null) throws NPE
177		*/
178		public void testOfferNull() {
179	<	try {
180	<	PriorityQueue q = new PriorityQueue(1);
179	>	PriorityQueue q = new PriorityQueue(1);
180	>	try {
181		q.offer(null);
182		shouldThrow();
183	<	} catch (NullPointerException success) { }
183	>	} catch (NullPointerException success) {}
184	>	}
185	>
186	>	/**
187	>	* add(null) throws NPE
188	>	*/
189	>	public void testAddNull() {
190	>	PriorityQueue q = new PriorityQueue(1);
191	>	try {
192	>	q.add(null);
193	>	shouldThrow();
194	>	} catch (NullPointerException success) {}
195		}
196
197		/**
#	Line 185 | Line 207 | public class PriorityQueueTest extends J
207		* Offer of non-Comparable throws CCE
208		*/
209		public void testOfferNonComparable() {
210	+	PriorityQueue q = new PriorityQueue(1);
211		try {
189	–	PriorityQueue q = new PriorityQueue(1);
190	–	q.offer(new Object());
191	–	q.offer(new Object());
212		q.offer(new Object());
213		shouldThrow();
214	+	} catch (ClassCastException success) {
215	+	assertTrue(q.isEmpty());
216	+	assertEquals(0, q.size());
217	+	assertNull(q.poll());
218		}
195	–	catch(ClassCastException success) {}
219		}
220
221		/**
#	Line 210 | Line 233 | public class PriorityQueueTest extends J
233		* addAll(null) throws NPE
234		*/
235		public void testAddAll1() {
236	+	PriorityQueue q = new PriorityQueue(1);
237		try {
214	–	PriorityQueue q = new PriorityQueue(1);
238		q.addAll(null);
239		shouldThrow();
240	<	}
218	<	catch (NullPointerException success) {}
240	>	} catch (NullPointerException success) {}
241		}
242	+
243		/**
244		* addAll of a collection with null elements throws NPE
245		*/
246		public void testAddAll2() {
247	+	PriorityQueue q = new PriorityQueue(SIZE);
248		try {
249	<	PriorityQueue q = new PriorityQueue(SIZE);
226	<	Integer[] ints = new Integer[SIZE];
227	<	q.addAll(Arrays.asList(ints));
249	>	q.addAll(Arrays.asList(new Integer[SIZE]));
250		shouldThrow();
251	<	}
230	<	catch (NullPointerException success) {}
251	>	} catch (NullPointerException success) {}
252		}
253	+
254		/**
255		* addAll of a collection with any null elements throws NPE after
256		* possibly adding some elements
257		*/
258		public void testAddAll3() {
259	+	PriorityQueue q = new PriorityQueue(SIZE);
260	+	Integer[] ints = new Integer[SIZE];
261	+	for (int i = 0; i < SIZE - 1; ++i)
262	+	ints[i] = new Integer(i);
263		try {
238	–	PriorityQueue q = new PriorityQueue(SIZE);
239	–	Integer[] ints = new Integer[SIZE];
240	–	for (int i = 0; i < SIZE-1; ++i)
241	–	ints[i] = new Integer(i);
264		q.addAll(Arrays.asList(ints));
265		shouldThrow();
266	<	}
245	<	catch (NullPointerException success) {}
266	>	} catch (NullPointerException success) {}
267		}
268
269		/**
270		* Queue contains all elements of successful addAll
271		*/
272		public void testAddAll5() {
273	<	try {
274	<	Integer[] empty = new Integer[0];
275	<	Integer[] ints = new Integer[SIZE];
276	<	for (int i = 0; i < SIZE; ++i)
277	<	ints[i] = new Integer(SIZE-1-i);
278	<	PriorityQueue q = new PriorityQueue(SIZE);
279	<	assertFalse(q.addAll(Arrays.asList(empty)));
280	<	assertTrue(q.addAll(Arrays.asList(ints)));
281	<	for (int i = 0; i < SIZE; ++i)
261	<	assertEquals(new Integer(i), q.poll());
262	<	}
263	<	finally {}
273	>	Integer[] empty = new Integer[0];
274	>	Integer[] ints = new Integer[SIZE];
275	>	for (int i = 0; i < SIZE; ++i)
276	>	ints[i] = new Integer(SIZE - 1 - i);
277	>	PriorityQueue q = new PriorityQueue(SIZE);
278	>	assertFalse(q.addAll(Arrays.asList(empty)));
279	>	assertTrue(q.addAll(Arrays.asList(ints)));
280	>	for (int i = 0; i < SIZE; ++i)
281	>	assertEquals(new Integer(i), q.poll());
282		}
283
284		/**
#	Line 269 | Line 287 | public class PriorityQueueTest extends J
287		public void testPoll() {
288		PriorityQueue q = populatedQueue(SIZE);
289		for (int i = 0; i < SIZE; ++i) {
290	<	assertEquals(i, ((Integer)q.poll()).intValue());
290	>	assertEquals(i, q.poll());
291		}
292	<	assertNull(q.poll());
292	>	assertNull(q.poll());
293		}
294
295		/**
#	Line 280 | Line 298 | public class PriorityQueueTest extends J
298		public void testPeek() {
299		PriorityQueue q = populatedQueue(SIZE);
300		for (int i = 0; i < SIZE; ++i) {
301	<	assertEquals(i, ((Integer)q.peek()).intValue());
302	<	q.poll();
301	>	assertEquals(i, q.peek());
302	>	assertEquals(i, q.poll());
303		assertTrue(q.peek() == null ||
304	<	i != ((Integer)q.peek()).intValue());
304	>	!q.peek().equals(i));
305		}
306	<	assertNull(q.peek());
306	>	assertNull(q.peek());
307		}
308
309		/**
#	Line 294 | Line 312 | public class PriorityQueueTest extends J
312		public void testElement() {
313		PriorityQueue q = populatedQueue(SIZE);
314		for (int i = 0; i < SIZE; ++i) {
315	<	assertEquals(i, ((Integer)q.element()).intValue());
316	<	q.poll();
315	>	assertEquals(i, q.element());
316	>	assertEquals(i, q.poll());
317		}
318		try {
319		q.element();
320		shouldThrow();
321	<	}
304	<	catch (NoSuchElementException success) {}
321	>	} catch (NoSuchElementException success) {}
322		}
323
324		/**
#	Line 310 | Line 327 | public class PriorityQueueTest extends J
327		public void testRemove() {
328		PriorityQueue q = populatedQueue(SIZE);
329		for (int i = 0; i < SIZE; ++i) {
330	<	assertEquals(i, ((Integer)q.remove()).intValue());
330	>	assertEquals(i, q.remove());
331		}
332		try {
333		q.remove();
334		shouldThrow();
335	<	} catch (NoSuchElementException success){
319	<	}
335	>	} catch (NoSuchElementException success) {}
336		}
337
338		/**
#	Line 324 | Line 340 | public class PriorityQueueTest extends J
340		*/
341		public void testRemoveElement() {
342		PriorityQueue q = populatedQueue(SIZE);
343	<	for (int i = 1; i < SIZE; i+=2) {
344	<	assertTrue(q.remove(new Integer(i)));
345	<	}
346	<	for (int i = 0; i < SIZE; i+=2) {
347	<	assertTrue(q.remove(new Integer(i)));
348	<	assertFalse(q.remove(new Integer(i+1)));
343	>	for (int i = 1; i < SIZE; i += 2) {
344	>	assertTrue(q.contains(i));
345	>	assertTrue(q.remove(i));
346	>	assertFalse(q.contains(i));
347	>	assertTrue(q.contains(i - 1));
348	>	}
349	>	for (int i = 0; i < SIZE; i += 2) {
350	>	assertTrue(q.contains(i));
351	>	assertTrue(q.remove(i));
352	>	assertFalse(q.contains(i));
353	>	assertFalse(q.remove(i + 1));
354	>	assertFalse(q.contains(i + 1));
355		}
356		assertTrue(q.isEmpty());
357		}
358	<
358	>
359		/**
360		* contains(x) reports true when elements added but not yet removed
361		*/
#	Line 388 | Line 410 | public class PriorityQueueTest extends J
410		assertTrue(changed);
411
412		assertTrue(q.containsAll(p));
413	<	assertEquals(SIZE-i, q.size());
413	>	assertEquals(SIZE - i, q.size());
414		p.remove();
415		}
416		}
#	Line 401 | Line 423 | public class PriorityQueueTest extends J
423		PriorityQueue q = populatedQueue(SIZE);
424		PriorityQueue p = populatedQueue(i);
425		assertTrue(q.removeAll(p));
426	<	assertEquals(SIZE-i, q.size());
426	>	assertEquals(SIZE - i, q.size());
427		for (int j = 0; j < i; ++j) {
428	<	Integer I = (Integer)(p.remove());
429	<	assertFalse(q.contains(I));
428	>	Integer x = (Integer)(p.remove());
429	>	assertFalse(q.contains(x));
430		}
431		}
432		}
#	Line 414 | Line 436 | public class PriorityQueueTest extends J
436		*/
437		public void testToArray() {
438		PriorityQueue q = populatedQueue(SIZE);
439	<	Object[] o = q.toArray();
439	>	Object[] o = q.toArray();
440		Arrays.sort(o);
441	<	for(int i = 0; i < o.length; i++)
442	<	assertEquals(o[i], q.poll());
441	>	for (int i = 0; i < o.length; i++)
442	>	assertSame(o[i], q.poll());
443		}
444
445		/**
446		* toArray(a) contains all elements
447		*/
448		public void testToArray2() {
449	<	PriorityQueue q = populatedQueue(SIZE);
450	<	Integer[] ints = new Integer[SIZE];
451	<	ints = (Integer[])q.toArray(ints);
449	>	PriorityQueue<Integer> q = populatedQueue(SIZE);
450	>	Integer[] ints = new Integer[SIZE];
451	>	Integer[] array = q.toArray(ints);
452	>	assertSame(ints, array);
453		Arrays.sort(ints);
454	<	for(int i = 0; i < ints.length; i++)
455	<	assertEquals(ints[i], q.poll());
454	>	for (int i = 0; i < ints.length; i++)
455	>	assertSame(ints[i], q.poll());
456		}
457	<
457	>
458		/**
459		* iterator iterates through all elements
460		*/
461		public void testIterator() {
462		PriorityQueue q = populatedQueue(SIZE);
463	<	int i = 0;
464	<	Iterator it = q.iterator();
465	<	while(it.hasNext()) {
463	>	Iterator it = q.iterator();
464	>	int i;
465	>	for (i = 0; it.hasNext(); i++)
466		assertTrue(q.contains(it.next()));
444	–	++i;
445	–	}
467		assertEquals(i, SIZE);
468	+	assertIteratorExhausted(it);
469	+	}
470	+
471	+	/**
472	+	* iterator of empty collection has no elements
473	+	*/
474	+	public void testEmptyIterator() {
475	+	assertIteratorExhausted(new PriorityQueue().iterator());
476		}
477
478		/**
479		* iterator.remove removes current element
480		*/
481	<	public void testIteratorRemove () {
481	>	public void testIteratorRemove() {
482		final PriorityQueue q = new PriorityQueue(3);
483		q.add(new Integer(2));
484		q.add(new Integer(1));
#	Line 465 | Line 494 | public class PriorityQueueTest extends J
494		assertFalse(it.hasNext());
495		}
496
468	–
497		/**
498		* toString contains toStrings of elements
499		*/
#	Line 473 | Line 501 | public class PriorityQueueTest extends J
501		PriorityQueue q = populatedQueue(SIZE);
502		String s = q.toString();
503		for (int i = 0; i < SIZE; ++i) {
504	<	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
504	>	assertTrue(s.contains(String.valueOf(i)));
505		}
506	<	}
506	>	}
507
508		/**
509	<	* A deserialized serialized queue has same elements
509	>	* A deserialized/reserialized queue has same elements
510		*/
511	<	public void testSerialization() {
512	<	PriorityQueue q = populatedQueue(SIZE);
513	<	try {
486	<	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
487	<	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
488	<	out.writeObject(q);
489	<	out.close();
511	>	public void testSerialization() throws Exception {
512	>	Queue x = populatedQueue(SIZE);
513	>	Queue y = serialClone(x);
514
515	<	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
516	<	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
517	<	PriorityQueue r = (PriorityQueue)in.readObject();
518	<	assertEquals(q.size(), r.size());
519	<	while (!q.isEmpty())
496	<	assertEquals(q.remove(), r.remove());
497	<	} catch(Exception e){
498	<	unexpectedException();
515	>	assertNotSame(x, y);
516	>	assertEquals(x.size(), y.size());
517	>	while (!x.isEmpty()) {
518	>	assertFalse(y.isEmpty());
519	>	assertEquals(x.remove(), y.remove());
520		}
521	+	assertTrue(y.isEmpty());
522		}
523		}

Diff Legend

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