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() {
        try {
            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());
        }
        finally {}
    }

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