test/tck/LinkedListTest.java

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

import junit.framework.*;
import java.util.*;
import java.util.concurrent.*;

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

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

    /**
     * Create a queue of given size containing consecutive
     * Integers 0 ... n.
     */
    private LinkedList<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.remove(new Integer(i)));
        }
        for (int i = 0; i < SIZE; i+=2) {
            assertTrue(q.remove(new Integer(i)));
            assertFalse(q.remove(new Integer(i+1)));
        }
        assertTrue(q.isEmpty());
    }

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

    /**
     * clear removes all elements
     */
    public void testClear() {
        LinkedList q = populatedQueue(SIZE);
        q.clear();
        assertTrue(q.isEmpty());
        assertEquals(0, q.size());
        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(it.next(), 1);
        it.remove();
        it = q.iterator();
        assertEquals(it.next(), 2);
        assertEquals(it.next(), 3);
        assertFalse(it.hasNext());
    }

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

    /**
     * Descending iterator ordering is reverse FIFO
     */
    public void testDescendingIteratorOrdering() {
        final LinkedList q = new LinkedList();
        q.add(new Integer(3));
        q.add(new Integer(2));
        q.add(new Integer(1));
        int k = 0;
        for (Iterator it = q.descendingIterator(); it.hasNext();) {
            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.indexOf(String.valueOf(i)) >= 0);
        }
    }

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