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 populatedQueue(int n) {
        LinkedList q = new LinkedList();
        assertTrue(q.isEmpty());
        for (int i = 0; i < n; ++i)
            assertTrue(q.offer(new Integer(i)));
        assertFalse(q.isEmpty());
        assertEquals(n, q.size());
        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
     */
    public void testToArray() {
        LinkedList q = populatedQueue(SIZE);
        Object[] o = q.toArray();
        Arrays.sort(o);
        for (int i = 0; i < o.length; i++)
            assertEquals(o[i], q.poll());
    }

    /**
     *  toArray(a) contains all elements
     */
    public void testToArray2() {
        LinkedList q = populatedQueue(SIZE);
        Integer[] ints = new Integer[SIZE];
        ints = (Integer[])q.toArray(ints);
        Arrays.sort(ints);
        for (int i = 0; i < ints.length; i++)
            assertEquals(ints[i], q.poll());
    }

    /**
     * toArray(null) throws NPE
     */
    public void testToArray_BadArg() {
        LinkedList l = new LinkedList();
        l.add(new Object());
        try {
            Object o[] = l.toArray(null);
            shouldThrow();
        } catch (NullPointerException success) {}
    }

    /**
     * toArray with incompatable aray type throws CCE
     */
    public void testToArray1_BadArg() {
        LinkedList l = new LinkedList();
        l.add(new Integer(5));
        try {
            Object o[] = 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(new Integer(3));
        q.add(new Integer(2));
        q.add(new Integer(1));
        Iterator it = q.descendingIterator();
        it.next();
        it.remove();
        it = q.descendingIterator();
        assertEquals(it.next(), 2);
        assertEquals(it.next(), 3);
        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);
        assertEquals(four,q.peek());
    }

    /**
     * peekFirst returns element inserted with push
     */
    public void testPush() {
        LinkedList q = populatedQueue(3);
        q.pollLast();
        q.push(four);
        assertEquals(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.16
Committed:	Sun Nov 22 18:57:17 2009 UTC (14 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.15:	+35 -37 lines
Log Message:	use autoboxing judiciously for readability
#	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.13	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	dl	1.3	private LinkedList populatedQueue(int n) {
27	dl	1.1	LinkedList q = new LinkedList();
28			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			* 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	dl	1.5	* 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	dl	1.6	* 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	dl	1.5	* toArray contains all elements
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	dl	1.1	Arrays.sort(o);
327	jsr166	1.13	for (int i = 0; i < o.length; i++)
328			assertEquals(o[i], q.poll());
329	dl	1.1	}
330
331	dl	1.4	/**
332	dl	1.5	* toArray(a) contains all elements
333	dl	1.4	*/
334			public void testToArray2() {
335	dl	1.3	LinkedList q = populatedQueue(SIZE);
336	jsr166	1.13	Integer[] ints = new Integer[SIZE];
337			ints = (Integer[])q.toArray(ints);
338	dl	1.1	Arrays.sort(ints);
339	jsr166	1.11	for (int i = 0; i < ints.length; i++)
340	dl	1.1	assertEquals(ints[i], q.poll());
341			}
342	dl	1.5
343			/**
344			* toArray(null) throws NPE
345			*/
346			public void testToArray_BadArg() {
347	jsr166	1.16	LinkedList l = new LinkedList();
348			l.add(new Object());
349	jsr166	1.13	try {
350			Object o[] = l.toArray(null);
351			shouldThrow();
352			} catch (NullPointerException success) {}
353	dl	1.5	}
354
355			/**
356			* toArray with incompatable aray type throws CCE
357			*/
358			public void testToArray1_BadArg() {
359	jsr166	1.16	LinkedList l = new LinkedList();
360			l.add(new Integer(5));
361	jsr166	1.13	try {
362	jsr166	1.16	Object o[] = l.toArray(new String[10]);
363	jsr166	1.13	shouldThrow();
364	jsr166	1.14	} catch (ArrayStoreException success) {}
365	dl	1.5	}
366	jsr166	1.10
367	dl	1.4	/**
368	dl	1.5	* iterator iterates through all elements
369	dl	1.4	*/
370			public void testIterator() {
371	dl	1.3	LinkedList q = populatedQueue(SIZE);
372	dl	1.1	int i = 0;
373	jsr166	1.13	Iterator it = q.iterator();
374	jsr166	1.11	while (it.hasNext()) {
375	dl	1.1	assertTrue(q.contains(it.next()));
376			++i;
377			}
378	dl	1.3	assertEquals(i, SIZE);
379	dl	1.1	}
380
381	dl	1.4	/**
382	dl	1.5	* iterator ordering is FIFO
383	dl	1.4	*/
384	dl	1.1	public void testIteratorOrdering() {
385			final LinkedList q = new LinkedList();
386			q.add(new Integer(1));
387			q.add(new Integer(2));
388			q.add(new Integer(3));
389			int k = 0;
390			for (Iterator it = q.iterator(); it.hasNext();) {
391	jsr166	1.16	assertEquals(++k, it.next());
392	dl	1.1	}
393
394	dl	1.4	assertEquals(3, k);
395	dl	1.1	}
396
397	dl	1.4	/**
398	dl	1.5	* iterator.remove removes current element
399	dl	1.4	*/
400	dl	1.1	public void testIteratorRemove () {
401			final LinkedList q = new LinkedList();
402			q.add(new Integer(1));
403			q.add(new Integer(2));
404			q.add(new Integer(3));
405			Iterator it = q.iterator();
406	jsr166	1.16	assertEquals(it.next(), 1);
407	dl	1.1	it.remove();
408			it = q.iterator();
409	jsr166	1.16	assertEquals(it.next(), 2);
410			assertEquals(it.next(), 3);
411	dl	1.1	assertFalse(it.hasNext());
412			}
413
414	dl	1.9	/**
415			* Descending iterator iterates through all elements
416			*/
417			public void testDescendingIterator() {
418			LinkedList q = populatedQueue(SIZE);
419			int i = 0;
420	jsr166	1.13	Iterator it = q.descendingIterator();
421	jsr166	1.11	while (it.hasNext()) {
422	dl	1.9	assertTrue(q.contains(it.next()));
423			++i;
424			}
425			assertEquals(i, SIZE);
426			assertFalse(it.hasNext());
427			try {
428			it.next();
429	jsr166	1.14	shouldThrow();
430			} catch (NoSuchElementException success) {}
431	dl	1.9	}
432
433			/**
434			* Descending iterator ordering is reverse FIFO
435			*/
436			public void testDescendingIteratorOrdering() {
437			final LinkedList q = new LinkedList();
438			q.add(new Integer(3));
439			q.add(new Integer(2));
440			q.add(new Integer(1));
441			int k = 0;
442			for (Iterator it = q.descendingIterator(); it.hasNext();) {
443	jsr166	1.16	assertEquals(++k, it.next());
444	dl	1.9	}
445
446			assertEquals(3, k);
447			}
448
449			/**
450			* descendingIterator.remove removes current element
451			*/
452			public void testDescendingIteratorRemove () {
453			final LinkedList q = new LinkedList();
454			q.add(new Integer(3));
455			q.add(new Integer(2));
456			q.add(new Integer(1));
457			Iterator it = q.descendingIterator();
458			it.next();
459			it.remove();
460			it = q.descendingIterator();
461	jsr166	1.16	assertEquals(it.next(), 2);
462			assertEquals(it.next(), 3);
463	dl	1.9	assertFalse(it.hasNext());
464			}
465
466	dl	1.1
467	dl	1.4	/**
468	dl	1.5	* toString contains toStrings of elements
469	dl	1.4	*/
470			public void testToString() {
471	dl	1.3	LinkedList q = populatedQueue(SIZE);
472	dl	1.1	String s = q.toString();
473	dl	1.3	for (int i = 0; i < SIZE; ++i) {
474	dl	1.1	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
475			}
476	jsr166	1.10	}
477	dl	1.1
478	dl	1.4	/**
479	dl	1.5	* peek returns element inserted with addFirst
480	dl	1.4	*/
481			public void testAddFirst() {
482	dl	1.3	LinkedList q = populatedQueue(3);
483	jsr166	1.13	q.addFirst(four);
484			assertEquals(four,q.peek());
485	jsr166	1.10	}
486	dl	1.1
487	dl	1.8	/**
488			* peekFirst returns element inserted with push
489			*/
490			public void testPush() {
491			LinkedList q = populatedQueue(3);
492			q.pollLast();
493	jsr166	1.13	q.push(four);
494			assertEquals(four,q.peekFirst());
495	jsr166	1.10	}
496	dl	1.8
497			/**
498			* pop removes next element, or throws NSEE if empty
499			*/
500			public void testPop() {
501			LinkedList q = populatedQueue(SIZE);
502			for (int i = 0; i < SIZE; ++i) {
503	jsr166	1.16	assertEquals(i, q.pop());
504	dl	1.8	}
505			try {
506			q.pop();
507			shouldThrow();
508	jsr166	1.14	} catch (NoSuchElementException success) {}
509	dl	1.8	}
510
511			/**
512	jsr166	1.10	* OfferFirst succeeds
513	dl	1.8	*/
514			public void testOfferFirst() {
515			LinkedList q = new LinkedList();
516			assertTrue(q.offerFirst(new Integer(0)));
517			assertTrue(q.offerFirst(new Integer(1)));
518			}
519
520			/**
521	jsr166	1.10	* OfferLast succeeds
522	dl	1.8	*/
523			public void testOfferLast() {
524			LinkedList q = new LinkedList();
525			assertTrue(q.offerLast(new Integer(0)));
526			assertTrue(q.offerLast(new Integer(1)));
527			}
528
529			/**
530			* pollLast succeeds unless empty
531			*/
532			public void testPollLast() {
533			LinkedList q = populatedQueue(SIZE);
534			for (int i = SIZE-1; i >= 0; --i) {
535	jsr166	1.16	assertEquals(i, q.pollLast());
536	dl	1.8	}
537	jsr166	1.13	assertNull(q.pollLast());
538	dl	1.8	}
539
540			/**
541			* peekFirst returns next element, or null if empty
542			*/
543			public void testPeekFirst() {
544			LinkedList q = populatedQueue(SIZE);
545			for (int i = 0; i < SIZE; ++i) {
546	jsr166	1.16	assertEquals(i, q.peekFirst());
547			assertEquals(i, q.pollFirst());
548	dl	1.8	assertTrue(q.peekFirst() == null \|\|
549	jsr166	1.16	!q.peekFirst().equals(i));
550	dl	1.8	}
551	jsr166	1.13	assertNull(q.peekFirst());
552	dl	1.8	}
553
554
555			/**
556			* peekLast returns next element, or null if empty
557			*/
558			public void testPeekLast() {
559			LinkedList q = populatedQueue(SIZE);
560			for (int i = SIZE-1; i >= 0; --i) {
561	jsr166	1.16	assertEquals(i, q.peekLast());
562			assertEquals(i, q.pollLast());
563	dl	1.8	assertTrue(q.peekLast() == null \|\|
564	jsr166	1.16	!q.peekLast().equals(i));
565	dl	1.8	}
566	jsr166	1.13	assertNull(q.peekLast());
567	dl	1.8	}
568
569			public void testFirstElement() {
570			LinkedList q = populatedQueue(SIZE);
571			for (int i = 0; i < SIZE; ++i) {
572	jsr166	1.16	assertEquals(i, q.getFirst());
573			assertEquals(i, q.pollFirst());
574	dl	1.8	}
575			try {
576			q.getFirst();
577			shouldThrow();
578	jsr166	1.14	} catch (NoSuchElementException success) {}
579	dl	1.8	}
580
581			/**
582			* getLast returns next element, or throws NSEE if empty
583			*/
584			public void testLastElement() {
585			LinkedList q = populatedQueue(SIZE);
586			for (int i = SIZE-1; i >= 0; --i) {
587	jsr166	1.16	assertEquals(i, q.getLast());
588			assertEquals(i, q.pollLast());
589	dl	1.8	}
590			try {
591			q.getLast();
592			shouldThrow();
593	jsr166	1.14	} catch (NoSuchElementException success) {}
594	jsr166	1.13	assertNull(q.peekLast());
595	dl	1.8	}
596
597			/**
598			* removeFirstOccurrence(x) removes x and returns true if present
599			*/
600			public void testRemoveFirstOccurrence() {
601			LinkedList q = populatedQueue(SIZE);
602			for (int i = 1; i < SIZE; i+=2) {
603			assertTrue(q.removeFirstOccurrence(new Integer(i)));
604			}
605			for (int i = 0; i < SIZE; i+=2) {
606			assertTrue(q.removeFirstOccurrence(new Integer(i)));
607			assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
608			}
609			assertTrue(q.isEmpty());
610			}
611
612			/**
613			* removeLastOccurrence(x) removes x and returns true if present
614			*/
615			public void testRemoveLastOccurrence() {
616			LinkedList q = populatedQueue(SIZE);
617			for (int i = 1; i < SIZE; i+=2) {
618			assertTrue(q.removeLastOccurrence(new Integer(i)));
619			}
620			for (int i = 0; i < SIZE; i+=2) {
621			assertTrue(q.removeLastOccurrence(new Integer(i)));
622			assertFalse(q.removeLastOccurrence(new Integer(i+1)));
623			}
624			assertTrue(q.isEmpty());
625			}
626
627	dl	1.1	}