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