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