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] = new Integer(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] = new Integer(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, ((Integer)q.poll()).intValue());
        }
        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, ((Integer)q.peek()).intValue());
            q.poll();
            assertTrue(q.peek() == null ||
                       i != ((Integer)q.peek()).intValue());
        }
        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, ((Integer)q.element()).intValue());
            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, ((Integer)q.remove()).intValue());
        }
        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());
        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));
            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 NPE
     */
    public void testToArray_BadArg() {
        try {
            LinkedList l = new LinkedList();
            l.add(new Object());
            Object o[] = l.toArray(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

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

        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();
        it.next();
        it.remove();
        it = q.iterator();
        assertEquals(it.next(), new Integer(2));
        assertEquals(it.next(), new Integer(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();) {
            int i = ((Integer)(it.next())).intValue();
            assertEquals(++k, i);
        }

        assertEquals(3, k);
    }

    /**
     * descendingIterator.remove removes current element
     */
    public void testDescendingIteratorRemove () {
        final LinkedList q = new LinkedList();
        q.add(new Integer(3));
        q.add(new Integer(2));
        q.add(new Integer(1));
        Iterator it = q.descendingIterator();
        it.next();
        it.remove();
        it = q.descendingIterator();
        assertEquals(it.next(), new Integer(2));
        assertEquals(it.next(), new Integer(3));
        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);
        assertEquals(four,q.peek());
    }

    /**
     * peekFirst returns element inserted with push
     */
    public void testPush() {
        LinkedList q = populatedQueue(3);
        q.pollLast();
        q.push(four);
        assertEquals(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, ((Integer)q.pop()).intValue());
        }
        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, ((Integer)q.pollLast()).intValue());
        }
        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, ((Integer)q.peekFirst()).intValue());
            q.pollFirst();
            assertTrue(q.peekFirst() == null ||
                       i != ((Integer)q.peekFirst()).intValue());
        }
        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, ((Integer)q.peekLast()).intValue());
            q.pollLast();
            assertTrue(q.peekLast() == null ||
                       i != ((Integer)q.peekLast()).intValue());
        }
        assertNull(q.peekLast());
    }

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