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] = new Integer(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] = 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());
    }

    /**
     * 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, ((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();
            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();) {
            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.14
Committed:	Sat Nov 21 02:39:41 2009 UTC (14 years, 5 months ago) by jsr166
Branch:	MAIN
Changes since 1.13:	+35 -53 lines
Log Message:	better exception handling
#	User	Rev	Content
1	dl	1.1	/*
2	dl	1.7	* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4			* http://creativecommons.org/licenses/publicdomain
5	jsr166	1.10	* Other contributors include Andrew Wright, Jeffrey Hayes,
6			* Pat Fisher, Mike Judd.
7	dl	1.1	*/
8
9			import junit.framework.*;
10			import java.util.*;
11			import java.util.concurrent.*;
12
13	dl	1.3	public class LinkedListTest extends JSR166TestCase {
14	dl	1.1	public static void main(String[] args) {
15	jsr166	1.13	junit.textui.TestRunner.run (suite());
16	dl	1.1	}
17
18			public static Test suite() {
19	jsr166	1.13	return new TestSuite(LinkedListTest.class);
20	dl	1.1	}
21
22			/**
23			* Create a queue of given size containing consecutive
24			* Integers 0 ... n.
25			*/
26	dl	1.3	private LinkedList populatedQueue(int n) {
27	dl	1.1	LinkedList q = new LinkedList();
28			assertTrue(q.isEmpty());
29	jsr166	1.13	for (int i = 0; i < n; ++i)
30			assertTrue(q.offer(new Integer(i)));
31	dl	1.1	assertFalse(q.isEmpty());
32	jsr166	1.13	assertEquals(n, q.size());
33	dl	1.1	return q;
34			}
35	jsr166	1.10
36	dl	1.4	/**
37	dl	1.5	* new queue is empty
38	dl	1.4	*/
39			public void testConstructor1() {
40	dl	1.1	assertEquals(0, new LinkedList().size());
41			}
42
43	dl	1.4	/**
44	dl	1.5	* Initializing from null Collection throws NPE
45	dl	1.4	*/
46	dl	1.1	public void testConstructor3() {
47			try {
48			LinkedList q = new LinkedList((Collection)null);
49	dl	1.4	shouldThrow();
50	jsr166	1.14	} catch (NullPointerException success) {}
51	dl	1.1	}
52
53	dl	1.4	/**
54	dl	1.5	* Queue contains all elements of collection used to initialize
55	dl	1.4	*/
56			public void testConstructor6() {
57	jsr166	1.14	Integer[] ints = new Integer[SIZE];
58			for (int i = 0; i < SIZE; ++i)
59			ints[i] = new Integer(i);
60			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			ints[i] = new Integer(i);
141			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			} 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			} catch (IndexOutOfBoundsException success) {}
174	dl	1.5	}
175
176			/**
177			* poll succeeds unless empty
178	dl	1.4	*/
179			public void testPoll() {
180	dl	1.3	LinkedList q = populatedQueue(SIZE);
181			for (int i = 0; i < SIZE; ++i) {
182	dl	1.1	assertEquals(i, ((Integer)q.poll()).intValue());
183			}
184	jsr166	1.13	assertNull(q.poll());
185	dl	1.1	}
186
187	dl	1.4	/**
188	dl	1.5	* peek returns next element, or null if empty
189	dl	1.4	*/
190			public void testPeek() {
191	dl	1.3	LinkedList q = populatedQueue(SIZE);
192			for (int i = 0; i < SIZE; ++i) {
193	dl	1.1	assertEquals(i, ((Integer)q.peek()).intValue());
194			q.poll();
195			assertTrue(q.peek() == null \|\|
196			i != ((Integer)q.peek()).intValue());
197			}
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	dl	1.1	assertEquals(i, ((Integer)q.element()).intValue());
208			q.poll();
209			}
210			try {
211			q.element();
212	dl	1.4	shouldThrow();
213	jsr166	1.14	} catch (NoSuchElementException success) {}
214	dl	1.1	}
215
216	dl	1.4	/**
217	dl	1.6	* remove removes next element, or throws NSEE if empty
218	dl	1.4	*/
219			public void testRemove() {
220	dl	1.3	LinkedList q = populatedQueue(SIZE);
221			for (int i = 0; i < SIZE; ++i) {
222	dl	1.1	assertEquals(i, ((Integer)q.remove()).intValue());
223			}
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			q.add(new Integer(1));
266			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			p.add(new Integer(i));
281			}
282			assertTrue(p.containsAll(q));
283			}
284
285	dl	1.4	/**
286	dl	1.5	* retainAll(c) retains only those elements of c and reports true if changed
287	dl	1.4	*/
288			public void testRetainAll() {
289	dl	1.3	LinkedList q = populatedQueue(SIZE);
290			LinkedList p = populatedQueue(SIZE);
291			for (int i = 0; i < SIZE; ++i) {
292	dl	1.1	boolean changed = q.retainAll(p);
293			if (i == 0)
294			assertFalse(changed);
295			else
296			assertTrue(changed);
297
298			assertTrue(q.containsAll(p));
299	dl	1.3	assertEquals(SIZE-i, q.size());
300	dl	1.1	p.remove();
301			}
302			}
303
304	dl	1.4	/**
305	dl	1.6	* removeAll(c) removes only those elements of c and reports true if changed
306	dl	1.4	*/
307			public void testRemoveAll() {
308	dl	1.3	for (int i = 1; i < SIZE; ++i) {
309			LinkedList q = populatedQueue(SIZE);
310			LinkedList p = populatedQueue(i);
311	dl	1.1	assertTrue(q.removeAll(p));
312	dl	1.3	assertEquals(SIZE-i, q.size());
313	dl	1.1	for (int j = 0; j < i; ++j) {
314			Integer I = (Integer)(p.remove());
315			assertFalse(q.contains(I));
316			}
317			}
318			}
319
320	dl	1.4	/**
321	dl	1.5	* toArray contains all elements
322	dl	1.4	*/
323			public void testToArray() {
324	dl	1.3	LinkedList q = populatedQueue(SIZE);
325	jsr166	1.13	Object[] o = q.toArray();
326	dl	1.1	Arrays.sort(o);
327	jsr166	1.13	for (int i = 0; i < o.length; i++)
328			assertEquals(o[i], q.poll());
329	dl	1.1	}
330
331	dl	1.4	/**
332	dl	1.5	* toArray(a) contains all elements
333	dl	1.4	*/
334			public void testToArray2() {
335	dl	1.3	LinkedList q = populatedQueue(SIZE);
336	jsr166	1.13	Integer[] ints = new Integer[SIZE];
337			ints = (Integer[])q.toArray(ints);
338	dl	1.1	Arrays.sort(ints);
339	jsr166	1.11	for (int i = 0; i < ints.length; i++)
340	dl	1.1	assertEquals(ints[i], q.poll());
341			}
342	dl	1.5
343			/**
344			* toArray(null) throws NPE
345			*/
346			public void testToArray_BadArg() {
347	jsr166	1.13	try {
348			LinkedList l = new LinkedList();
349			l.add(new Object());
350			Object o[] = l.toArray(null);
351			shouldThrow();
352			} catch (NullPointerException success) {}
353	dl	1.5	}
354
355			/**
356			* toArray with incompatable aray type throws CCE
357			*/
358			public void testToArray1_BadArg() {
359	jsr166	1.13	try {
360			LinkedList l = new LinkedList();
361			l.add(new Integer(5));
362			Object o[] = l.toArray(new String[10] );
363			shouldThrow();
364	jsr166	1.14	} catch (ArrayStoreException success) {}
365	dl	1.5	}
366	jsr166	1.10
367	dl	1.4	/**
368	dl	1.5	* iterator iterates through all elements
369	dl	1.4	*/
370			public void testIterator() {
371	dl	1.3	LinkedList q = populatedQueue(SIZE);
372	dl	1.1	int i = 0;
373	jsr166	1.13	Iterator it = q.iterator();
374	jsr166	1.11	while (it.hasNext()) {
375	dl	1.1	assertTrue(q.contains(it.next()));
376			++i;
377			}
378	dl	1.3	assertEquals(i, SIZE);
379	dl	1.1	}
380
381	dl	1.4	/**
382	dl	1.5	* iterator ordering is FIFO
383	dl	1.4	*/
384	dl	1.1	public void testIteratorOrdering() {
385			final LinkedList q = new LinkedList();
386			q.add(new Integer(1));
387			q.add(new Integer(2));
388			q.add(new Integer(3));
389			int k = 0;
390			for (Iterator it = q.iterator(); it.hasNext();) {
391			int i = ((Integer)(it.next())).intValue();
392	dl	1.4	assertEquals(++k, i);
393	dl	1.1	}
394
395	dl	1.4	assertEquals(3, k);
396	dl	1.1	}
397
398	dl	1.4	/**
399	dl	1.5	* iterator.remove removes current element
400	dl	1.4	*/
401	dl	1.1	public void testIteratorRemove () {
402			final LinkedList q = new LinkedList();
403			q.add(new Integer(1));
404			q.add(new Integer(2));
405			q.add(new Integer(3));
406			Iterator it = q.iterator();
407			it.next();
408			it.remove();
409			it = q.iterator();
410			assertEquals(it.next(), new Integer(2));
411			assertEquals(it.next(), new Integer(3));
412			assertFalse(it.hasNext());
413			}
414
415	dl	1.9	/**
416			* Descending iterator iterates through all elements
417			*/
418			public void testDescendingIterator() {
419			LinkedList q = populatedQueue(SIZE);
420			int i = 0;
421	jsr166	1.13	Iterator it = q.descendingIterator();
422	jsr166	1.11	while (it.hasNext()) {
423	dl	1.9	assertTrue(q.contains(it.next()));
424			++i;
425			}
426			assertEquals(i, SIZE);
427			assertFalse(it.hasNext());
428			try {
429			it.next();
430	jsr166	1.14	shouldThrow();
431			} catch (NoSuchElementException success) {}
432	dl	1.9	}
433
434			/**
435			* Descending iterator ordering is reverse FIFO
436			*/
437			public void testDescendingIteratorOrdering() {
438			final LinkedList q = new LinkedList();
439			q.add(new Integer(3));
440			q.add(new Integer(2));
441			q.add(new Integer(1));
442			int k = 0;
443			for (Iterator it = q.descendingIterator(); it.hasNext();) {
444			int i = ((Integer)(it.next())).intValue();
445			assertEquals(++k, i);
446			}
447
448			assertEquals(3, k);
449			}
450
451			/**
452			* descendingIterator.remove removes current element
453			*/
454			public void testDescendingIteratorRemove () {
455			final LinkedList q = new LinkedList();
456			q.add(new Integer(3));
457			q.add(new Integer(2));
458			q.add(new Integer(1));
459			Iterator it = q.descendingIterator();
460			it.next();
461			it.remove();
462			it = q.descendingIterator();
463			assertEquals(it.next(), new Integer(2));
464			assertEquals(it.next(), new Integer(3));
465			assertFalse(it.hasNext());
466			}
467
468	dl	1.1
469	dl	1.4	/**
470	dl	1.5	* toString contains toStrings of elements
471	dl	1.4	*/
472			public void testToString() {
473	dl	1.3	LinkedList q = populatedQueue(SIZE);
474	dl	1.1	String s = q.toString();
475	dl	1.3	for (int i = 0; i < SIZE; ++i) {
476	dl	1.1	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
477			}
478	jsr166	1.10	}
479	dl	1.1
480	dl	1.4	/**
481	dl	1.5	* peek returns element inserted with addFirst
482	dl	1.4	*/
483			public void testAddFirst() {
484	dl	1.3	LinkedList q = populatedQueue(3);
485	jsr166	1.13	q.addFirst(four);
486			assertEquals(four,q.peek());
487	jsr166	1.10	}
488	dl	1.1
489	dl	1.8	/**
490			* peekFirst returns element inserted with push
491			*/
492			public void testPush() {
493			LinkedList q = populatedQueue(3);
494			q.pollLast();
495	jsr166	1.13	q.push(four);
496			assertEquals(four,q.peekFirst());
497	jsr166	1.10	}
498	dl	1.8
499			/**
500			* pop removes next element, or throws NSEE if empty
501			*/
502			public void testPop() {
503			LinkedList q = populatedQueue(SIZE);
504			for (int i = 0; i < SIZE; ++i) {
505			assertEquals(i, ((Integer)q.pop()).intValue());
506			}
507			try {
508			q.pop();
509			shouldThrow();
510	jsr166	1.14	} catch (NoSuchElementException success) {}
511	dl	1.8	}
512
513			/**
514	jsr166	1.10	* OfferFirst succeeds
515	dl	1.8	*/
516			public void testOfferFirst() {
517			LinkedList q = new LinkedList();
518			assertTrue(q.offerFirst(new Integer(0)));
519			assertTrue(q.offerFirst(new Integer(1)));
520			}
521
522			/**
523	jsr166	1.10	* OfferLast succeeds
524	dl	1.8	*/
525			public void testOfferLast() {
526			LinkedList q = new LinkedList();
527			assertTrue(q.offerLast(new Integer(0)));
528			assertTrue(q.offerLast(new Integer(1)));
529			}
530
531			/**
532			* pollLast succeeds unless empty
533			*/
534			public void testPollLast() {
535			LinkedList q = populatedQueue(SIZE);
536			for (int i = SIZE-1; i >= 0; --i) {
537			assertEquals(i, ((Integer)q.pollLast()).intValue());
538			}
539	jsr166	1.13	assertNull(q.pollLast());
540	dl	1.8	}
541
542			/**
543			* peekFirst returns next element, or null if empty
544			*/
545			public void testPeekFirst() {
546			LinkedList q = populatedQueue(SIZE);
547			for (int i = 0; i < SIZE; ++i) {
548			assertEquals(i, ((Integer)q.peekFirst()).intValue());
549			q.pollFirst();
550			assertTrue(q.peekFirst() == null \|\|
551			i != ((Integer)q.peekFirst()).intValue());
552			}
553	jsr166	1.13	assertNull(q.peekFirst());
554	dl	1.8	}
555
556
557			/**
558			* peekLast returns next element, or null if empty
559			*/
560			public void testPeekLast() {
561			LinkedList q = populatedQueue(SIZE);
562			for (int i = SIZE-1; i >= 0; --i) {
563			assertEquals(i, ((Integer)q.peekLast()).intValue());
564			q.pollLast();
565			assertTrue(q.peekLast() == null \|\|
566			i != ((Integer)q.peekLast()).intValue());
567			}
568	jsr166	1.13	assertNull(q.peekLast());
569	dl	1.8	}
570
571			public void testFirstElement() {
572			LinkedList q = populatedQueue(SIZE);
573			for (int i = 0; i < SIZE; ++i) {
574			assertEquals(i, ((Integer)q.getFirst()).intValue());
575			q.pollFirst();
576			}
577			try {
578			q.getFirst();
579			shouldThrow();
580	jsr166	1.14	} catch (NoSuchElementException success) {}
581	dl	1.8	}
582
583			/**
584			* getLast returns next element, or throws NSEE if empty
585			*/
586			public void testLastElement() {
587			LinkedList q = populatedQueue(SIZE);
588			for (int i = SIZE-1; i >= 0; --i) {
589			assertEquals(i, ((Integer)q.getLast()).intValue());
590			q.pollLast();
591			}
592			try {
593			q.getLast();
594			shouldThrow();
595	jsr166	1.14	} catch (NoSuchElementException success) {}
596	jsr166	1.13	assertNull(q.peekLast());
597	dl	1.8	}
598
599			/**
600			* removeFirstOccurrence(x) removes x and returns true if present
601			*/
602			public void testRemoveFirstOccurrence() {
603			LinkedList q = populatedQueue(SIZE);
604			for (int i = 1; i < SIZE; i+=2) {
605			assertTrue(q.removeFirstOccurrence(new Integer(i)));
606			}
607			for (int i = 0; i < SIZE; i+=2) {
608			assertTrue(q.removeFirstOccurrence(new Integer(i)));
609			assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
610			}
611			assertTrue(q.isEmpty());
612			}
613
614			/**
615			* removeLastOccurrence(x) removes x and returns true if present
616			*/
617			public void testRemoveLastOccurrence() {
618			LinkedList q = populatedQueue(SIZE);
619			for (int i = 1; i < SIZE; i+=2) {
620			assertTrue(q.removeLastOccurrence(new Integer(i)));
621			}
622			for (int i = 0; i < SIZE; i+=2) {
623			assertTrue(q.removeLastOccurrence(new Integer(i)));
624			assertFalse(q.removeLastOccurrence(new Integer(i+1)));
625			}
626			assertTrue(q.isEmpty());
627			}
628
629	dl	1.1	}