test/tck/LinkedListTest.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 * Other contributors include Andrew Wright, Jeffrey Hayes,
 * Pat Fisher, Mike Judd.
 */

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

import junit.framework.Test;

public class LinkedListTest extends JSR166TestCase {
    public static void main(String[] args) {
        main(suite(), args);
    }

    public static Test suite() {
        class Implementation implements CollectionImplementation {
            public Class<?> klazz() { return LinkedList.class; }
            public Collection emptyCollection() { return new LinkedList(); }
            public Object makeElement(int i) { return i; }
            public boolean isConcurrent() { return false; }
            public boolean permitsNulls() { return true; }
        }
        class SubListImplementation extends Implementation {
            public Collection emptyCollection() {
                return new LinkedList().subList(0, 0);
            }
        }
        return newTestSuite(
                LinkedListTest.class,
                CollectionTest.testSuite(new Implementation()),
                CollectionTest.testSuite(new SubListImplementation()));
    }

    /**
     * Returns a new queue of given size containing consecutive
     * Integers 0 ... n - 1.
     */
    private static LinkedList<Integer> populatedQueue(int n) {
        LinkedList<Integer> 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());
        assertEquals((Integer) 0, q.peekFirst());
        assertEquals((Integer) (n - 1), q.peekLast());
        return q;
    }

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

    /**
     * Initializing from null Collection throws NPE
     */
    public void testConstructor3() {
        try {
            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);
        assertNull(q.get(0));
        assertTrue(q.contains(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() {
        LinkedList q = new LinkedList();
        try {
            q.addAll(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * Queue contains all elements, in traversal order, of successful addAll
     */
    public void testAddAll5() {
        Integer[] empty = new Integer[0];
        Integer[] ints = new Integer[SIZE];
        for (int i = 0; i < SIZE; ++i)
            ints[i] = i;
        LinkedList q = new LinkedList();
        assertFalse(q.addAll(Arrays.asList(empty)));
        assertTrue(q.addAll(Arrays.asList(ints)));
        for (int i = 0; i < SIZE; ++i)
            assertEquals(ints[i], q.poll());
    }

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

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

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

    /**
     * peek returns next element, or null if empty
     */
    public void testPeek() {
        LinkedList q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.peek());
            assertEquals(i, q.poll());
            assertTrue(q.peek() == null ||
                       !q.peek().equals(i));
        }
        assertNull(q.peek());
    }

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

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

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

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

    /**
     * clear removes all elements
     */
    public void testClear() {
        LinkedList q = populatedQueue(SIZE);
        q.clear();
        assertTrue(q.isEmpty());
        assertEquals(0, q.size());
        assertTrue(q.add(new Integer(1)));
        assertFalse(q.isEmpty());
        q.clear();
        assertTrue(q.isEmpty());
    }

    /**
     * containsAll(c) is true when c contains a subset of elements
     */
    public void testContainsAll() {
        LinkedList q = populatedQueue(SIZE);
        LinkedList p = new LinkedList();
        for (int i = 0; i < SIZE; ++i) {
            assertTrue(q.containsAll(p));
            assertFalse(p.containsAll(q));
            assertTrue(p.add(new Integer(i)));
        }
        assertTrue(p.containsAll(q));
    }

    /**
     * retainAll(c) retains only those elements of c and reports true if changed
     */
    public void testRetainAll() {
        LinkedList q = populatedQueue(SIZE);
        LinkedList p = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            boolean changed = q.retainAll(p);
            if (i == 0)
                assertFalse(changed);
            else
                assertTrue(changed);

            assertTrue(q.containsAll(p));
            assertEquals(SIZE - i, q.size());
            p.remove();
        }
    }

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

    /**
     * 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);
        Iterator it = q.iterator();
        int i;
        for (i = 0; it.hasNext(); i++)
            assertTrue(q.contains(it.next()));
        assertEquals(i, SIZE);
        assertIteratorExhausted(it);
    }

    /**
     * iterator of empty collection has no elements
     */
    public void testEmptyIterator() {
        assertIteratorExhausted(new LinkedList().iterator());
    }

    /**
     * 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(1, it.next());
        it.remove();
        it = q.iterator();
        assertEquals(2, it.next());
        assertEquals(3, it.next());
        assertFalse(it.hasNext());
    }

    /**
     * Descending iterator iterates through all elements
     */
    public void testDescendingIterator() {
        LinkedList q = populatedQueue(SIZE);
        int i = 0;
        Iterator it = q.descendingIterator();
        while (it.hasNext()) {
            assertTrue(q.contains(it.next()));
            ++i;
        }
        assertEquals(i, SIZE);
        assertFalse(it.hasNext());
        try {
            it.next();
            shouldThrow();
        } catch (NoSuchElementException success) {}
    }

    /**
     * Descending iterator ordering is reverse FIFO
     */
    public void testDescendingIteratorOrdering() {
        final LinkedList q = new LinkedList();
        q.add(new Integer(3));
        q.add(new Integer(2));
        q.add(new Integer(1));
        int k = 0;
        for (Iterator it = q.descendingIterator(); it.hasNext();) {
            assertEquals(++k, it.next());
        }

        assertEquals(3, k);
    }

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

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

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

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

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

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

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

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

    /**
     * peekFirst returns next element, or null if empty
     */
    public void testPeekFirst() {
        LinkedList q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.peekFirst());
            assertEquals(i, q.pollFirst());
            assertTrue(q.peekFirst() == null ||
                       !q.peekFirst().equals(i));
        }
        assertNull(q.peekFirst());
    }

    /**
     * peekLast returns next element, or null if empty
     */
    public void testPeekLast() {
        LinkedList q = populatedQueue(SIZE);
        for (int i = SIZE - 1; i >= 0; --i) {
            assertEquals(i, q.peekLast());
            assertEquals(i, q.pollLast());
            assertTrue(q.peekLast() == null ||
                       !q.peekLast().equals(i));
        }
        assertNull(q.peekLast());
    }

    public void testFirstElement() {
        LinkedList q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.getFirst());
            assertEquals(i, q.pollFirst());
        }
        try {
            q.getFirst();
            shouldThrow();
        } catch (NoSuchElementException success) {}
    }

    /**
     * getLast returns next element, or throws NSEE if empty
     */
    public void testLastElement() {
        LinkedList q = populatedQueue(SIZE);
        for (int i = SIZE - 1; i >= 0; --i) {
            assertEquals(i, q.getLast());
            assertEquals(i, q.pollLast());
        }
        try {
            q.getLast();
            shouldThrow();
        } catch (NoSuchElementException success) {}
        assertNull(q.peekLast());
    }

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

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

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