test/tck/ArrayDequeTest.java

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        assertEquals(3, k);
    }

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

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

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

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

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


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

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

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

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