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