--- jsr166/src/main/java/util/LinkedList.java	2003/12/28 00:55:45	1.14
+++ jsr166/src/main/java/util/LinkedList.java	2005/05/16 05:17:07	1.28
@@ -1,7 +1,7 @@
 /*
  * %W% %E%
  *
- * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  */
 
@@ -14,14 +14,12 @@ package java.util;
  * the <tt>LinkedList</tt> class provides uniformly named methods to
  * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
  * beginning and end of the list.  These operations allow linked lists to be
- * used as a stack, queue, or double-ended queue (deque).<p>
+ * used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
+ * double-ended queue}. <p>
  *
- * The class implements the <tt>Queue</tt> interface, providing
+ * The class implements the <tt>Deque</tt> interface, providing
  * first-in-first-out queue operations for <tt>add</tt>,
- * <tt>poll</tt>, etc. Other stack and deque operations could be
- * easily recast in terms of the standard list operations.  They're
- * included here primarily for convenience, though they may run
- * slightly faster than the equivalent List operations.<p>
+ * <tt>poll</tt>, along with other stack and deque operations.<p>
  *
  * All of the operations perform as could be expected for a doubly-linked
  * list.  Operations that index into the list will traverse the list from
@@ -38,16 +36,17 @@ package java.util;
  * Collections.synchronizedList method.  This is best done at creation time,
  * to prevent accidental unsynchronized access to the list: <pre>
  *     List list = Collections.synchronizedList(new LinkedList(...));
- * </pre><p>
+ * </pre>
  *
- * The iterators returned by the this class's <tt>iterator</tt> and
+ * <p>The iterators returned by this class's <tt>iterator</tt> and
  * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
- * structurally modified at any time after the iterator is created, in any way
- * except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
- * the iterator will throw a <tt>ConcurrentModificationException</tt>.  Thus,
- * in the face of concurrent modification, the iterator fails quickly and
- * cleanly, rather than risking arbitrary, non-deterministic behavior at an
- * undetermined time in the future.
+ * structurally modified at any time after the iterator is created, in
+ * any way except through the Iterator's own <tt>remove</tt> or
+ * <tt>add</tt> methods, the iterator will throw a {@link
+ * ConcurrentModificationException}.  Thus, in the face of concurrent
+ * modification, the iterator fails quickly and cleanly, rather than
+ * risking arbitrary, non-deterministic behavior at an undetermined
+ * time in the future.
  *
  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  * as it is, generally speaking, impossible to make any hard guarantees in the
@@ -55,9 +54,9 @@ package java.util;
  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  * Therefore, it would be wrong to write a program that depended on this
  * exception for its correctness:   <i>the fail-fast behavior of iterators
- * should be used only to detect bugs.</i><p>
+ * should be used only to detect bugs.</i>
  *
- * This class is a member of the
+ * <p>This class is a member of the
  * <a href="{@docRoot}/../guide/collections/index.html">
  * Java Collections Framework</a>.
  *
@@ -73,7 +72,7 @@ package java.util;
 
 public class LinkedList<E>
     extends AbstractSequentialList<E>
