1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17
18package org.apache.harmony.tests.java.util;
19
20import java.io.Serializable;
21import java.util.ArrayDeque;
22import java.util.ArrayList;
23import java.util.Arrays;
24import java.util.ConcurrentModificationException;
25import java.util.Iterator;
26import java.util.LinkedList;
27import java.util.NoSuchElementException;
28import java.util.Spliterator;
29
30import junit.framework.TestCase;
31
32import libcore.java.util.ForEachRemainingTester;
33import libcore.java.util.SpliteratorTester;
34import org.apache.harmony.testframework.serialization.SerializationTest;
35import org.apache.harmony.testframework.serialization.SerializationTest.SerializableAssert;
36
37public class ArrayDequeTest extends TestCase {
38
39    private Object testObjOne;
40
41    private Object testObjTwo;
42
43    private Object testObjThree;
44
45    private Object testObjFour;
46
47    private Object testObjLast;
48
49    private ArrayDeque<Object> testQue;
50
51    @Override
52    protected void setUp() throws Exception {
53        super.setUp();
54        testObjOne = new Object();
55        testObjTwo = new Object();
56        testObjThree = new Object();
57        testObjFour = new Object();
58        testObjLast = new Object();
59        testQue = new ArrayDeque<Object>();
60    }
61
62    /**
63     * {@link java.util.ArrayDeque#ArrayDeque()}
64     */
65    public void test_Constructor() throws Exception {
66        assertEquals(0, new ArrayDeque<Object>().size());
67    }
68
69    /**
70     * {@link java.util.ArrayDeque#ArrayDeque(java.util.Collection)}
71     */
72    public void test_Constructor_LCollection() throws Exception {
73        assertEquals(0, new ArrayDeque<Object>(new ArrayList<Object>()).size());
74        try {
75            new ArrayDeque<Object>(null);
76            fail("should throw NPE");
77        } catch (NullPointerException e) {
78            // expected
79        }
80    }
81
82    /**
83     * {@link java.util.ArrayDeque#ArrayDeque(int)}
84     */
85    public void test_Constructor_Int() throws Exception {
86        assertEquals(0, new ArrayDeque<Object>(8).size());
87        ArrayDeque<Object> zeroCapQue = new ArrayDeque<Object>(0);
88        assertEquals(0, zeroCapQue.size());
89        zeroCapQue.add(testObjOne);
90        assertEquals(1, zeroCapQue.size());
91        assertEquals(0, new ArrayDeque<Object>(0).size());
92        ArrayDeque<Object> negCapQue = new ArrayDeque<Object>(-1);
93        assertEquals(0, negCapQue.size());
94        negCapQue.add(testObjOne);
95        assertEquals(1, negCapQue.size());
96        ArrayDeque<Object> oneCapQue = new ArrayDeque<Object>(1);
97        assertEquals(0, oneCapQue.size());
98        oneCapQue.add(testObjOne);
99        assertEquals(1, oneCapQue.size());
100        oneCapQue.add(testObjOne);
101        assertEquals(2, oneCapQue.size());
102    }
103
104    /**
105     * {@link java.util.ArrayDeque#addFirst(Object)}
106     */
107    public void test_addFirst() throws Exception {
108        testQue.addFirst(testObjOne);
109        assertEquals(1, testQue.size());
110        assertEquals(testObjOne, testQue.peek());
111        testQue.addFirst(testObjOne);
112        assertEquals(2, testQue.size());
113        assertEquals(testObjOne, testQue.peek());
114        testQue.addFirst(testObjTwo);
115        assertEquals(3, testQue.size());
116        assertEquals(testObjTwo, testQue.peek());
117        assertEquals(testObjOne, testQue.getLast());
118        try {
119            testQue.addFirst(null);
120            fail("should throw NullPointerException");
121        } catch (NullPointerException e) {
122            // expected
123        }
124    }
125
126    /**
127     * {@link java.util.ArrayDeque#addLast(Object)}
128     */
129    public void test_addLast() throws Exception {
130        testQue.addLast(testObjOne);
131        assertEquals(1, testQue.size());
132        assertEquals(testObjOne, testQue.peek());
133        testQue.addLast(testObjOne);
134        assertEquals(2, testQue.size());
135        assertEquals(testObjOne, testQue.peek());
136        testQue.addLast(testObjTwo);
137        assertEquals(3, testQue.size());
138        assertEquals(testObjOne, testQue.peek());
139        assertEquals(testObjTwo, testQue.getLast());
140        try {
141            testQue.addLast(null);
142            fail("should throw NullPointerException");
143        } catch (NullPointerException e) {
144            // expected
145        }
146    }
147
148    /**
149     * {@link java.util.ArrayDeque#offerFirst(Object)}
150     */
151    public void test_offerFirst() throws Exception {
152        assertTrue(testQue.offerFirst(testObjOne));
153        assertEquals(1, testQue.size());
154        assertEquals(testObjOne, testQue.peek());
155        assertTrue(testQue.offerFirst(testObjOne));
156        assertEquals(2, testQue.size());
157        assertEquals(testObjOne, testQue.peek());
158        assertTrue(testQue.offerFirst(testObjTwo));
159        assertEquals(3, testQue.size());
160        assertEquals(testObjTwo, testQue.peek());
161        assertEquals(testObjOne, testQue.getLast());
162        try {
163            testQue.offerFirst(null);
164            fail("should throw NullPointerException");
165        } catch (NullPointerException e) {
166            // expected
167        }
168    }
169
170    /**
171     * {@link java.util.ArrayDeque#offerLast(Object)}
172     */
173    public void test_offerLast() throws Exception {
174        assertTrue(testQue.offerLast(testObjOne));
175        assertEquals(1, testQue.size());
176        assertEquals(testObjOne, testQue.peek());
177        assertTrue(testQue.offerLast(testObjOne));
178        assertEquals(2, testQue.size());
179        assertEquals(testObjOne, testQue.peek());
180        assertTrue(testQue.offerLast(testObjTwo));
181        assertEquals(3, testQue.size());
182        assertEquals(testObjOne, testQue.peek());
183        assertEquals(testObjTwo, testQue.getLast());
184        try {
185            testQue.offerLast(null);
186            fail("should throw NullPointerException");
187        } catch (NullPointerException e) {
188            // expected
189        }
190    }
191
192    /**
193     * {@link java.util.ArrayDeque#removeFirst()}
194     */
195    public void test_removeFirst() throws Exception {
196        assertTrue(testQue.offerLast(testObjOne));
197        assertTrue(testQue.offerLast(testObjTwo));
198        assertTrue(testQue.offerLast(testObjThree));
199        assertEquals(3, testQue.size());
200        assertEquals(testObjOne, testQue.removeFirst());
201        assertEquals(2, testQue.size());
202        assertEquals(testObjTwo, testQue.removeFirst());
203        assertEquals(testObjThree, testQue.removeFirst());
204        assertEquals(0, testQue.size());
205        try {
206            testQue.removeFirst();
207            fail("should throw NoSuchElementException ");
208        } catch (NoSuchElementException e) {
209            // expected
210        }
211    }
212
213    /**
214     * {@link java.util.ArrayDeque#removeLast()}
215     */
216    public void test_removeLast() throws Exception {
217        assertTrue(testQue.offerLast(testObjOne));
218        assertTrue(testQue.offerLast(testObjTwo));
219        assertTrue(testQue.offerLast(testObjThree));
220        assertEquals(3, testQue.size());
221        assertEquals(testObjThree, testQue.removeLast());
222        assertEquals(2, testQue.size());
223        assertEquals(testObjTwo, testQue.removeLast());
224        assertEquals(testObjOne, testQue.removeLast());
225        assertEquals(0, testQue.size());
226        try {
227            testQue.removeLast();
228            fail("should throw NoSuchElementException ");
229        } catch (NoSuchElementException e) {
230            // expected
231        }
232    }
233
234    /**
235     * {@link java.util.ArrayDeque#pollFirst()}
236     */
237    public void test_pollFirst() throws Exception {
238        assertTrue(testQue.offerLast(testObjOne));
239        assertTrue(testQue.offerLast(testObjTwo));
240        assertTrue(testQue.offerLast(testObjThree));
241        assertEquals(3, testQue.size());
242        assertEquals(testObjOne, testQue.pollFirst());
243        assertEquals(2, testQue.size());
244        assertEquals(testObjTwo, testQue.pollFirst());
245        assertEquals(testObjThree, testQue.pollFirst());
246        assertEquals(0, testQue.size());
247        assertNull(testQue.pollFirst());
248    }
249
250    /**
251     * {@link java.util.ArrayDeque#peekLast()}
252     */
253    public void test_pollLast() throws Exception {
254        assertTrue(testQue.offerLast(testObjOne));
255        assertTrue(testQue.offerLast(testObjTwo));
256        assertTrue(testQue.offerLast(testObjThree));
257        assertEquals(3, testQue.size());
258        assertEquals(testObjThree, testQue.pollLast());
259        assertEquals(2, testQue.size());
260        assertEquals(testObjTwo, testQue.pollLast());
261        assertEquals(testObjOne, testQue.pollLast());
262        assertEquals(0, testQue.size());
263        assertNull(testQue.pollFirst());
264    }
265
266    /**
267     * {@link java.util.ArrayDeque#getFirst()}
268     */
269    public void test_getFirst() throws Exception {
270        assertTrue(testQue.offerLast(testObjOne));
271        assertTrue(testQue.offerLast(testObjTwo));
272        assertTrue(testQue.offerLast(testObjThree));
273        assertEquals(3, testQue.size());
274        assertEquals(testObjOne, testQue.getFirst());
275        assertEquals(3, testQue.size());
276        assertEquals(testObjOne, testQue.pollFirst());
277        assertEquals(testObjTwo, testQue.getFirst());
278        assertEquals(testObjTwo, testQue.pollFirst());
279        assertEquals(testObjThree, testQue.pollFirst());
280        assertEquals(0, testQue.size());
281        try {
282            testQue.getFirst();
283            fail("should throw NoSuchElementException ");
284        } catch (NoSuchElementException e) {
285            // expected
286        }
287    }
288
289    /**
290     * {@link java.util.ArrayDeque#getLast()}
291     */
292    public void test_getLast() throws Exception {
293        assertTrue(testQue.offerLast(testObjOne));
294        assertTrue(testQue.offerLast(testObjTwo));
295        assertTrue(testQue.offerLast(testObjThree));
296        assertEquals(3, testQue.size());
297        assertEquals(testObjThree, testQue.getLast());
298        assertEquals(3, testQue.size());
299        assertEquals(testObjThree, testQue.pollLast());
300        assertEquals(testObjTwo, testQue.getLast());
301        assertEquals(testObjTwo, testQue.pollLast());
302        assertEquals(testObjOne, testQue.pollLast());
303        assertEquals(0, testQue.size());
304        try {
305            testQue.getLast();
306            fail("should throw NoSuchElementException ");
307        } catch (NoSuchElementException e) {
308            // expected
309        }
310    }
311
312    /**
313     * {@link java.util.ArrayDeque#peekFirst()}
314     */
315    public void test_peekFirst() throws Exception {
316        assertTrue(testQue.offerLast(testObjOne));
317        assertTrue(testQue.offerLast(testObjTwo));
318        assertTrue(testQue.offerLast(testObjThree));
319        assertEquals(3, testQue.size());
320        assertEquals(testObjOne, testQue.peekFirst());
321        assertEquals(3, testQue.size());
322        assertEquals(testObjOne, testQue.pollFirst());
323        assertEquals(testObjTwo, testQue.peekFirst());
324        assertEquals(testObjTwo, testQue.pollFirst());
325        assertEquals(testObjThree, testQue.pollFirst());
326        assertEquals(0, testQue.size());
327        assertEquals(null, testQue.peekFirst());
328    }
329
330    /**
331     * {@link java.util.ArrayDeque#peekLast()}
332     */
333    public void test_peekLast() throws Exception {
334        assertTrue(testQue.offerLast(testObjOne));
335        assertTrue(testQue.offerLast(testObjTwo));
336        assertTrue(testQue.offerLast(testObjThree));
337        assertEquals(3, testQue.size());
338        assertEquals(testObjThree, testQue.peekLast());
339        assertEquals(3, testQue.size());
340        assertEquals(testObjThree, testQue.pollLast());
341        assertEquals(testObjTwo, testQue.peekLast());
342        assertEquals(testObjTwo, testQue.pollLast());
343        assertEquals(testObjOne, testQue.pollLast());
344        assertEquals(0, testQue.size());
345        assertNull(testQue.peekLast());
346    }
347
348    /**
349     * {@link java.util.ArrayDeque#removeFirstOccurrence(Object)}
350     */
351    public void test_removeFirstOccurrence() throws Exception {
352        assertTrue(testQue.offerLast(testObjOne));
353        assertTrue(testQue.offerLast(testObjTwo));
354        assertTrue(testQue.offerLast(testObjOne));
355        assertTrue(testQue.offerLast(testObjThree));
356        assertTrue(testQue.offerLast(testObjOne));
357        assertEquals(5, testQue.size());
358        assertTrue(testQue.removeFirstOccurrence(testObjOne));
359        assertFalse(testQue.removeFirstOccurrence(testObjFour));
360        assertEquals(testObjTwo, testQue.peekFirst());
361        assertEquals(testObjOne, testQue.peekLast());
362        assertEquals(4, testQue.size());
363        assertTrue(testQue.removeFirstOccurrence(testObjOne));
364        assertEquals(3, testQue.size());
365        assertEquals(testObjOne, testQue.peekLast());
366        assertTrue(testQue.removeFirstOccurrence(testObjOne));
367        assertEquals(2, testQue.size());
368        assertEquals(testObjThree, testQue.peekLast());
369        assertFalse(testQue.removeFirstOccurrence(testObjOne));
370    }
371
372    /**
373     * {@link java.util.ArrayDeque#removeLastOccurrence(Object)}
374     */
375    public void test_removeLastOccurrence() throws Exception {
376        assertTrue(testQue.offerLast(testObjOne));
377        assertTrue(testQue.offerLast(testObjTwo));
378        assertTrue(testQue.offerLast(testObjOne));
379        assertTrue(testQue.offerLast(testObjThree));
380        assertTrue(testQue.offerLast(testObjOne));
381        assertEquals(5, testQue.size());
382        assertTrue(testQue.removeLastOccurrence(testObjOne));
383        assertFalse(testQue.removeLastOccurrence(testObjFour));
384        assertEquals(testObjOne, testQue.peekFirst());
385        assertEquals(testObjThree, testQue.peekLast());
386        assertEquals(4, testQue.size());
387        assertTrue(testQue.removeLastOccurrence(testObjOne));
388        assertEquals(3, testQue.size());
389        assertEquals(testObjOne, testQue.peekFirst());
390        assertEquals(testObjThree, testQue.peekLast());
391        assertTrue(testQue.removeLastOccurrence(testObjOne));
392        assertEquals(2, testQue.size());
393        assertEquals(testObjThree, testQue.peekLast());
394        assertFalse(testQue.removeLastOccurrence(testObjOne));
395    }
396
397    /**
398     * {@link java.util.ArrayDeque#add(Object)}
399     */
400    public void test_add() throws Exception {
401        assertTrue(testQue.add(testObjOne));
402        assertTrue(testQue.add(testObjTwo));
403        assertTrue(testQue.add(testObjOne));
404        assertTrue(testQue.add(testObjThree));
405        assertEquals(testObjOne, testQue.peekFirst());
406        assertEquals(testObjThree, testQue.peekLast());
407        try {
408            testQue.add(null);
409            fail("Should throw NullPointerException");
410        } catch (NullPointerException e) {
411            // expected
412        }
413    }
414
415    /**
416     * {@link java.util.ArrayDeque#offer(Object)}
417     */
418    public void test_offer() throws Exception {
419        assertTrue(testQue.offer(testObjOne));
420        assertTrue(testQue.offer(testObjTwo));
421        assertTrue(testQue.offer(testObjOne));
422        assertTrue(testQue.offer(testObjThree));
423        assertEquals(testObjOne, testQue.peekFirst());
424        assertEquals(testObjThree, testQue.peekLast());
425        try {
426            testQue.offer(null);
427            fail("Should throw NullPointerException");
428        } catch (NullPointerException e) {
429            // expected
430        }
431    }
432
433    /**
434     * {@link java.util.ArrayDeque#remove()}
435     */
436    public void test_remove() throws Exception {
437        assertTrue(testQue.offerLast(testObjOne));
438        assertTrue(testQue.offerLast(testObjTwo));
439        assertTrue(testQue.offerLast(testObjThree));
440        assertEquals(3, testQue.size());
441        assertEquals(testObjOne, testQue.remove());
442        assertEquals(2, testQue.size());
443        assertEquals(testObjTwo, testQue.remove());
444        assertEquals(testObjThree, testQue.remove());
445        assertEquals(0, testQue.size());
446        try {
447            testQue.remove();
448            fail("should throw NoSuchElementException ");
449        } catch (NoSuchElementException e) {
450            // expected
451        }
452    }
453
454    /**
455     * {@link java.util.ArrayDeque#poll()}
456     */
457    public void test_poll() throws Exception {
458        assertTrue(testQue.offerLast(testObjOne));
459        assertTrue(testQue.offerLast(testObjTwo));
460        assertTrue(testQue.offerLast(testObjThree));
461        assertEquals(3, testQue.size());
462        assertEquals(testObjOne, testQue.poll());
463        assertEquals(2, testQue.size());
464        assertEquals(testObjTwo, testQue.poll());
465        assertEquals(testObjThree, testQue.poll());
466        assertEquals(0, testQue.size());
467        assertNull(testQue.poll());
468    }
469
470    /**
471     * {@link java.util.ArrayDeque#element()}
472     */
473    public void test_element() throws Exception {
474        assertTrue(testQue.offerLast(testObjOne));
475        assertTrue(testQue.offerLast(testObjTwo));
476        assertTrue(testQue.offerLast(testObjThree));
477        assertEquals(3, testQue.size());
478        assertEquals(testObjOne, testQue.element());
479        assertEquals(3, testQue.size());
480        assertEquals(testObjOne, testQue.pollFirst());
481        assertEquals(testObjTwo, testQue.element());
482        assertEquals(testObjTwo, testQue.pollFirst());
483        assertEquals(testObjThree, testQue.element());
484        assertEquals(testObjThree, testQue.pollFirst());
485        assertEquals(0, testQue.size());
486        try {
487            testQue.element();
488            fail("should throw NoSuchElementException ");
489        } catch (NoSuchElementException e) {
490            // expected
491        }
492    }
493
494    /**
495     * {@link java.util.ArrayDeque#peek()}
496     */
497    public void test_peek() throws Exception {
498        assertTrue(testQue.offerLast(testObjOne));
499        assertTrue(testQue.offerLast(testObjTwo));
500        assertTrue(testQue.offerLast(testObjThree));
501        assertEquals(3, testQue.size());
502        assertEquals(testObjOne, testQue.peek());
503        assertEquals(3, testQue.size());
504        assertEquals(testObjOne, testQue.pollFirst());
505        assertEquals(testObjTwo, testQue.peek());
506        assertEquals(testObjTwo, testQue.pollFirst());
507        assertEquals(testObjThree, testQue.pollFirst());
508        assertEquals(0, testQue.size());
509        assertEquals(null, testQue.peek());
510    }
511
512    /**
513     * {@link java.util.ArrayDeque#push(Object)}
514     */
515    public void test_push() throws Exception {
516        testQue.push(testObjOne);
517        assertEquals(1, testQue.size());
518        assertEquals(testObjOne, testQue.peek());
519        testQue.push(testObjOne);
520        assertEquals(2, testQue.size());
521        assertEquals(testObjOne, testQue.peek());
522        testQue.push(testObjTwo);
523        assertEquals(3, testQue.size());
524        assertEquals(testObjTwo, testQue.peek());
525        assertEquals(testObjOne, testQue.getLast());
526        try {
527            testQue.push(null);
528            fail("should throw NullPointerException");
529        } catch (NullPointerException e) {
530            // expected
531        }
532    }
533
534    /**
535     * {@link java.util.ArrayDeque#pop()}
536     */
537    public void test_pop() throws Exception {
538        assertTrue(testQue.offerLast(testObjOne));
539        assertTrue(testQue.offerLast(testObjTwo));
540        assertTrue(testQue.offerLast(testObjThree));
541        assertEquals(3, testQue.size());
542        assertEquals(testObjOne, testQue.pop());
543        assertEquals(2, testQue.size());
544        assertEquals(testObjTwo, testQue.pop());
545        assertEquals(testObjThree, testQue.pop());
546        assertEquals(0, testQue.size());
547        try {
548            testQue.pop();
549            fail("should throw NoSuchElementException ");
550        } catch (NoSuchElementException e) {
551            // expected
552        }
553    }
554
555    /**
556     * {@link java.util.ArrayDeque#addFirst(Object)}
557     */
558    public void test_size() throws Exception {
559        assertEquals(0, testQue.size());
560        assertTrue(testQue.add(testObjOne));
561        assertTrue(testQue.add(testObjTwo));
562        assertEquals(2, testQue.size());
563        assertTrue(testQue.add(testObjOne));
564        assertTrue(testQue.add(testObjThree));
565        assertEquals(4, testQue.size());
566        testQue.remove();
567        testQue.remove();
568        assertEquals(2, testQue.size());
569        testQue.clear();
570        assertEquals(0, testQue.size());
571    }
572
573    /**
574     * {@link java.util.ArrayDeque#isEmpty()}
575     */
576    public void test_isEmpty() throws Exception {
577        assertTrue(testQue.isEmpty());
578        assertTrue(testQue.add(testObjOne));
579        assertFalse(testQue.isEmpty());
580        assertTrue(testQue.add(testObjTwo));
581        assertFalse(testQue.isEmpty());
582        assertTrue(testQue.add(testObjOne));
583        assertTrue(testQue.add(testObjThree));
584        assertFalse(testQue.isEmpty());
585        testQue.remove();
586        testQue.remove();
587        assertFalse(testQue.isEmpty());
588        testQue.clear();
589        assertTrue(testQue.isEmpty());
590    }
591
592    /**
593     * {@link java.util.ArrayDeque#iterator()}
594     */
595    public void test_iterator() throws Exception {
596        assertFalse(testQue.iterator().hasNext());
597        assertTrue(testQue.add(testObjOne));
598        assertTrue(testQue.add(testObjTwo));
599        assertTrue(testQue.add(testObjOne));
600        assertTrue(testQue.add(testObjThree));
601        assertTrue(testQue.add(testObjLast));
602        Iterator result = testQue.iterator();
603        assertEquals(5, testQue.size());
604        try {
605            result.remove();
606            fail("should throw IllegalStateException");
607        } catch (IllegalStateException e) {
608            // expected
609        }
610        assertTrue(testQue.add(testObjThree));
611        try {
612            result.next();
613            fail("should throw ConcurrentModificationException");
614        } catch (ConcurrentModificationException e) {
615            // expected
616        }
617        result = testQue.iterator();
618        assertEquals(testObjOne, result.next());
619        assertEquals(testObjTwo, result.next());
620        assertEquals(testObjOne, result.next());
621        assertEquals(testObjThree, result.next());
622        assertEquals(testObjLast, result.next());
623        assertTrue(result.hasNext());
624        result.remove();
625        assertEquals(testObjThree, result.next());
626        assertFalse(result.hasNext());
627        try {
628            result.next();
629            fail("should throw NoSuchElementException");
630        } catch (NoSuchElementException e) {
631            // expected
632        }
633        // test a full array
634        ArrayDeque<Object> ad = new ArrayDeque<Object>();
635        // fill the array
636        for (int i = 0; i < 16; ++i) {
637            ad.addLast(new Object());
638        }
639        assertTrue(ad.iterator().hasNext());
640        Iterator<Object> iter = ad.iterator();
641        for (int i = 0; i < 16; ++i) {
642            assertTrue(iter.hasNext());
643            iter.next();
644        }
645        iter.remove();
646        // test un-full array
647        ad = new ArrayDeque<Object>();
648        // fill the array
649        for (int i = 0; i < 5; ++i) {
650            ad.addLast(new Object());
651        }
652        iter = ad.iterator();
653        for (int i = 0; i < 5; ++i) {
654            assertTrue(iter.hasNext());
655            iter.next();
656        }
657        iter.remove();
658
659        ad = new ArrayDeque<Object>();
660        // fill the array
661        for (int i = 0; i < 16; ++i) {
662            ad.addLast(new Object());
663        }
664        iter = ad.iterator();
665        assertTrue(iter.hasNext());
666        for (int i = 0; i < ad.size(); ++i) {
667            iter.next();
668        }
669        assertFalse(iter.hasNext());
670        iter.remove();
671        ad.add(new Object());
672        assertFalse(iter.hasNext());
673    }
674
675    /**
676     * {@link java.util.ArrayDeque#descendingIterator()}
677     */
678    public void test_descendingIterator() throws Exception {
679        assertFalse(testQue.descendingIterator().hasNext());
680        assertTrue(testQue.add(testObjOne));
681        assertTrue(testQue.add(testObjTwo));
682        assertTrue(testQue.add(testObjOne));
683        assertTrue(testQue.add(testObjThree));
684        assertTrue(testQue.add(testObjLast));
685        Iterator result = testQue.descendingIterator();
686        assertEquals(5, testQue.size());
687        try {
688            result.remove();
689            fail("should throw IllegalStateException");
690        } catch (IllegalStateException e) {
691            // expected
692        }
693        assertTrue(testQue.add(testObjFour));
694
695        // a strange behavior here, RI's descendingIterator() and iterator() is
696        // properly different. Notice spec: "The iterators returned by this
697        // class's iterator method are fail-fast". RI shows descendingIterator()
698        // is not an iterator method.
699        assertEquals(testObjLast, result.next());
700
701        result = testQue.descendingIterator();
702        assertEquals(testObjFour, result.next());
703        assertEquals(testObjLast, result.next());
704        assertEquals(testObjThree, result.next());
705        assertEquals(testObjOne, result.next());
706        assertEquals(testObjTwo, result.next());
707        assertTrue(result.hasNext());
708        result.remove();
709        assertEquals(testObjOne, result.next());
710        assertFalse(result.hasNext());
711        try {
712            result.next();
713            fail("should throw NoSuchElementException");
714        } catch (NoSuchElementException e) {
715            // expected
716        }
717        // test a full array
718        ArrayDeque<Object> ad = new ArrayDeque<Object>();
719        // fill the array
720        for (int i = 0; i < 16; ++i) {
721            ad.addLast(new Object());
722        }
723        assertTrue(ad.descendingIterator().hasNext());
724        Iterator<Object> iter = ad.descendingIterator();
725        for (int i = 0; i < 16; ++i) {
726            assertTrue(iter.hasNext());
727            iter.next();
728        }
729        iter.remove();
730        // test un-full array
731        ad = new ArrayDeque<Object>();
732        // fill the array
733        for (int i = 0; i < 5; ++i) {
734            ad.addLast(new Object());
735        }
736        iter = ad.descendingIterator();
737        for (int i = 0; i < 5; ++i) {
738            assertTrue(iter.hasNext());
739            iter.next();
740        }
741        iter.remove();
742
743        ad = new ArrayDeque<Object>();
744        // fill the array
745        for (int i = 0; i < 16; ++i) {
746            ad.addLast(new Object());
747        }
748        iter = ad.descendingIterator();
749        assertTrue(iter.hasNext());
750        for (int i = 0; i < ad.size(); ++i) {
751            iter.next();
752        }
753        assertFalse(iter.hasNext());
754        iter.remove();
755        ad.add(new Object());
756        assertFalse(iter.hasNext());
757    }
758
759    /**
760     * {@link java.util.ArrayDeque#contains(Object)}
761     */
762    public void test_contains() throws Exception {
763        assertFalse(testQue.contains(testObjFour));
764        assertFalse(testQue.contains(null));
765        assertTrue(testQue.add(testObjOne));
766        assertTrue(testQue.add(testObjTwo));
767        assertTrue(testQue.add(testObjOne));
768        assertTrue(testQue.add(testObjThree));
769        assertTrue(testQue.add(testObjLast));
770
771        assertTrue(testQue.contains(testObjOne));
772        assertTrue(testQue.contains(testObjTwo));
773        assertTrue(testQue.contains(testObjThree));
774        assertTrue(testQue.contains(testObjLast));
775        assertFalse(testQue.contains(null));
776        testQue.clear();
777        assertFalse(testQue.contains(testObjOne));
778        assertFalse(testQue.contains(testObjTwo));
779    }
780
781    /**
782     * {@link java.util.ArrayDeque#remove(Object)}
783     */
784    public void test_remove_LObject() throws Exception {
785        assertTrue(testQue.offerLast(testObjOne));
786        assertTrue(testQue.offerLast(testObjTwo));
787        assertTrue(testQue.offerLast(testObjOne));
788        assertTrue(testQue.offerLast(testObjThree));
789        assertTrue(testQue.offerLast(testObjOne));
790        assertEquals(5, testQue.size());
791        assertTrue(testQue.remove(testObjOne));
792        assertFalse(testQue.remove(testObjFour));
793        assertEquals(testObjTwo, testQue.peekFirst());
794        assertEquals(testObjOne, testQue.peekLast());
795        assertEquals(4, testQue.size());
796        assertTrue(testQue.remove(testObjOne));
797        assertEquals(3, testQue.size());
798        assertEquals(testObjOne, testQue.peekLast());
799        assertTrue(testQue.remove(testObjOne));
800        assertEquals(2, testQue.size());
801        assertEquals(testObjThree, testQue.peekLast());
802        assertFalse(testQue.remove(testObjOne));
803    }
804
805    /**
806     * {@link java.util.ArrayDeque#clear()}
807     */
808    public void test_clear() throws Exception {
809        assertTrue(testQue.isEmpty());
810        testQue.clear();
811        assertTrue(testQue.isEmpty());
812        assertTrue(testQue.add(testObjOne));
813        assertTrue(testQue.add(testObjTwo));
814        assertTrue(testQue.add(testObjOne));
815        assertTrue(testQue.add(testObjThree));
816        testQue.clear();
817        assertTrue(testQue.isEmpty());
818    }
819
820    /**
821     * {@link java.util.ArrayDeque#toArray()}
822     */
823    public void test_toArray() throws Exception {
824        assertEquals(0, testQue.toArray().length);
825        assertTrue(testQue.add(testObjOne));
826        assertTrue(testQue.add(testObjTwo));
827        assertTrue(testQue.add(testObjOne));
828        assertTrue(testQue.add(testObjThree));
829        assertTrue(testQue.add(testObjLast));
830        Object[] result = testQue.toArray();
831        assertEquals(5, testQue.size());
832        assertEquals(testObjOne, result[0]);
833        assertEquals(testObjTwo, result[1]);
834        assertEquals(testObjOne, result[2]);
835        assertEquals(testObjThree, result[3]);
836        assertEquals(testObjLast, result[4]);
837        // change in array do not affect ArrayDeque
838        result[0] = null;
839        assertEquals(5, testQue.size());
840        assertEquals(testObjOne, testQue.peek());
841    }
842
843    /**
844     * {@link java.util.ArrayDeque#toArray(Object[])}
845     */
846    public void test_toArray_$LObject() throws Exception {
847        Object[] array = new Object[0];
848        Object[] result = testQue.toArray(array);
849        assertEquals(0, result.length);
850        assertEquals(array, result);
851        assertTrue(testQue.add(testObjOne));
852        assertTrue(testQue.add(testObjTwo));
853        assertTrue(testQue.add(testObjOne));
854        assertTrue(testQue.add(testObjThree));
855        assertTrue(testQue.add(testObjLast));
856        result = testQue.toArray(array);
857        assertEquals(5, testQue.size());
858        assertEquals(5, result.length);
859        assertEquals(0, array.length);
860        assertFalse(array == result);
861        assertEquals(testObjOne, result[0]);
862        assertEquals(testObjTwo, result[1]);
863        assertEquals(testObjOne, result[2]);
864        assertEquals(testObjThree, result[3]);
865        assertEquals(testObjLast, result[4]);
866        // change in array do not affect ArrayDeque
867        result[0] = null;
868        assertEquals(5, testQue.size());
869        assertEquals(testObjOne, testQue.peek());
870        try {
871            testQue.toArray(null);
872            fail("should throw NullPointerException");
873        } catch (NullPointerException e) {
874            // expected
875        }
876
877    }
878
879    /**
880     * {@link java.util.ArrayDeque#clone()}
881     */
882    public void test_clone() throws Exception {
883        ArrayDeque<Object> cloned = testQue.clone();
884        assertEquals(0, cloned.size());
885        assertFalse(cloned == testQue);
886        assertTrue(testQue.add(testObjOne));
887        assertTrue(testQue.add(testObjTwo));
888        assertTrue(testQue.add(testObjOne));
889        assertTrue(testQue.add(testObjThree));
890        assertTrue(testQue.add(testObjLast));
891        assertTrue(testQue.add(testQue));
892        cloned = testQue.clone();
893        assertEquals(6, cloned.size());
894        while (0 != testQue.size()) {
895            assertEquals(testQue.remove(), cloned.remove());
896        }
897    }
898
899    public void test_forEachRemaining_iterator() throws Exception {
900        ForEachRemainingTester.test_forEachRemaining(new ArrayDeque<>(),
901                new String[]{ "foo", "bar", "baz "});
902        ForEachRemainingTester.test_forEachRemaining_NPE(new ArrayDeque<>(),
903                new String[]{"foo", "bar", "baz "});
904    }
905
906    public void test_forEachRemaining_CME() throws Exception {
907        ArrayDeque<String> adq = new ArrayDeque<>();
908        adq.add("foo");
909
910        // The ArrayDeque forEachRemaining implementation doesn't use a precise check
911        // for concurrent modifications.
912        adq.iterator().forEachRemaining(s -> adq.add(s));
913    }
914
915    public void test_spliterator() throws Exception {
916        ArrayList<Integer> testElements = new ArrayList<>(
917                Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16));
918        ArrayDeque<Integer> adq = new ArrayDeque<>();
919        adq.addAll(testElements);
920
921        SpliteratorTester.runBasicIterationTests(adq.spliterator(), testElements);
922        SpliteratorTester.runBasicSplitTests(adq, testElements);
923        SpliteratorTester.testSpliteratorNPE(adq.spliterator());
924
925        assertTrue(adq.spliterator().hasCharacteristics(
926                Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED));
927
928        SpliteratorTester.runOrderedTests(adq);
929        SpliteratorTester.runSizedTests(adq, 16 /* expected size */);
930        SpliteratorTester.runSubSizedTests(adq, 16 /* expected size */);
931        SpliteratorTester.assertSupportsTrySplit(adq);
932    }
933
934    public void test_spliterator_CME() throws Exception {
935        ArrayDeque<Integer> adq = new ArrayDeque<>();
936        adq.add(52);
937
938        Spliterator<Integer> sp = adq.spliterator();
939
940        // Spliterators from ArrayDequeues never throw CME. The following statements
941        // would have thrown a CME on most other collection classes.
942        assertTrue(sp.tryAdvance(value -> adq.add(value)));
943        sp.forEachRemaining(value -> adq.add(value));
944    }
945
946    /**
947     * java.util.ArrayDeque#Serialization()
948     */
949    public void test_serialization() throws Exception {
950        assertTrue(testQue.add(new Integer(1)));
951        assertTrue(testQue.add(new Integer(2)));
952        assertTrue(testQue.add(new Integer(3)));
953        assertTrue(testQue.add(new Integer(4)));
954        assertTrue(testQue.add(new Integer(5)));
955        SerializationTest.verifySelf(testQue, new SerializableAssert() {
956            public void assertDeserialized(Serializable initial,
957                    Serializable deserialized) {
958                ArrayDeque<Object> formerQue = (ArrayDeque) initial;
959                ArrayDeque<Object> deserializedQue = (ArrayDeque) deserialized;
960                assertEquals(formerQue.remove(), deserializedQue.remove());
961            }
962        });
963    }
964
965    /**
966     * serialization/deserialization compatibility with RI.
967     */
968    @SuppressWarnings({ "unchecked", "boxing" })
969    public void testSerializationCompatibility() throws Exception {
970        assertTrue(testQue.add(new Integer(1)));
971        assertTrue(testQue.add(new Integer(2)));
972        assertTrue(testQue.add(new Integer(3)));
973        assertTrue(testQue.add(new Integer(4)));
974        assertTrue(testQue.add(new Integer(5)));
975        SerializationTest.verifyGolden(this, testQue, new SerializableAssert() {
976            public void assertDeserialized(Serializable initial,
977                    Serializable deserialized) {
978                ArrayDeque<Object> formerQue = (ArrayDeque) initial;
979                ArrayDeque<Object> deserializedQue = (ArrayDeque) deserialized;
980                assertEquals(formerQue.remove(), deserializedQue.remove());
981            }
982        });
983    }
984}
985