--- jsr166/src/test/tck/LinkedListTest.java	2003/10/05 23:00:40	1.6
+++ jsr166/src/test/tck/LinkedListTest.java	2010/11/03 07:54:52	1.21
@@ -1,8 +1,9 @@
 /*
- * Written by members of JCP JSR-166 Expert Group and released to the
- * public domain. Use, modify, and redistribute this code in any way
- * without acknowledgement. Other contributors include Andrew Wright,
- * Jeffrey Hayes, Pat Fischer, Mike Judd.
+ * 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.*;
@@ -11,11 +12,11 @@ import java.util.concurrent.*;
 
 public class LinkedListTest extends JSR166TestCase {
     public static void main(String[] args) {
-	junit.textui.TestRunner.run (suite());	
+        junit.textui.TestRunner.run(suite());
     }
 
     public static Test suite() {
-	return new TestSuite(LinkedListTest.class);
+        return new TestSuite(LinkedListTest.class);
     }
 
     /**
@@ -25,13 +26,13 @@ public class LinkedListTest extends JSR1
     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)));
+        for (int i = 0; i < n; ++i)
+            assertTrue(q.offer(new Integer(i)));
         assertFalse(q.isEmpty());
-	assertEquals(n, q.size());
+        assertEquals(n, q.size());
         return q;
     }
- 
+
     /**
      * new queue is empty
      */
@@ -46,24 +47,19 @@ public class LinkedListTest extends JSR1
         try {
             LinkedList q = new LinkedList((Collection)null);
             shouldThrow();
-        }
-        catch (NullPointerException success) {}
+        } 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 {}
+        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());
     }
 
     /**
@@ -99,16 +95,12 @@ public class LinkedListTest extends JSR1
      * offer(null) succeeds
      */
     public void testOfferNull() {
-	try {
-            LinkedList q = new LinkedList();
-            q.offer(null);
-        } catch (NullPointerException ie) { 
-            unexpectedException();
-        }   
+        LinkedList q = new LinkedList();
+        q.offer(null);
     }
 
     /**
-     * Offer succeeds 
+     * Offer succeeds
      */
     public void testOffer() {
         LinkedList q = new LinkedList();
@@ -135,79 +127,75 @@ public class LinkedListTest extends JSR1
             LinkedList q = new LinkedList();
             q.addAll(null);
             shouldThrow();
-        }
-        catch (NullPointerException success) {}
+        } 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 {}
+        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() {
-	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) {}
+        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() {
-	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){}
+        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
+     * poll succeeds unless empty
      */
     public void testPoll() {
         LinkedList q = populatedQueue(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.poll()).intValue());
+            assertEquals(i, q.poll());
         }
-	assertNull(q.poll());
+        assertNull(q.poll());
     }
 
     /**
-     *  peek returns next element, or null if empty
+     * 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();
+            assertEquals(i, q.peek());
+            assertEquals(i, q.poll());
             assertTrue(q.peek() == null ||
-                       i != ((Integer)q.peek()).intValue());
+                       !q.peek().equals(i));
         }
-	assertNull(q.peek());
+        assertNull(q.peek());
     }
 
     /**
@@ -216,29 +204,27 @@ public class LinkedListTest extends JSR1
     public void testElement() {
         LinkedList q = populatedQueue(SIZE);
         for (int i = 0; i < SIZE; ++i) {
-            assertEquals(i, ((Integer)q.element()).intValue());
-            q.poll();
+            assertEquals(i, q.element());
+            assertEquals(i, q.poll());
         }
         try {
             q.element();
             shouldThrow();
-        }
-        catch (NoSuchElementException success) {}
+        } catch (NoSuchElementException success) {}
     }
 
     /**
-     *  remove removes next element, or throws NSEE if empty
+     * 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());
+            assertEquals(i, q.remove());
         }
         try {
             q.remove();
             shouldThrow();
-        } catch (NoSuchElementException success){
-	}   
+        } catch (NoSuchElementException success) {}
     }
 
     /**
@@ -255,7 +241,7 @@ public class LinkedListTest extends JSR1
         }
         assertTrue(q.isEmpty());
     }
-	
+
     /**
      * contains(x) reports true when elements added but not yet removed
      */