-    implements List<E>, Queue<E>, Cloneable, java.io.Serializable
+    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
 {
     private transient Entry<E> header = new Entry<E>(null, null, null);
     private transient int size = 0;
@@ -90,8 +89,8 @@ public class LinkedList<E>
      * collection, in the order they are returned by the collection's
      * iterator.
      *
-     * @param  c the collection whose elements are to be placed into this list.
-     * @throws NullPointerException if the specified collection is null.
+     * @param  c the collection whose elements are to be placed into this list
+     * @throws NullPointerException if the specified collection is null
      */
      public LinkedList(Collection<? extends E> c) {
 	 this();
@@ -101,8 +100,8 @@ public class LinkedList<E>
     /**
      * Returns the first element in this list.
      *
-     * @return the first element in this list.
-     * @throws    NoSuchElementException if this list is empty.
+     * @return the first element in this list
+     * @throws NoSuchElementException if this list is empty
      */
     public E getFirst() {
 	if (size==0)
@@ -114,8 +113,8 @@ public class LinkedList<E>
     /**
      * Returns the last element in this list.
      *
-     * @return the last element in this list.
-     * @throws    NoSuchElementException if this list is empty.
+     * @return the last element in this list
+     * @throws NoSuchElementException if this list is empty
      */
     public E getLast()  {
 	if (size==0)
@@ -127,8 +126,8 @@ public class LinkedList<E>
     /**
      * Removes and returns the first element from this list.
      *
-     * @return the first element from this list.
-     * @throws    NoSuchElementException if this list is empty.
+     * @return the first element from this list
+     * @throws NoSuchElementException if this list is empty
      */
     public E removeFirst() {
 	return remove(header.next);
@@ -137,8 +136,8 @@ public class LinkedList<E>
     /**
      * Removes and returns the last element from this list.
      *
-     * @return the last element from this list.
-     * @throws    NoSuchElementException if this list is empty.
+     * @return the last element from this list
+     * @throws NoSuchElementException if this list is empty
      */
     public E removeLast() {
 	return remove(header.previous);
@@ -147,30 +146,30 @@ public class LinkedList<E>
     /**
      * Inserts the given element at the beginning of this list.
      *
-     * @param o the element to be inserted at the beginning of this list.
+     * @param e the element to be inserted at the beginning of this list
      */
-    public void addFirst(E o) {
-	addBefore(o, header.next);
+    public void addFirst(E e) {
+	addBefore(e, header.next);
     }
 
     /**
      * Appends the given element to the end of this list.  (Identical in
      * function to the <tt>add</tt> method; included only for consistency.)
      *
-     * @param o the element to be inserted at the end of this list.
+     * @param e the element to be inserted at the end of this list
      */
-    public void addLast(E o) {
-	addBefore(o, header);
+    public void addLast(E e) {
+	addBefore(e, header);
     }
 
     /**
      * Returns <tt>true</tt> if this list contains the specified element.
      * More formally, returns <tt>true</tt> if and only if this list contains
-     * at least one element <tt>e</tt> such that <tt>(o==null ? e==null
-     * : o.equals(e))</tt>.
+     * at least one element <tt>e</tt> such that
+     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
      *
-     * @param o element whose presence in this list is to be tested.
-     * @return <tt>true</tt> if this list contains the specified element.
+     * @param o element whose presence in this list is to be tested
+     * @return <tt>true</tt> if this list contains the specified element
      */
     public boolean contains(Object o) {
         return indexOf(o) != -1;
@@ -179,7 +178,7 @@ public class LinkedList<E>
     /**
      * Returns the number of elements in this list.
      *
-     * @return the number of elements in this list.
+     * @return the number of elements in this list
      */
     public int size() {
 	return size;
@@ -188,24 +187,26 @@ public class LinkedList<E>
     /**
      * Appends the specified element to the end of this list.
      *
-     * @param o element to be appended to this list.
-     * @return <tt>true</tt> (as per the general contract of
-     * <tt>Collection.add</tt>).
+     * @param e element to be appended to this list
+     * @return <tt>true</tt> (as per the spec for {@link Collection#add})
      */
-    public boolean add(E o) {
-	addBefore(o, header);
+    public boolean add(E e) {
+	addBefore(e, header);
         return true;
     }
 
     /**
-     * Removes the first occurrence of the specified element in this list.  If
-     * the list does not contain the element, it is unchanged.  More formally,
-     * removes the element with the lowest index <tt>i</tt> such that
-     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
-     * element exists).
+     * Removes the first occurrence of the specified element from this list,
+     * if it is present.  If this list does not contain the element, it is
+     * unchanged.  More formally, removes the element with the lowest index
+     * <tt>i</tt> such that
+     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
+     * (if such an element exists).  Returns <tt>true</tt> if this list
+     * contained the specified element (or equivalently, if this list
+     * changed as a result of the call).
      *
-     * @param o element to be removed from this list, if present.
-     * @return <tt>true</tt> if the list contained the specified element.
+     * @param o element to be removed from this list, if present
+     * @return <tt>true</tt> if this list contained the specified element
      */
     public boolean remove(Object o) {
         if (o==null) {
@@ -234,9 +235,9 @@ public class LinkedList<E>
      * progress.  (This implies that the behavior of this call is undefined if
      * the specified Collection is this list, and this list is nonempty.)
      *
-     * @param c the elements to be inserted into this list.
-     * @return <tt>true</tt> if this list changed as a result of the call.
-     * @throws NullPointerException if the specified collection is null.
+     * @param c the elements to be inserted into this list
+     * @return <tt>true</tt> if this list changed as a result of the call
+     * @throws NullPointerException if the specified collection is null
      */
     public boolean addAll(Collection<? extends E> c) {
         return addAll(size, c);
@@ -250,13 +251,12 @@ public class LinkedList<E>
      * in the list in the order that they are returned by the
      * specified collection's iterator.
      *
-     * @param index index at which to insert first element
-     *		    from the specified collection.
-     * @param c elements to be inserted into this list.
-     * @return <tt>true</tt> if this list changed as a result of the call.
-     * @throws IndexOutOfBoundsException if the specified index is out of
-     *            range (<tt>index &lt; 0 || index &gt; size()</tt>).
-     * @throws NullPointerException if the specified collection is null.
+     * @param index index at which to insert the first element
+     *              from the specified collection
+     * @param c elements to be inserted into this list
+     * @return <tt>true</tt> if this list changed as a result of the call
+     * @throws IndexOutOfBoundsException {@inheritDoc}
+     * @throws NullPointerException if the specified collection is null
      */
     public boolean addAll(int index, Collection<? extends E> c) {
         if (index < 0 || index > size)
@@ -303,11 +303,9 @@ public class LinkedList<E>
     /**
      * Returns the element at the specified position in this list.
      *
-     * @param index index of element to return.
-     * @return the element at the specified position in this list.
-     *
-     * @throws IndexOutOfBoundsException if the specified index is is out of
-     * range (<tt>index &lt; 0 || index &gt;= size()</tt>).
+     * @param index index of the element to return
+     * @return the element at the specified position in this list
+     * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public E get(int index) {
         return entry(index).element;
@@ -317,11 +315,10 @@ public class LinkedList<E>
      * Replaces the element at the specified position in this list with the
      * specified element.
      *
-     * @param index index of element to replace.
-     * @param element element to be stored at the specified position.
-     * @return the element previously at the specified position.
-     * @throws IndexOutOfBoundsException if the specified index is out of
-     *		  range (<tt>index &lt; 0 || index &gt;= size()</tt>).
+     * @param index index of the element to replace
+     * @param element element to be stored at the specified position
+     * @return the element previously at the specified position
+     * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public E set(int index, E element) {
         Entry<E> e = entry(index);
@@ -335,11 +332,9 @@ public class LinkedList<E>
      * Shifts the element currently at that position (if any) and any
      * subsequent elements to the right (adds one to their indices).
      *
-     * @param index index at which the specified element is to be inserted.
-     * @param element element to be inserted.
-     *
-     * @throws IndexOutOfBoundsException if the specified index is out of
-     *		  range (<tt>index &lt; 0 || index &gt; size()</tt>).
+     * @param index index at which the specified element is to be inserted
+     * @param element element to be inserted
+     * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public void add(int index, E element) {
         addBefore(element, (index==size ? header : entry(index)));
@@ -350,18 +345,16 @@ public class LinkedList<E>
      * subsequent elements to the left (subtracts one from their indices).
      * Returns the element that was removed from the list.
      *
-     * @param index the index of the element to removed.
-     * @return the element previously at the specified position.
-     *
-     * @throws IndexOutOfBoundsException if the specified index is out of
-     * 		  range (<tt>index &lt; 0 || index &gt;= size()</tt>).
+     * @param index the index of the element to be removed
+     * @return the element previously at the specified position
+     * @throws IndexOutOfBoundsException {@inheritDoc}
      */
     public E remove(int index) {
         return remove(entry(index));
     }
 
     /**
-     * Return the indexed entry.
+     * Returns the indexed entry.
      */
     private Entry<E> entry(int index) {
         if (index < 0 || index >= size)
@@ -388,10 +381,10 @@ public class LinkedList<E>
      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
      * there is no such index.
      *
-     * @param o element to search for.
+     * @param o element to search for
      * @return the index in this list of the first occurrence of the
-     * 	       specified element, or -1 if the list does not contain this
-     * 	       element.
+     *         specified element, or -1 if the list does not contain this
+     *         element
      */
     public int indexOf(Object o) {
         int index = 0;
@@ -418,10 +411,10 @@ public class LinkedList<E>
      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
      * there is no such index.
      *
-     * @param o element to search for.
+     * @param o element to search for
      * @return the index in this list of the last occurrence of the
-     * 	       specified element, or -1 if the list does not contain this
-     * 	       element.
+     *         specified element, or -1 if the list does not contain this
+     *         element
      */
     public int lastIndexOf(Object o) {
         int index = size;
@@ -445,7 +438,7 @@ public class LinkedList<E>
 
     /**
      * Retrieves, but does not remove, the head (first element) of this list.
-     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
+     * @return the head of this list, or <tt>null</tt> if this list is empty
      * @since 1.5
      */
     public E peek() {
@@ -456,8 +449,8 @@ public class LinkedList<E>
 
     /**
      * Retrieves, but does not remove, the head (first element) of this list.
-     * @return the head of this queue.
-     * @throws NoSuchElementException if this queue is empty.
+     * @return the head of this list
+     * @throws NoSuchElementException if this list is empty
      * @since 1.5
      */
     public E element() {
@@ -465,8 +458,8 @@ public class LinkedList<E>
     }
 
     /**
-     * Retrieves and removes the head (first element) of this list.
-     * @return the head of this queue, or <tt>null</tt> if this queue is empty.
+     * Retrieves and removes the head (first element) of this list
+     * @return the head of this list, or <tt>null</tt> if this list is empty
      * @since 1.5
      */
     public E poll() {
@@ -477,8 +470,9 @@ public class LinkedList<E>
 
     /**
      * Retrieves and removes the head (first element) of this list.
-     * @return the head of this queue.
-     * @throws NoSuchElementException if this queue is empty.
+     *
+     * @return the head of this list
+     * @throws NoSuchElementException if this list is empty
      * @since 1.5
      */
     public E remove() {
@@ -488,13 +482,162 @@ public class LinkedList<E>
     /**
      * Adds the specified element as the tail (last element) of this list.
      *
-     * @param o the element to add.
-     * @return <tt>true</tt> (as per the general contract of
-     * <tt>Queue.offer</tt>)
+     * @param e the element to add
+     * @return <tt>true</tt> (as per the spec for {@link Queue#offer})
      * @since 1.5
      */
-    public boolean offer(E o) {
-        return add(o);
+    public boolean offer(E e) {
+        return add(e);
+    }
+
+    // Deque operations
+    /**
+     * Inserts the specified element at the front of this list.
+     *
+     * @param e the element to insert
+     * @return <tt>true</tt> (as per the spec for {@link Deque#offerFirst})
+     * @since 1.6
+     */
+    public boolean offerFirst(E e) {
+        addFirst(e);
+        return true;
+    }
+
+    /**
+     * Inserts the specified element at the end of this list.
+     *
+     * @param e the element to insert
+     * @return <tt>true</tt> (as per the spec for {@link Deque#offerLast})
+     * @since 1.6
+     */
+    public boolean offerLast(E e) {
+        addLast(e);
+        return true;
+    }
+
+    /**
+     * Retrieves, but does not remove, the first element of this list,
+     * or returns <tt>null</tt> if this list is empty.
+     *
+     * @return the first element of this list, or <tt>null</tt>
+     *         if this list is empty
+     * @since 1.6
+     */
+    public E peekFirst() {
+        if (size==0)
+            return null;
+        return getFirst();
+    }
+
+    /**
+     * Retrieves, but does not remove, the last element of this list,
+     * or returns <tt>null</tt> if this list is empty.
+     *
+     * @return the last element of this list, or <tt>null</tt>
+     *         if this list is empty
+     * @since 1.6
+     */
+    public E peekLast() {
+        if (size==0)
+            return null;
+        return getLast();
+    }
+
+    /**
+     * Retrieves and removes the first element of this list, or
+     * <tt>null</tt> if this list is empty.
+     *
+     * @return the first element of this list, or <tt>null</tt> if
+     *     this list is empty
+     * @since 1.6
+     */
+    public E pollFirst() {
+        if (size==0)
+            return null;
+        return removeFirst();
+    }
+
+    /**
+     * Retrieves and removes the last element of this list, or
+     * <tt>null</tt> if this list is empty.
+     *
+     * @return the last element of this list, or <tt>null</tt> if
+     *     this list is empty
+     * @since 1.6
+     */
+    public E pollLast() {
+        if (size==0)
+            return null;
+        return removeLast();
+    }
+
+    /**
+     * Pushes an element onto the stack represented by this list.  In other
+     * words, inserts the element at the front of this list.
+     *
+     * <p>This method is equivalent to {@link #addFirst}.
+     *
+     * @param e the element to push
+     * @since 1.6
+     */
+    public void push(E e) {
+        addFirst(e);
+    }
+
+    /**
+     * Pops an element from the stack represented by this list.  In other
+     * words, removes and returns the first element of this list.
+     *
+     * <p>This method is equivalent to {@link #removeFirst()}.
+     *
+     * @return the element at the front of this list (which is the top
+     *         of the stack represented by this list)
+     * @throws NoSuchElementException if this list is empty
+     * @since 1.6
+     */
+    public E pop() {
+        return removeFirst();
+    }
+
+    /**
+     * Removes the first occurrence of the specified element in this
+     * list (when traversing the list from head to tail).  If the list
+     * does not contain the element, it is unchanged.
+     *
+     * @param o element to be removed from this list, if present
+     * @return <tt>true</tt> if the list contained the specified element
+     * @since 1.6
+     */
+    public boolean removeFirstOccurrence(Object o) {
+        return remove(o);
+    }
+
+    /**
+     * Removes the last occurrence of the specified element in this
+     * list (when traversing the list from head to tail).  If the list
+     * does not contain the element, it is unchanged.
+     *
+     * @param o element to be removed from this list, if present
+     * @return <tt>true</tt> if the list contained the specified element
+     * @since 1.6
+     */
+    public boolean removeLastOccurrence(Object o) {
+        if (o==null) {
+            for (Entry e = header.previous; e != header; e = e.previous) {
+                if (e.element==null) {
+                    remove(e);
+                    return true;
+                }
+            }
+        } else {
+            for (Entry e = header.previous; e != header; e = e.previous) {
+                if (o.equals(e.element)) {
+                    remove(e);
+                    return true;
+                }
+            }
+        }
+        return false;
     }
 
     /**
@@ -511,12 +654,11 @@ public class LinkedList<E>
      * than risking arbitrary, non-deterministic behavior at an undetermined
      * time in the future.
      *
-     * @param index index of first element to be returned from the
-     *		    list-iterator (by a call to <tt>next</tt>).
+     * @param index index of the first element to be returned from the
+     *              list-iterator (by a call to <tt>next</tt>)
      * @return a ListIterator of the elements in this list (in proper
-     * 	       sequence), starting at the specified position in the list.
-     * @throws    IndexOutOfBoundsException if index is out of range
-     *		  (<tt>index &lt; 0 || index &gt; size()</tt>).
+     *         sequence), starting at the specified position in the list
+     * @throws IndexOutOfBoundsException {@inheritDoc}
      * @see List#listIterator(int)
      */
     public ListIterator<E> listIterator(int index) {
@@ -597,17 +739,17 @@ public class LinkedList<E>
 	    expectedModCount++;
 	}
 
-	public void set(E o) {
+	public void set(E e) {
 	    if (lastReturned == header)
 		throw new IllegalStateException();
 	    checkForComodification();
-	    lastReturned.element = o;
+	    lastReturned.element = e;
 	}
 
-	public void add(E o) {
+	public void add(E e) {
 	    checkForComodification();
 	    lastReturned = header;
-	    addBefore(o, next);
+	    addBefore(e, next);
 	    nextIndex++;
 	    expectedModCount++;
 	}
@@ -630,8 +772,8 @@ public class LinkedList<E>
 	}
     }
 
-    private Entry<E> addBefore(E o, Entry<E> e) {
-	Entry<E> newEntry = new Entry<E>(o, e, e.previous);
+    private Entry<E> addBefore(E e, Entry<E> entry) {
+	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
 	newEntry.previous.next = newEntry;
 	newEntry.next.previous = newEntry;
 	size++;
@@ -657,7 +799,7 @@ public class LinkedList<E>
      * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
      * themselves are not cloned.)
      *
-     * @return a shallow copy of this <tt>LinkedList</tt> instance.
+     * @return a shallow copy of this <tt>LinkedList</tt> instance
      */
     public Object clone() {
         LinkedList<E> clone = null;
@@ -685,7 +827,7 @@ public class LinkedList<E>
      * in the correct order.
      *
      * @return an array containing all of the elements in this list
-     * 	       in the correct order.
+     *         in the correct order
      */
     public Object[] toArray() {
 	Object[] result = new Object[size];
@@ -710,12 +852,12 @@ public class LinkedList<E>
      * does not contain any null elements.
      *
      * @param a the array into which the elements of the list are to
-     *		be stored, if it is big enough; otherwise, a new array of the
-     * 		same runtime type is allocated for this purpose.
-     * @return an array containing the elements of the list.
+     *          be stored, if it is big enough; otherwise, a new array of the
+     *          same runtime type is allocated for this purpose.
+     * @return an array containing the elements of the list
      * @throws ArrayStoreException if the runtime type of a is not a
-     *         supertype of the runtime type of every element in this list.
-     * @throws NullPointerException if the specified array is null.
+     *         supertype of the runtime type of every element in this list
+     * @throws NullPointerException if the specified array is null
      */
     public <T> T[] toArray(T[] a) {
         if (a.length < size)
@@ -739,8 +881,8 @@ public class LinkedList<E>
      * is, serialize it).
      *
      * @serialData The size of the list (the number of elements it
-     *		   contains) is emitted (int), followed by all of its
-     * elements (each an Object) in the proper order.
+     *             contains) is emitted (int), followed by all of its
+     *             elements (each an Object) in the proper order.
      */
     private void writeObject(java.io.ObjectOutputStream s)
         throws java.io.IOException {