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);
        assertSame(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, q.pop());
        }
        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() {
        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());
    }

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

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

    /**
     *  poll succeeds unless empty
     */
    public void testPoll() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.poll());
        }
        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, q.remove());
        }
        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, q.peekFirst());
            assertEquals(i, q.pollFirst());
            assertTrue(q.peekFirst() == null ||
                       !q.peekFirst().equals(i));
        }
        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, q.peek());
            assertEquals(i, q.poll());
            assertTrue(q.peek() == null ||
                       !q.peek().equals(i));
        }
        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, q.peekLast());
            assertEquals(i, q.pollLast());
            assertTrue(q.peekLast() == null ||
                       !q.peekLast().equals(i));
        }
        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, q.getFirst());
            assertEquals(i, 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, q.getLast());
            assertEquals(i, 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, q.removeFirst());
        }
        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)));
            assertEquals(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());
        assertTrue(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));
            assertTrue(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);
            assertEquals(changed, (i > 0));
            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) {
                assertFalse(q.contains(p.removeFirst()));
            }
        }
    }

    /**
     *  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() {
        ArrayDeque l = new ArrayDeque();
        l.add(new Object());
        try {
            Object o[] = l.toArray(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * toArray with incompatible aray type throws CCE
     */
    public void testToArray1_BadArg() {
        ArrayDeque l = new ArrayDeque();
        l.add(new Integer(5));
        try {
            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();) {
            assertEquals(++k, it.next());
        }

        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();
            shouldThrow();
        } 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();) {
                assertEquals(++k, it.next());
            }

            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);
        assertSame(four, q.peekFirst());
    }

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

}
Revision:	1.14
Committed:	Wed Dec 23 00:47:16 2009 UTC (14 years, 4 months ago) by jsr166
Branch:	MAIN
Changes since 1.13:	+1 -1 lines
Log Message:	typos
#	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	assertSame(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, q.pop());
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	Integer[] empty = new Integer[0];
184	Integer[] ints = new Integer[SIZE];
185	for (int i = 0; i < SIZE; ++i)
186	ints[i] = new Integer(i);
187	ArrayDeque q = new ArrayDeque();
188	assertFalse(q.addAll(Arrays.asList(empty)));
189	assertTrue(q.addAll(Arrays.asList(ints)));
190	for (int i = 0; i < SIZE; ++i)
191	assertEquals(ints[i], q.pollFirst());
192	}
193
194	/**
195	* pollFirst succeeds unless empty
196	*/
197	public void testPollFirst() {
198	ArrayDeque q = populatedDeque(SIZE);
199	for (int i = 0; i < SIZE; ++i) {
200	assertEquals(i, q.pollFirst());
201	}
202	assertNull(q.pollFirst());
203	}
204
205	/**
206	* pollLast succeeds unless empty
207	*/
208	public void testPollLast() {
209	ArrayDeque q = populatedDeque(SIZE);
210	for (int i = SIZE-1; i >= 0; --i) {
211	assertEquals(i, q.pollLast());
212	}
213	assertNull(q.pollLast());
214	}
215
216	/**
217	* poll succeeds unless empty
218	*/
219	public void testPoll() {
220	ArrayDeque q = populatedDeque(SIZE);
221	for (int i = 0; i < SIZE; ++i) {
222	assertEquals(i, q.poll());
223	}
224	assertNull(q.poll());
225	}
226
227	/**
228	* remove removes next element, or throws NSEE if empty
229	*/
230	public void testRemove() {
231	ArrayDeque q = populatedDeque(SIZE);
232	for (int i = 0; i < SIZE; ++i) {
233	assertEquals(i, q.remove());
234	}
235	try {
236	q.remove();
237	shouldThrow();
238	} catch (NoSuchElementException success) {}
239	}
240
241	/**
242	* peekFirst returns next element, or null if empty
243	*/
244	public void testPeekFirst() {
245	ArrayDeque q = populatedDeque(SIZE);
246	for (int i = 0; i < SIZE; ++i) {
247	assertEquals(i, q.peekFirst());
248	assertEquals(i, q.pollFirst());
249	assertTrue(q.peekFirst() == null \|\|
250	!q.peekFirst().equals(i));
251	}
252	assertNull(q.peekFirst());
253	}
254
255	/**
256	* peek returns next element, or null if empty
257	*/
258	public void testPeek() {
259	ArrayDeque q = populatedDeque(SIZE);
260	for (int i = 0; i < SIZE; ++i) {
261	assertEquals(i, q.peek());
262	assertEquals(i, q.poll());
263	assertTrue(q.peek() == null \|\|
264	!q.peek().equals(i));
265	}
266	assertNull(q.peek());
267	}
268
269	/**
270	* peekLast returns next element, or null if empty
271	*/
272	public void testPeekLast() {
273	ArrayDeque q = populatedDeque(SIZE);
274	for (int i = SIZE-1; i >= 0; --i) {
275	assertEquals(i, q.peekLast());
276	assertEquals(i, q.pollLast());
277	assertTrue(q.peekLast() == null \|\|
278	!q.peekLast().equals(i));
279	}
280	assertNull(q.peekLast());
281	}
282
283	/**
284	* getFirst returns next getFirst, or throws NSEE if empty
285	*/
286	public void testFirstElement() {
287	ArrayDeque q = populatedDeque(SIZE);
288	for (int i = 0; i < SIZE; ++i) {
289	assertEquals(i, q.getFirst());
290	assertEquals(i, q.pollFirst());
291	}
292	try {
293	q.getFirst();
294	shouldThrow();
295	} catch (NoSuchElementException success) {}
296	}
297
298	/**
299	* getLast returns next element, or throws NSEE if empty
300	*/
301	public void testLastElement() {
302	ArrayDeque q = populatedDeque(SIZE);
303	for (int i = SIZE-1; i >= 0; --i) {
304	assertEquals(i, q.getLast());
305	assertEquals(i, q.pollLast());
306	}
307	try {
308	q.getLast();
309	shouldThrow();
310	} catch (NoSuchElementException success) {}
311	assertNull(q.peekLast());
312	}
313
314
315	/**
316	* removeFirst removes next element, or throws NSEE if empty
317	*/
318	public void testRemoveFirst() {
319	ArrayDeque q = populatedDeque(SIZE);
320	for (int i = 0; i < SIZE; ++i) {
321	assertEquals(i, q.removeFirst());
322	}
323	try {
324	q.removeFirst();
325	shouldThrow();
326	} catch (NoSuchElementException success) {}
327	}
328
329	/**
330	* removeFirstOccurrence(x) removes x and returns true if present
331	*/
332	public void testRemoveFirstOccurrence() {
333	ArrayDeque q = populatedDeque(SIZE);
334	for (int i = 1; i < SIZE; i+=2) {
335	assertTrue(q.removeFirstOccurrence(new Integer(i)));
336	}
337	for (int i = 0; i < SIZE; i+=2) {
338	assertTrue(q.removeFirstOccurrence(new Integer(i)));
339	assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
340	}
341	assertTrue(q.isEmpty());
342	}
343
344	/**
345	* removeLastOccurrence(x) removes x and returns true if present
346	*/
347	public void testRemoveLastOccurrence() {
348	ArrayDeque q = populatedDeque(SIZE);
349	for (int i = 1; i < SIZE; i+=2) {
350	assertTrue(q.removeLastOccurrence(new Integer(i)));
351	}
352	for (int i = 0; i < SIZE; i+=2) {
353	assertTrue(q.removeLastOccurrence(new Integer(i)));
354	assertFalse(q.removeLastOccurrence(new Integer(i+1)));
355	}
356	assertTrue(q.isEmpty());
357	}
358
359	/**
360	* contains(x) reports true when elements added but not yet removed
361	*/
362	public void testContains() {
363	ArrayDeque q = populatedDeque(SIZE);
364	for (int i = 0; i < SIZE; ++i) {
365	assertTrue(q.contains(new Integer(i)));
366	assertEquals(i, q.pollFirst());
367	assertFalse(q.contains(new Integer(i)));
368	}
369	}
370
371	/**
372	* clear removes all elements
373	*/
374	public void testClear() {
375	ArrayDeque q = populatedDeque(SIZE);
376	q.clear();
377	assertTrue(q.isEmpty());
378	assertEquals(0, q.size());
379	assertTrue(q.add(new Integer(1)));
380	assertFalse(q.isEmpty());
381	q.clear();
382	assertTrue(q.isEmpty());
383	}
384
385	/**
386	* containsAll(c) is true when c contains a subset of elements
387	*/
388	public void testContainsAll() {
389	ArrayDeque q = populatedDeque(SIZE);
390	ArrayDeque p = new ArrayDeque();
391	for (int i = 0; i < SIZE; ++i) {
392	assertTrue(q.containsAll(p));
393	assertFalse(p.containsAll(q));
394	assertTrue(p.add(new Integer(i)));
395	}
396	assertTrue(p.containsAll(q));
397	}
398
399	/**
400	* retainAll(c) retains only those elements of c and reports true if changed
401	*/
402	public void testRetainAll() {
403	ArrayDeque q = populatedDeque(SIZE);
404	ArrayDeque p = populatedDeque(SIZE);
405	for (int i = 0; i < SIZE; ++i) {
406	boolean changed = q.retainAll(p);
407	assertEquals(changed, (i > 0));
408	assertTrue(q.containsAll(p));
409	assertEquals(SIZE-i, q.size());
410	p.removeFirst();
411	}
412	}
413
414	/**
415	* removeAll(c) removes only those elements of c and reports true if changed
416	*/
417	public void testRemoveAll() {
418	for (int i = 1; i < SIZE; ++i) {
419	ArrayDeque q = populatedDeque(SIZE);
420	ArrayDeque p = populatedDeque(i);
421	assertTrue(q.removeAll(p));
422	assertEquals(SIZE-i, q.size());
423	for (int j = 0; j < i; ++j) {
424	assertFalse(q.contains(p.removeFirst()));
425	}
426	}
427	}
428
429	/**
430	* toArray contains all elements
431	*/
432	public void testToArray() {
433	ArrayDeque q = populatedDeque(SIZE);
434	Object[] o = q.toArray();
435	Arrays.sort(o);
436	for (int i = 0; i < o.length; i++)
437	assertEquals(o[i], q.pollFirst());
438	}
439
440	/**
441	* toArray(a) contains all elements
442	*/
443	public void testToArray2() {
444	ArrayDeque q = populatedDeque(SIZE);
445	Integer[] ints = new Integer[SIZE];
446	ints = (Integer[])q.toArray(ints);
447	Arrays.sort(ints);
448	for (int i = 0; i < ints.length; i++)
449	assertEquals(ints[i], q.pollFirst());
450	}
451
452	/**
453	* toArray(null) throws NPE
454	*/
455	public void testToArray_BadArg() {
456	ArrayDeque l = new ArrayDeque();
457	l.add(new Object());
458	try {
459	Object o[] = l.toArray(null);
460	shouldThrow();
461	} catch (NullPointerException success) {}
462	}
463
464	/**
465	* toArray with incompatible aray type throws CCE
466	*/
467	public void testToArray1_BadArg() {
468	ArrayDeque l = new ArrayDeque();
469	l.add(new Integer(5));
470	try {
471	Object o[] = l.toArray(new String[10]);
472	shouldThrow();
473	} catch (ArrayStoreException success) {}
474	}
475
476	/**
477	* iterator iterates through all elements
478	*/
479	public void testIterator() {
480	ArrayDeque q = populatedDeque(SIZE);
481	int i = 0;
482	Iterator it = q.iterator();
483	while (it.hasNext()) {
484	assertTrue(q.contains(it.next()));
485	++i;
486	}
487	assertEquals(i, SIZE);
488	}
489
490	/**
491	* iterator ordering is FIFO
492	*/
493	public void testIteratorOrdering() {
494	final ArrayDeque q = new ArrayDeque();
495	q.add(new Integer(1));
496	q.add(new Integer(2));
497	q.add(new Integer(3));
498	int k = 0;
499	for (Iterator it = q.iterator(); it.hasNext();) {
500	assertEquals(++k, it.next());
501	}
502
503	assertEquals(3, k);
504	}
505
506	/**
507	* iterator.remove removes current element
508	*/
509	public void testIteratorRemove () {
510	final ArrayDeque q = new ArrayDeque();
511	final Random rng = new Random();
512	for (int iters = 0; iters < 100; ++iters) {
513	int max = rng.nextInt(5) + 2;
514	int split = rng.nextInt(max-1) + 1;
515	for (int j = 1; j <= max; ++j)
516	q.add(new Integer(j));
517	Iterator it = q.iterator();
518	for (int j = 1; j <= split; ++j)
519	assertEquals(it.next(), new Integer(j));
520	it.remove();
521	assertEquals(it.next(), new Integer(split+1));
522	for (int j = 1; j <= split; ++j)
523	q.remove(new Integer(j));
524	it = q.iterator();
525	for (int j = split+1; j <= max; ++j) {
526	assertEquals(it.next(), new Integer(j));
527	it.remove();
528	}
529	assertFalse(it.hasNext());
530	assertTrue(q.isEmpty());
531	}
532	}
533
534	/**
535	* Descending iterator iterates through all elements
536	*/
537	public void testDescendingIterator() {
538	ArrayDeque q = populatedDeque(SIZE);
539	int i = 0;
540	Iterator it = q.descendingIterator();
541	while (it.hasNext()) {
542	assertTrue(q.contains(it.next()));
543	++i;
544	}
545	assertEquals(i, SIZE);
546	assertFalse(it.hasNext());
547	try {
548	it.next();
549	shouldThrow();
550	} catch (NoSuchElementException success) {}
551	}
552
553	/**
554	* Descending iterator ordering is reverse FIFO
555	*/
556	public void testDescendingIteratorOrdering() {
557	final ArrayDeque q = new ArrayDeque();
558	for (int iters = 0; iters < 100; ++iters) {
559	q.add(new Integer(3));
560	q.add(new Integer(2));
561	q.add(new Integer(1));
562	int k = 0;
563	for (Iterator it = q.descendingIterator(); it.hasNext();) {
564	assertEquals(++k, it.next());
565	}
566
567	assertEquals(3, k);
568	q.remove();
569	q.remove();
570	q.remove();
571	}
572	}
573
574	/**
575	* descendingIterator.remove removes current element
576	*/
577	public void testDescendingIteratorRemove () {
578	final ArrayDeque q = new ArrayDeque();
579	final Random rng = new Random();
580	for (int iters = 0; iters < 100; ++iters) {
581	int max = rng.nextInt(5) + 2;
582	int split = rng.nextInt(max-1) + 1;
583	for (int j = max; j >= 1; --j)
584	q.add(new Integer(j));
585	Iterator it = q.descendingIterator();
586	for (int j = 1; j <= split; ++j)
587	assertEquals(it.next(), new Integer(j));
588	it.remove();
589	assertEquals(it.next(), new Integer(split+1));
590	for (int j = 1; j <= split; ++j)
591	q.remove(new Integer(j));
592	it = q.descendingIterator();
593	for (int j = split+1; j <= max; ++j) {
594	assertEquals(it.next(), new Integer(j));
595	it.remove();
596	}
597	assertFalse(it.hasNext());
598	assertTrue(q.isEmpty());
599	}
600	}
601
602
603	/**
604	* toString contains toStrings of elements
605	*/
606	public void testToString() {
607	ArrayDeque q = populatedDeque(SIZE);
608	String s = q.toString();
609	for (int i = 0; i < SIZE; ++i) {
610	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
611	}
612	}
613
614	/**
615	* peekFirst returns element inserted with addFirst
616	*/
617	public void testAddFirst() {
618	ArrayDeque q = populatedDeque(3);
619	q.addFirst(four);
620	assertSame(four, q.peekFirst());
621	}
622
623	/**
624	* peekLast returns element inserted with addLast
625	*/
626	public void testAddLast() {
627	ArrayDeque q = populatedDeque(3);
628	q.addLast(four);
629	assertSame(four, q.peekLast());
630	}
631
632	}