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() {
        try {
            Integer[] ints = new Integer[SIZE];
            for (int i = 0; i < SIZE; ++i)
                ints[i] = new Integer(i);
            LinkedList q = new LinkedList(Arrays.asList(ints));
            for (int i = 0; i < SIZE; ++i)
                assertEquals(ints[i], q.poll());
        }
        finally {}
    }

    /**
     * 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() {
        try {
            LinkedList q = new LinkedList();
            q.offer(null);
        } catch (NullPointerException ie) {
            unexpectedException();
        }
    }

    /**
     * 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() {
        try {
            Integer[] empty = new Integer[0];
            Integer[] ints = new Integer[SIZE];
            for (int i = 0; i < SIZE; ++i)
                ints[i] = new Integer(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());
        }
        finally {}
    }

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

    /**
     * addAll with negative index throws IOOBE
     */
    public void testAddAll4_BadIndex() {
        try {
            LinkedList l = new LinkedList();
            l.add(new Object());
            LinkedList m = new LinkedList();
            m.add(new Object());
            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, ((Integer)q.poll()).intValue());
        }
        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, ((Integer)q.peek()).intValue());
            q.poll();
            assertTrue(q.peek() == null ||
                       i != ((Integer)q.peek()).intValue());
        }
        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, ((Integer)q.element()).intValue());
            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, ((Integer)q.remove()).intValue());
        }
        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());
        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));
            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() {
        try {
            LinkedList l = new LinkedList();
            l.add(new Object());
            Object o[] = l.toArray(null);
            shouldThrow();
        } catch (NullPointerException success){}
    }

    /**
     * toArray with incompatable aray type throws CCE
     */
    public void testToArray1_BadArg() {
        try {
            LinkedList l = new LinkedList();
            l.add(new Integer(5));
            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();) {
            int i = ((Integer)(it.next())).intValue();
            assertEquals(++k, i);
        }

        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();
        it.next();
        it.remove();
        it = q.iterator();
        assertEquals(it.next(), new Integer(2));
        assertEquals(it.next(), new Integer(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();
        } 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();) {
            int i = ((Integer)(it.next())).intValue();
            assertEquals(++k, i);
        }

        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(), new Integer(2));
        assertEquals(it.next(), new Integer(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, ((Integer)q.pop()).intValue());
        }
        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, ((Integer)q.pollLast()).intValue());
        }
        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, ((Integer)q.peekFirst()).intValue());
            q.pollFirst();
            assertTrue(q.peekFirst() == null ||
                       i != ((Integer)q.peekFirst()).intValue());
        }
        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, ((Integer)q.peekLast()).intValue());
            q.pollLast();
            assertTrue(q.peekLast() == null ||
                       i != ((Integer)q.peekLast()).intValue());
        }
        assertNull(q.peekLast());
    }

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