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
     */
    @SuppressWarnings("CollectionToArraySafeParameter")
    public void testToArray_incompatibleArrayType() {
        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.52
Committed:	Wed Jan 27 02:55:18 2021 UTC (3 years, 3 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.51:	+2 -1 lines
Log Message:	Suppress all new errorprone "errors"
#	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	@SuppressWarnings("CollectionToArraySafeParameter")
393	public void testToArray_incompatibleArrayType() {
394	LinkedList<Item> l = new LinkedList<>();
395	l.add(five);
396	try {
397	l.toArray(new String[10]);
398	shouldThrow();
399	} catch (ArrayStoreException success) {}
400	}
401
402	/**
403	* iterator iterates through all elements
404	*/
405	public void testIterator() {
406	LinkedList<Item> q = populatedQueue(SIZE);
407	Iterator<? extends Item> it = q.iterator();
408	int i;
409	for (i = 0; it.hasNext(); i++)
410	mustContain(q, it.next());
411	mustEqual(i, SIZE);
412	assertIteratorExhausted(it);
413	}
414
415	/**
416	* iterator of empty collection has no elements
417	*/
418	public void testEmptyIterator() {
419	assertIteratorExhausted(new LinkedList<>().iterator());
420	}
421
422	/**
423	* iterator ordering is FIFO
424	*/
425	public void testIteratorOrdering() {
426	final LinkedList<Item> q = new LinkedList<>();
427	q.add(one);
428	q.add(two);
429	q.add(three);
430	int k = 0;
431	for (Iterator<? extends Item> it = q.iterator(); it.hasNext();) {
432	mustEqual(++k, it.next());
433	}
434
435	mustEqual(3, k);
436	}
437
438	/**
439	* iterator.remove removes current element
440	*/
441	public void testIteratorRemove() {
442	final LinkedList<Item> q = new LinkedList<>();
443	q.add(one);
444	q.add(two);
445	q.add(three);
446	Iterator<? extends Item> it = q.iterator();
447	mustEqual(1, it.next());
448	it.remove();
449	it = q.iterator();
450	mustEqual(2, it.next());
451	mustEqual(3, it.next());
452	assertFalse(it.hasNext());
453	}
454
455	/**
456	* Descending iterator iterates through all elements
457	*/
458	public void testDescendingIterator() {
459	LinkedList<Item> q = populatedQueue(SIZE);
460	int i = 0;
461	Iterator<? extends Item> it = q.descendingIterator();
462	while (it.hasNext()) {
463	mustContain(q, it.next());
464	++i;
465	}
466	mustEqual(i, SIZE);
467	assertFalse(it.hasNext());
468	try {
469	it.next();
470	shouldThrow();
471	} catch (NoSuchElementException success) {}
472	}
473
474	/**
475	* Descending iterator ordering is reverse FIFO
476	*/
477	public void testDescendingIteratorOrdering() {
478	final LinkedList<Item> q = new LinkedList<>();
479	q.add(three);
480	q.add(two);
481	q.add(one);
482	int k = 0;
483	for (Iterator<? extends Item> it = q.descendingIterator(); it.hasNext();) {
484	mustEqual(++k, it.next());
485	}
486
487	mustEqual(3, k);
488	}
489
490	/**
491	* descendingIterator.remove removes current element
492	*/
493	public void testDescendingIteratorRemove() {
494	final LinkedList<Item> q = new LinkedList<>();
495	q.add(three);
496	q.add(two);
497	q.add(one);
498	Iterator<? extends Item> it = q.descendingIterator();
499	it.next();
500	it.remove();
501	it = q.descendingIterator();
502	assertSame(it.next(), two);
503	assertSame(it.next(), three);
504	assertFalse(it.hasNext());
505	}
506
507	/**
508	* toString contains toStrings of elements
509	*/
510	public void testToString() {
511	LinkedList<Item> q = populatedQueue(SIZE);
512	String s = q.toString();
513	for (int i = 0; i < SIZE; ++i) {
514	assertTrue(s.contains(String.valueOf(i)));
515	}
516	}
517
518	/**
519	* peek returns element inserted with addFirst
520	*/
521	public void testAddFirst() {
522	LinkedList<Item> q = populatedQueue(3);
523	q.addFirst(four);
524	assertSame(four, q.peek());
525	}
526
527	/**
528	* peekFirst returns element inserted with push
529	*/
530	public void testPush() {
531	LinkedList<Item> q = populatedQueue(3);
532	q.push(four);
533	assertSame(four, q.peekFirst());
534	}
535
536	/**
537	* pop removes next element, or throws NSEE if empty
538	*/
539	public void testPop() {
540	LinkedList<Item> q = populatedQueue(SIZE);
541	for (int i = 0; i < SIZE; ++i) {
542	mustEqual(i, q.pop());
543	}
544	try {
545	q.pop();
546	shouldThrow();
547	} catch (NoSuchElementException success) {}
548	}
549
550	/**
551	* OfferFirst succeeds
552	*/
553	public void testOfferFirst() {
554	LinkedList<Item> q = new LinkedList<>();
555	assertTrue(q.offerFirst(zero));
556	assertTrue(q.offerFirst(one));
557	}
558
559	/**
560	* OfferLast succeeds
561	*/
562	public void testOfferLast() {
563	LinkedList<Item> q = new LinkedList<>();
564	assertTrue(q.offerLast(zero));
565	assertTrue(q.offerLast(one));
566	}
567
568	/**
569	* pollLast succeeds unless empty
570	*/
571	public void testPollLast() {
572	LinkedList<Item> q = populatedQueue(SIZE);
573	for (int i = SIZE - 1; i >= 0; --i) {
574	mustEqual(i, q.pollLast());
575	}
576	assertNull(q.pollLast());
577	}
578
579	/**
580	* peekFirst returns next element, or null if empty
581	*/
582	public void testPeekFirst() {
583	LinkedList<Item> q = populatedQueue(SIZE);
584	for (int i = 0; i < SIZE; ++i) {
585	mustEqual(i, q.peekFirst());
586	mustEqual(i, q.pollFirst());
587	assertTrue(q.peekFirst() == null \|\|
588	!q.peekFirst().equals(i));
589	}
590	assertNull(q.peekFirst());
591	}
592
593	/**
594	* peekLast returns next element, or null if empty
595	*/
596	public void testPeekLast() {
597	LinkedList<Item> q = populatedQueue(SIZE);
598	for (int i = SIZE - 1; i >= 0; --i) {
599	mustEqual(i, q.peekLast());
600	mustEqual(i, q.pollLast());
601	assertTrue(q.peekLast() == null \|\|
602	!q.peekLast().equals(i));
603	}
604	assertNull(q.peekLast());
605	}
606
607	public void testFirstElement() {
608	LinkedList<Item> q = populatedQueue(SIZE);
609	for (int i = 0; i < SIZE; ++i) {
610	mustEqual(i, q.getFirst());
611	mustEqual(i, q.pollFirst());
612	}
613	try {
614	q.getFirst();
615	shouldThrow();
616	} catch (NoSuchElementException success) {}
617	}
618
619	/**
620	* getLast returns next element, or throws NSEE if empty
621	*/
622	public void testLastElement() {
623	LinkedList<Item> q = populatedQueue(SIZE);
624	for (int i = SIZE - 1; i >= 0; --i) {
625	mustEqual(i, q.getLast());
626	mustEqual(i, q.pollLast());
627	}
628	try {
629	q.getLast();
630	shouldThrow();
631	} catch (NoSuchElementException success) {}
632	assertNull(q.peekLast());
633	}
634
635	/**
636	* removeFirstOccurrence(x) removes x and returns true if present
637	*/
638	public void testRemoveFirstOccurrence() {
639	LinkedList<Item> q = populatedQueue(SIZE);
640	for (int i = 1; i < SIZE; i += 2) {
641	assertTrue(q.removeFirstOccurrence(itemFor(i)));
642	}
643	for (int i = 0; i < SIZE; i += 2) {
644	assertTrue(q.removeFirstOccurrence(itemFor(i)));
645	assertFalse(q.removeFirstOccurrence(itemFor(i + 1)));
646	}
647	assertTrue(q.isEmpty());
648	}
649
650	/**
651	* removeLastOccurrence(x) removes x and returns true if present
652	*/
653	public void testRemoveLastOccurrence() {
654	LinkedList<Item> q = populatedQueue(SIZE);
655	for (int i = 1; i < SIZE; i += 2) {
656	assertTrue(q.removeLastOccurrence(itemFor(i)));
657	}
658	for (int i = 0; i < SIZE; i += 2) {
659	assertTrue(q.removeLastOccurrence(itemFor(i)));
660	assertFalse(q.removeLastOccurrence(itemFor(i + 1)));
661	}
662	assertTrue(q.isEmpty());
663	}
664
665	}