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.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(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.25
Committed:	Thu Nov 18 20:21:53 2010 UTC (13 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.24:	+9 -3 lines
Log Message:	add more assertions to testRemoveElement
#	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	jsr166	1.25	assertTrue(q.contains(i));
237			assertTrue(q.remove((Integer)i));
238			assertFalse(q.contains(i));
239			assertTrue(q.contains(i-1));
240	dl	1.1	}
241	dl	1.3	for (int i = 0; i < SIZE; i+=2) {
242	jsr166	1.25	assertTrue(q.contains(i));
243			assertTrue(q.remove((Integer)i));
244			assertFalse(q.contains(i));
245			assertFalse(q.remove((Integer)(i+1)));
246			assertFalse(q.contains(i+1));
247	dl	1.1	}
248	dl	1.2	assertTrue(q.isEmpty());
249	dl	1.1	}
250	jsr166	1.10
251	dl	1.4	/**
252	dl	1.5	* contains(x) reports true when elements added but not yet removed
253	dl	1.4	*/
254			public void testContains() {
255	dl	1.3	LinkedList q = populatedQueue(SIZE);
256			for (int i = 0; i < SIZE; ++i) {
257	dl	1.1	assertTrue(q.contains(new Integer(i)));
258			q.poll();
259			assertFalse(q.contains(new Integer(i)));
260			}
261			}
262
263	dl	1.4	/**
264	dl	1.5	* clear removes all elements
265	dl	1.4	*/
266			public void testClear() {
267	dl	1.3	LinkedList q = populatedQueue(SIZE);
268	dl	1.1	q.clear();
269			assertTrue(q.isEmpty());
270			assertEquals(0, q.size());
271	jsr166	1.16	assertTrue(q.add(new Integer(1)));
272	dl	1.1	assertFalse(q.isEmpty());
273			q.clear();
274			assertTrue(q.isEmpty());
275			}
276
277	dl	1.4	/**
278	dl	1.5	* containsAll(c) is true when c contains a subset of elements
279	dl	1.4	*/
280			public void testContainsAll() {
281	dl	1.3	LinkedList q = populatedQueue(SIZE);
282	dl	1.1	LinkedList p = new LinkedList();
283	dl	1.3	for (int i = 0; i < SIZE; ++i) {
284	dl	1.1	assertTrue(q.containsAll(p));
285			assertFalse(p.containsAll(q));
286	jsr166	1.16	assertTrue(p.add(new Integer(i)));
287	dl	1.1	}
288			assertTrue(p.containsAll(q));
289			}
290
291	dl	1.4	/**
292	dl	1.5	* retainAll(c) retains only those elements of c and reports true if changed
293	dl	1.4	*/
294			public void testRetainAll() {
295	dl	1.3	LinkedList q = populatedQueue(SIZE);
296			LinkedList p = populatedQueue(SIZE);
297			for (int i = 0; i < SIZE; ++i) {
298	dl	1.1	boolean changed = q.retainAll(p);
299			if (i == 0)
300			assertFalse(changed);
301			else
302			assertTrue(changed);
303
304			assertTrue(q.containsAll(p));
305	dl	1.3	assertEquals(SIZE-i, q.size());
306	dl	1.1	p.remove();
307			}
308			}
309
310	dl	1.4	/**
311	dl	1.6	* removeAll(c) removes only those elements of c and reports true if changed
312	dl	1.4	*/
313			public void testRemoveAll() {
314	dl	1.3	for (int i = 1; i < SIZE; ++i) {
315			LinkedList q = populatedQueue(SIZE);
316			LinkedList p = populatedQueue(i);
317	dl	1.1	assertTrue(q.removeAll(p));
318	dl	1.3	assertEquals(SIZE-i, q.size());
319	dl	1.1	for (int j = 0; j < i; ++j) {
320			Integer I = (Integer)(p.remove());
321			assertFalse(q.contains(I));
322			}
323			}
324			}
325
326	dl	1.4	/**
327	jsr166	1.23	* toArray contains all elements in FIFO order
328	dl	1.4	*/
329			public void testToArray() {
330	dl	1.3	LinkedList q = populatedQueue(SIZE);
331	jsr166	1.13	Object[] o = q.toArray();
332			for (int i = 0; i < o.length; i++)
333	jsr166	1.23	assertSame(o[i], q.poll());
334	dl	1.1	}
335
336	dl	1.4	/**
337	jsr166	1.23	* toArray(a) contains all elements in FIFO order
338	dl	1.4	*/
339			public void testToArray2() {
340	jsr166	1.24	LinkedList<Integer> q = populatedQueue(SIZE);
341	jsr166	1.13	Integer[] ints = new Integer[SIZE];
342	jsr166	1.24	Integer[] array = q.toArray(ints);
343			assertSame(ints, array);
344	jsr166	1.11	for (int i = 0; i < ints.length; i++)
345	jsr166	1.23	assertSame(ints[i], q.poll());
346	dl	1.1	}
347	dl	1.5
348			/**
349	jsr166	1.22	* toArray(null) throws NullPointerException
350	dl	1.5	*/
351	jsr166	1.22	public void testToArray_NullArg() {
352	jsr166	1.16	LinkedList l = new LinkedList();
353			l.add(new Object());
354	jsr166	1.13	try {
355	jsr166	1.22	l.toArray(null);
356	jsr166	1.13	shouldThrow();
357			} catch (NullPointerException success) {}
358	dl	1.5	}
359
360			/**
361	jsr166	1.21	* toArray(incompatible array type) throws ArrayStoreException
362	dl	1.5	*/
363			public void testToArray1_BadArg() {
364	jsr166	1.16	LinkedList l = new LinkedList();
365			l.add(new Integer(5));
366	jsr166	1.13	try {
367	jsr166	1.21	l.toArray(new String[10]);
368	jsr166	1.13	shouldThrow();
369	jsr166	1.14	} catch (ArrayStoreException success) {}
370	dl	1.5	}
371	jsr166	1.10
372	dl	1.4	/**
373	jsr166	1.20	* iterator iterates through all elements
374	dl	1.4	*/
375			public void testIterator() {
376	dl	1.3	LinkedList q = populatedQueue(SIZE);
377	dl	1.1	int i = 0;
378	jsr166	1.13	Iterator it = q.iterator();
379	jsr166	1.11	while (it.hasNext()) {
380	dl	1.1	assertTrue(q.contains(it.next()));
381			++i;
382			}
383	dl	1.3	assertEquals(i, SIZE);
384	dl	1.1	}
385
386	dl	1.4	/**
387	jsr166	1.20	* iterator ordering is FIFO
388	dl	1.4	*/
389	dl	1.1	public void testIteratorOrdering() {
390			final LinkedList q = new LinkedList();
391			q.add(new Integer(1));
392			q.add(new Integer(2));
393			q.add(new Integer(3));
394			int k = 0;
395			for (Iterator it = q.iterator(); it.hasNext();) {
396	jsr166	1.16	assertEquals(++k, it.next());
397	dl	1.1	}
398
399	dl	1.4	assertEquals(3, k);
400	dl	1.1	}
401
402	dl	1.4	/**
403	dl	1.5	* iterator.remove removes current element
404	dl	1.4	*/
405	jsr166	1.19	public void testIteratorRemove() {
406	dl	1.1	final LinkedList q = new LinkedList();
407			q.add(new Integer(1));
408			q.add(new Integer(2));
409			q.add(new Integer(3));
410			Iterator it = q.iterator();
411	jsr166	1.16	assertEquals(it.next(), 1);
412	dl	1.1	it.remove();
413			it = q.iterator();
414	jsr166	1.16	assertEquals(it.next(), 2);
415			assertEquals(it.next(), 3);
416	dl	1.1	assertFalse(it.hasNext());
417			}
418
419	dl	1.9	/**
420	jsr166	1.20	* Descending iterator iterates through all elements
421	dl	1.9	*/
422			public void testDescendingIterator() {
423			LinkedList q = populatedQueue(SIZE);
424			int i = 0;
425	jsr166	1.13	Iterator it = q.descendingIterator();
426	jsr166	1.11	while (it.hasNext()) {
427	dl	1.9	assertTrue(q.contains(it.next()));
428			++i;
429			}
430			assertEquals(i, SIZE);
431			assertFalse(it.hasNext());
432			try {
433			it.next();
434	jsr166	1.14	shouldThrow();
435			} catch (NoSuchElementException success) {}
436	dl	1.9	}
437
438			/**
439	jsr166	1.20	* Descending iterator ordering is reverse FIFO
440	dl	1.9	*/
441			public void testDescendingIteratorOrdering() {
442			final LinkedList q = new LinkedList();
443			q.add(new Integer(3));
444			q.add(new Integer(2));
445			q.add(new Integer(1));
446			int k = 0;
447			for (Iterator it = q.descendingIterator(); it.hasNext();) {
448	jsr166	1.16	assertEquals(++k, it.next());
449	dl	1.9	}
450
451			assertEquals(3, k);
452			}
453
454			/**
455			* descendingIterator.remove removes current element
456			*/
457	jsr166	1.19	public void testDescendingIteratorRemove() {
458	dl	1.9	final LinkedList q = new LinkedList();
459	jsr166	1.17	q.add(three);
460			q.add(two);
461			q.add(one);
462	dl	1.9	Iterator it = q.descendingIterator();
463			it.next();
464			it.remove();
465			it = q.descendingIterator();
466	jsr166	1.17	assertSame(it.next(), two);
467			assertSame(it.next(), three);
468	dl	1.9	assertFalse(it.hasNext());
469			}
470
471	dl	1.1
472	dl	1.4	/**
473	dl	1.5	* toString contains toStrings of elements
474	dl	1.4	*/
475			public void testToString() {
476	dl	1.3	LinkedList q = populatedQueue(SIZE);
477	dl	1.1	String s = q.toString();
478	dl	1.3	for (int i = 0; i < SIZE; ++i) {
479	dl	1.1	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
480			}
481	jsr166	1.10	}
482	dl	1.1
483	dl	1.4	/**
484	dl	1.5	* peek returns element inserted with addFirst
485	dl	1.4	*/
486			public void testAddFirst() {
487	dl	1.3	LinkedList q = populatedQueue(3);
488	jsr166	1.13	q.addFirst(four);
489	jsr166	1.17	assertSame(four, q.peek());
490	jsr166	1.10	}
491	dl	1.1
492	dl	1.8	/**
493			* peekFirst returns element inserted with push
494			*/
495			public void testPush() {
496			LinkedList q = populatedQueue(3);
497	jsr166	1.13	q.push(four);
498	jsr166	1.17	assertSame(four, q.peekFirst());
499	jsr166	1.10	}
500	dl	1.8
501			/**
502	jsr166	1.20	* pop removes next element, or throws NSEE if empty
503	dl	1.8	*/
504			public void testPop() {
505			LinkedList q = populatedQueue(SIZE);
506			for (int i = 0; i < SIZE; ++i) {
507	jsr166	1.16	assertEquals(i, q.pop());
508	dl	1.8	}
509			try {
510			q.pop();
511			shouldThrow();
512	jsr166	1.14	} catch (NoSuchElementException success) {}
513	dl	1.8	}
514
515			/**
516	jsr166	1.10	* OfferFirst succeeds
517	dl	1.8	*/
518			public void testOfferFirst() {
519			LinkedList q = new LinkedList();
520			assertTrue(q.offerFirst(new Integer(0)));
521			assertTrue(q.offerFirst(new Integer(1)));
522			}
523
524			/**
525	jsr166	1.10	* OfferLast succeeds
526	dl	1.8	*/
527			public void testOfferLast() {
528			LinkedList q = new LinkedList();
529			assertTrue(q.offerLast(new Integer(0)));
530			assertTrue(q.offerLast(new Integer(1)));
531			}
532
533			/**
534	jsr166	1.20	* pollLast succeeds unless empty
535	dl	1.8	*/
536			public void testPollLast() {
537			LinkedList q = populatedQueue(SIZE);
538			for (int i = SIZE-1; i >= 0; --i) {
539	jsr166	1.16	assertEquals(i, q.pollLast());
540	dl	1.8	}
541	jsr166	1.13	assertNull(q.pollLast());
542	dl	1.8	}
543
544			/**
545	jsr166	1.20	* peekFirst returns next element, or null if empty
546	dl	1.8	*/
547			public void testPeekFirst() {
548			LinkedList q = populatedQueue(SIZE);
549			for (int i = 0; i < SIZE; ++i) {
550	jsr166	1.16	assertEquals(i, q.peekFirst());
551			assertEquals(i, q.pollFirst());
552	dl	1.8	assertTrue(q.peekFirst() == null \|\|
553	jsr166	1.16	!q.peekFirst().equals(i));
554	dl	1.8	}
555	jsr166	1.13	assertNull(q.peekFirst());
556	dl	1.8	}
557
558
559			/**
560	jsr166	1.20	* peekLast returns next element, or null if empty
561	dl	1.8	*/
562			public void testPeekLast() {
563			LinkedList q = populatedQueue(SIZE);
564			for (int i = SIZE-1; i >= 0; --i) {
565	jsr166	1.16	assertEquals(i, q.peekLast());
566			assertEquals(i, q.pollLast());
567	dl	1.8	assertTrue(q.peekLast() == null \|\|
568	jsr166	1.16	!q.peekLast().equals(i));
569	dl	1.8	}
570	jsr166	1.13	assertNull(q.peekLast());
571	dl	1.8	}
572
573			public void testFirstElement() {
574			LinkedList q = populatedQueue(SIZE);
575			for (int i = 0; i < SIZE; ++i) {
576	jsr166	1.16	assertEquals(i, q.getFirst());
577			assertEquals(i, q.pollFirst());
578	dl	1.8	}
579			try {
580			q.getFirst();
581			shouldThrow();
582	jsr166	1.14	} catch (NoSuchElementException success) {}
583	dl	1.8	}
584
585			/**
586	jsr166	1.20	* getLast returns next element, or throws NSEE if empty
587	dl	1.8	*/
588			public void testLastElement() {
589			LinkedList q = populatedQueue(SIZE);
590			for (int i = SIZE-1; i >= 0; --i) {
591	jsr166	1.16	assertEquals(i, q.getLast());
592			assertEquals(i, q.pollLast());
593	dl	1.8	}
594			try {
595			q.getLast();
596			shouldThrow();
597	jsr166	1.14	} catch (NoSuchElementException success) {}
598	jsr166	1.13	assertNull(q.peekLast());
599	dl	1.8	}
600
601			/**
602			* removeFirstOccurrence(x) removes x and returns true if present
603			*/
604			public void testRemoveFirstOccurrence() {
605			LinkedList q = populatedQueue(SIZE);
606			for (int i = 1; i < SIZE; i+=2) {
607			assertTrue(q.removeFirstOccurrence(new Integer(i)));
608			}
609			for (int i = 0; i < SIZE; i+=2) {
610			assertTrue(q.removeFirstOccurrence(new Integer(i)));
611			assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
612			}
613			assertTrue(q.isEmpty());
614			}
615
616			/**
617			* removeLastOccurrence(x) removes x and returns true if present
618			*/
619			public void testRemoveLastOccurrence() {
620			LinkedList q = populatedQueue(SIZE);
621			for (int i = 1; i < SIZE; i+=2) {
622			assertTrue(q.removeLastOccurrence(new Integer(i)));
623			}
624			for (int i = 0; i < SIZE; i+=2) {
625			assertTrue(q.removeLastOccurrence(new Integer(i)));
626			assertFalse(q.removeLastOccurrence(new Integer(i+1)));
627			}
628			assertTrue(q.isEmpty());
629			}
630
631	dl	1.1	}