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() {
        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, ((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();
            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();) {
                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.11
Committed:	Sat Nov 21 20:34:59 2009 UTC (14 years, 5 months ago) by jsr166
Branch:	MAIN
Changes since 1.10:	+1 -0 lines
Log Message:	add missing shouldThrow()
#	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	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, ((Integer)q.pollFirst()).intValue());
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, ((Integer)q.pollLast()).intValue());
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, ((Integer)q.poll()).intValue());
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, ((Integer)q.remove()).intValue());
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, ((Integer)q.peekFirst()).intValue());
248	q.pollFirst();
249	assertTrue(q.peekFirst() == null \|\|
250	i != ((Integer)q.peekFirst()).intValue());
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, ((Integer)q.peek()).intValue());
262	q.poll();
263	assertTrue(q.peek() == null \|\|
264	i != ((Integer)q.peek()).intValue());
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, ((Integer)q.peekLast()).intValue());
276	q.pollLast();
277	assertTrue(q.peekLast() == null \|\|
278	i != ((Integer)q.peekLast()).intValue());
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, ((Integer)q.getFirst()).intValue());
290	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, ((Integer)q.getLast()).intValue());
305	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, ((Integer)q.removeFirst()).intValue());
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	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	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	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	if (i == 0)
408	assertFalse(changed);
409	else
410	assertTrue(changed);
411
412	assertTrue(q.containsAll(p));
413	assertEquals(SIZE-i, q.size());
414	p.removeFirst();
415	}
416	}
417
418	/**
419	* removeAll(c) removes only those elements of c and reports true if changed
420	*/
421	public void testRemoveAll() {
422	for (int i = 1; i < SIZE; ++i) {
423	ArrayDeque q = populatedDeque(SIZE);
424	ArrayDeque p = populatedDeque(i);
425	assertTrue(q.removeAll(p));
426	assertEquals(SIZE-i, q.size());
427	for (int j = 0; j < i; ++j) {
428	Integer I = (Integer)(p.removeFirst());
429	assertFalse(q.contains(I));
430	}
431	}
432	}
433
434	/**
435	* toArray contains all elements
436	*/
437	public void testToArray() {
438	ArrayDeque q = populatedDeque(SIZE);
439	Object[] o = q.toArray();
440	Arrays.sort(o);
441	for (int i = 0; i < o.length; i++)
442	assertEquals(o[i], q.pollFirst());
443	}
444
445	/**
446	* toArray(a) contains all elements
447	*/
448	public void testToArray2() {
449	ArrayDeque q = populatedDeque(SIZE);
450	Integer[] ints = new Integer[SIZE];
451	ints = (Integer[])q.toArray(ints);
452	Arrays.sort(ints);
453	for (int i = 0; i < ints.length; i++)
454	assertEquals(ints[i], q.pollFirst());
455	}
456
457	/**
458	* toArray(null) throws NPE
459	*/
460	public void testToArray_BadArg() {
461	try {
462	ArrayDeque l = new ArrayDeque();
463	l.add(new Object());
464	Object o[] = l.toArray(null);
465	shouldThrow();
466	} catch (NullPointerException success) {}
467	}
468
469	/**
470	* toArray with incompatable aray type throws CCE
471	*/
472	public void testToArray1_BadArg() {
473	try {
474	ArrayDeque l = new ArrayDeque();
475	l.add(new Integer(5));
476	Object o[] = l.toArray(new String[10] );
477	shouldThrow();
478	} catch (ArrayStoreException success) {}
479	}
480
481	/**
482	* iterator iterates through all elements
483	*/
484	public void testIterator() {
485	ArrayDeque q = populatedDeque(SIZE);
486	int i = 0;
487	Iterator it = q.iterator();
488	while (it.hasNext()) {
489	assertTrue(q.contains(it.next()));
490	++i;
491	}
492	assertEquals(i, SIZE);
493	}
494
495	/**
496	* iterator ordering is FIFO
497	*/
498	public void testIteratorOrdering() {
499	final ArrayDeque q = new ArrayDeque();
500	q.add(new Integer(1));
501	q.add(new Integer(2));
502	q.add(new Integer(3));
503	int k = 0;
504	for (Iterator it = q.iterator(); it.hasNext();) {
505	int i = ((Integer)(it.next())).intValue();
506	assertEquals(++k, i);
507	}
508
509	assertEquals(3, k);
510	}
511
512	/**
513	* iterator.remove removes current element
514	*/
515	public void testIteratorRemove () {
516	final ArrayDeque q = new ArrayDeque();
517	final Random rng = new Random();
518	for (int iters = 0; iters < 100; ++iters) {
519	int max = rng.nextInt(5) + 2;
520	int split = rng.nextInt(max-1) + 1;
521	for (int j = 1; j <= max; ++j)
522	q.add(new Integer(j));
523	Iterator it = q.iterator();
524	for (int j = 1; j <= split; ++j)
525	assertEquals(it.next(), new Integer(j));
526	it.remove();
527	assertEquals(it.next(), new Integer(split+1));
528	for (int j = 1; j <= split; ++j)
529	q.remove(new Integer(j));
530	it = q.iterator();
531	for (int j = split+1; j <= max; ++j) {
532	assertEquals(it.next(), new Integer(j));
533	it.remove();
534	}
535	assertFalse(it.hasNext());
536	assertTrue(q.isEmpty());
537	}
538	}
539
540	/**
541	* Descending iterator iterates through all elements
542	*/
543	public void testDescendingIterator() {
544	ArrayDeque q = populatedDeque(SIZE);
545	int i = 0;
546	Iterator it = q.descendingIterator();
547	while (it.hasNext()) {
548	assertTrue(q.contains(it.next()));
549	++i;
550	}
551	assertEquals(i, SIZE);
552	assertFalse(it.hasNext());
553	try {
554	it.next();
555	shouldThrow();
556	} catch (NoSuchElementException success) {}
557	}
558
559	/**
560	* Descending iterator ordering is reverse FIFO
561	*/
562	public void testDescendingIteratorOrdering() {
563	final ArrayDeque q = new ArrayDeque();
564	for (int iters = 0; iters < 100; ++iters) {
565	q.add(new Integer(3));
566	q.add(new Integer(2));
567	q.add(new Integer(1));
568	int k = 0;
569	for (Iterator it = q.descendingIterator(); it.hasNext();) {
570	int i = ((Integer)(it.next())).intValue();
571	assertEquals(++k, i);
572	}
573
574	assertEquals(3, k);
575	q.remove();
576	q.remove();
577	q.remove();
578	}
579	}
580
581	/**
582	* descendingIterator.remove removes current element
583	*/
584	public void testDescendingIteratorRemove () {
585	final ArrayDeque q = new ArrayDeque();
586	final Random rng = new Random();
587	for (int iters = 0; iters < 100; ++iters) {
588	int max = rng.nextInt(5) + 2;
589	int split = rng.nextInt(max-1) + 1;
590	for (int j = max; j >= 1; --j)
591	q.add(new Integer(j));
592	Iterator it = q.descendingIterator();
593	for (int j = 1; j <= split; ++j)
594	assertEquals(it.next(), new Integer(j));
595	it.remove();
596	assertEquals(it.next(), new Integer(split+1));
597	for (int j = 1; j <= split; ++j)
598	q.remove(new Integer(j));
599	it = q.descendingIterator();
600	for (int j = split+1; j <= max; ++j) {
601	assertEquals(it.next(), new Integer(j));
602	it.remove();
603	}
604	assertFalse(it.hasNext());
605	assertTrue(q.isEmpty());
606	}
607	}
608
609
610	/**
611	* toString contains toStrings of elements
612	*/
613	public void testToString() {
614	ArrayDeque q = populatedDeque(SIZE);
615	String s = q.toString();
616	for (int i = 0; i < SIZE; ++i) {
617	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
618	}
619	}
620
621	/**
622	* peekFirst returns element inserted with addFirst
623	*/
624	public void testAddFirst() {
625	ArrayDeque q = populatedDeque(3);
626	q.addFirst(four);
627	assertEquals(four,q.peekFirst());
628	}
629
630	/**
631	* peekLast returns element inserted with addLast
632	*/
633	public void testAddLast() {
634	ArrayDeque q = populatedDeque(3);
635	q.addLast(four);
636	assertEquals(four,q.peekLast());
637	}
638
639	}