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<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.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 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.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.24
Committed:	Fri Nov 5 00:17:22 2010 UTC (13 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.23:	+5 -4 lines
Log Message:	very small improvements to testToArray2
#	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<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.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 in FIFO order
322	*/
323	public void testToArray() {
324	LinkedList q = populatedQueue(SIZE);
325	Object[] o = q.toArray();
326	for (int i = 0; i < o.length; i++)
327	assertSame(o[i], q.poll());
328	}
329
330	/**
331	* toArray(a) contains all elements in FIFO order
332	*/
333	public void testToArray2() {
334	LinkedList<Integer> q = populatedQueue(SIZE);
335	Integer[] ints = new Integer[SIZE];
336	Integer[] array = q.toArray(ints);
337	assertSame(ints, array);
338	for (int i = 0; i < ints.length; i++)
339	assertSame(ints[i], q.poll());
340	}
341
342	/**
343	* toArray(null) throws NullPointerException
344	*/
345	public void testToArray_NullArg() {
346	LinkedList l = new LinkedList();
347	l.add(new Object());
348	try {
349	l.toArray(null);
350	shouldThrow();
351	} catch (NullPointerException success) {}
352	}
353
354	/**
355	* toArray(incompatible array type) throws ArrayStoreException
356	*/
357	public void testToArray1_BadArg() {
358	LinkedList l = new LinkedList();
359	l.add(new Integer(5));
360	try {
361	l.toArray(new String[10]);
362	shouldThrow();
363	} catch (ArrayStoreException success) {}
364	}
365
366	/**
367	* iterator iterates through all elements
368	*/
369	public void testIterator() {
370	LinkedList q = populatedQueue(SIZE);
371	int i = 0;
372	Iterator it = q.iterator();
373	while (it.hasNext()) {
374	assertTrue(q.contains(it.next()));
375	++i;
376	}
377	assertEquals(i, SIZE);
378	}
379
380	/**
381	* iterator ordering is FIFO
382	*/
383	public void testIteratorOrdering() {
384	final LinkedList q = new LinkedList();
385	q.add(new Integer(1));
386	q.add(new Integer(2));
387	q.add(new Integer(3));
388	int k = 0;
389	for (Iterator it = q.iterator(); it.hasNext();) {
390	assertEquals(++k, it.next());
391	}
392
393	assertEquals(3, k);
394	}
395
396	/**
397	* iterator.remove removes current element
398	*/
399	public void testIteratorRemove() {
400	final LinkedList q = new LinkedList();
401	q.add(new Integer(1));
402	q.add(new Integer(2));
403	q.add(new Integer(3));
404	Iterator it = q.iterator();
405	assertEquals(it.next(), 1);
406	it.remove();
407	it = q.iterator();
408	assertEquals(it.next(), 2);
409	assertEquals(it.next(), 3);
410	assertFalse(it.hasNext());
411	}
412
413	/**
414	* Descending iterator iterates through all elements
415	*/
416	public void testDescendingIterator() {
417	LinkedList q = populatedQueue(SIZE);
418	int i = 0;
419	Iterator it = q.descendingIterator();
420	while (it.hasNext()) {
421	assertTrue(q.contains(it.next()));
422	++i;
423	}
424	assertEquals(i, SIZE);
425	assertFalse(it.hasNext());
426	try {
427	it.next();
428	shouldThrow();
429	} catch (NoSuchElementException success) {}
430	}
431
432	/**
433	* Descending iterator ordering is reverse FIFO
434	*/
435	public void testDescendingIteratorOrdering() {
436	final LinkedList q = new LinkedList();
437	q.add(new Integer(3));
438	q.add(new Integer(2));
439	q.add(new Integer(1));
440	int k = 0;
441	for (Iterator it = q.descendingIterator(); it.hasNext();) {
442	assertEquals(++k, it.next());
443	}
444
445	assertEquals(3, k);
446	}
447
448	/**
449	* descendingIterator.remove removes current element
450	*/
451	public void testDescendingIteratorRemove() {
452	final LinkedList q = new LinkedList();
453	q.add(three);
454	q.add(two);
455	q.add(one);
456	Iterator it = q.descendingIterator();
457	it.next();
458	it.remove();
459	it = q.descendingIterator();
460	assertSame(it.next(), two);
461	assertSame(it.next(), three);
462	assertFalse(it.hasNext());
463	}
464
465
466	/**
467	* toString contains toStrings of elements
468	*/
469	public void testToString() {
470	LinkedList q = populatedQueue(SIZE);
471	String s = q.toString();
472	for (int i = 0; i < SIZE; ++i) {
473	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
474	}
475	}
476
477	/**
478	* peek returns element inserted with addFirst
479	*/
480	public void testAddFirst() {
481	LinkedList q = populatedQueue(3);
482	q.addFirst(four);
483	assertSame(four, q.peek());
484	}
485
486	/**
487	* peekFirst returns element inserted with push
488	*/
489	public void testPush() {
490	LinkedList q = populatedQueue(3);
491	q.push(four);
492	assertSame(four, q.peekFirst());
493	}
494
495	/**
496	* pop removes next element, or throws NSEE if empty
497	*/
498	public void testPop() {
499	LinkedList q = populatedQueue(SIZE);
500	for (int i = 0; i < SIZE; ++i) {
501	assertEquals(i, q.pop());
502	}
503	try {
504	q.pop();
505	shouldThrow();
506	} catch (NoSuchElementException success) {}
507	}
508
509	/**
510	* OfferFirst succeeds
511	*/
512	public void testOfferFirst() {
513	LinkedList q = new LinkedList();
514	assertTrue(q.offerFirst(new Integer(0)));
515	assertTrue(q.offerFirst(new Integer(1)));
516	}
517
518	/**
519	* OfferLast succeeds
520	*/
521	public void testOfferLast() {
522	LinkedList q = new LinkedList();
523	assertTrue(q.offerLast(new Integer(0)));
524	assertTrue(q.offerLast(new Integer(1)));
525	}
526
527	/**
528	* pollLast succeeds unless empty
529	*/
530	public void testPollLast() {
531	LinkedList q = populatedQueue(SIZE);
532	for (int i = SIZE-1; i >= 0; --i) {
533	assertEquals(i, q.pollLast());
534	}
535	assertNull(q.pollLast());
536	}
537
538	/**
539	* peekFirst returns next element, or null if empty
540	*/
541	public void testPeekFirst() {
542	LinkedList q = populatedQueue(SIZE);
543	for (int i = 0; i < SIZE; ++i) {
544	assertEquals(i, q.peekFirst());
545	assertEquals(i, q.pollFirst());
546	assertTrue(q.peekFirst() == null \|\|
547	!q.peekFirst().equals(i));
548	}
549	assertNull(q.peekFirst());
550	}
551
552
553	/**
554	* peekLast returns next element, or null if empty
555	*/
556	public void testPeekLast() {
557	LinkedList q = populatedQueue(SIZE);
558	for (int i = SIZE-1; i >= 0; --i) {
559	assertEquals(i, q.peekLast());
560	assertEquals(i, q.pollLast());
561	assertTrue(q.peekLast() == null \|\|
562	!q.peekLast().equals(i));
563	}
564	assertNull(q.peekLast());
565	}
566
567	public void testFirstElement() {
568	LinkedList q = populatedQueue(SIZE);
569	for (int i = 0; i < SIZE; ++i) {
570	assertEquals(i, q.getFirst());
571	assertEquals(i, q.pollFirst());
572	}
573	try {
574	q.getFirst();
575	shouldThrow();
576	} catch (NoSuchElementException success) {}
577	}
578
579	/**
580	* getLast returns next element, or throws NSEE if empty
581	*/
582	public void testLastElement() {
583	LinkedList q = populatedQueue(SIZE);
584	for (int i = SIZE-1; i >= 0; --i) {
585	assertEquals(i, q.getLast());
586	assertEquals(i, q.pollLast());
587	}
588	try {
589	q.getLast();
590	shouldThrow();
591	} catch (NoSuchElementException success) {}
592	assertNull(q.peekLast());
593	}
594
595	/**
596	* removeFirstOccurrence(x) removes x and returns true if present
597	*/
598	public void testRemoveFirstOccurrence() {
599	LinkedList q = populatedQueue(SIZE);
600	for (int i = 1; i < SIZE; i+=2) {
601	assertTrue(q.removeFirstOccurrence(new Integer(i)));
602	}
603	for (int i = 0; i < SIZE; i+=2) {
604	assertTrue(q.removeFirstOccurrence(new Integer(i)));
605	assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
606	}
607	assertTrue(q.isEmpty());
608	}
609
610	/**
611	* removeLastOccurrence(x) removes x and returns true if present
612	*/
613	public void testRemoveLastOccurrence() {
614	LinkedList q = populatedQueue(SIZE);
615	for (int i = 1; i < SIZE; i+=2) {
616	assertTrue(q.removeLastOccurrence(new Integer(i)));
617	}
618	for (int i = 0; i < SIZE; i+=2) {
619	assertTrue(q.removeLastOccurrence(new Integer(i)));
620	assertFalse(q.removeLastOccurrence(new Integer(i+1)));
621	}
622	assertTrue(q.isEmpty());
623	}
624
625	}