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()
#	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	jsr166	1.10	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	dl	1.1	}
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	jsr166	1.8	assertNull(q.pollFirst());
203	dl	1.1	}
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	jsr166	1.8	assertNull(q.pollLast());
214	dl	1.1	}
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	jsr166	1.8	assertNull(q.poll());
225	dl	1.1	}
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	jsr166	1.9	} catch (NoSuchElementException success) {}
239	dl	1.1	}
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	jsr166	1.8	assertNull(q.peekFirst());
253	dl	1.1	}
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	jsr166	1.8	assertNull(q.peek());
267	dl	1.1	}
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	jsr166	1.8	assertNull(q.peekLast());
281	dl	1.1	}
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	jsr166	1.9	} catch (NoSuchElementException success) {}
296	dl	1.1	}
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	jsr166	1.9	} catch (NoSuchElementException success) {}
311	jsr166	1.8	assertNull(q.peekLast());
312	dl	1.1	}
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	jsr166	1.9	} catch (NoSuchElementException success) {}
327	dl	1.1	}
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	jsr166	1.8	Object[] o = q.toArray();
440	dl	1.1	Arrays.sort(o);
441	jsr166	1.8	for (int i = 0; i < o.length; i++)
442			assertEquals(o[i], q.pollFirst());
443	dl	1.1	}
444
445			/**
446			* toArray(a) contains all elements
447			*/
448			public void testToArray2() {
449			ArrayDeque q = populatedDeque(SIZE);
450	jsr166	1.8	Integer[] ints = new Integer[SIZE];
451			ints = (Integer[])q.toArray(ints);
452	dl	1.1	Arrays.sort(ints);
453	jsr166	1.6	for (int i = 0; i < ints.length; i++)
454	dl	1.1	assertEquals(ints[i], q.pollFirst());
455			}
456
457			/**
458			* toArray(null) throws NPE
459			*/
460			public void testToArray_BadArg() {
461	jsr166	1.8	try {
462			ArrayDeque l = new ArrayDeque();
463			l.add(new Object());
464			Object o[] = l.toArray(null);
465			shouldThrow();
466			} catch (NullPointerException success) {}
467	dl	1.1	}
468
469			/**
470			* toArray with incompatable aray type throws CCE
471			*/
472			public void testToArray1_BadArg() {
473	jsr166	1.8	try {
474			ArrayDeque l = new ArrayDeque();
475			l.add(new Integer(5));
476			Object o[] = l.toArray(new String[10] );
477			shouldThrow();
478	jsr166	1.9	} catch (ArrayStoreException success) {}
479	dl	1.1	}
480	jsr166	1.5
481	dl	1.1	/**
482			* iterator iterates through all elements
483			*/
484			public void testIterator() {
485			ArrayDeque q = populatedDeque(SIZE);
486			int i = 0;
487	jsr166	1.8	Iterator it = q.iterator();
488	jsr166	1.6	while (it.hasNext()) {
489	dl	1.1	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	dl	1.4	final Random rng = new Random();
518	dl	1.3	for (int iters = 0; iters < 100; ++iters) {
519	dl	1.4	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	dl	1.3	Iterator it = q.iterator();
524	jsr166	1.5	for (int j = 1; j <= split; ++j)
525	dl	1.4	assertEquals(it.next(), new Integer(j));
526	dl	1.3	it.remove();
527	dl	1.4	assertEquals(it.next(), new Integer(split+1));
528	jsr166	1.5	for (int j = 1; j <= split; ++j)
529	dl	1.4	q.remove(new Integer(j));
530	dl	1.3	it = q.iterator();
531	dl	1.4	for (int j = split+1; j <= max; ++j) {
532			assertEquals(it.next(), new Integer(j));
533			it.remove();
534			}
535	dl	1.3	assertFalse(it.hasNext());
536	dl	1.4	assertTrue(q.isEmpty());
537	dl	1.3	}
538	dl	1.1	}
539
540	dl	1.2	/**
541			* Descending iterator iterates through all elements
542			*/
543			public void testDescendingIterator() {
544			ArrayDeque q = populatedDeque(SIZE);
545			int i = 0;
546	jsr166	1.8	Iterator it = q.descendingIterator();
547	jsr166	1.6	while (it.hasNext()) {
548	dl	1.2	assertTrue(q.contains(it.next()));
549			++i;
550			}
551			assertEquals(i, SIZE);
552			assertFalse(it.hasNext());
553			try {
554			it.next();
555	jsr166	1.11	shouldThrow();
556	jsr166	1.9	} catch (NoSuchElementException success) {}
557	dl	1.2	}
558
559			/**
560			* Descending iterator ordering is reverse FIFO
561			*/
562			public void testDescendingIteratorOrdering() {
563			final ArrayDeque q = new ArrayDeque();
564	dl	1.3	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	jsr166	1.5
574	dl	1.3	assertEquals(3, k);
575			q.remove();
576			q.remove();
577			q.remove();
578	dl	1.2	}
579			}
580
581			/**
582			* descendingIterator.remove removes current element
583			*/
584			public void testDescendingIteratorRemove () {
585			final ArrayDeque q = new ArrayDeque();
586	dl	1.4	final Random rng = new Random();
587	dl	1.3	for (int iters = 0; iters < 100; ++iters) {
588	dl	1.4	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	dl	1.3	Iterator it = q.descendingIterator();
593	jsr166	1.5	for (int j = 1; j <= split; ++j)
594	dl	1.4	assertEquals(it.next(), new Integer(j));
595	dl	1.3	it.remove();
596	dl	1.4	assertEquals(it.next(), new Integer(split+1));
597	jsr166	1.5	for (int j = 1; j <= split; ++j)
598	dl	1.4	q.remove(new Integer(j));
599	dl	1.3	it = q.descendingIterator();
600	dl	1.4	for (int j = split+1; j <= max; ++j) {
601			assertEquals(it.next(), new Integer(j));
602			it.remove();
603			}
604	dl	1.3	assertFalse(it.hasNext());
605	dl	1.4	assertTrue(q.isEmpty());
606	dl	1.3	}
607	dl	1.2	}
608
609	dl	1.1
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	jsr166	1.5	}
620	dl	1.1
621			/**
622			* peekFirst returns element inserted with addFirst
623			*/
624			public void testAddFirst() {
625			ArrayDeque q = populatedDeque(3);
626	jsr166	1.8	q.addFirst(four);
627			assertEquals(four,q.peekFirst());
628	jsr166	1.5	}
629	dl	1.1
630			/**
631			* peekLast returns element inserted with addLast
632			*/
633			public void testAddLast() {
634			ArrayDeque q = populatedDeque(3);
635	jsr166	1.8	q.addLast(four);
636			assertEquals(four,q.peekLast());
637	jsr166	1.5	}
638	dl	1.1
639			}