test/tck/LinkedListTest.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/publicdomain/zero/1.0/
 * Other contributors include Andrew Wright, Jeffrey Hayes,
 * Pat Fisher, Mike Judd.
 */

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

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

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

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

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

    /**
     * Initializing from null Collection throws NPE
     */
    public void testConstructor3() {
        try {
            LinkedList q = new LinkedList((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] = i;
        LinkedList q = new LinkedList(Arrays.asList(ints));
        for (int i = 0; i < SIZE; ++i)
            assertEquals(ints[i], q.poll());
    }

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

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

    /**
     * offer(null) succeeds
     */
    public void testOfferNull() {
        LinkedList q = new LinkedList();
        q.offer(null);
    }

    /**
     * Offer succeeds
     */
    public void testOffer() {
        LinkedList q = new LinkedList();
        assertTrue(q.offer(new Integer(0)));
        assertTrue(q.offer(new Integer(1)));
    }

    /**
     * add succeeds
     */
    public void testAdd() {
        LinkedList q = new LinkedList();
        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 {
            LinkedList q = new LinkedList();
            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] = i;
        LinkedList q = new LinkedList();
        assertFalse(q.addAll(Arrays.asList(empty)));
        assertTrue(q.addAll(Arrays.asList(ints)));
        for (int i = 0; i < SIZE; ++i)
            assertEquals(ints[i], q.poll());
    }

    /**
     * addAll with too large an index throws IOOBE
     */
    public void testAddAll2_IndexOutOfBoundsException() {
        LinkedList l = new LinkedList();
        l.add(new Object());
        LinkedList m = new LinkedList();
        m.add(new Object());
        try {
            l.addAll(4,m);
            shouldThrow();
        } catch (IndexOutOfBoundsException success) {}
    }

    /**
     * addAll with negative index throws IOOBE
     */
    public void testAddAll4_BadIndex() {
        LinkedList l = new LinkedList();
        l.add(new Object());
        LinkedList m = new LinkedList();
        m.add(new Object());
        try {
            l.addAll(-1,m);
            shouldThrow();
        } catch (IndexOutOfBoundsException success) {}
    }

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

    /**
     * peek returns next element, or null if empty
     */
    public void testPeek() {
        LinkedList q = populatedQueue(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());
    }

    /**
     * element returns next element, or throws NSEE if empty
     */
    public void testElement() {
        LinkedList q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.element());
            assertEquals(i, q.poll());
        }
        try {
            q.element();
            shouldThrow();
        } catch (NoSuchElementException success) {}
    }

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

    /**
     * remove(x) removes x and returns true if present
     */
    public void testRemoveElement() {
        LinkedList q = populatedQueue(SIZE);
        for (int i = 1; i < SIZE; i+=2) {
            assertTrue(q.contains(i));
            assertTrue(q.remove((Integer)i));
            assertFalse(q.contains(i));
            assertTrue(q.contains(i-1));
        }
        for (int i = 0; i < SIZE; i+=2) {
            assertTrue(q.contains(i));
            assertTrue(q.remove((Integer)i));
            assertFalse(q.contains(i));
            assertFalse(q.remove((Integer)(i+1)));
            assertFalse(q.contains(i+1));
        }
        assertTrue(q.isEmpty());
    }

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

    /**
     * clear removes all elements
     */
    public void testClear() {
        LinkedList q = populatedQueue(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() {
        LinkedList q = populatedQueue(SIZE);
        LinkedList p = new LinkedList();
        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() {
        LinkedList q = populatedQueue(SIZE);
        LinkedList p = populatedQueue(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.remove();
        }
    }

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

    /**
     * toArray contains all elements in FIFO order
     */
    public void testToArray() {
        LinkedList q = populatedQueue(SIZE);
        Object[] o = q.toArray();
        for (int i = 0; i < o.length; i++)
            assertSame(o[i], q.poll());
    }

    /**
     * toArray(a) contains all elements in FIFO order
     */
    public void testToArray2() {
        LinkedList<Integer> q = populatedQueue(SIZE);
        Integer[] ints = new Integer[SIZE];
        Integer[] array = q.toArray(ints);
        assertSame(ints, array);
        for (int i = 0; i < ints.length; i++)
            assertSame(ints[i], q.poll());
    }

    /**
     * toArray(null) throws NullPointerException
     */
    public void testToArray_NullArg() {
        LinkedList l = new LinkedList();
        l.add(new Object());
        try {
            l.toArray(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * toArray(incompatible array type) throws ArrayStoreException
     */
    public void testToArray1_BadArg() {
        LinkedList l = new LinkedList();
        l.add(new Integer(5));
        try {
            l.toArray(new String[10]);
            shouldThrow();
        } catch (ArrayStoreException success) {}
    }

    /**
     * iterator iterates through all elements
     */
    public void testIterator() {
        LinkedList q = populatedQueue(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 LinkedList q = new LinkedList();
        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 LinkedList q = new LinkedList();
        q.add(new Integer(1));
        q.add(new Integer(2));
        q.add(new Integer(3));
        Iterator it = q.iterator();
        assertEquals(it.next(), 1);
        it.remove();
        it = q.iterator();
        assertEquals(it.next(), 2);
        assertEquals(it.next(), 3);
        assertFalse(it.hasNext());
    }

    /**
     * Descending iterator iterates through all elements
     */
    public void testDescendingIterator() {
        LinkedList q = populatedQueue(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 LinkedList q = new LinkedList();
        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);
    }

    /**
     * descendingIterator.remove removes current element
     */
    public void testDescendingIteratorRemove() {
        final LinkedList q = new LinkedList();
        q.add(three);
        q.add(two);
        q.add(one);
        Iterator it = q.descendingIterator();
        it.next();
        it.remove();
        it = q.descendingIterator();
        assertSame(it.next(), two);
        assertSame(it.next(), three);
        assertFalse(it.hasNext());
    }

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

    /**
     * peek returns element inserted with addFirst
     */
    public void testAddFirst() {
        LinkedList q = populatedQueue(3);
        q.addFirst(four);
        assertSame(four, q.peek());
    }

    /**
     * peekFirst returns element inserted with push
     */
    public void testPush() {
        LinkedList q = populatedQueue(3);
        q.push(four);
        assertSame(four, q.peekFirst());
    }

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

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

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

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

    /**
     * peekFirst returns next element, or null if empty
     */
    public void testPeekFirst() {
        LinkedList q = populatedQueue(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());
    }

    /**
     * peekLast returns next element, or null if empty
     */
    public void testPeekLast() {
        LinkedList q = populatedQueue(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());
    }

    public void testFirstElement() {
        LinkedList q = populatedQueue(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() {
        LinkedList q = populatedQueue(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());
    }

    /**
     * removeFirstOccurrence(x) removes x and returns true if present
     */
    public void testRemoveFirstOccurrence() {
        LinkedList q = populatedQueue(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() {
        LinkedList q = populatedQueue(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());
    }

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