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