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