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/licenses/publicdomain
 * 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 populatedQueue(int n) {
        LinkedList q = new LinkedList();
        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.remove(new Integer(i)));
        }
        for (int i = 0; i < SIZE; i+=2) {
            assertTrue(q.remove(new Integer(i)));
            assertFalse(q.remove(new Integer(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
     */
    public void testToArray() {
        LinkedList q = populatedQueue(SIZE);
        Object[] o = q.toArray();
        Arrays.sort(o);
        for (int i = 0; i < o.length; i++)
            assertEquals(o[i], q.poll());
    }

    /**
     * toArray(a) contains all elements
     */
    public void testToArray2() {
        LinkedList q = populatedQueue(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.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.indexOf(String.valueOf(i)) >= 0);
        }
    }

    /**
     * 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.22
Committed:	Wed Nov 3 16:46:34 2010 UTC (13 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.21:	+3 -3 lines
Log Message:	minor improvements to testToArray_BadArg
#	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/licenses/publicdomain
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 populatedQueue(int n) {
27	LinkedList q = new LinkedList();
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.remove(new Integer(i)));
237	}
238	for (int i = 0; i < SIZE; i+=2) {
239	assertTrue(q.remove(new Integer(i)));
240	assertFalse(q.remove(new Integer(i+1)));
241	}
242	assertTrue(q.isEmpty());
243	}
244
245	/**
246	* contains(x) reports true when elements added but not yet removed
247	*/
248	public void testContains() {
249	LinkedList q = populatedQueue(SIZE);
250	for (int i = 0; i < SIZE; ++i) {
251	assertTrue(q.contains(new Integer(i)));
252	q.poll();
253	assertFalse(q.contains(new Integer(i)));
254	}
255	}
256
257	/**
258	* clear removes all elements
259	*/
260	public void testClear() {
261	LinkedList q = populatedQueue(SIZE);
262	q.clear();
263	assertTrue(q.isEmpty());
264	assertEquals(0, q.size());
265	assertTrue(q.add(new Integer(1)));
266	assertFalse(q.isEmpty());
267	q.clear();
268	assertTrue(q.isEmpty());
269	}
270
271	/**
272	* containsAll(c) is true when c contains a subset of elements
273	*/
274	public void testContainsAll() {
275	LinkedList q = populatedQueue(SIZE);
276	LinkedList p = new LinkedList();
277	for (int i = 0; i < SIZE; ++i) {
278	assertTrue(q.containsAll(p));
279	assertFalse(p.containsAll(q));
280	assertTrue(p.add(new Integer(i)));
281	}
282	assertTrue(p.containsAll(q));
283	}
284
285	/**
286	* retainAll(c) retains only those elements of c and reports true if changed
287	*/
288	public void testRetainAll() {
289	LinkedList q = populatedQueue(SIZE);
290	LinkedList p = populatedQueue(SIZE);
291	for (int i = 0; i < SIZE; ++i) {
292	boolean changed = q.retainAll(p);
293	if (i == 0)
294	assertFalse(changed);
295	else
296	assertTrue(changed);
297
298	assertTrue(q.containsAll(p));
299	assertEquals(SIZE-i, q.size());
300	p.remove();
301	}
302	}
303
304	/**
305	* removeAll(c) removes only those elements of c and reports true if changed
306	*/
307	public void testRemoveAll() {
308	for (int i = 1; i < SIZE; ++i) {
309	LinkedList q = populatedQueue(SIZE);
310	LinkedList p = populatedQueue(i);
311	assertTrue(q.removeAll(p));
312	assertEquals(SIZE-i, q.size());
313	for (int j = 0; j < i; ++j) {
314	Integer I = (Integer)(p.remove());
315	assertFalse(q.contains(I));
316	}
317	}
318	}
319
320	/**
321	* toArray contains all elements
322	*/
323	public void testToArray() {
324	LinkedList q = populatedQueue(SIZE);
325	Object[] o = q.toArray();
326	Arrays.sort(o);
327	for (int i = 0; i < o.length; i++)
328	assertEquals(o[i], q.poll());
329	}
330
331	/**
332	* toArray(a) contains all elements
333	*/
334	public void testToArray2() {
335	LinkedList q = populatedQueue(SIZE);
336	Integer[] ints = new Integer[SIZE];
337	ints = (Integer[])q.toArray(ints);
338	Arrays.sort(ints);
339	for (int i = 0; i < ints.length; i++)
340	assertEquals(ints[i], q.poll());
341	}
342
343	/**
344	* toArray(null) throws NullPointerException
345	*/
346	public void testToArray_NullArg() {
347	LinkedList l = new LinkedList();
348	l.add(new Object());
349	try {
350	l.toArray(null);
351	shouldThrow();
352	} catch (NullPointerException success) {}
353	}
354
355	/**
356	* toArray(incompatible array type) throws ArrayStoreException
357	*/
358	public void testToArray1_BadArg() {
359	LinkedList l = new LinkedList();
360	l.add(new Integer(5));
361	try {
362	l.toArray(new String[10]);
363	shouldThrow();
364	} catch (ArrayStoreException success) {}
365	}
366
367	/**
368	* iterator iterates through all elements
369	*/
370	public void testIterator() {
371	LinkedList q = populatedQueue(SIZE);
372	int i = 0;
373	Iterator it = q.iterator();
374	while (it.hasNext()) {
375	assertTrue(q.contains(it.next()));
376	++i;
377	}
378	assertEquals(i, SIZE);
379	}
380
381	/**
382	* iterator ordering is FIFO
383	*/
384	public void testIteratorOrdering() {
385	final LinkedList q = new LinkedList();
386	q.add(new Integer(1));
387	q.add(new Integer(2));
388	q.add(new Integer(3));
389	int k = 0;
390	for (Iterator it = q.iterator(); it.hasNext();) {
391	assertEquals(++k, it.next());
392	}
393
394	assertEquals(3, k);
395	}
396
397	/**
398	* iterator.remove removes current element
399	*/
400	public void testIteratorRemove() {
401	final LinkedList q = new LinkedList();
402	q.add(new Integer(1));
403	q.add(new Integer(2));
404	q.add(new Integer(3));
405	Iterator it = q.iterator();
406	assertEquals(it.next(), 1);
407	it.remove();
408	it = q.iterator();
409	assertEquals(it.next(), 2);
410	assertEquals(it.next(), 3);
411	assertFalse(it.hasNext());
412	}
413
414	/**
415	* Descending iterator iterates through all elements
416	*/
417	public void testDescendingIterator() {
418	LinkedList q = populatedQueue(SIZE);
419	int i = 0;
420	Iterator it = q.descendingIterator();
421	while (it.hasNext()) {
422	assertTrue(q.contains(it.next()));
423	++i;
424	}
425	assertEquals(i, SIZE);
426	assertFalse(it.hasNext());
427	try {
428	it.next();
429	shouldThrow();
430	} catch (NoSuchElementException success) {}
431	}
432
433	/**
434	* Descending iterator ordering is reverse FIFO
435	*/
436	public void testDescendingIteratorOrdering() {
437	final LinkedList q = new LinkedList();
438	q.add(new Integer(3));
439	q.add(new Integer(2));
440	q.add(new Integer(1));
441	int k = 0;
442	for (Iterator it = q.descendingIterator(); it.hasNext();) {
443	assertEquals(++k, it.next());
444	}
445
446	assertEquals(3, k);
447	}
448
449	/**
450	* descendingIterator.remove removes current element
451	*/
452	public void testDescendingIteratorRemove() {
453	final LinkedList q = new LinkedList();
454	q.add(three);
455	q.add(two);
456	q.add(one);
457	Iterator it = q.descendingIterator();
458	it.next();
459	it.remove();
460	it = q.descendingIterator();
461	assertSame(it.next(), two);
462	assertSame(it.next(), three);
463	assertFalse(it.hasNext());
464	}
465
466
467	/**
468	* toString contains toStrings of elements
469	*/
470	public void testToString() {
471	LinkedList q = populatedQueue(SIZE);
472	String s = q.toString();
473	for (int i = 0; i < SIZE; ++i) {
474	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
475	}
476	}
477
478	/**
479	* peek returns element inserted with addFirst
480	*/
481	public void testAddFirst() {
482	LinkedList q = populatedQueue(3);
483	q.addFirst(four);
484	assertSame(four, q.peek());
485	}
486
487	/**
488	* peekFirst returns element inserted with push
489	*/
490	public void testPush() {
491	LinkedList q = populatedQueue(3);
492	q.push(four);
493	assertSame(four, q.peekFirst());
494	}
495
496	/**
497	* pop removes next element, or throws NSEE if empty
498	*/
499	public void testPop() {
500	LinkedList q = populatedQueue(SIZE);
501	for (int i = 0; i < SIZE; ++i) {
502	assertEquals(i, q.pop());
503	}
504	try {
505	q.pop();
506	shouldThrow();
507	} catch (NoSuchElementException success) {}
508	}
509
510	/**
511	* OfferFirst succeeds
512	*/
513	public void testOfferFirst() {
514	LinkedList q = new LinkedList();
515	assertTrue(q.offerFirst(new Integer(0)));
516	assertTrue(q.offerFirst(new Integer(1)));
517	}
518
519	/**
520	* OfferLast succeeds
521	*/
522	public void testOfferLast() {
523	LinkedList q = new LinkedList();
524	assertTrue(q.offerLast(new Integer(0)));
525	assertTrue(q.offerLast(new Integer(1)));
526	}
527
528	/**
529	* pollLast succeeds unless empty
530	*/
531	public void testPollLast() {
532	LinkedList q = populatedQueue(SIZE);
533	for (int i = SIZE-1; i >= 0; --i) {
534	assertEquals(i, q.pollLast());
535	}
536	assertNull(q.pollLast());
537	}
538
539	/**
540	* peekFirst returns next element, or null if empty
541	*/
542	public void testPeekFirst() {
543	LinkedList q = populatedQueue(SIZE);
544	for (int i = 0; i < SIZE; ++i) {
545	assertEquals(i, q.peekFirst());
546	assertEquals(i, q.pollFirst());
547	assertTrue(q.peekFirst() == null \|\|
548	!q.peekFirst().equals(i));
549	}
550	assertNull(q.peekFirst());
551	}
552
553
554	/**
555	* peekLast returns next element, or null if empty
556	*/
557	public void testPeekLast() {
558	LinkedList q = populatedQueue(SIZE);
559	for (int i = SIZE-1; i >= 0; --i) {
560	assertEquals(i, q.peekLast());
561	assertEquals(i, q.pollLast());
562	assertTrue(q.peekLast() == null \|\|
563	!q.peekLast().equals(i));
564	}
565	assertNull(q.peekLast());
566	}
567
568	public void testFirstElement() {
569	LinkedList q = populatedQueue(SIZE);
570	for (int i = 0; i < SIZE; ++i) {
571	assertEquals(i, q.getFirst());
572	assertEquals(i, q.pollFirst());
573	}
574	try {
575	q.getFirst();
576	shouldThrow();
577	} catch (NoSuchElementException success) {}
578	}
579
580	/**
581	* getLast returns next element, or throws NSEE if empty
582	*/
583	public void testLastElement() {
584	LinkedList q = populatedQueue(SIZE);
585	for (int i = SIZE-1; i >= 0; --i) {
586	assertEquals(i, q.getLast());
587	assertEquals(i, q.pollLast());
588	}
589	try {
590	q.getLast();
591	shouldThrow();
592	} catch (NoSuchElementException success) {}
593	assertNull(q.peekLast());
594	}
595
596	/**
597	* removeFirstOccurrence(x) removes x and returns true if present
598	*/
599	public void testRemoveFirstOccurrence() {
600	LinkedList q = populatedQueue(SIZE);
601	for (int i = 1; i < SIZE; i+=2) {
602	assertTrue(q.removeFirstOccurrence(new Integer(i)));
603	}
604	for (int i = 0; i < SIZE; i+=2) {
605	assertTrue(q.removeFirstOccurrence(new Integer(i)));
606	assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
607	}
608	assertTrue(q.isEmpty());
609	}
610
611	/**
612	* removeLastOccurrence(x) removes x and returns true if present
613	*/
614	public void testRemoveLastOccurrence() {
615	LinkedList q = populatedQueue(SIZE);
616	for (int i = 1; i < SIZE; i+=2) {
617	assertTrue(q.removeLastOccurrence(new Integer(i)));
618	}
619	for (int i = 0; i < SIZE; i+=2) {
620	assertTrue(q.removeLastOccurrence(new Integer(i)));
621	assertFalse(q.removeLastOccurrence(new Integer(i+1)));
622	}
623	assertTrue(q.isEmpty());
624	}
625
626	}