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);
        assertSame(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, q.pop());
        }
        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, q.pollFirst());
        }
        assertNull(q.pollFirst());
    }

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

    /**
     *  poll succeeds unless empty
     */
    public void testPoll() {
        ArrayDeque q = populatedDeque(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.poll());
        }
        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, q.remove());
        }
        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, q.peekFirst());
            assertEquals(i, q.pollFirst());
            assertTrue(q.peekFirst() == null ||
                       !q.peekFirst().equals(i));
        }
        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, q.peek());
            assertEquals(i, q.poll());
            assertTrue(q.peek() == null ||
                       !q.peek().equals(i));
        }
        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, q.peekLast());
            assertEquals(i, q.pollLast());
            assertTrue(q.peekLast() == null ||
                       !q.peekLast().equals(i));
        }
        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, q.getFirst());
            assertEquals(i, 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, q.getLast());
            assertEquals(i, 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, q.removeFirst());
        }
        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)));
            assertEquals(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());
        assertTrue(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));
            assertTrue(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);
            assertEquals(changed, (i > 0));
            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) {
                assertFalse(q.contains(p.removeFirst()));
            }
        }
    }

    /**
     *  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() {
        ArrayDeque l = new ArrayDeque();
        l.add(new Object());
        try {
            Object o[] = l.toArray(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * toArray with incompatable aray type throws CCE
     */
    public void testToArray1_BadArg() {
        ArrayDeque l = new ArrayDeque();
        l.add(new Integer(5));
        try {
            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();) {
            assertEquals(++k, it.next());
        }

        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();) {
                assertEquals(++k, it.next());
            }

            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);
        assertSame(four, q.peekFirst());
    }

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

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