@@ -276,7 +262,7 @@ public class LinkedListTest extends JSR1
         q.clear();
         assertTrue(q.isEmpty());
         assertEquals(0, q.size());
-        q.add(new Integer(1));
+        assertTrue(q.add(new Integer(1)));
         assertFalse(q.isEmpty());
         q.clear();
         assertTrue(q.isEmpty());
@@ -291,7 +277,7 @@ public class LinkedListTest extends JSR1
         for (int i = 0; i < SIZE; ++i) {
             assertTrue(q.containsAll(p));
             assertFalse(p.containsAll(q));
-            p.add(new Integer(i));
+            assertTrue(p.add(new Integer(i)));
         }
         assertTrue(p.containsAll(q));
     }
@@ -332,25 +318,25 @@ public class LinkedListTest extends JSR1
     }
 
     /**
-     *  toArray contains all elements
+     * toArray contains all elements
      */
     public void testToArray() {
         LinkedList q = populatedQueue(SIZE);
-	Object[] o = q.toArray();
+        Object[] o = q.toArray();
         Arrays.sort(o);
-	for(int i = 0; i < o.length; i++)
-	    assertEquals(o[i], q.poll());
+        for (int i = 0; i < o.length; i++)
+            assertEquals(o[i], q.poll());
     }
 
     /**
-     *  toArray(a) contains all elements
+     * toArray(a) contains all elements
      */
     public void testToArray2() {
         LinkedList q = populatedQueue(SIZE);
-	Integer[] ints = new Integer[SIZE];
-	ints = (Integer[])q.toArray(ints);
+        Integer[] ints = new Integer[SIZE];
+        ints = (Integer[])q.toArray(ints);
         Arrays.sort(ints);
-        for(int i = 0; i < ints.length; i++)
+        for (int i = 0; i < ints.length; i++)
             assertEquals(ints[i], q.poll());
     }
 
@@ -358,34 +344,34 @@ public class LinkedListTest extends JSR1
      * 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){}
+        LinkedList l = new LinkedList();
+        l.add(new Object());
+        try {
+            Object o[] = l.toArray(null);
+            shouldThrow();
+        } catch (NullPointerException success) {}
     }
 
     /**
-     * toArray with incompatable aray type throws CCE
+     * toArray(incompatible array type) throws ArrayStoreException
      */
     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){}
+        LinkedList l = new LinkedList();
+        l.add(new Integer(5));
+        try {
+            l.toArray(new String[10]);
+            shouldThrow();
+        } catch (ArrayStoreException success) {}
     }
-    
+
     /**
-     *  iterator iterates through all elements
+     * iterator iterates through all elements
      */
     public void testIterator() {
         LinkedList q = populatedQueue(SIZE);
         int i = 0;
-	Iterator it = q.iterator();
-        while(it.hasNext()) {
+        Iterator it = q.iterator();
+        while (it.hasNext()) {
             assertTrue(q.contains(it.next()));
             ++i;
         }
@@ -393,7 +379,7 @@ public class LinkedListTest extends JSR1
     }
 
     /**
-     *  iterator ordering is FIFO
+     * iterator ordering is FIFO
      */
     public void testIteratorOrdering() {
         final LinkedList q = new LinkedList();
@@ -402,8 +388,7 @@ public class LinkedListTest extends JSR1
         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(++k, it.next());
         }
 
         assertEquals(3, k);
@@ -412,17 +397,69 @@ public class LinkedListTest extends JSR1
     /**
      * iterator.remove removes current element
      */
-    public void testIteratorRemove () {
+    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();
+        assertEquals(it.next(), 1);
         it.remove();
         it = q.iterator();
-        assertEquals(it.next(), new Integer(2));
-        assertEquals(it.next(), new Integer(3));
+        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());
     }
 
@@ -436,15 +473,154 @@ public class LinkedListTest extends JSR1
         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());
-    }	
+        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());
+    }
 
 }