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 junit.framework.*;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

public class LinkedListTest extends JSR166TestCase {
    public static void main(String[] args) {
        junit.textui.TestRunner.run(suite());
    }

    public static Test suite() {
        return new TestSuite(LinkedListTest.class);
    }

    /**
     * Create a queue of given size containing consecutive
     * Integers 0 ... n.
     */
    private LinkedList<Integer> populatedQueue(int n) {
        LinkedList<Integer> q = new LinkedList<Integer>();
        assertTrue(q.isEmpty());
        for (int i = 0; i < n; ++i)
            assertTrue(q.offer(new Integer(i)));
        assertFalse(q.isEmpty());
        assertEquals(n, q.size());
        return q;
    }

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

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

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

    /**
     * isEmpty is true before add, false after
     */
    public void testEmpty() {
        LinkedList q = new LinkedList();
        assertTrue(q.isEmpty());
        q.add(new Integer(1));
        assertFalse(q.isEmpty());
        q.add(new Integer(2));
        q.remove();
        q.remove();
        assertTrue(q.isEmpty());
    }

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

    /**
     * offer(null) succeeds
     */
    public void testOfferNull() {
        LinkedList q = new LinkedList();
        q.offer(null);
    }

    /**
     * Offer succeeds
     */
    public void testOffer() {
        LinkedList q = new LinkedList();
        assertTrue(q.offer(new Integer(0)));
        assertTrue(q.offer(new Integer(1)));
    }

    /**
     * add succeeds
     */
    public void testAdd() {
        LinkedList q = new LinkedList();
        for (int i = 0; i < SIZE; ++i) {
            assertEquals(i, q.size());
            assertTrue(q.add(new Integer(i)));
        }
    }

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

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

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

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

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

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

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

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

    /**
     * remove(x) removes x and returns true if present
     */
    public void testRemoveElement() {
        LinkedList q = populatedQueue(SIZE);
        for (int i = 1; i < SIZE; i+=2) {
            assertTrue(q.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 I = (Integer)(p.remove());
                assertFalse(q.contains(I));
            }
        }
    }

    /**
     * toArray contains all elements in FIFO order
     */
    public void testToArray() {
        LinkedList q = populatedQueue(SIZE);
        Object[] o = q.toArray();
        for (int i = 0; i < o.length; i++)
            assertSame(o[i], q.poll());
    }

    /**
     * toArray(a) contains all elements in FIFO order
     */
    public void testToArray2() {
        LinkedList<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);
        int i = 0;
        Iterator it = q.iterator();
        while (it.hasNext()) {
            assertTrue(q.contains(it.next()));
            ++i;
        }
        assertEquals(i, SIZE);
    }

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

        assertEquals(3, k);
    }

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