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.8
Committed:	Sat Nov 21 02:07:26 2009 UTC (14 years, 5 months ago) by jsr166
Branch:	MAIN
Changes since 1.7:	+42 -42 lines
Log Message:	untabify
#	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			}
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	jsr166	1.8	try {
102	dl	1.1	ArrayDeque q = new ArrayDeque(1);
103			q.push(null);
104			shouldThrow();
105	jsr166	1.5	} catch (NullPointerException success) { }
106	dl	1.1	}
107
108			/**
109			* peekFirst returns element inserted with push
110			*/
111			public void testPush() {
112			ArrayDeque q = populatedDeque(3);
113			q.pollLast();
114	jsr166	1.8	q.push(four);
115			assertEquals(four,q.peekFirst());
116	jsr166	1.5	}
117	dl	1.1
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	jsr166	1.7	} catch (NoSuchElementException success) {
130	jsr166	1.8	}
131	dl	1.1	}
132
133			/**
134			* offer(null) throws NPE
135			*/
136			public void testOfferFirstNull() {
137	jsr166	1.8	try {
138	dl	1.1	ArrayDeque q = new ArrayDeque();
139			q.offerFirst(null);
140			shouldThrow();
141	jsr166	1.5	} catch (NullPointerException success) {
142			}
143	dl	1.1	}
144
145			/**
146	jsr166	1.5	* OfferFirst succeeds
147	dl	1.1	*/
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	jsr166	1.5	* OfferLast succeeds
156	dl	1.1	*/
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	jsr166	1.8	assertNull(q.pollFirst());
213	dl	1.1	}
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	jsr166	1.8	assertNull(q.pollLast());
224	dl	1.1	}
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	jsr166	1.8	assertNull(q.poll());
235	dl	1.1	}
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	jsr166	1.7	} catch (NoSuchElementException success) {
249	jsr166	1.8	}
250	dl	1.1	}
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	jsr166	1.8	assertNull(q.peekFirst());
264	dl	1.1	}
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	jsr166	1.8	assertNull(q.peek());
278	dl	1.1	}
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	jsr166	1.8	assertNull(q.peekLast());
292	dl	1.1	}
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	jsr166	1.8	assertNull(q.peekLast());
325	dl	1.1	}
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	jsr166	1.7	} catch (NoSuchElementException success) {
340	jsr166	1.8	}
341	dl	1.1	}
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	jsr166	1.8	Object[] o = q.toArray();
454	dl	1.1	Arrays.sort(o);
455	jsr166	1.8	for (int i = 0; i < o.length; i++)
456			assertEquals(o[i], q.pollFirst());
457	dl	1.1	}
458
459			/**
460			* toArray(a) contains all elements
461			*/
462			public void testToArray2() {
463			ArrayDeque q = populatedDeque(SIZE);
464	jsr166	1.8	Integer[] ints = new Integer[SIZE];
465			ints = (Integer[])q.toArray(ints);
466	dl	1.1	Arrays.sort(ints);
467	jsr166	1.6	for (int i = 0; i < ints.length; i++)
468	dl	1.1	assertEquals(ints[i], q.pollFirst());
469			}
470
471			/**
472			* toArray(null) throws NPE
473			*/
474			public void testToArray_BadArg() {
475	jsr166	1.8	try {
476			ArrayDeque l = new ArrayDeque();
477			l.add(new Object());
478			Object o[] = l.toArray(null);
479			shouldThrow();
480			} catch (NullPointerException success) {}
481	dl	1.1	}
482
483			/**
484			* toArray with incompatable aray type throws CCE
485			*/
486			public void testToArray1_BadArg() {
487	jsr166	1.8	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	dl	1.1	}
494	jsr166	1.5
495	dl	1.1	/**
496			* iterator iterates through all elements
497			*/
498			public void testIterator() {
499			ArrayDeque q = populatedDeque(SIZE);
500			int i = 0;
501	jsr166	1.8	Iterator it = q.iterator();
502	jsr166	1.6	while (it.hasNext()) {
503	dl	1.1	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	dl	1.4	final Random rng = new Random();
532	dl	1.3	for (int iters = 0; iters < 100; ++iters) {
533	dl	1.4	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	dl	1.3	Iterator it = q.iterator();
538	jsr166	1.5	for (int j = 1; j <= split; ++j)
539	dl	1.4	assertEquals(it.next(), new Integer(j));
540	dl	1.3	it.remove();
541	dl	1.4	assertEquals(it.next(), new Integer(split+1));
542	jsr166	1.5	for (int j = 1; j <= split; ++j)
543	dl	1.4	q.remove(new Integer(j));
544	dl	1.3	it = q.iterator();
545	dl	1.4	for (int j = split+1; j <= max; ++j) {
546			assertEquals(it.next(), new Integer(j));
547			it.remove();
548			}
549	dl	1.3	assertFalse(it.hasNext());
550	dl	1.4	assertTrue(q.isEmpty());
551	dl	1.3	}
552	dl	1.1	}
553
554	dl	1.2	/**
555			* Descending iterator iterates through all elements
556			*/
557			public void testDescendingIterator() {
558			ArrayDeque q = populatedDeque(SIZE);
559			int i = 0;
560	jsr166	1.8	Iterator it = q.descendingIterator();
561	jsr166	1.6	while (it.hasNext()) {
562	dl	1.2	assertTrue(q.contains(it.next()));
563			++i;
564			}
565			assertEquals(i, SIZE);
566			assertFalse(it.hasNext());
567			try {
568			it.next();
569	jsr166	1.6	} catch (NoSuchElementException success) {
570	dl	1.2	}
571			}
572
573			/**
574			* Descending iterator ordering is reverse FIFO
575			*/
576			public void testDescendingIteratorOrdering() {
577			final ArrayDeque q = new ArrayDeque();
578	dl	1.3	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	jsr166	1.5
588	dl	1.3	assertEquals(3, k);
589			q.remove();
590			q.remove();
591			q.remove();
592	dl	1.2	}
593			}
594
595			/**
596			* descendingIterator.remove removes current element
597			*/
598			public void testDescendingIteratorRemove () {
599			final ArrayDeque q = new ArrayDeque();
600	dl	1.4	final Random rng = new Random();
601	dl	1.3	for (int iters = 0; iters < 100; ++iters) {
602	dl	1.4	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	dl	1.3	Iterator it = q.descendingIterator();
607	jsr166	1.5	for (int j = 1; j <= split; ++j)
608	dl	1.4	assertEquals(it.next(), new Integer(j));
609	dl	1.3	it.remove();
610	dl	1.4	assertEquals(it.next(), new Integer(split+1));
611	jsr166	1.5	for (int j = 1; j <= split; ++j)
612	dl	1.4	q.remove(new Integer(j));
613	dl	1.3	it = q.descendingIterator();
614	dl	1.4	for (int j = split+1; j <= max; ++j) {
615			assertEquals(it.next(), new Integer(j));
616			it.remove();
617			}
618	dl	1.3	assertFalse(it.hasNext());
619	dl	1.4	assertTrue(q.isEmpty());
620	dl	1.3	}
621	dl	1.2	}
622
623	dl	1.1
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	jsr166	1.5	}
634	dl	1.1
635			/**
636			* peekFirst returns element inserted with addFirst
637			*/
638			public void testAddFirst() {
639			ArrayDeque q = populatedDeque(3);
640	jsr166	1.8	q.addFirst(four);
641			assertEquals(four,q.peekFirst());
642	jsr166	1.5	}
643	dl	1.1
644			/**
645			* peekLast returns element inserted with addLast
646			*/
647			public void testAddLast() {
648			ArrayDeque q = populatedDeque(3);
649	jsr166	1.8	q.addLast(four);
650			assertEquals(four,q.peekLast());
651	jsr166	1.5	}
652	dl	1.1
653			}