ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/ArrayDequeTest.java
Revision: 1.61
Committed: Wed Jan 27 02:55:18 2021 UTC (3 years, 2 months ago) by jsr166
Branch: MAIN
CVS Tags: HEAD
Changes since 1.60: +1 -0 lines
Log Message:
Suppress all new errorprone "errors"

File Contents

# Content
1 /*
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 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 main(suite(), args);
23 }
24
25 public static Test suite() {
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 * 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<>(); break;
48 case 1: q = new ArrayDeque<>(0); break;
49 case 2: q = new ArrayDeque<>(1); break;
50 case 3: q = new ArrayDeque<>(Math.max(0, n - 1)); break;
51 case 4: q = new ArrayDeque<>(n); break;
52 case 5: q = new ArrayDeque<>(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 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
83 /**
84 * new deque is empty
85 */
86 public void testConstructor1() {
87 mustEqual(0, new ArrayDeque<Item>().size());
88 }
89
90 /**
91 * Initializing from null Collection throws NPE
92 */
93 public void testConstructor3() {
94 try {
95 new ArrayDeque<Object>((Collection<Object>)null);
96 shouldThrow();
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 * 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 Item[] items = defaultItems;
126 ArrayDeque<Item> q = new ArrayDeque<>(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<Item> q = new ArrayDeque<>();
136 assertTrue(q.isEmpty());
137 q.add(one);
138 assertFalse(q.isEmpty());
139 q.add(two);
140 q.removeFirst();
141 q.removeFirst();
142 assertTrue(q.isEmpty());
143 }
144
145 /**
146 * size changes when elements added and removed
147 */
148 public void testSize() {
149 ArrayDeque<Item> q = populatedDeque(SIZE);
150 for (int i = 0; i < SIZE; ++i) {
151 mustEqual(SIZE - i, q.size());
152 q.removeFirst();
153 }
154 for (int i = 0; i < SIZE; ++i) {
155 mustEqual(i, q.size());
156 mustAdd(q, i);
157 }
158 }
159
160 /**
161 * push(null) throws NPE
162 */
163 public void testPushNull() {
164 ArrayDeque<Item> q = new ArrayDeque<>(1);
165 try {
166 q.push(null);
167 shouldThrow();
168 } catch (NullPointerException success) {}
169 }
170
171 /**
172 * peekFirst() returns element inserted with push
173 */
174 public void testPush() {
175 ArrayDeque<Item> q = populatedDeque(3);
176 q.pollLast();
177 q.push(four);
178 assertSame(four, q.peekFirst());
179 }
180
181 /**
182 * pop() removes next element, or throws NSEE if empty
183 */
184 public void testPop() {
185 ArrayDeque<Item> q = populatedDeque(SIZE);
186 for (int i = 0; i < SIZE; ++i) {
187 mustEqual(i, q.pop());
188 }
189 try {
190 q.pop();
191 shouldThrow();
192 } catch (NoSuchElementException success) {}
193 }
194
195 /**
196 * offer(null) throws NPE
197 */
198 public void testOfferNull() {
199 ArrayDeque<Item> q = new ArrayDeque<>();
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 ArrayDeque<Item> q = new ArrayDeque<>();
211 try {
212 q.offerFirst(null);
213 shouldThrow();
214 } catch (NullPointerException success) {}
215 }
216
217 /**
218 * offerLast(null) throws NPE
219 */
220 public void testOfferLastNull() {
221 ArrayDeque<Item> q = new ArrayDeque<>();
222 try {
223 q.offerLast(null);
224 shouldThrow();
225 } catch (NullPointerException success) {}
226 }
227
228 /**
229 * offer(x) succeeds
230 */
231 public void testOffer() {
232 ArrayDeque<Item> q = new ArrayDeque<>();
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<Item> q = new ArrayDeque<>();
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(x) succeeds
252 */
253 public void testOfferLast() {
254 ArrayDeque<Item> q = new ArrayDeque<>();
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<>();
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<>();
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<>();
288 try {
289 q.addLast(null);
290 shouldThrow();
291 } catch (NullPointerException success) {}
292 }
293
294 /**
295 * add(x) succeeds
296 */
297 public void testAdd() {
298 ArrayDeque<Item> q = new ArrayDeque<>();
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<>();
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<>();
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<>();
332 try {
333 q.addAll(null);
334 shouldThrow();
335 } catch (NullPointerException success) {}
336 }
337
338 /**
339 * addAll of a collection with null elements throws NPE
340 */
341 public void testAddAll2() {
342 ArrayDeque<Item> q = new ArrayDeque<>();
343 try {
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<>();
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 * 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<>();
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<Item> q = populatedDeque(SIZE);
380 for (int i = 0; i < SIZE; ++i) {
381 mustEqual(i, q.pollFirst());
382 }
383 assertNull(q.pollFirst());
384 }
385
386 /**
387 * pollLast() succeeds unless empty
388 */
389 public void testPollLast() {
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());
395 }
396
397 /**
398 * poll() succeeds unless empty
399 */
400 public void testPoll() {
401 ArrayDeque<Item> q = populatedDeque(SIZE);
402 for (int i = 0; i < SIZE; ++i) {
403 mustEqual(i, q.poll());
404 }
405 assertNull(q.poll());
406 }
407
408 /**
409 * remove() removes next element, or throws NSEE if empty
410 */
411 public void testRemove() {
412 ArrayDeque<Item> q = populatedDeque(SIZE);
413 for (int i = 0; i < SIZE; ++i) {
414 mustEqual(i, q.remove());
415 }
416 try {
417 q.remove();
418 shouldThrow();
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
445 */
446 public void testPeekFirst() {
447 ArrayDeque<Item> q = populatedDeque(SIZE);
448 for (int i = 0; i < SIZE; ++i) {
449 mustEqual(i, q.peekFirst());
450 mustEqual(i, q.pollFirst());
451 assertTrue(q.peekFirst() == null ||
452 !q.peekFirst().equals(i));
453 }
454 assertNull(q.peekFirst());
455 }
456
457 /**
458 * peek() returns next element, or null if empty
459 */
460 public void testPeek() {
461 ArrayDeque<Item> q = populatedDeque(SIZE);
462 for (int i = 0; i < SIZE; ++i) {
463 mustEqual(i, q.peek());
464 mustEqual(i, q.poll());
465 assertTrue(q.peek() == null ||
466 !q.peek().equals(i));
467 }
468 assertNull(q.peek());
469 }
470
471 /**
472 * peekLast() returns next element, or null if empty
473 */
474 public void testPeekLast() {
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 !q.peekLast().equals(i));
481 }
482 assertNull(q.peekLast());
483 }
484
485 /**
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<Item> q = populatedDeque(SIZE);
505 for (int i = 0; i < SIZE; ++i) {
506 mustEqual(i, q.getFirst());
507 mustEqual(i, q.pollFirst());
508 }
509 try {
510 q.getFirst();
511 shouldThrow();
512 } catch (NoSuchElementException success) {}
513 }
514
515 /**
516 * getLast() returns last element, or throws NSEE if empty
517 */
518 public void testLastElement() {
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 } catch (NoSuchElementException success) {}
528 assertNull(q.peekLast());
529 }
530
531 /**
532 * removeFirst() removes first element, or throws NSEE if empty
533 */
534 public void testRemoveFirst() {
535 ArrayDeque<Item> q = populatedDeque(SIZE);
536 for (int i = 0; i < SIZE; ++i) {
537 mustEqual(i, q.removeFirst());
538 }
539 try {
540 q.removeFirst();
541 shouldThrow();
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 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<>();
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 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<>();
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<Item> q = populatedDeque(SIZE);
614 for (int i = 0; i < SIZE; ++i) {
615 mustContain(q, i);
616 mustEqual(i, q.pollFirst());
617 mustNotContain(q, i);
618 }
619 }
620
621 /**
622 * clear removes all elements
623 */
624 public void testClear() {
625 ArrayDeque<Item> q = populatedDeque(SIZE);
626 q.clear();
627 assertTrue(q.isEmpty());
628 mustEqual(0, q.size());
629 mustAdd(q, one);
630 assertFalse(q.isEmpty());
631 q.clear();
632 assertTrue(q.isEmpty());
633 }
634
635 /**
636 * containsAll(c) is true when c contains a subset of elements
637 */
638 public void testContainsAll() {
639 ArrayDeque<Item> q = populatedDeque(SIZE);
640 ArrayDeque<Item> p = new ArrayDeque<>();
641 for (int i = 0; i < SIZE; ++i) {
642 assertTrue(q.containsAll(p));
643 assertFalse(p.containsAll(q));
644 mustAdd(p, i);
645 }
646 assertTrue(p.containsAll(q));
647 }
648
649 /**
650 * retainAll(c) retains only those elements of c and reports true if changed
651 */
652 public void testRetainAll() {
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 mustEqual(changed, (i > 0));
658 assertTrue(q.containsAll(p));
659 mustEqual(SIZE - i, q.size());
660 p.removeFirst();
661 }
662 }
663
664 /**
665 * removeAll(c) removes only those elements of c and reports true if changed
666 */
667 public void testRemoveAll() {
668 for (int i = 1; i < SIZE; ++i) {
669 ArrayDeque<Item> q = populatedDeque(SIZE);
670 ArrayDeque<Item> p = populatedDeque(i);
671 assertTrue(q.removeAll(p));
672 mustEqual(SIZE - i, q.size());
673 for (int j = 0; j < i; ++j) {
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() and toArray(a) contain all elements in FIFO order
712 */
713 public void testToArray() {
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(null) throws NullPointerException
735 */
736 public void testToArray_NullArg() {
737 ArrayDeque<Item> l = new ArrayDeque<>();
738 l.add(zero);
739 try {
740 l.toArray((Object[])null);
741 shouldThrow();
742 } catch (NullPointerException success) {}
743 }
744
745 /**
746 * toArray(incompatible array type) throws ArrayStoreException
747 */
748 @SuppressWarnings("CollectionToArraySafeParameter")
749 public void testToArray_incompatibleArrayType() {
750 ArrayDeque<Item> l = new ArrayDeque<>();
751 l.add(five);
752 try {
753 l.toArray(new String[10]);
754 shouldThrow();
755 } catch (ArrayStoreException success) {}
756 try {
757 l.toArray(new String[0]);
758 shouldThrow();
759 } catch (ArrayStoreException success) {}
760 }
761
762 /**
763 * Iterator iterates through all elements
764 */
765 public void testIterator() {
766 ArrayDeque<Item> q = populatedDeque(SIZE);
767 Iterator<? extends Item> it = q.iterator();
768 int i;
769 for (i = 0; it.hasNext(); i++)
770 mustContain(q, it.next());
771 mustEqual(i, SIZE);
772 assertIteratorExhausted(it);
773 }
774
775 /**
776 * iterator of empty collection has no elements
777 */
778 public void testEmptyIterator() {
779 Deque<Item> c = new ArrayDeque<>();
780 assertIteratorExhausted(c.iterator());
781 assertIteratorExhausted(c.descendingIterator());
782 }
783
784 /**
785 * Iterator ordering is FIFO
786 */
787 public void testIteratorOrdering() {
788 final ArrayDeque<Item> q = new ArrayDeque<>();
789 q.add(one);
790 q.add(two);
791 q.add(three);
792 int k = 0;
793 for (Iterator<? extends Item> it = q.iterator(); it.hasNext();) {
794 mustEqual(++k, it.next());
795 }
796
797 mustEqual(3, k);
798 }
799
800 /**
801 * iterator.remove() removes current element
802 */
803 public void testIteratorRemove() {
804 final ArrayDeque<Item> q = new ArrayDeque<>();
805 final Random rng = new Random();
806 for (int iters = 0; iters < 100; ++iters) {
807 int max = rng.nextInt(5) + 2;
808 int split = rng.nextInt(max - 1) + 1;
809 for (int j = 1; j <= max; ++j)
810 mustAdd(q, j);
811 Iterator<? extends Item> it = q.iterator();
812 for (int j = 1; j <= split; ++j)
813 mustEqual(it.next(), j);
814 it.remove();
815 mustEqual(it.next(), split + 1);
816 for (int j = 1; j <= split; ++j)
817 q.remove(itemFor(j));
818 it = q.iterator();
819 for (int j = split + 1; j <= max; ++j) {
820 mustEqual(it.next(), j);
821 it.remove();
822 }
823 assertFalse(it.hasNext());
824 assertTrue(q.isEmpty());
825 }
826 }
827
828 /**
829 * Descending iterator iterates through all elements
830 */
831 public void testDescendingIterator() {
832 ArrayDeque<Item> q = populatedDeque(SIZE);
833 int i = 0;
834 Iterator<? extends Item> it = q.descendingIterator();
835 while (it.hasNext()) {
836 mustContain(q, it.next());
837 ++i;
838 }
839 mustEqual(i, SIZE);
840 assertFalse(it.hasNext());
841 try {
842 it.next();
843 shouldThrow();
844 } catch (NoSuchElementException success) {}
845 }
846
847 /**
848 * Descending iterator ordering is reverse FIFO
849 */
850 public void testDescendingIteratorOrdering() {
851 final ArrayDeque<Item> q = new ArrayDeque<>();
852 for (int iters = 0; iters < 100; ++iters) {
853 q.add(three);
854 q.add(two);
855 q.add(one);
856 int k = 0;
857 for (Iterator<? extends Item> it = q.descendingIterator(); it.hasNext();) {
858 mustEqual(++k, it.next());
859 }
860
861 mustEqual(3, k);
862 q.remove();
863 q.remove();
864 q.remove();
865 }
866 }
867
868 /**
869 * descendingIterator.remove() removes current element
870 */
871 public void testDescendingIteratorRemove() {
872 final ArrayDeque<Item> q = new ArrayDeque<>();
873 final Random rng = new Random();
874 for (int iters = 0; iters < 100; ++iters) {
875 int max = rng.nextInt(5) + 2;
876 int split = rng.nextInt(max - 1) + 1;
877 for (int j = max; j >= 1; --j)
878 q.add(itemFor(j));
879 Iterator<? extends Item> it = q.descendingIterator();
880 for (int j = 1; j <= split; ++j)
881 mustEqual(it.next(), itemFor(j));
882 it.remove();
883 mustEqual(it.next(), itemFor(split + 1));
884 for (int j = 1; j <= split; ++j)
885 q.remove(itemFor(j));
886 it = q.descendingIterator();
887 for (int j = split + 1; j <= max; ++j) {
888 mustEqual(it.next(), j);
889 it.remove();
890 }
891 assertFalse(it.hasNext());
892 assertTrue(q.isEmpty());
893 }
894 }
895
896 /**
897 * toString() contains toStrings of elements
898 */
899 public void testToString() {
900 ArrayDeque<Item> q = populatedDeque(SIZE);
901 String s = q.toString();
902 for (int i = 0; i < SIZE; ++i) {
903 assertTrue(s.contains(String.valueOf(i)));
904 }
905 }
906
907 /**
908 * A deserialized/reserialized deque has same elements in same order
909 */
910 public void testSerialization() throws Exception {
911 Queue<Item> x = populatedDeque(SIZE);
912 Queue<Item> y = serialClone(x);
913
914 assertNotSame(y, x);
915 mustEqual(x.size(), y.size());
916 mustEqual(x.toString(), y.toString());
917 mustEqual(Arrays.toString(x.toArray()), Arrays.toString(y.toArray()));
918 assertTrue(Arrays.equals(x.toArray(), y.toArray()));
919 while (!x.isEmpty()) {
920 assertFalse(y.isEmpty());
921 mustEqual(x.remove(), y.remove());
922 }
923 assertTrue(y.isEmpty());
924 }
925
926 /**
927 * A cloned deque has same elements in same order
928 */
929 public void testClone() throws Exception {
930 ArrayDeque<Item> x = populatedDeque(SIZE);
931 ArrayDeque<Item> y = x.clone();
932
933 assertNotSame(y, x);
934 mustEqual(x.size(), y.size());
935 mustEqual(x.toString(), y.toString());
936 assertTrue(Arrays.equals(x.toArray(), y.toArray()));
937 while (!x.isEmpty()) {
938 assertFalse(y.isEmpty());
939 mustEqual(x.remove(), y.remove());
940 }
941 assertTrue(y.isEmpty());
942 }
943
944 /**
945 * remove(null), contains(null) always return false
946 */
947 public void testNeverContainsNull() {
948 Deque<?>[] qs = {
949 new ArrayDeque<>(),
950 populatedDeque(2),
951 };
952
953 for (Deque<?> q : qs) {
954 assertFalse(q.contains(null));
955 assertFalse(q.remove(null));
956 assertFalse(q.removeFirstOccurrence(null));
957 assertFalse(q.removeLastOccurrence(null));
958 }
959 }
960
961 }