ViewVC Help

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

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

Comparing jsr166/src/test/tck/ArrayDequeTest.java (file contents):
Revision 1.2 by dl, Wed Sep 14 23:50:31 2005 UTC vs.
Revision 1.59 by dl, Tue Jan 26 13:33:05 2021 UTC

#	Line 1 | Line 1
1		/*
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
2	>	* Written by Doug Lea and Martin Buchholz with assistance from
3	>	* members of JCP JSR-166 Expert Group and released to the public
4	>	* domain, as explained at
5	>	* http://creativecommons.org/publicdomain/zero/1.0/
6		*/
7
8	<	import junit.framework.*;
9	<	import java.util.*;
10	<	import java.util.concurrent.*;
8	>	import java.util.ArrayDeque;
9	>	import java.util.Arrays;
10	>	import java.util.Collection;
11	>	import java.util.Deque;
12	>	import java.util.Iterator;
13	>	import java.util.NoSuchElementException;
14	>	import java.util.Queue;
15	>	import java.util.Random;
16	>	import java.util.concurrent.ThreadLocalRandom;
17	>
18	>	import junit.framework.Test;
19
20		public class ArrayDequeTest extends JSR166TestCase {
21		public static void main(String[] args) {
22	<	junit.textui.TestRunner.run (suite());
22	>	main(suite(), args);
23		}
24
25		public static Test suite() {
26	<	return new TestSuite(ArrayDequeTest.class);
26	>	class Implementation implements CollectionImplementation {
27	>	public Class<?> klazz() { return ArrayDeque.class; }
28	>	public Collection emptyCollection() { return populatedDeque(0); }
29	>	public Object makeElement(int i) { return JSR166TestCase.itemFor(i); }
30	>	public boolean isConcurrent() { return false; }
31	>	public boolean permitsNulls() { return false; }
32	>	}
33	>	return newTestSuite(ArrayDequeTest.class,
34	>	CollectionTest.testSuite(new Implementation()));
35		}
36
37		/**
38	<	* Create a queue of given size containing consecutive
39	<	* Integers 0 ... n.
40	<	*/
41	<	private ArrayDeque populatedDeque(int n) {
42	<	ArrayDeque q = new ArrayDeque();
38	>	* Returns a new deque of given size containing consecutive
39	>	* Items 0 ... n - 1.
40	>	*/
41	>	private static ArrayDeque<Item> populatedDeque(int n) {
42	>	// Randomize various aspects of memory layout, including
43	>	// capacity slop and wraparound.
44	>	final ArrayDeque<Item> q;
45	>	ThreadLocalRandom rnd = ThreadLocalRandom.current();
46	>	switch (rnd.nextInt(6)) {
47	>	case 0: q = new ArrayDeque<Item>();      break;
48	>	case 1: q = new ArrayDeque<Item>(0);     break;
49	>	case 2: q = new ArrayDeque<Item>(1);     break;
50	>	case 3: q = new ArrayDeque<Item>(Math.max(0, n - 1)); break;
51	>	case 4: q = new ArrayDeque<Item>(n);     break;
52	>	case 5: q = new ArrayDeque<Item>(n + 1); break;
53	>	default: throw new AssertionError();
54	>	}
55	>	switch (rnd.nextInt(3)) {
56	>	case 0:
57	>	q.addFirst(fortytwo);
58	>	mustEqual(42, q.removeLast());
59	>	break;
60	>	case 1:
61	>	q.addLast(fortytwo);
62	>	mustEqual(42, q.removeFirst());
63	>	break;
64	>	case 2: /* do nothing */ break;
65	>	default: throw new AssertionError();
66	>	}
67		assertTrue(q.isEmpty());
68	<	for(int i = 0; i < n; ++i)
69	<	assertTrue(q.offerLast(new Integer(i)));
70	<	assertFalse(q.isEmpty());
71	<	assertEquals(n, q.size());
68	>	if (rnd.nextBoolean())
69	>	for (int i = 0; i < n; i++)
70	>	assertTrue(q.offerLast(itemFor(i)));
71	>	else
72	>	for (int i = n; --i >= 0; )
73	>	q.addFirst(itemFor(i));
74	>	mustEqual(n, q.size());
75	>	if (n > 0) {
76	>	assertFalse(q.isEmpty());
77	>	mustEqual(0, q.peekFirst());
78	>	mustEqual((n - 1), q.peekLast());
79	>	}
80		return q;
81		}
82	<
82	>
83		/**
84	<	* new queue is empty
84	>	* new deque is empty
85		*/
86		public void testConstructor1() {
87	<	assertEquals(0, new ArrayDeque().size());
87	>	mustEqual(0, new ArrayDeque<Item>().size());
88		}
89
90		/**
#	Line 43 | Line 92 | public class ArrayDequeTest extends JSR1
92		*/
93		public void testConstructor3() {
94		try {
95	<	ArrayDeque q = new ArrayDeque((Collection)null);
95	>	new ArrayDeque<Object>((Collection<Object>)null);
96		shouldThrow();
97	<	}
98	<	catch (NullPointerException success) {}
97	>	} catch (NullPointerException success) {}
98	>	}
99	>
100	>	/**
101	>	* Initializing from Collection of null elements throws NPE
102	>	*/
103	>	public void testConstructor4() {
104	>	try {
105	>	new ArrayDeque<Item>(Arrays.asList(new Item[SIZE]));
106	>	shouldThrow();
107	>	} catch (NullPointerException success) {}
108		}
109
110		/**
111	<	* Queue contains all elements of collection used to initialize
111	>	* Initializing from Collection with some null elements throws NPE
112	>	*/
113	>	public void testConstructor5() {
114	>	Item[] items = new Item[2]; items[0] = zero;
115	>	try {
116	>	new ArrayDeque<Item>(Arrays.asList(items));
117	>	shouldThrow();
118	>	} catch (NullPointerException success) {}
119	>	}
120
121	+	/**
122	+	* Deque contains all elements of collection used to initialize
123		*/
124		public void testConstructor6() {
125	<	try {
126	<	Integer[] ints = new Integer[SIZE];
127	<	for (int i = 0; i < SIZE; ++i)
128	<	ints[i] = new Integer(i);
61	<	ArrayDeque q = new ArrayDeque(Arrays.asList(ints));
62	<	for (int i = 0; i < SIZE; ++i)
63	<	assertEquals(ints[i], q.pollFirst());
64	<	}
65	<	finally {}
125	>	Item[] items = defaultItems;
126	>	ArrayDeque<Item> q = new ArrayDeque<Item>(Arrays.asList(items));
127	>	for (int i = 0; i < SIZE; ++i)
128	>	mustEqual(items[i], q.pollFirst());
129		}
130
131		/**
132		* isEmpty is true before add, false after
133		*/
134		public void testEmpty() {
135	<	ArrayDeque q = new ArrayDeque();
135	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
136		assertTrue(q.isEmpty());
137	<	q.add(new Integer(1));
137	>	q.add(one);
138		assertFalse(q.isEmpty());
139	<	q.add(new Integer(2));
139	>	q.add(two);
140		q.removeFirst();
141		q.removeFirst();
142		assertTrue(q.isEmpty());
#	Line 83 | Line 146 | public class ArrayDequeTest extends JSR1
146		* size changes when elements added and removed
147		*/
148		public void testSize() {
149	<	ArrayDeque q = populatedDeque(SIZE);
149	>	ArrayDeque<Item> q = populatedDeque(SIZE);
150		for (int i = 0; i < SIZE; ++i) {
151	<	assertEquals(SIZE-i, q.size());
151	>	mustEqual(SIZE - i, q.size());
152		q.removeFirst();
153		}
154		for (int i = 0; i < SIZE; ++i) {
155	<	assertEquals(i, q.size());
156	<	q.add(new Integer(i));
155	>	mustEqual(i, q.size());
156	>	mustAdd(q, i);
157		}
158		}
159
#	Line 98 | Line 161 | public class ArrayDequeTest extends JSR1
161		* push(null) throws NPE
162		*/
163		public void testPushNull() {
164	<	try {
165	<	ArrayDeque q = new ArrayDeque(1);
164	>	ArrayDeque<Item> q = new ArrayDeque<Item>(1);
165	>	try {
166		q.push(null);
167		shouldThrow();
168	<	} catch (NullPointerException success) { }
168	>	} catch (NullPointerException success) {}
169		}
170
171		/**
172	<	* peekFirst returns element inserted with push
172	>	* peekFirst() returns element inserted with push
173		*/
174		public void testPush() {
175	<	ArrayDeque q = populatedDeque(3);
175	>	ArrayDeque<Item> q = populatedDeque(3);
176		q.pollLast();
177	<	q.push(four);
178	<	assertEquals(four,q.peekFirst());
179	<	}
177	>	q.push(four);
178	>	assertSame(four, q.peekFirst());
179	>	}
180
181		/**
182	<	*  pop removes next element, or throws NSEE if empty
182	>	* pop() removes next element, or throws NSEE if empty
183		*/
184		public void testPop() {
185	<	ArrayDeque q = populatedDeque(SIZE);
185	>	ArrayDeque<Item> q = populatedDeque(SIZE);
186		for (int i = 0; i < SIZE; ++i) {
187	<	assertEquals(i, ((Integer)q.pop()).intValue());
187	>	mustEqual(i, q.pop());
188		}
189		try {
190		q.pop();
191		shouldThrow();
192	<	} catch (NoSuchElementException success){
130	<	}
192	>	} catch (NoSuchElementException success) {}
193		}
194
195		/**
196		* offer(null) throws NPE
197		*/
198	+	public void testOfferNull() {
199	+	ArrayDeque<Item> q = new ArrayDeque<Item>();
200	+	try {
201	+	q.offer(null);
202	+	shouldThrow();
203	+	} catch (NullPointerException success) {}
204	+	}
205	+
206	+	/**
207	+	* offerFirst(null) throws NPE
208	+	*/
209		public void testOfferFirstNull() {
210	<	try {
211	<	ArrayDeque q = new ArrayDeque();
210	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
211	>	try {
212		q.offerFirst(null);
213		shouldThrow();
214	<	} catch (NullPointerException success) {
215	<	}
214	>	} catch (NullPointerException success) {}
215	>	}
216	>
217	>	/**
218	>	* offerLast(null) throws NPE
219	>	*/
220	>	public void testOfferLastNull() {
221	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
222	>	try {
223	>	q.offerLast(null);
224	>	shouldThrow();
225	>	} catch (NullPointerException success) {}
226		}
227
228		/**
229	<	* OfferFirst succeeds
229	>	* offer(x) succeeds
230	>	*/
231	>	public void testOffer() {
232	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
233	>	assertTrue(q.offer(zero));
234	>	assertTrue(q.offer(one));
235	>	assertSame(zero, q.peekFirst());
236	>	assertSame(one, q.peekLast());
237	>	}
238	>
239	>	/**
240	>	* offerFirst(x) succeeds
241		*/
242		public void testOfferFirst() {
243	<	ArrayDeque q = new ArrayDeque();
244	<	assertTrue(q.offerFirst(new Integer(0)));
245	<	assertTrue(q.offerFirst(new Integer(1)));
243	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
244	>	assertTrue(q.offerFirst(zero));
245	>	assertTrue(q.offerFirst(one));
246	>	assertSame(one, q.peekFirst());
247	>	assertSame(zero, q.peekLast());
248		}
249
250		/**
251	<	* OfferLast succeeds
251	>	* offerLast(x) succeeds
252		*/
253		public void testOfferLast() {
254	<	ArrayDeque q = new ArrayDeque();
255	<	assertTrue(q.offerLast(new Integer(0)));
256	<	assertTrue(q.offerLast(new Integer(1)));
254	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
255	>	assertTrue(q.offerLast(zero));
256	>	assertTrue(q.offerLast(one));
257	>	assertSame(zero, q.peekFirst());
258	>	assertSame(one, q.peekLast());
259	>	}
260	>
261	>	/**
262	>	* add(null) throws NPE
263	>	*/
264	>	public void testAddNull() {
265	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
266	>	try {
267	>	q.add(null);
268	>	shouldThrow();
269	>	} catch (NullPointerException success) {}
270	>	}
271	>
272	>	/**
273	>	* addFirst(null) throws NPE
274	>	*/
275	>	public void testAddFirstNull() {
276	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
277	>	try {
278	>	q.addFirst(null);
279	>	shouldThrow();
280	>	} catch (NullPointerException success) {}
281	>	}
282	>
283	>	/**
284	>	* addLast(null) throws NPE
285	>	*/
286	>	public void testAddLastNull() {
287	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
288	>	try {
289	>	q.addLast(null);
290	>	shouldThrow();
291	>	} catch (NullPointerException success) {}
292		}
293
294		/**
295	<	* add succeeds
295	>	* add(x) succeeds
296		*/
297		public void testAdd() {
298	<	ArrayDeque q = new ArrayDeque();
299	<	for (int i = 0; i < SIZE; ++i) {
300	<	assertEquals(i, q.size());
301	<	assertTrue(q.add(new Integer(i)));
302	<	}
298	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
299	>	assertTrue(q.add(zero));
300	>	assertTrue(q.add(one));
301	>	assertSame(zero, q.peekFirst());
302	>	assertSame(one, q.peekLast());
303	>	}
304	>
305	>	/**
306	>	* addFirst(x) succeeds
307	>	*/
308	>	public void testAddFirst() {
309	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
310	>	q.addFirst(zero);
311	>	q.addFirst(one);
312	>	assertSame(one, q.peekFirst());
313	>	assertSame(zero, q.peekLast());
314	>	}
315	>
316	>	/**
317	>	* addLast(x) succeeds
318	>	*/
319	>	public void testAddLast() {
320	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
321	>	q.addLast(zero);
322	>	q.addLast(one);
323	>	assertSame(zero, q.peekFirst());
324	>	assertSame(one, q.peekLast());
325		}
326
327		/**
328		* addAll(null) throws NPE
329		*/
330		public void testAddAll1() {
331	+	ArrayDeque<Item> q = new ArrayDeque<Item>();
332		try {
179	–	ArrayDeque q = new ArrayDeque();
333		q.addAll(null);
334		shouldThrow();
335	<	}
183	<	catch (NullPointerException success) {}
335	>	} catch (NullPointerException success) {}
336		}
337
338		/**
339	<	* Queue contains all elements, in traversal order, of successful addAll
339	>	* addAll of a collection with null elements throws NPE
340		*/
341	<	public void testAddAll5() {
341	>	public void testAddAll2() {
342	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
343		try {
344	<	Integer[] empty = new Integer[0];
345	<	Integer[] ints = new Integer[SIZE];
346	<	for (int i = 0; i < SIZE; ++i)
347	<	ints[i] = new Integer(i);
348	<	ArrayDeque q = new ArrayDeque();
349	<	assertFalse(q.addAll(Arrays.asList(empty)));
350	<	assertTrue(q.addAll(Arrays.asList(ints)));
351	<	for (int i = 0; i < SIZE; ++i)
352	<	assertEquals(ints[i], q.pollFirst());
353	<	}
354	<	finally {}
344	>	q.addAll(Arrays.asList(new Item[SIZE]));
345	>	shouldThrow();
346	>	} catch (NullPointerException success) {}
347	>	}
348	>
349	>	/**
350	>	* addAll of a collection with any null elements throws NPE after
351	>	* possibly adding some elements
352	>	*/
353	>	public void testAddAll3() {
354	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
355	>	Item[] items = new Item[2]; items[0] = zero;
356	>	try {
357	>	q.addAll(Arrays.asList(items));
358	>	shouldThrow();
359	>	} catch (NullPointerException success) {}
360		}
361
362		/**
363	<	*  pollFirst succeeds unless empty
363	>	* Deque contains all elements, in traversal order, of successful addAll
364	>	*/
365	>	public void testAddAll5() {
366	>	Item[] empty = new Item[0];
367	>	Item[] items = defaultItems;
368	>	ArrayDeque<Item> q = new ArrayDeque<Item>();
369	>	assertFalse(q.addAll(Arrays.asList(empty)));
370	>	assertTrue(q.addAll(Arrays.asList(items)));
371	>	for (int i = 0; i < SIZE; ++i)
372	>	mustEqual(items[i], q.pollFirst());
373	>	}
374	>
375	>	/**
376	>	* pollFirst() succeeds unless empty
377		*/
378		public void testPollFirst() {
379	<	ArrayDeque q = populatedDeque(SIZE);
379	>	ArrayDeque<Item> q = populatedDeque(SIZE);
380		for (int i = 0; i < SIZE; ++i) {
381	<	assertEquals(i, ((Integer)q.pollFirst()).intValue());
381	>	mustEqual(i, q.pollFirst());
382		}
383	<	assertNull(q.pollFirst());
383	>	assertNull(q.pollFirst());
384		}
385
386		/**
387	<	*  pollLast succeeds unless empty
387	>	* pollLast() succeeds unless empty
388		*/
389		public void testPollLast() {
390	<	ArrayDeque q = populatedDeque(SIZE);
391	<	for (int i = SIZE-1; i >= 0; --i) {
392	<	assertEquals(i, ((Integer)q.pollLast()).intValue());
390	>	ArrayDeque<Item> q = populatedDeque(SIZE);
391	>	for (int i = SIZE - 1; i >= 0; --i) {
392	>	mustEqual(i, q.pollLast());
393		}
394	<	assertNull(q.pollLast());
394	>	assertNull(q.pollLast());
395		}
396
397		/**
398	<	*  poll succeeds unless empty
398	>	* poll() succeeds unless empty
399		*/
400		public void testPoll() {
401	<	ArrayDeque q = populatedDeque(SIZE);
401	>	ArrayDeque<Item> q = populatedDeque(SIZE);
402		for (int i = 0; i < SIZE; ++i) {
403	<	assertEquals(i, ((Integer)q.poll()).intValue());
403	>	mustEqual(i, q.poll());
404		}
405	<	assertNull(q.poll());
405	>	assertNull(q.poll());
406		}
407
408		/**
409	<	*  remove removes next element, or throws NSEE if empty
409	>	* remove() removes next element, or throws NSEE if empty
410		*/
411		public void testRemove() {
412	<	ArrayDeque q = populatedDeque(SIZE);
412	>	ArrayDeque<Item> q = populatedDeque(SIZE);
413		for (int i = 0; i < SIZE; ++i) {
414	<	assertEquals(i, ((Integer)q.remove()).intValue());
414	>	mustEqual(i, q.remove());
415		}
416		try {
417		q.remove();
418		shouldThrow();
419	<	} catch (NoSuchElementException success){
420	<	}
419	>	} catch (NoSuchElementException success) {}
420	>	}
421	>
422	>	/**
423	>	* remove(x) removes x and returns true if present
424	>	*/
425	>	public void testRemoveElement() {
426	>	ArrayDeque<Item> q = populatedDeque(SIZE);
427	>	for (int i = 1; i < SIZE; i += 2) {
428	>	mustContain(q, i);
429	>	mustRemove(q, i);
430	>	mustNotContain(q, i);
431	>	mustContain(q, i - 1);
432	>	}
433	>	for (int i = 0; i < SIZE; i += 2) {
434	>	mustContain(q, i);
435	>	mustRemove(q, i);
436	>	mustNotContain(q, i);
437	>	mustNotRemove(q, i + 1);
438	>	mustNotContain(q, i + 1);
439	>	}
440	>	assertTrue(q.isEmpty());
441		}
442
443		/**
444	<	*  peekFirst returns next element, or null if empty
444	>	* peekFirst() returns next element, or null if empty
445		*/
446		public void testPeekFirst() {
447	<	ArrayDeque q = populatedDeque(SIZE);
447	>	ArrayDeque<Item> q = populatedDeque(SIZE);
448		for (int i = 0; i < SIZE; ++i) {
449	<	assertEquals(i, ((Integer)q.peekFirst()).intValue());
450	<	q.pollFirst();
449	>	mustEqual(i, q.peekFirst());
450	>	mustEqual(i, q.pollFirst());
451		assertTrue(q.peekFirst() == null ||
452	<	i != ((Integer)q.peekFirst()).intValue());
452	>	!q.peekFirst().equals(i));
453		}
454	<	assertNull(q.peekFirst());
454	>	assertNull(q.peekFirst());
455		}
456
457		/**
458	<	*  peek returns next element, or null if empty
458	>	* peek() returns next element, or null if empty
459		*/
460		public void testPeek() {
461	<	ArrayDeque q = populatedDeque(SIZE);
461	>	ArrayDeque<Item> q = populatedDeque(SIZE);
462		for (int i = 0; i < SIZE; ++i) {
463	<	assertEquals(i, ((Integer)q.peek()).intValue());
464	<	q.poll();
463	>	mustEqual(i, q.peek());
464	>	mustEqual(i, q.poll());
465		assertTrue(q.peek() == null ||
466	<	i != ((Integer)q.peek()).intValue());
466	>	!q.peek().equals(i));
467		}
468	<	assertNull(q.peek());
468	>	assertNull(q.peek());
469		}
470
471		/**
472	<	*  peekLast returns next element, or null if empty
472	>	* peekLast() returns next element, or null if empty
473		*/
474		public void testPeekLast() {
475	<	ArrayDeque q = populatedDeque(SIZE);
476	<	for (int i = SIZE-1; i >= 0; --i) {
477	<	assertEquals(i, ((Integer)q.peekLast()).intValue());
478	<	q.pollLast();
475	>	ArrayDeque<Item> q = populatedDeque(SIZE);
476	>	for (int i = SIZE - 1; i >= 0; --i) {
477	>	mustEqual(i, q.peekLast());
478	>	mustEqual(i, q.pollLast());
479		assertTrue(q.peekLast() == null ||
480	<	i != ((Integer)q.peekLast()).intValue());
480	>	!q.peekLast().equals(i));
481		}
482	<	assertNull(q.peekLast());
482	>	assertNull(q.peekLast());
483		}
484
485		/**
486	<	* getFirst returns next getFirst, or throws NSEE if empty
486	>	* element() returns first element, or throws NSEE if empty
487	>	*/
488	>	public void testElement() {
489	>	ArrayDeque<Item> q = populatedDeque(SIZE);
490	>	for (int i = 0; i < SIZE; ++i) {
491	>	mustEqual(i, q.element());
492	>	mustEqual(i, q.poll());
493	>	}
494	>	try {
495	>	q.element();
496	>	shouldThrow();
497	>	} catch (NoSuchElementException success) {}
498	>	}
499	>
500	>	/**
501	>	* getFirst() returns first element, or throws NSEE if empty
502		*/
503		public void testFirstElement() {
504	<	ArrayDeque q = populatedDeque(SIZE);
504	>	ArrayDeque<Item> q = populatedDeque(SIZE);
505		for (int i = 0; i < SIZE; ++i) {
506	<	assertEquals(i, ((Integer)q.getFirst()).intValue());
507	<	q.pollFirst();
506	>	mustEqual(i, q.getFirst());
507	>	mustEqual(i, q.pollFirst());
508		}
509		try {
510		q.getFirst();
511		shouldThrow();
512	<	}
307	<	catch (NoSuchElementException success) {}
512	>	} catch (NoSuchElementException success) {}
513		}
514
515		/**
516	<	*  getLast returns next element, or throws NSEE if empty
516	>	* getLast() returns last element, or throws NSEE if empty
517		*/
518		public void testLastElement() {
519	<	ArrayDeque q = populatedDeque(SIZE);
520	<	for (int i = SIZE-1; i >= 0; --i) {
521	<	assertEquals(i, ((Integer)q.getLast()).intValue());
522	<	q.pollLast();
519	>	ArrayDeque<Item> q = populatedDeque(SIZE);
520	>	for (int i = SIZE - 1; i >= 0; --i) {
521	>	mustEqual(i, q.getLast());
522	>	mustEqual(i, q.pollLast());
523		}
524		try {
525		q.getLast();
526		shouldThrow();
527	<	}
528	<	catch (NoSuchElementException success) {}
324	<	assertNull(q.peekLast());
527	>	} catch (NoSuchElementException success) {}
528	>	assertNull(q.peekLast());
529		}
530
327	–
531		/**
532	<	*  removeFirst removes next element, or throws NSEE if empty
532	>	* removeFirst() removes first element, or throws NSEE if empty
533		*/
534		public void testRemoveFirst() {
535	<	ArrayDeque q = populatedDeque(SIZE);
535	>	ArrayDeque<Item> q = populatedDeque(SIZE);
536		for (int i = 0; i < SIZE; ++i) {
537	<	assertEquals(i, ((Integer)q.removeFirst()).intValue());
537	>	mustEqual(i, q.removeFirst());
538		}
539		try {
540		q.removeFirst();
541		shouldThrow();
542	<	} catch (NoSuchElementException success){
543	<	}
542	>	} catch (NoSuchElementException success) {}
543	>	assertNull(q.peekFirst());
544	>	}
545	>
546	>	/**
547	>	* removeLast() removes last element, or throws NSEE if empty
548	>	*/
549	>	public void testRemoveLast() {
550	>	ArrayDeque<Item> q = populatedDeque(SIZE);
551	>	for (int i = SIZE - 1; i >= 0; --i) {
552	>	mustEqual(i, q.removeLast());
553	>	}
554	>	try {
555	>	q.removeLast();
556	>	shouldThrow();
557	>	} catch (NoSuchElementException success) {}
558	>	assertNull(q.peekLast());
559		}
560
561		/**
562		* removeFirstOccurrence(x) removes x and returns true if present
563		*/
564		public void testRemoveFirstOccurrence() {
565	<	ArrayDeque q = populatedDeque(SIZE);
566	<	for (int i = 1; i < SIZE; i+=2) {
567	<	assertTrue(q.removeFirstOccurrence(new Integer(i)));
568	<	}
569	<	for (int i = 0; i < SIZE; i+=2) {
570	<	assertTrue(q.removeFirstOccurrence(new Integer(i)));
571	<	assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
565	>	Deque<Item> q = populatedDeque(SIZE);
566	>	assertFalse(q.removeFirstOccurrence(null));
567	>	for (int i = 1; i < SIZE; i += 2) {
568	>	assertTrue(q.removeFirstOccurrence(itemFor(i)));
569	>	mustNotContain(q, i);
570	>	}
571	>	for (int i = 0; i < SIZE; i += 2) {
572	>	assertTrue(q.removeFirstOccurrence(itemFor(i)));
573	>	assertFalse(q.removeFirstOccurrence(itemFor(i + 1)));
574	>	mustNotContain(q, i);
575	>	mustNotContain(q, i + 1);
576		}
577		assertTrue(q.isEmpty());
578	+	assertFalse(q.removeFirstOccurrence(null));
579	+	assertFalse(q.removeFirstOccurrence(fortytwo));
580	+	q = new ArrayDeque<Item>();
581	+	assertFalse(q.removeFirstOccurrence(null));
582	+	assertFalse(q.removeFirstOccurrence(fortytwo));
583		}
584
585		/**
586		* removeLastOccurrence(x) removes x and returns true if present
587		*/
588		public void testRemoveLastOccurrence() {
589	<	ArrayDeque q = populatedDeque(SIZE);
590	<	for (int i = 1; i < SIZE; i+=2) {
591	<	assertTrue(q.removeLastOccurrence(new Integer(i)));
592	<	}
593	<	for (int i = 0; i < SIZE; i+=2) {
594	<	assertTrue(q.removeLastOccurrence(new Integer(i)));
595	<	assertFalse(q.removeLastOccurrence(new Integer(i+1)));
589	>	Deque<Item> q = populatedDeque(SIZE);
590	>	assertFalse(q.removeLastOccurrence(null));
591	>	for (int i = 1; i < SIZE; i += 2) {
592	>	assertTrue(q.removeLastOccurrence(itemFor(i)));
593	>	mustNotContain(q, i);
594	>	}
595	>	for (int i = 0; i < SIZE; i += 2) {
596	>	assertTrue(q.removeLastOccurrence(itemFor(i)));
597	>	assertFalse(q.removeLastOccurrence(itemFor(i + 1)));
598	>	mustNotContain(q, i);
599	>	mustNotContain(q, i + 1);
600		}
601		assertTrue(q.isEmpty());
602	+	assertFalse(q.removeLastOccurrence(null));
603	+	assertFalse(q.removeLastOccurrence(fortytwo));
604	+	q = new ArrayDeque<Item>();
605	+	assertFalse(q.removeLastOccurrence(null));
606	+	assertFalse(q.removeLastOccurrence(fortytwo));
607		}
608
609		/**
610		* contains(x) reports true when elements added but not yet removed
611		*/
612		public void testContains() {
613	<	ArrayDeque q = populatedDeque(SIZE);
613	>	ArrayDeque<Item> q = populatedDeque(SIZE);
614		for (int i = 0; i < SIZE; ++i) {
615	<	assertTrue(q.contains(new Integer(i)));
616	<	q.pollFirst();
617	<	assertFalse(q.contains(new Integer(i)));
615	>	mustContain(q, i);
616	>	mustEqual(i, q.pollFirst());
617	>	mustNotContain(q, i);
618		}
619		}
620
#	Line 386 | Line 622 | public class ArrayDequeTest extends JSR1
622		* clear removes all elements
623		*/
624		public void testClear() {
625	<	ArrayDeque q = populatedDeque(SIZE);
625	>	ArrayDeque<Item> q = populatedDeque(SIZE);
626		q.clear();
627		assertTrue(q.isEmpty());
628	<	assertEquals(0, q.size());
629	<	q.add(new Integer(1));
628	>	mustEqual(0, q.size());
629	>	mustAdd(q, one);
630		assertFalse(q.isEmpty());
631		q.clear();
632		assertTrue(q.isEmpty());
#	Line 400 | Line 636 | public class ArrayDequeTest extends JSR1
636		* containsAll(c) is true when c contains a subset of elements
637		*/
638		public void testContainsAll() {
639	<	ArrayDeque q = populatedDeque(SIZE);
640	<	ArrayDeque p = new ArrayDeque();
639	>	ArrayDeque<Item> q = populatedDeque(SIZE);
640	>	ArrayDeque<Item> p = new ArrayDeque<Item>();
641		for (int i = 0; i < SIZE; ++i) {
642		assertTrue(q.containsAll(p));
643		assertFalse(p.containsAll(q));
644	<	p.add(new Integer(i));
644	>	mustAdd(p, i);
645		}
646		assertTrue(p.containsAll(q));
647		}
#	Line 414 | Line 650 | public class ArrayDequeTest extends JSR1
650		* retainAll(c) retains only those elements of c and reports true if changed
651		*/
652		public void testRetainAll() {
653	<	ArrayDeque q = populatedDeque(SIZE);
654	<	ArrayDeque p = populatedDeque(SIZE);
653	>	ArrayDeque<Item> q = populatedDeque(SIZE);
654	>	ArrayDeque<Item> p = populatedDeque(SIZE);
655		for (int i = 0; i < SIZE; ++i) {
656		boolean changed = q.retainAll(p);
657	<	if (i == 0)
422	<	assertFalse(changed);
423	<	else
424	<	assertTrue(changed);
425	<
657	>	mustEqual(changed, (i > 0));
658		assertTrue(q.containsAll(p));
659	<	assertEquals(SIZE-i, q.size());
659	>	mustEqual(SIZE - i, q.size());
660		p.removeFirst();
661		}
662		}
#	Line 434 | Line 666 | public class ArrayDequeTest extends JSR1
666		*/
667		public void testRemoveAll() {
668		for (int i = 1; i < SIZE; ++i) {
669	<	ArrayDeque q = populatedDeque(SIZE);
670	<	ArrayDeque p = populatedDeque(i);
669	>	ArrayDeque<Item> q = populatedDeque(SIZE);
670	>	ArrayDeque<Item> p = populatedDeque(i);
671		assertTrue(q.removeAll(p));
672	<	assertEquals(SIZE-i, q.size());
672	>	mustEqual(SIZE - i, q.size());
673		for (int j = 0; j < i; ++j) {
674	<	Integer I = (Integer)(p.removeFirst());
443	<	assertFalse(q.contains(I));
674	>	mustNotContain(q, p.removeFirst());
675		}
676		}
677		}
678
679	+	void checkToArray(ArrayDeque<Item> q) {
680	+	int size = q.size();
681	+	Object[] a1 = q.toArray();
682	+	mustEqual(size, a1.length);
683	+	Item[] a2 = q.toArray(new Item[0]);
684	+	mustEqual(size, a2.length);
685	+	Item[] a3 = q.toArray(new Item[Math.max(0, size - 1)]);
686	+	mustEqual(size, a3.length);
687	+	Item[] a4 = new Item[size];
688	+	assertSame(a4, q.toArray(a4));
689	+	Item[] a5 = new Item[size + 1];
690	+	Arrays.fill(a5, fortytwo);
691	+	assertSame(a5, q.toArray(a5));
692	+	Item[] a6 = new Item[size + 2];
693	+	Arrays.fill(a6, fortytwo);
694	+	assertSame(a6, q.toArray(a6));
695	+	Object[][] as = { a1, a2, a3, a4, a5, a6 };
696	+	for (Object[] a : as) {
697	+	if (a.length > size) assertNull(a[size]);
698	+	if (a.length > size + 1) mustEqual(fortytwo, a[size + 1]);
699	+	}
700	+	Iterator<? extends Item> it = q.iterator();
701	+	Item s = q.peekFirst();
702	+	for (int i = 0; i < size; i++) {
703	+	Item x = (Item) it.next();
704	+	mustEqual(s.value + i, x);
705	+	for (Object[] a : as)
706	+	assertSame(a[i], x);
707	+	}
708	+	}
709	+
710		/**
711	<	*  toArray contains all elements
711	>	* toArray() and toArray(a) contain all elements in FIFO order
712		*/
713		public void testToArray() {
714	<	ArrayDeque q = populatedDeque(SIZE);
715	<	Object[] o = q.toArray();
716	<	Arrays.sort(o);
717	<	for(int i = 0; i < o.length; i++)
718	<	assertEquals(o[i], q.pollFirst());
714	>	final int size = ThreadLocalRandom.current().nextInt(10);
715	>	ArrayDeque<Item> q = new ArrayDeque<>(size);
716	>	for (int i = 0; i < size; i++) {
717	>	checkToArray(q);
718	>	q.addLast(itemFor(i));
719	>	}
720	>	// Provoke wraparound
721	>	int added = size * 2;
722	>	for (int i = 0; i < added; i++) {
723	>	checkToArray(q);
724	>	mustEqual(i, q.poll());
725	>	q.addLast(itemFor(size + i));
726	>	}
727	>	for (int i = 0; i < size; i++) {
728	>	checkToArray(q);
729	>	mustEqual((added + i), q.poll());
730	>	}
731		}
732
733		/**
734	<	*  toArray(a) contains all elements
734	>	* toArray(null) throws NullPointerException
735		*/
736	<	public void testToArray2() {
737	<	ArrayDeque q = populatedDeque(SIZE);
738	<	Integer[] ints = new Integer[SIZE];
739	<	ints = (Integer[])q.toArray(ints);
740	<	Arrays.sort(ints);
741	<	for(int i = 0; i < ints.length; i++)
742	<	assertEquals(ints[i], q.pollFirst());
736	>	public void testToArray_NullArg() {
737	>	ArrayDeque<Item> l = new ArrayDeque<Item>();
738	>	l.add(zero);
739	>	try {
740	>	l.toArray((Object[])null);
741	>	shouldThrow();
742	>	} catch (NullPointerException success) {}
743		}
744
745		/**
746	<	* toArray(null) throws NPE
746	>	* toArray(incompatible array type) throws ArrayStoreException
747		*/
748	<	public void testToArray_BadArg() {
749	<	try {
750	<	ArrayDeque l = new ArrayDeque();
751	<	l.add(new Object());
752	<	Object o[] = l.toArray(null);
753	<	shouldThrow();
754	<	} catch(NullPointerException success){}
748	>	public void testToArray_incompatibleArrayType() {
749	>	ArrayDeque<Item> l = new ArrayDeque<Item>();
750	>	l.add(five);
751	>	try {
752	>	l.toArray(new String[10]);
753	>	shouldThrow();
754	>	} catch (ArrayStoreException success) {}
755	>	try {
756	>	l.toArray(new String[0]);
757	>	shouldThrow();
758	>	} catch (ArrayStoreException success) {}
759		}
760
761		/**
762	<	* toArray with incompatable aray type throws CCE
762	>	* Iterator iterates through all elements
763		*/
764	<	public void testToArray1_BadArg() {
765	<	try {
766	<	ArrayDeque l = new ArrayDeque();
767	<	l.add(new Integer(5));
768	<	Object o[] = l.toArray(new String[10] );
769	<	shouldThrow();
770	<	} catch(ArrayStoreException  success){}
764	>	public void testIterator() {
765	>	ArrayDeque<Item> q = populatedDeque(SIZE);
766	>	Iterator<? extends Item> it = q.iterator();
767	>	int i;
768	>	for (i = 0; it.hasNext(); i++)
769	>	mustContain(q, it.next());
770	>	mustEqual(i, SIZE);
771	>	assertIteratorExhausted(it);
772		}
773	<
773	>
774		/**
775	<	*  iterator iterates through all elements
775	>	* iterator of empty collection has no elements
776		*/
777	<	public void testIterator() {
778	<	ArrayDeque q = populatedDeque(SIZE);
779	<	int i = 0;
780	<	Iterator it = q.iterator();
502	<	while(it.hasNext()) {
503	<	assertTrue(q.contains(it.next()));
504	<	++i;
505	<	}
506	<	assertEquals(i, SIZE);
777	>	public void testEmptyIterator() {
778	>	Deque<Item> c = new ArrayDeque<Item>();
779	>	assertIteratorExhausted(c.iterator());
780	>	assertIteratorExhausted(c.descendingIterator());
781		}
782
783		/**
784	<	*  iterator ordering is FIFO
784	>	* Iterator ordering is FIFO
785		*/
786		public void testIteratorOrdering() {
787	<	final ArrayDeque q = new ArrayDeque();
788	<	q.add(new Integer(1));
789	<	q.add(new Integer(2));
790	<	q.add(new Integer(3));
787	>	final ArrayDeque<Item> q = new ArrayDeque<Item>();
788	>	q.add(one);
789	>	q.add(two);
790	>	q.add(three);
791		int k = 0;
792	<	for (Iterator it = q.iterator(); it.hasNext();) {
793	<	int i = ((Integer)(it.next())).intValue();
520	<	assertEquals(++k, i);
792	>	for (Iterator<? extends Item> it = q.iterator(); it.hasNext();) {
793	>	mustEqual(++k, it.next());
794		}
795
796	<	assertEquals(3, k);
796	>	mustEqual(3, k);
797		}
798
799		/**
800	<	* iterator.remove removes current element
801	<	*/
802	<	public void testIteratorRemove () {
803	<	final ArrayDeque q = new ArrayDeque();
804	<	q.add(new Integer(1));
805	<	q.add(new Integer(2));
806	<	q.add(new Integer(3));
807	<	Iterator it = q.iterator();
808	<	it.next();
809	<	it.remove();
810	<	it = q.iterator();
811	<	assertEquals(it.next(), new Integer(2));
812	<	assertEquals(it.next(), new Integer(3));
813	<	assertFalse(it.hasNext());
800	>	* iterator.remove() removes current element
801	>	*/
802	>	public void testIteratorRemove() {
803	>	final ArrayDeque<Item> q = new ArrayDeque<Item>();
804	>	final Random rng = new Random();
805	>	for (int iters = 0; iters < 100; ++iters) {
806	>	int max = rng.nextInt(5) + 2;
807	>	int split = rng.nextInt(max - 1) + 1;
808	>	for (int j = 1; j <= max; ++j)
809	>	mustAdd(q, j);
810	>	Iterator<? extends Item> it = q.iterator();
811	>	for (int j = 1; j <= split; ++j)
812	>	mustEqual(it.next(), j);
813	>	it.remove();
814	>	mustEqual(it.next(), split + 1);
815	>	for (int j = 1; j <= split; ++j)
816	>	q.remove(itemFor(j));
817	>	it = q.iterator();
818	>	for (int j = split + 1; j <= max; ++j) {
819	>	mustEqual(it.next(), j);
820	>	it.remove();
821	>	}
822	>	assertFalse(it.hasNext());
823	>	assertTrue(q.isEmpty());
824	>	}
825		}
826
827		/**
828	<	*  Descending iterator iterates through all elements
828	>	* Descending iterator iterates through all elements
829		*/
830		public void testDescendingIterator() {
831	<	ArrayDeque q = populatedDeque(SIZE);
831	>	ArrayDeque<Item> q = populatedDeque(SIZE);
832		int i = 0;
833	<	Iterator it = q.descendingIterator();
834	<	while(it.hasNext()) {
835	<	assertTrue(q.contains(it.next()));
833	>	Iterator<? extends Item> it = q.descendingIterator();
834	>	while (it.hasNext()) {
835	>	mustContain(q, it.next());
836		++i;
837		}
838	<	assertEquals(i, SIZE);
838	>	mustEqual(i, SIZE);
839		assertFalse(it.hasNext());
840		try {
841		it.next();
842	<	} catch(NoSuchElementException success) {
843	<	}
842	>	shouldThrow();
843	>	} catch (NoSuchElementException success) {}
844		}
845
846		/**
847	<	*  Descending iterator ordering is reverse FIFO
847	>	* Descending iterator ordering is reverse FIFO
848		*/
849		public void testDescendingIteratorOrdering() {
850	<	final ArrayDeque q = new ArrayDeque();
851	<	q.add(new Integer(3));
852	<	q.add(new Integer(2));
853	<	q.add(new Integer(1));
854	<	int k = 0;
855	<	for (Iterator it = q.descendingIterator(); it.hasNext();) {
856	<	int i = ((Integer)(it.next())).intValue();
857	<	assertEquals(++k, i);
858	<	}
850	>	final ArrayDeque<Item> q = new ArrayDeque<Item>();
851	>	for (int iters = 0; iters < 100; ++iters) {
852	>	q.add(three);
853	>	q.add(two);
854	>	q.add(one);
855	>	int k = 0;
856	>	for (Iterator<? extends Item> it = q.descendingIterator(); it.hasNext();) {
857	>	mustEqual(++k, it.next());
858	>	}
859
860	<	assertEquals(3, k);
860	>	mustEqual(3, k);
861	>	q.remove();
862	>	q.remove();
863	>	q.remove();
864	>	}
865		}
866
867		/**
868	<	* descendingIterator.remove removes current element
868	>	* descendingIterator.remove() removes current element
869		*/
870	<	public void testDescendingIteratorRemove () {
871	<	final ArrayDeque q = new ArrayDeque();
872	<	q.add(new Integer(3));
873	<	q.add(new Integer(2));
874	<	q.add(new Integer(1));
875	<	Iterator it = q.descendingIterator();
876	<	it.next();
877	<	it.remove();
878	<	it = q.descendingIterator();
879	<	assertEquals(it.next(), new Integer(2));
880	<	assertEquals(it.next(), new Integer(3));
881	<	assertFalse(it.hasNext());
870	>	public void testDescendingIteratorRemove() {
871	>	final ArrayDeque<Item> q = new ArrayDeque<Item>();
872	>	final Random rng = new Random();
873	>	for (int iters = 0; iters < 100; ++iters) {
874	>	int max = rng.nextInt(5) + 2;
875	>	int split = rng.nextInt(max - 1) + 1;
876	>	for (int j = max; j >= 1; --j)
877	>	q.add(itemFor(j));
878	>	Iterator<? extends Item> it = q.descendingIterator();
879	>	for (int j = 1; j <= split; ++j)
880	>	mustEqual(it.next(), itemFor(j));
881	>	it.remove();
882	>	mustEqual(it.next(), itemFor(split + 1));
883	>	for (int j = 1; j <= split; ++j)
884	>	q.remove(itemFor(j));
885	>	it = q.descendingIterator();
886	>	for (int j = split + 1; j <= max; ++j) {
887	>	mustEqual(it.next(), j);
888	>	it.remove();
889	>	}
890	>	assertFalse(it.hasNext());
891	>	assertTrue(q.isEmpty());
892	>	}
893		}
894
596	–
895		/**
896	<	* toString contains toStrings of elements
896	>	* toString() contains toStrings of elements
897		*/
898		public void testToString() {
899	<	ArrayDeque q = populatedDeque(SIZE);
899	>	ArrayDeque<Item> q = populatedDeque(SIZE);
900		String s = q.toString();
901		for (int i = 0; i < SIZE; ++i) {
902	<	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
902	>	assertTrue(s.contains(String.valueOf(i)));
903		}
904	<	}
904	>	}
905
906		/**
907	<	* peekFirst returns element inserted with addFirst
907	>	* A deserialized/reserialized deque has same elements in same order
908		*/
909	<	public void testAddFirst() {
910	<	ArrayDeque q = populatedDeque(3);
911	<	q.addFirst(four);
912	<	assertEquals(four,q.peekFirst());
913	<	}
909	>	public void testSerialization() throws Exception {
910	>	Queue<Item> x = populatedDeque(SIZE);
911	>	Queue<Item> y = serialClone(x);
912	>
913	>	assertNotSame(y, x);
914	>	mustEqual(x.size(), y.size());
915	>	mustEqual(x.toString(), y.toString());
916	>	mustEqual(Arrays.toString(x.toArray()), Arrays.toString(y.toArray()));
917	>	assertTrue(Arrays.equals(x.toArray(), y.toArray()));
918	>	while (!x.isEmpty()) {
919	>	assertFalse(y.isEmpty());
920	>	mustEqual(x.remove(), y.remove());
921	>	}
922	>	assertTrue(y.isEmpty());
923	>	}
924
925		/**
926	<	* peekLast returns element inserted with addLast
926	>	* A cloned deque has same elements in same order
927		*/
928	<	public void testAddLast() {
929	<	ArrayDeque q = populatedDeque(3);
930	<	q.addLast(four);
931	<	assertEquals(four,q.peekLast());
932	<	}
928	>	public void testClone() throws Exception {
929	>	ArrayDeque<Item> x = populatedDeque(SIZE);
930	>	ArrayDeque<Item> y = x.clone();
931	>
932	>	assertNotSame(y, x);
933	>	mustEqual(x.size(), y.size());
934	>	mustEqual(x.toString(), y.toString());
935	>	assertTrue(Arrays.equals(x.toArray(), y.toArray()));
936	>	while (!x.isEmpty()) {
937	>	assertFalse(y.isEmpty());
938	>	mustEqual(x.remove(), y.remove());
939	>	}
940	>	assertTrue(y.isEmpty());
941	>	}
942	>
943	>	/**
944	>	* remove(null), contains(null) always return false
945	>	*/
946	>	public void testNeverContainsNull() {
947	>	Deque<?>[] qs = {
948	>	new ArrayDeque<Object>(),
949	>	populatedDeque(2),
950	>	};
951	>
952	>	for (Deque<?> q : qs) {
953	>	assertFalse(q.contains(null));
954	>	assertFalse(q.remove(null));
955	>	assertFalse(q.removeFirstOccurrence(null));
956	>	assertFalse(q.removeLastOccurrence(null));
957	>	}
958	>	}
959
960		}

Diff Legend

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