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.List;
import java.util.NoSuchElementException;
import java.util.concurrent.ThreadLocalRandom;

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 List emptyCollection() { return new LinkedList(); }
            public Object makeElement(int i) { return JSR166TestCase.itemFor(i); }
            public boolean isConcurrent() { return false; }
            public boolean permitsNulls() { return true; }
        }
        class SubListImplementation extends Implementation {
            @SuppressWarnings("unchecked")
            public List emptyCollection() {
                List list = super.emptyCollection();
                ThreadLocalRandom rnd = ThreadLocalRandom.current();
                if (rnd.nextBoolean())
                    list.add(makeElement(rnd.nextInt()));
                int i = rnd.nextInt(list.size() + 1);
                return list.subList(i, i);
            }
        }
        return newTestSuite(
                LinkedListTest.class,
                CollectionTest.testSuite(new Implementation()),
                CollectionTest.testSuite(new SubListImplementation()));
    }

    /**
     * Returns a new queue of given size containing consecutive
     * Items 0 ... n - 1.
     */
    private static LinkedList<Item> populatedQueue(int n) {
        LinkedList<Item> q = new LinkedList<>();
        assertTrue(q.isEmpty());
        for (int i = 0; i < n; ++i)
            mustOffer(q, i);
        assertFalse(q.isEmpty());
        mustEqual(n, q.size());
        mustEqual(0, q.peekFirst());
        mustEqual((n - 1), q.peekLast());
        return q;
    }

    /**
     * new queue is empty
     */
    public void testConstructor1() {
        mustEqual(0, new LinkedList<Item>().size());
    }

    /**
     * Initializing from null Collection throws NPE
     */
    public void testConstructor3() {
        try {
            new LinkedList<Item>((Collection<Item>)null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * Queue contains all elements of collection used to initialize
     */
    public void testConstructor6() {
        Item[] items = defaultItems;
        LinkedList<Item> q = new LinkedList<>(Arrays.asList(items));
        for (int i = 0; i < SIZE; ++i)
            mustEqual(items[i], q.poll());
    }

    /**
     * isEmpty is true before add, false after
     */
    public void testEmpty() {
        LinkedList<Item> q = new LinkedList<>();
        assertTrue(q.isEmpty());
        q.add(one);
        assertFalse(q.isEmpty());
        q.add(two);
        q.remove();
        q.remove();
        assertTrue(q.isEmpty());
    }

    /**
     * size changes when elements added and removed
     */
    public void testSize() {
        LinkedList<Item> q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            mustEqual(SIZE - i, q.size());
            q.remove();
        }
        for (int i = 0; i < SIZE; ++i) {
            mustEqual(i, q.size());
            mustAdd(q, i);
        }
    }

    /**
     * offer(null) succeeds
     */
    public void testOfferNull() {
        LinkedList<Item> q = new LinkedList<>();
        q.offer(null);
        assertNull(q.get(0));
        assertTrue(q.contains(null));
    }

    /**
     * Offer succeeds
     */
    public void testOffer() {
        LinkedList<Item> q = new LinkedList<>();
        mustOffer(q, zero);
        mustOffer(q, one);
    }

    /**
     * add succeeds
     */
    public void testAdd() {
        LinkedList<Item> q = new LinkedList<>();
        for (int i = 0; i < SIZE; ++i) {
            mustEqual(i, q.size());
            mustAdd(q, i);
        }
    }

    /**
     * addAll(null) throws NPE
     */
    public void testAddAll1() {
        LinkedList<Item> q = new LinkedList<>();
        try {
            q.addAll(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

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

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

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

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

    /**
     * peek returns next element, or null if empty
     */
    public void testPeek() {
        LinkedList<Item> q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            mustEqual(i, q.peek());
            mustEqual(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<Item> q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            mustEqual(i, q.element());
            mustEqual(i, q.poll());
        }
        try {
            q.element();
            shouldThrow();
        } catch (NoSuchElementException success) {}
    }

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

    /**
     * remove(x) removes x and returns true if present
     */
    public void testRemoveElement() {
        LinkedList<Item> q = populatedQueue(SIZE);
        for (int i = 1; i < SIZE; i += 2) {
            mustContain(q, i);
            mustRemove(q, i);
            mustNotContain(q, i);
            mustContain(q, i - 1);
        }
        for (int i = 0; i < SIZE; i += 2) {
            mustContain(q, i);
            mustRemove(q, i);
            mustNotContain(q, i);
            mustNotRemove(q, i + 1);
            mustNotContain(q, i + 1);
        }
        assertTrue(q.isEmpty());
    }

    /**
     * contains(x) reports true when elements added but not yet removed
     */
    public void testContains() {
        LinkedList<Item> q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            mustContain(q, i);
            q.poll();
            mustNotContain(q, i);
        }
    }

    /**
     * clear removes all elements
     */
    public void testClear() {
        LinkedList<Item> q = populatedQueue(SIZE);
        q.clear();
        assertTrue(q.isEmpty());
        mustEqual(0, q.size());
        mustAdd(q, one);
        assertFalse(q.isEmpty());
        q.clear();
        assertTrue(q.isEmpty());
    }

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

    /**
     * retainAll(c) retains only those elements of c and reports true if changed
     */
    public void testRetainAll() {
        LinkedList<Item> q = populatedQueue(SIZE);
        LinkedList<Item> 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));
            mustEqual(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<Item> q = populatedQueue(SIZE);
            LinkedList<Item> p = populatedQueue(i);
            assertTrue(q.removeAll(p));
            mustEqual(SIZE - i, q.size());
            for (int j = 0; j < i; ++j) {
                mustNotContain(q, p.remove());
            }
        }
    }

    /**
     * toArray contains all elements in FIFO order
     */
    public void testToArray() {
        LinkedList<Item> q = populatedQueue(SIZE);
        Object[] a = q.toArray();
        assertSame(Object[].class, a.getClass());
        for (Object o : a)
            assertSame(o, q.poll());
        assertTrue(q.isEmpty());
    }

    /**
     * toArray(a) contains all elements in FIFO order
     */
    public void testToArray2() {
        LinkedList<Item> q = populatedQueue(SIZE);
        Item[] items = new Item[SIZE];
        Item[] array = q.toArray(items);
        assertSame(items, array);
        for (Item o : items)
            assertSame(o, q.poll());
        assertTrue(q.isEmpty());
    }

    /**
     * toArray(null) throws NullPointerException
     */
    public void testToArray_NullArg() {
        LinkedList<Item> l = new LinkedList<>();
        l.add(zero);
        try {
            l.toArray((Item[])null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * toArray(incompatible array type) throws ArrayStoreException
     */
    public void testToArray1_BadArg() {
        LinkedList<Item> l = new LinkedList<>();
        l.add(five);
        try {
            l.toArray(new String[10]);
            shouldThrow();
        } catch (ArrayStoreException success) {}
    }

    /**
     * iterator iterates through all elements
     */
    public void testIterator() {
        LinkedList<Item> q = populatedQueue(SIZE);
        Iterator<? extends Item> it = q.iterator();
        int i;
        for (i = 0; it.hasNext(); i++)
            mustContain(q, it.next());
        mustEqual(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<Item> q = new LinkedList<>();
        q.add(one);
        q.add(two);
        q.add(three);
        int k = 0;
        for (Iterator<? extends Item> it = q.iterator(); it.hasNext();) {
            mustEqual(++k, it.next());
        }

        mustEqual(3, k);
    }

    /**
     * iterator.remove removes current element
     */
    public void testIteratorRemove() {
        final LinkedList<Item> q = new LinkedList<>();
        q.add(one);
        q.add(two);
        q.add(three);
        Iterator<? extends Item> it = q.iterator();
        mustEqual(1, it.next());
        it.remove();
        it = q.iterator();
        mustEqual(2, it.next());
        mustEqual(3, it.next());
        assertFalse(it.hasNext());
    }

    /**
     * Descending iterator iterates through all elements
     */
    public void testDescendingIterator() {
        LinkedList<Item> q = populatedQueue(SIZE);
        int i = 0;
        Iterator<? extends Item> it = q.descendingIterator();
        while (it.hasNext()) {
            mustContain(q, it.next());
            ++i;
        }
        mustEqual(i, SIZE);
        assertFalse(it.hasNext());
        try {
            it.next();
            shouldThrow();
        } catch (NoSuchElementException success) {}
    }

    /**
     * Descending iterator ordering is reverse FIFO
     */
    public void testDescendingIteratorOrdering() {
        final LinkedList<Item> q = new LinkedList<>();
        q.add(three);
        q.add(two);
        q.add(one);
        int k = 0;
        for (Iterator<? extends Item> it = q.descendingIterator(); it.hasNext();) {
            mustEqual(++k, it.next());
        }

        mustEqual(3, k);
    }

    /**
     * descendingIterator.remove removes current element
     */
    public void testDescendingIteratorRemove() {
        final LinkedList<Item> q = new LinkedList<>();
        q.add(three);
        q.add(two);
        q.add(one);
        Iterator<? extends Item> 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<Item> 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<Item> q = populatedQueue(3);
        q.addFirst(four);
        assertSame(four, q.peek());
    }

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

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

    /**
     * OfferFirst succeeds
     */
    public void testOfferFirst() {
        LinkedList<Item> q = new LinkedList<>();
        assertTrue(q.offerFirst(zero));
        assertTrue(q.offerFirst(one));
    }

    /**
     * OfferLast succeeds
     */
    public void testOfferLast() {
        LinkedList<Item> q = new LinkedList<>();
        assertTrue(q.offerLast(zero));
        assertTrue(q.offerLast(one));
    }

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

    /**
     * peekFirst returns next element, or null if empty
     */
    public void testPeekFirst() {
        LinkedList<Item> q = populatedQueue(SIZE);
        for (int i = 0; i < SIZE; ++i) {
            mustEqual(i, q.peekFirst());
            mustEqual(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<Item> q = populatedQueue(SIZE);
        for (int i = SIZE - 1; i >= 0; --i) {
            mustEqual(i, q.peekLast());
            mustEqual(i, q.pollLast());
            assertTrue(q.peekLast() == null ||
                       !q.peekLast().equals(i));
        }
        assertNull(q.peekLast());
    }

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

    /**
     * getLast returns next element, or throws NSEE if empty
     */
    public void testLastElement() {
        LinkedList<Item> q = populatedQueue(SIZE);
        for (int i = SIZE - 1; i >= 0; --i) {
            mustEqual(i, q.getLast());
            mustEqual(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<Item> q = populatedQueue(SIZE);
        for (int i = 1; i < SIZE; i += 2) {
            assertTrue(q.removeFirstOccurrence(itemFor(i)));
        }
        for (int i = 0; i < SIZE; i += 2) {
            assertTrue(q.removeFirstOccurrence(itemFor(i)));
            assertFalse(q.removeFirstOccurrence(itemFor(i + 1)));
        }
        assertTrue(q.isEmpty());
    }

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

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