test/tck/ArrayDequeTest.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

import junit.framework.*;
import java.util.*;
import java.util.concurrent.*;

public class ArrayDequeTest extends JSR166TestCase {
    public static void main(String[] args) {
        junit.textui.TestRunner.run (suite());
    }

    public static Test suite() {
        return new TestSuite(ArrayDequeTest.class);
    }

    /**
     * Create a queue of given size containing consecutive
     * Integers 0 ... n.
     */
    private ArrayDeque populatedDeque(int n) {
        ArrayDeque q = new ArrayDeque();
        assertTrue(q.isEmpty());
        for (int i = 0; i < n; ++i)
            assertTrue(q.offerLast(new Integer(i)));
        assertFalse(q.isEmpty());
        assertEquals(n, q.size());
        return q;
    }

    /**
     * new queue is empty
     */
    public void testConstructor1() {
        assertEquals(0, new ArrayDeque().size());
    }

    /**
     * Initializing from null Collection throws NPE
     */
    public void testConstructor3() {
        try {
            ArrayDeque q = new ArrayDeque((Collection)null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * Queue contains all elements of collection used to initialize

     */
    public void testConstructor6() {
        Integer[] ints = new Integer[SIZE];
        for (int i = 0; i < SIZE; ++i)
            ints[i] = new Integer(i);
        ArrayDeque q = new ArrayDeque(Arrays.asList(ints));
        for (int i = 0; i < SIZE; ++i)
            assertEquals(ints[i], q.pollFirst());
    }

    /**
     * isEmpty is true before add, false after
     */
    public void testEmpty() {
        ArrayDeque q = new ArrayDeque();
        assertTrue(q.isEmpty());
        q.add(new Integer(1));
        assertFalse(q.isEmpty());
        q.add(new Integer(2));
        q.removeFirst();
        q.removeFirst();
        assertTrue(q.isEmpty());
    }

    /**
     * size changes when elements added and removed
     */
    public void testSize() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(SIZE-i, q.size());
            q.removeFirst();
        }
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.size());
            q.add(new Integer(i));
        }
    }

    /**
     * push(null) throws NPE
     */
    public void testPushNull() {
        try {
            ArrayDeque q = new ArrayDeque(1);
            q.push(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * peekFirst returns element inserted with push
     */
    public void testPush() {
        ArrayDeque q = populatedDeque(3);
        q.pollLast();
        q.push(four);
        assertEquals(four,q.peekFirst());
    }

    /**
     *  pop removes next element, or throws NSEE if empty
     */
    public void testPop() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.pop()).intValue());
        }
        try {
            q.pop();
            shouldThrow();
        } catch (NoSuchElementException success) {}
    }

    /**
     * offer(null) throws NPE
     */
    public void testOfferFirstNull() {
        try {
            ArrayDeque q = new ArrayDeque();
            q.offerFirst(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * OfferFirst succeeds
     */
    public void testOfferFirst() {
        ArrayDeque q = new ArrayDeque();
        assertTrue(q.offerFirst(new Integer(0)));
        assertTrue(q.offerFirst(new Integer(1)));
    }

    /**
     * OfferLast succeeds
     */
    public void testOfferLast() {
        ArrayDeque q = new ArrayDeque();
        assertTrue(q.offerLast(new Integer(0)));
        assertTrue(q.offerLast(new Integer(1)));
    }

    /**
     * add succeeds
     */
    public void testAdd() {
        ArrayDeque q = new ArrayDeque();
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.size());
            assertTrue(q.add(new Integer(i)));
        }
    }

    /**
     * addAll(null) throws NPE
     */
    public void testAddAll1() {
        try {
            ArrayDeque q = new ArrayDeque();
            q.addAll(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * Queue contains all elements, in traversal order, of successful addAll
     */
    public void testAddAll5() {
        try {
            Integer[] empty = new Integer[0];
            Integer[] ints = new Integer[SIZE];
            for (int i = 0; i < SIZE; ++i)
                ints[i] = new Integer(i);
            ArrayDeque q = new ArrayDeque();
            assertFalse(q.addAll(Arrays.asList(empty)));
            assertTrue(q.addAll(Arrays.asList(ints)));
            for (int i = 0; i < SIZE; ++i)
                assertEquals(ints[i], q.pollFirst());
        }
        finally {}
    }

    /**
     *  pollFirst succeeds unless empty
     */
    public void testPollFirst() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.pollFirst()).intValue());
        }
        assertNull(q.pollFirst());
    }

    /**
     *  pollLast succeeds unless empty
     */
    public void testPollLast() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = SIZE-1; i >= 0; --i) {
            assertEquals(i, ((Integer)q.pollLast()).intValue());
        }
        assertNull(q.pollLast());
    }

    /**
     *  poll succeeds unless empty
     */
    public void testPoll() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.poll()).intValue());
        }
        assertNull(q.poll());
    }

    /**
     *  remove removes next element, or throws NSEE if empty
     */
    public void testRemove() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.remove()).intValue());
        }
        try {
            q.remove();
            shouldThrow();
        } catch (NoSuchElementException success) {}
    }

    /**
     *  peekFirst returns next element, or null if empty
     */
    public void testPeekFirst() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.peekFirst()).intValue());
            q.pollFirst();
            assertTrue(q.peekFirst() == null ||
                       i != ((Integer)q.peekFirst()).intValue());
        }
        assertNull(q.peekFirst());
    }

    /**
     *  peek returns next element, or null if empty
     */
    public void testPeek() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.peek()).intValue());
            q.poll();
            assertTrue(q.peek() == null ||
                       i != ((Integer)q.peek()).intValue());
        }
        assertNull(q.peek());
    }

    /**
     *  peekLast returns next element, or null if empty
     */
    public void testPeekLast() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = SIZE-1; i >= 0; --i) {
            assertEquals(i, ((Integer)q.peekLast()).intValue());
            q.pollLast();
            assertTrue(q.peekLast() == null ||
                       i != ((Integer)q.peekLast()).intValue());
        }
        assertNull(q.peekLast());
    }

    /**
     * getFirst returns next getFirst, or throws NSEE if empty
     */
    public void testFirstElement() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.getFirst()).intValue());
            q.pollFirst();
        }
        try {
            q.getFirst();
            shouldThrow();
        } catch (NoSuchElementException success) {}
    }

    /**
     *  getLast returns next element, or throws NSEE if empty
     */
    public void testLastElement() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = SIZE-1; i >= 0; --i) {
            assertEquals(i, ((Integer)q.getLast()).intValue());
            q.pollLast();
        }
        try {
            q.getLast();
            shouldThrow();
        } catch (NoSuchElementException success) {}
        assertNull(q.peekLast());
    }


    /**
     *  removeFirst removes next element, or throws NSEE if empty
     */
    public void testRemoveFirst() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, ((Integer)q.removeFirst()).intValue());
        }
        try {
            q.removeFirst();
            shouldThrow();
        } catch (NoSuchElementException success) {}
    }

    /**
     * removeFirstOccurrence(x) removes x and returns true if present
     */
    public void testRemoveFirstOccurrence() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 1; i < SIZE; i+=2) {
            assertTrue(q.removeFirstOccurrence(new Integer(i)));
        }
        for (int i = 0; i < SIZE; i+=2) {
            assertTrue(q.removeFirstOccurrence(new Integer(i)));
            assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
        }
        assertTrue(q.isEmpty());
    }

    /**
     * removeLastOccurrence(x) removes x and returns true if present
     */
    public void testRemoveLastOccurrence() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 1; i < SIZE; i+=2) {
            assertTrue(q.removeLastOccurrence(new Integer(i)));
        }
        for (int i = 0; i < SIZE; i+=2) {
            assertTrue(q.removeLastOccurrence(new Integer(i)));
            assertFalse(q.removeLastOccurrence(new Integer(i+1)));
        }
        assertTrue(q.isEmpty());
    }

    /**
     * contains(x) reports true when elements added but not yet removed
     */
    public void testContains() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertTrue(q.contains(new Integer(i)));
            q.pollFirst();
            assertFalse(q.contains(new Integer(i)));
        }
    }

    /**
     * clear removes all elements
     */
    public void testClear() {
        ArrayDeque q = populatedDeque(SIZE);
        q.clear();
        assertTrue(q.isEmpty());
        assertEquals(0, q.size());
        q.add(new Integer(1));
        assertFalse(q.isEmpty());
        q.clear();
        assertTrue(q.isEmpty());
    }

    /**
     * containsAll(c) is true when c contains a subset of elements
     */
    public void testContainsAll() {
        ArrayDeque q = populatedDeque(SIZE);
        ArrayDeque p = new ArrayDeque();
        for (int i = 0; i < SIZE; ++i) {
            assertTrue(q.containsAll(p));
            assertFalse(p.containsAll(q));
            p.add(new Integer(i));
        }
        assertTrue(p.containsAll(q));
    }

    /**
     * retainAll(c) retains only those elements of c and reports true if changed
     */
    public void testRetainAll() {
        ArrayDeque q = populatedDeque(SIZE);
        ArrayDeque p = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            boolean changed = q.retainAll(p);
            if (i == 0)
                assertFalse(changed);
            else
                assertTrue(changed);

            assertTrue(q.containsAll(p));
            assertEquals(SIZE-i, q.size());
            p.removeFirst();
        }
    }

    /**
     * removeAll(c) removes only those elements of c and reports true if changed
     */
    public void testRemoveAll() {
        for (int i = 1; i < SIZE; ++i) {
            ArrayDeque q = populatedDeque(SIZE);
            ArrayDeque p = populatedDeque(i);
            assertTrue(q.removeAll(p));
            assertEquals(SIZE-i, q.size());
            for (int j = 0; j < i; ++j) {
                Integer I = (Integer)(p.removeFirst());
                assertFalse(q.contains(I));
            }
        }
    }

    /**
     *  toArray contains all elements
     */
    public void testToArray() {
        ArrayDeque q = populatedDeque(SIZE);
        Object[] o = q.toArray();
        Arrays.sort(o);
        for (int i = 0; i < o.length; i++)
            assertEquals(o[i], q.pollFirst());
    }

    /**
     *  toArray(a) contains all elements
     */
    public void testToArray2() {
        ArrayDeque q = populatedDeque(SIZE);
        Integer[] ints = new Integer[SIZE];
        ints = (Integer[])q.toArray(ints);
        Arrays.sort(ints);
        for (int i = 0; i < ints.length; i++)
            assertEquals(ints[i], q.pollFirst());
    }

    /**
     * toArray(null) throws NPE
     */
    public void testToArray_BadArg() {
        try {
            ArrayDeque l = new ArrayDeque();
            l.add(new Object());
            Object o[] = l.toArray(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * toArray with incompatable aray type throws CCE
     */
    public void testToArray1_BadArg() {
        try {
            ArrayDeque l = new ArrayDeque();
            l.add(new Integer(5));
            Object o[] = l.toArray(new String[10] );
            shouldThrow();
        } catch (ArrayStoreException success) {}
    }

    /**
     *  iterator iterates through all elements
     */
    public void testIterator() {
        ArrayDeque q = populatedDeque(SIZE);
        int i = 0;
        Iterator it = q.iterator();
        while (it.hasNext()) {
            assertTrue(q.contains(it.next()));
            ++i;
        }
        assertEquals(i, SIZE);
    }

    /**
     *  iterator ordering is FIFO
     */
    public void testIteratorOrdering() {
        final ArrayDeque q = new ArrayDeque();
        q.add(new Integer(1));
        q.add(new Integer(2));
        q.add(new Integer(3));
        int k = 0;
        for (Iterator it = q.iterator(); it.hasNext();) {
            int i = ((Integer)(it.next())).intValue();
            assertEquals(++k, i);
        }

        assertEquals(3, k);
    }

    /**
     * iterator.remove removes current element
     */
    public void testIteratorRemove () {
        final ArrayDeque q = new ArrayDeque();
        final Random rng = new Random();
        for (int iters = 0; iters < 100; ++iters) {
            int max = rng.nextInt(5) + 2;
            int split = rng.nextInt(max-1) + 1;
            for (int j = 1; j <= max; ++j)
                q.add(new Integer(j));
            Iterator it = q.iterator();
            for (int j = 1; j <= split; ++j)
                assertEquals(it.next(), new Integer(j));
            it.remove();
            assertEquals(it.next(), new Integer(split+1));
            for (int j = 1; j <= split; ++j)
                q.remove(new Integer(j));
            it = q.iterator();
            for (int j = split+1; j <= max; ++j) {
                assertEquals(it.next(), new Integer(j));
                it.remove();
            }
            assertFalse(it.hasNext());
            assertTrue(q.isEmpty());
        }
    }

    /**
     *  Descending iterator iterates through all elements
     */
    public void testDescendingIterator() {
        ArrayDeque q = populatedDeque(SIZE);
        int i = 0;
        Iterator it = q.descendingIterator();
        while (it.hasNext()) {
            assertTrue(q.contains(it.next()));
            ++i;
        }
        assertEquals(i, SIZE);
        assertFalse(it.hasNext());
        try {
            it.next();
        } catch (NoSuchElementException success) {}
    }

    /**
     *  Descending iterator ordering is reverse FIFO
     */
    public void testDescendingIteratorOrdering() {
        final ArrayDeque q = new ArrayDeque();
        for (int iters = 0; iters < 100; ++iters) {
            q.add(new Integer(3));
            q.add(new Integer(2));
            q.add(new Integer(1));
            int k = 0;
            for (Iterator it = q.descendingIterator(); it.hasNext();) {
                int i = ((Integer)(it.next())).intValue();
                assertEquals(++k, i);
            }

            assertEquals(3, k);
            q.remove();
            q.remove();
            q.remove();
        }
    }

    /**
     * descendingIterator.remove removes current element
     */
    public void testDescendingIteratorRemove () {
        final ArrayDeque q = new ArrayDeque();
        final Random rng = new Random();
        for (int iters = 0; iters < 100; ++iters) {
            int max = rng.nextInt(5) + 2;
            int split = rng.nextInt(max-1) + 1;
            for (int j = max; j >= 1; --j)
                q.add(new Integer(j));
            Iterator it = q.descendingIterator();
            for (int j = 1; j <= split; ++j)
                assertEquals(it.next(), new Integer(j));
            it.remove();
            assertEquals(it.next(), new Integer(split+1));
            for (int j = 1; j <= split; ++j)
                q.remove(new Integer(j));
            it = q.descendingIterator();
            for (int j = split+1; j <= max; ++j) {
                assertEquals(it.next(), new Integer(j));
                it.remove();
            }
            assertFalse(it.hasNext());
            assertTrue(q.isEmpty());
        }
    }


    /**
     * toString contains toStrings of elements
     */
    public void testToString() {
        ArrayDeque q = populatedDeque(SIZE);
        String s = q.toString();
        for (int i = 0; i < SIZE; ++i) {
            assertTrue(s.indexOf(String.valueOf(i)) >= 0);
        }
    }

    /**
     * peekFirst returns element inserted with addFirst
     */
    public void testAddFirst() {
        ArrayDeque q = populatedDeque(3);
        q.addFirst(four);
        assertEquals(four,q.peekFirst());
    }

    /**
     * peekLast returns element inserted with addLast
     */
    public void testAddLast() {
        ArrayDeque q = populatedDeque(3);
        q.addLast(four);
        assertEquals(four,q.peekLast());
    }

}
Revision:	1.9
Committed:	Sat Nov 21 10:25:05 2009 UTC (14 years, 5 months ago) by jsr166
Branch:	MAIN
Changes since 1.8:	+17 -29 lines
Log Message:	improve exception handling
#	Content
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/licenses/publicdomain
5	*/
6
7	import junit.framework.*;
8	import java.util.*;
9	import java.util.concurrent.*;
10
11	public class ArrayDequeTest extends JSR166TestCase {
12	public static void main(String[] args) {
13	junit.textui.TestRunner.run (suite());
14	}
15
16	public static Test suite() {
17	return new TestSuite(ArrayDequeTest.class);
18	}
19
20	/**
21	* Create a queue of given size containing consecutive
22	* Integers 0 ... n.
23	*/
24	private ArrayDeque populatedDeque(int n) {
25	ArrayDeque q = new ArrayDeque();
26	assertTrue(q.isEmpty());
27	for (int i = 0; i < n; ++i)
28	assertTrue(q.offerLast(new Integer(i)));
29	assertFalse(q.isEmpty());
30	assertEquals(n, q.size());
31	return q;
32	}
33
34	/**
35	* new queue is empty
36	*/
37	public void testConstructor1() {
38	assertEquals(0, new ArrayDeque().size());
39	}
40
41	/**
42	* Initializing from null Collection throws NPE
43	*/
44	public void testConstructor3() {
45	try {
46	ArrayDeque q = new ArrayDeque((Collection)null);
47	shouldThrow();
48	} catch (NullPointerException success) {}
49	}
50
51	/**
52	* Queue contains all elements of collection used to initialize
53
54	*/
55	public void testConstructor6() {
56	Integer[] ints = new Integer[SIZE];
57	for (int i = 0; i < SIZE; ++i)
58	ints[i] = new Integer(i);
59	ArrayDeque q = new ArrayDeque(Arrays.asList(ints));
60	for (int i = 0; i < SIZE; ++i)
61	assertEquals(ints[i], q.pollFirst());
62	}
63
64	/**
65	* isEmpty is true before add, false after
66	*/
67	public void testEmpty() {
68	ArrayDeque q = new ArrayDeque();
69	assertTrue(q.isEmpty());
70	q.add(new Integer(1));
71	assertFalse(q.isEmpty());
72	q.add(new Integer(2));
73	q.removeFirst();
74	q.removeFirst();
75	assertTrue(q.isEmpty());
76	}
77
78	/**
79	* size changes when elements added and removed
80	*/
81	public void testSize() {
82	ArrayDeque q = populatedDeque(SIZE);
83	for (int i = 0; i < SIZE; ++i) {
84	assertEquals(SIZE-i, q.size());
85	q.removeFirst();
86	}
87	for (int i = 0; i < SIZE; ++i) {
88	assertEquals(i, q.size());
89	q.add(new Integer(i));
90	}
91	}
92
93	/**
94	* push(null) throws NPE
95	*/
96	public void testPushNull() {
97	try {
98	ArrayDeque q = new ArrayDeque(1);
99	q.push(null);
100	shouldThrow();
101	} catch (NullPointerException success) {}
102	}
103
104	/**
105	* peekFirst returns element inserted with push
106	*/
107	public void testPush() {
108	ArrayDeque q = populatedDeque(3);
109	q.pollLast();
110	q.push(four);
111	assertEquals(four,q.peekFirst());
112	}
113
114	/**
115	* pop removes next element, or throws NSEE if empty
116	*/
117	public void testPop() {
118	ArrayDeque q = populatedDeque(SIZE);
119	for (int i = 0; i < SIZE; ++i) {
120	assertEquals(i, ((Integer)q.pop()).intValue());
121	}
122	try {
123	q.pop();
124	shouldThrow();
125	} catch (NoSuchElementException success) {}
126	}
127
128	/**
129	* offer(null) throws NPE
130	*/
131	public void testOfferFirstNull() {
132	try {
133	ArrayDeque q = new ArrayDeque();
134	q.offerFirst(null);
135	shouldThrow();
136	} catch (NullPointerException success) {}
137	}
138
139	/**
140	* OfferFirst succeeds
141	*/
142	public void testOfferFirst() {
143	ArrayDeque q = new ArrayDeque();
144	assertTrue(q.offerFirst(new Integer(0)));
145	assertTrue(q.offerFirst(new Integer(1)));
146	}
147
148	/**
149	* OfferLast succeeds
150	*/
151	public void testOfferLast() {
152	ArrayDeque q = new ArrayDeque();
153	assertTrue(q.offerLast(new Integer(0)));
154	assertTrue(q.offerLast(new Integer(1)));
155	}
156
157	/**
158	* add succeeds
159	*/
160	public void testAdd() {
161	ArrayDeque q = new ArrayDeque();
162	for (int i = 0; i < SIZE; ++i) {
163	assertEquals(i, q.size());
164	assertTrue(q.add(new Integer(i)));
165	}
166	}
167
168	/**
169	* addAll(null) throws NPE
170	*/
171	public void testAddAll1() {
172	try {
173	ArrayDeque q = new ArrayDeque();
174	q.addAll(null);
175	shouldThrow();
176	} catch (NullPointerException success) {}
177	}
178
179	/**
180	* Queue contains all elements, in traversal order, of successful addAll
181	*/
182	public void testAddAll5() {
183	try {
184	Integer[] empty = new Integer[0];
185	Integer[] ints = new Integer[SIZE];
186	for (int i = 0; i < SIZE; ++i)
187	ints[i] = new Integer(i);
188	ArrayDeque q = new ArrayDeque();
189	assertFalse(q.addAll(Arrays.asList(empty)));
190	assertTrue(q.addAll(Arrays.asList(ints)));
191	for (int i = 0; i < SIZE; ++i)
192	assertEquals(ints[i], q.pollFirst());
193	}
194	finally {}
195	}
196
197	/**
198	* pollFirst succeeds unless empty
199	*/
200	public void testPollFirst() {
201	ArrayDeque q = populatedDeque(SIZE);
202	for (int i = 0; i < SIZE; ++i) {
203	assertEquals(i, ((Integer)q.pollFirst()).intValue());
204	}
205	assertNull(q.pollFirst());
206	}
207
208	/**
209	* pollLast succeeds unless empty
210	*/
211	public void testPollLast() {
212	ArrayDeque q = populatedDeque(SIZE);
213	for (int i = SIZE-1; i >= 0; --i) {
214	assertEquals(i, ((Integer)q.pollLast()).intValue());
215	}
216	assertNull(q.pollLast());
217	}
218
219	/**
220	* poll succeeds unless empty
221	*/
222	public void testPoll() {
223	ArrayDeque q = populatedDeque(SIZE);
224	for (int i = 0; i < SIZE; ++i) {
225	assertEquals(i, ((Integer)q.poll()).intValue());
226	}
227	assertNull(q.poll());
228	}
229
230	/**
231	* remove removes next element, or throws NSEE if empty
232	*/
233	public void testRemove() {
234	ArrayDeque q = populatedDeque(SIZE);
235	for (int i = 0; i < SIZE; ++i) {
236	assertEquals(i, ((Integer)q.remove()).intValue());
237	}
238	try {
239	q.remove();
240	shouldThrow();
241	} catch (NoSuchElementException success) {}
242	}
243
244	/**
245	* peekFirst returns next element, or null if empty
246	*/
247	public void testPeekFirst() {
248	ArrayDeque q = populatedDeque(SIZE);
249	for (int i = 0; i < SIZE; ++i) {
250	assertEquals(i, ((Integer)q.peekFirst()).intValue());
251	q.pollFirst();
252	assertTrue(q.peekFirst() == null \|\|
253	i != ((Integer)q.peekFirst()).intValue());
254	}
255	assertNull(q.peekFirst());
256	}
257
258	/**
259	* peek returns next element, or null if empty
260	*/
261	public void testPeek() {
262	ArrayDeque q = populatedDeque(SIZE);
263	for (int i = 0; i < SIZE; ++i) {
264	assertEquals(i, ((Integer)q.peek()).intValue());
265	q.poll();
266	assertTrue(q.peek() == null \|\|
267	i != ((Integer)q.peek()).intValue());
268	}
269	assertNull(q.peek());
270	}
271
272	/**
273	* peekLast returns next element, or null if empty
274	*/
275	public void testPeekLast() {
276	ArrayDeque q = populatedDeque(SIZE);
277	for (int i = SIZE-1; i >= 0; --i) {
278	assertEquals(i, ((Integer)q.peekLast()).intValue());
279	q.pollLast();
280	assertTrue(q.peekLast() == null \|\|
281	i != ((Integer)q.peekLast()).intValue());
282	}
283	assertNull(q.peekLast());
284	}
285
286	/**
287	* getFirst returns next getFirst, or throws NSEE if empty
288	*/
289	public void testFirstElement() {
290	ArrayDeque q = populatedDeque(SIZE);
291	for (int i = 0; i < SIZE; ++i) {
292	assertEquals(i, ((Integer)q.getFirst()).intValue());
293	q.pollFirst();
294	}
295	try {
296	q.getFirst();
297	shouldThrow();
298	} catch (NoSuchElementException success) {}
299	}
300
301	/**
302	* getLast returns next element, or throws NSEE if empty
303	*/
304	public void testLastElement() {
305	ArrayDeque q = populatedDeque(SIZE);
306	for (int i = SIZE-1; i >= 0; --i) {
307	assertEquals(i, ((Integer)q.getLast()).intValue());
308	q.pollLast();
309	}
310	try {
311	q.getLast();
312	shouldThrow();
313	} catch (NoSuchElementException success) {}
314	assertNull(q.peekLast());
315	}
316
317
318	/**
319	* removeFirst removes next element, or throws NSEE if empty
320	*/
321	public void testRemoveFirst() {
322	ArrayDeque q = populatedDeque(SIZE);
323	for (int i = 0; i < SIZE; ++i) {
324	assertEquals(i, ((Integer)q.removeFirst()).intValue());
325	}
326	try {
327	q.removeFirst();
328	shouldThrow();
329	} catch (NoSuchElementException success) {}
330	}
331
332	/**
333	* removeFirstOccurrence(x) removes x and returns true if present
334	*/
335	public void testRemoveFirstOccurrence() {
336	ArrayDeque q = populatedDeque(SIZE);
337	for (int i = 1; i < SIZE; i+=2) {
338	assertTrue(q.removeFirstOccurrence(new Integer(i)));
339	}
340	for (int i = 0; i < SIZE; i+=2) {
341	assertTrue(q.removeFirstOccurrence(new Integer(i)));
342	assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
343	}
344	assertTrue(q.isEmpty());
345	}
346
347	/**
348	* removeLastOccurrence(x) removes x and returns true if present
349	*/
350	public void testRemoveLastOccurrence() {
351	ArrayDeque q = populatedDeque(SIZE);
352	for (int i = 1; i < SIZE; i+=2) {
353	assertTrue(q.removeLastOccurrence(new Integer(i)));
354	}
355	for (int i = 0; i < SIZE; i+=2) {
356	assertTrue(q.removeLastOccurrence(new Integer(i)));
357	assertFalse(q.removeLastOccurrence(new Integer(i+1)));
358	}
359	assertTrue(q.isEmpty());
360	}
361
362	/**
363	* contains(x) reports true when elements added but not yet removed
364	*/
365	public void testContains() {
366	ArrayDeque q = populatedDeque(SIZE);
367	for (int i = 0; i < SIZE; ++i) {
368	assertTrue(q.contains(new Integer(i)));
369	q.pollFirst();
370	assertFalse(q.contains(new Integer(i)));
371	}
372	}
373
374	/**
375	* clear removes all elements
376	*/
377	public void testClear() {
378	ArrayDeque q = populatedDeque(SIZE);
379	q.clear();
380	assertTrue(q.isEmpty());
381	assertEquals(0, q.size());
382	q.add(new Integer(1));
383	assertFalse(q.isEmpty());
384	q.clear();
385	assertTrue(q.isEmpty());
386	}
387
388	/**
389	* containsAll(c) is true when c contains a subset of elements
390	*/
391	public void testContainsAll() {
392	ArrayDeque q = populatedDeque(SIZE);
393	ArrayDeque p = new ArrayDeque();
394	for (int i = 0; i < SIZE; ++i) {
395	assertTrue(q.containsAll(p));
396	assertFalse(p.containsAll(q));
397	p.add(new Integer(i));
398	}
399	assertTrue(p.containsAll(q));
400	}
401
402	/**
403	* retainAll(c) retains only those elements of c and reports true if changed
404	*/
405	public void testRetainAll() {
406	ArrayDeque q = populatedDeque(SIZE);
407	ArrayDeque p = populatedDeque(SIZE);
408	for (int i = 0; i < SIZE; ++i) {
409	boolean changed = q.retainAll(p);
410	if (i == 0)
411	assertFalse(changed);
412	else
413	assertTrue(changed);
414
415	assertTrue(q.containsAll(p));
416	assertEquals(SIZE-i, q.size());
417	p.removeFirst();
418	}
419	}
420
421	/**
422	* removeAll(c) removes only those elements of c and reports true if changed
423	*/
424	public void testRemoveAll() {
425	for (int i = 1; i < SIZE; ++i) {
426	ArrayDeque q = populatedDeque(SIZE);
427	ArrayDeque p = populatedDeque(i);
428	assertTrue(q.removeAll(p));
429	assertEquals(SIZE-i, q.size());
430	for (int j = 0; j < i; ++j) {
431	Integer I = (Integer)(p.removeFirst());
432	assertFalse(q.contains(I));
433	}
434	}
435	}
436
437	/**
438	* toArray contains all elements
439	*/
440	public void testToArray() {
441	ArrayDeque q = populatedDeque(SIZE);
442	Object[] o = q.toArray();
443	Arrays.sort(o);
444	for (int i = 0; i < o.length; i++)
445	assertEquals(o[i], q.pollFirst());
446	}
447
448	/**
449	* toArray(a) contains all elements
450	*/
451	public void testToArray2() {
452	ArrayDeque q = populatedDeque(SIZE);
453	Integer[] ints = new Integer[SIZE];
454	ints = (Integer[])q.toArray(ints);
455	Arrays.sort(ints);
456	for (int i = 0; i < ints.length; i++)
457	assertEquals(ints[i], q.pollFirst());
458	}
459
460	/**
461	* toArray(null) throws NPE
462	*/
463	public void testToArray_BadArg() {
464	try {
465	ArrayDeque l = new ArrayDeque();
466	l.add(new Object());
467	Object o[] = l.toArray(null);
468	shouldThrow();
469	} catch (NullPointerException success) {}
470	}
471
472	/**
473	* toArray with incompatable aray type throws CCE
474	*/
475	public void testToArray1_BadArg() {
476	try {
477	ArrayDeque l = new ArrayDeque();
478	l.add(new Integer(5));
479	Object o[] = l.toArray(new String[10] );
480	shouldThrow();
481	} catch (ArrayStoreException success) {}
482	}
483
484	/**
485	* iterator iterates through all elements
486	*/
487	public void testIterator() {
488	ArrayDeque q = populatedDeque(SIZE);
489	int i = 0;
490	Iterator it = q.iterator();
491	while (it.hasNext()) {
492	assertTrue(q.contains(it.next()));
493	++i;
494	}
495	assertEquals(i, SIZE);
496	}
497
498	/**
499	* iterator ordering is FIFO
500	*/
501	public void testIteratorOrdering() {
502	final ArrayDeque q = new ArrayDeque();
503	q.add(new Integer(1));
504	q.add(new Integer(2));
505	q.add(new Integer(3));
506	int k = 0;
507	for (Iterator it = q.iterator(); it.hasNext();) {
508	int i = ((Integer)(it.next())).intValue();
509	assertEquals(++k, i);
510	}
511
512	assertEquals(3, k);
513	}
514
515	/**
516	* iterator.remove removes current element
517	*/
518	public void testIteratorRemove () {
519	final ArrayDeque q = new ArrayDeque();
520	final Random rng = new Random();
521	for (int iters = 0; iters < 100; ++iters) {
522	int max = rng.nextInt(5) + 2;
523	int split = rng.nextInt(max-1) + 1;
524	for (int j = 1; j <= max; ++j)
525	q.add(new Integer(j));
526	Iterator it = q.iterator();
527	for (int j = 1; j <= split; ++j)
528	assertEquals(it.next(), new Integer(j));
529	it.remove();
530	assertEquals(it.next(), new Integer(split+1));
531	for (int j = 1; j <= split; ++j)
532	q.remove(new Integer(j));
533	it = q.iterator();
534	for (int j = split+1; j <= max; ++j) {
535	assertEquals(it.next(), new Integer(j));
536	it.remove();
537	}
538	assertFalse(it.hasNext());
539	assertTrue(q.isEmpty());
540	}
541	}
542
543	/**
544	* Descending iterator iterates through all elements
545	*/
546	public void testDescendingIterator() {
547	ArrayDeque q = populatedDeque(SIZE);
548	int i = 0;
549	Iterator it = q.descendingIterator();
550	while (it.hasNext()) {
551	assertTrue(q.contains(it.next()));
552	++i;
553	}
554	assertEquals(i, SIZE);
555	assertFalse(it.hasNext());
556	try {
557	it.next();
558	} catch (NoSuchElementException success) {}
559	}
560
561	/**
562	* Descending iterator ordering is reverse FIFO
563	*/
564	public void testDescendingIteratorOrdering() {
565	final ArrayDeque q = new ArrayDeque();
566	for (int iters = 0; iters < 100; ++iters) {
567	q.add(new Integer(3));
568	q.add(new Integer(2));
569	q.add(new Integer(1));
570	int k = 0;
571	for (Iterator it = q.descendingIterator(); it.hasNext();) {
572	int i = ((Integer)(it.next())).intValue();
573	assertEquals(++k, i);
574	}
575
576	assertEquals(3, k);
577	q.remove();
578	q.remove();
579	q.remove();
580	}
581	}
582
583	/**
584	* descendingIterator.remove removes current element
585	*/
586	public void testDescendingIteratorRemove () {
587	final ArrayDeque q = new ArrayDeque();
588	final Random rng = new Random();
589	for (int iters = 0; iters < 100; ++iters) {
590	int max = rng.nextInt(5) + 2;
591	int split = rng.nextInt(max-1) + 1;
592	for (int j = max; j >= 1; --j)
593	q.add(new Integer(j));
594	Iterator it = q.descendingIterator();
595	for (int j = 1; j <= split; ++j)
596	assertEquals(it.next(), new Integer(j));
597	it.remove();
598	assertEquals(it.next(), new Integer(split+1));
599	for (int j = 1; j <= split; ++j)
600	q.remove(new Integer(j));
601	it = q.descendingIterator();
602	for (int j = split+1; j <= max; ++j) {
603	assertEquals(it.next(), new Integer(j));
604	it.remove();
605	}
606	assertFalse(it.hasNext());
607	assertTrue(q.isEmpty());
608	}
609	}
610
611
612	/**
613	* toString contains toStrings of elements
614	*/
615	public void testToString() {
616	ArrayDeque q = populatedDeque(SIZE);
617	String s = q.toString();
618	for (int i = 0; i < SIZE; ++i) {
619	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
620	}
621	}
622
623	/**
624	* peekFirst returns element inserted with addFirst
625	*/
626	public void testAddFirst() {
627	ArrayDeque q = populatedDeque(3);
628	q.addFirst(four);
629	assertEquals(four,q.peekFirst());
630	}
631
632	/**
633	* peekLast returns element inserted with addLast
634	*/
635	public void testAddLast() {
636	ArrayDeque q = populatedDeque(3);
637	q.addLast(four);
638	assertEquals(four,q.peekLast());
639	}
640
641	}