--- jsr166/src/main/java/util/LinkedList.java	2005/07/18 19:14:17	1.38
+++ jsr166/src/main/java/util/LinkedList.java	2008/05/18 23:47:56	1.48
@@ -1,12 +1,29 @@
 /*
- * %W% %E%
+ * Copyright 1997-2006 Sun Microsystems, Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
- * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
- * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
  */
 
 package java.util;
-import java.util.*; // for javadoc (till 6280605 is fixed)
 
 /**
  * Linked list implementation of the <tt>List</tt> interface.  Implements all
@@ -60,14 +77,14 @@ import java.util.*; // for javadoc (till
  * should be used only to detect bugs.</i>
  *
  * <p>This class is a member of the
- * <a href="{@docRoot}/../guide/collections/index.html">
+ * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  * Java Collections Framework</a>.
  *
  * @author  Josh Bloch
  * @version %I%, %G%
- * @see	    List
- * @see	    ArrayList
- * @see	    Vector
+ * @see     List
+ * @see     ArrayList
+ * @see     Vector
  * @since 1.2
  * @param <E> the type of elements held in this collection
  */
@@ -95,8 +112,8 @@ public class LinkedList<E>
      * @throws NullPointerException if the specified collection is null
      */
     public LinkedList(Collection<? extends E> c) {
-	this();
-	addAll(c);
+        this();
+        addAll(c);
     }
 
     /**
@@ -106,10 +123,10 @@ public class LinkedList<E>
      * @throws NoSuchElementException if this list is empty
      */
     public E getFirst() {
-	if (size==0)
-	    throw new NoSuchElementException();
+        if (size==0)
+            throw new NoSuchElementException();
 
-	return header.next.element;
+        return header.next.element;
     }
 
     /**
@@ -119,10 +136,10 @@ public class LinkedList<E>
      * @throws NoSuchElementException if this list is empty
      */
     public E getLast()  {
-	if (size==0)
-	    throw new NoSuchElementException();
+        if (size==0)
+            throw new NoSuchElementException();
 
-	return header.previous.element;
+        return header.previous.element;
     }
 
     /**
@@ -132,7 +149,7 @@ public class LinkedList<E>
      * @throws NoSuchElementException if this list is empty
      */
     public E removeFirst() {
-	return remove(header.next);
+        return remove(header.next);
     }
 
     /**
@@ -142,7 +159,7 @@ public class LinkedList<E>
      * @throws NoSuchElementException if this list is empty
      */
     public E removeLast() {
-	return remove(header.previous);
+        return remove(header.previous);
     }
 
     /**
@@ -151,7 +168,7 @@ public class LinkedList<E>
      * @param e the element to add
      */
     public void addFirst(E e) {
-	addBefore(e, header.next);
+        addBefore(e, header.next);
     }
 
     /**
@@ -162,7 +179,7 @@ public class LinkedList<E>
      * @param e the element to add
      */
     public void addLast(E e) {
-	addBefore(e, header);
+        addBefore(e, header);
     }
 
     /**
@@ -184,7 +201,7 @@ public class LinkedList<E>
      * @return the number of elements in this list
      */
     public int size() {
-	return size;
+        return size;
     }
 
     /**
@@ -196,7 +213,7 @@ public class LinkedList<E>
      * @return <tt>true</tt> (as specified by {@link Collection#add})
      */
     public boolean add(E e) {
-	addBefore(e, header);
+        addBefore(e, header);
         return true;
     }
 
@@ -271,11 +288,11 @@ public class LinkedList<E>
         int numNew = a.length;
         if (numNew==0)
             return false;
-	modCount++;
+        modCount++;
 
         Entry<E> successor = (index==size ? header : entry(index));
         Entry<E> predecessor = successor.previous;
-	for (int i=0; i<numNew; i++) {
+        for (int i=0; i<numNew; i++) {
             Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
             predecessor.next = e;
             predecessor = e;
@@ -299,7 +316,7 @@ public class LinkedList<E>
         }
         header.next = header.previous = header;
         size = 0;
-	modCount++;
+        modCount++;
     }
 
 
@@ -510,7 +527,7 @@ public class LinkedList<E>
      * 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})
+     * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
      * @since 1.6
      */
     public boolean offerLast(E e) {
@@ -547,8 +564,8 @@ public class LinkedList<E>
     }
 
     /**
-     * Retrieves and removes the first element of this list, or
-     * <tt>null</tt> if this list is empty.
+     * Retrieves and removes 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
@@ -561,8 +578,8 @@ public class LinkedList<E>
     }
 
     /**
-     * Retrieves and removes the last element of this list, or
-     * <tt>null</tt> if this list is empty.
+     * Retrieves and removes 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
@@ -665,68 +682,68 @@ public class LinkedList<E>
      * @see List#listIterator(int)
      */
     public ListIterator<E> listIterator(int index) {
-	return new ListItr(index);
+        return new ListItr(index);
     }
 
     private class ListItr implements ListIterator<E> {
-	private Entry<E> lastReturned = header;
-	private Entry<E> next;
-	private int nextIndex;
-	private int expectedModCount = modCount;
-
-	ListItr(int index) {
-	    if (index < 0 || index > size)
-		throw new IndexOutOfBoundsException("Index: "+index+
-						    ", Size: "+size);
-	    if (index < (size >> 1)) {
-		next = header.next;
-		for (nextIndex=0; nextIndex<index; nextIndex++)
-		    next = next.next;
-	    } else {
-		next = header;
-		for (nextIndex=size; nextIndex>index; nextIndex--)
-		    next = next.previous;
-	    }
-	}
-
-	public boolean hasNext() {
-	    return nextIndex != size;
-	}
-
-	public E next() {
-	    checkForComodification();
-	    if (nextIndex == size)
-		throw new NoSuchElementException();
-
-	    lastReturned = next;
-	    next = next.next;
-	    nextIndex++;
-	    return lastReturned.element;
-	}
-
-	public boolean hasPrevious() {
-	    return nextIndex != 0;
-	}
-
-	public E previous() {
-	    if (nextIndex == 0)
-		throw new NoSuchElementException();
-
-	    lastReturned = next = next.previous;
-	    nextIndex--;
-	    checkForComodification();
-	    return lastReturned.element;
-	}
-
-	public int nextIndex() {
-	    return nextIndex;
-	}
-
-	public int previousIndex() {
-	    return nextIndex-1;
-	}
+        private Entry<E> lastReturned = header;
+        private Entry<E> next;
+        private int nextIndex;
+        private int expectedModCount = modCount;
+
+        ListItr(int index) {
+            if (index < 0 || index > size)
+                throw new IndexOutOfBoundsException("Index: "+index+
+                                                    ", Size: "+size);
+            if (index < (size >> 1)) {
+                next = header.next;
+                for (nextIndex=0; nextIndex<index; nextIndex++)
+                    next = next.next;
+            } else {
+                next = header;
+                for (nextIndex=size; nextIndex>index; nextIndex--)
+                    next = next.previous;
+            }
+        }
+
+        public boolean hasNext() {
+            return nextIndex != size;
+        }
+
+        public E next() {
+            checkForComodification();
+            if (nextIndex == size)
+                throw new NoSuchElementException();
+
+            lastReturned = next;
+            next = next.next;
+            nextIndex++;
+            return lastReturned.element;
+        }
+
+        public boolean hasPrevious() {
+            return nextIndex != 0;
+        }
+
+        public E previous() {
+            if (nextIndex == 0)
+                throw new NoSuchElementException();
+
+            lastReturned = next = next.previous;
+            nextIndex--;
+            checkForComodification();
+            return lastReturned.element;
+        }
+
+        public int nextIndex() {
+            return nextIndex;
+        }
+
+        public int previousIndex() {
+            return nextIndex-1;
+        }
 
-	public void remove() {
+        public void remove() {
             checkForComodification();
             Entry<E> lastNext = lastReturned.next;
             try {
@@ -734,71 +751,92 @@ public class LinkedList<E>
             } catch (NoSuchElementException e) {
                 throw new IllegalStateException();
             }
-	    if (next==lastReturned)
+            if (next==lastReturned)
                 next = lastNext;
             else
-		nextIndex--;
-	    lastReturned = header;
-	    expectedModCount++;
-	}
-
-	public void set(E e) {
-	    if (lastReturned == header)
-		throw new IllegalStateException();
-	    checkForComodification();
-	    lastReturned.element = e;
-	}
-
-	public void add(E e) {
-	    checkForComodification();
-	    lastReturned = header;
-	    addBefore(e, next);
-	    nextIndex++;
-	    expectedModCount++;
-	}
-
-	final void checkForComodification() {
-	    if (modCount != expectedModCount)
-		throw new ConcurrentModificationException();
-	}
+                nextIndex--;
+            lastReturned = header;
+            expectedModCount++;
+        }
+
+        public void set(E e) {
+            if (lastReturned == header)
+                throw new IllegalStateException();
+            checkForComodification();
+            lastReturned.element = e;
+        }
+
+        public void add(E e) {
+            checkForComodification();
+            lastReturned = header;
+            addBefore(e, next);
+            nextIndex++;
+            expectedModCount++;
+        }
+
+        final void checkForComodification() {
+            if (modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+        }
     }
 
     private static class Entry<E> {
-	E element;
-	Entry<E> next;
-	Entry<E> previous;
-
-	Entry(E element, Entry<E> next, Entry<E> previous) {
-	    this.element = element;
-	    this.next = next;
-	    this.previous = previous;
-	}
+        E element;
+        Entry<E> next;
+        Entry<E> previous;
+
+        Entry(E element, Entry<E> next, Entry<E> previous) {
+            this.element = element;
+            this.next = next;
+            this.previous = 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++;
-	modCount++;
-	return newEntry;
+        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
+        newEntry.previous.next = newEntry;
+        newEntry.next.previous = newEntry;
+        size++;
+        modCount++;
+        return newEntry;
     }
 
     private E remove(Entry<E> e) {
-	if (e == header)
-	    throw new NoSuchElementException();
+        if (e == header)
+            throw new NoSuchElementException();
 
         E result = e.element;
-	e.previous.next = e.next;
-	e.next.previous = e.previous;
+        e.previous.next = e.next;
+        e.next.previous = e.previous;
         e.next = e.previous = null;
         e.element = null;
-	size--;
-	modCount++;
+        size--;
+        modCount++;
         return result;
     }
 
     /**
+     * @since 1.6
+     */
+    public Iterator<E> descendingIterator() {
+        return new DescendingIterator();
+    }
+
+    /** Adapter to provide descending iterators via ListItr.previous */
+    private class DescendingIterator implements Iterator {
+        final ListItr itr = new ListItr(size());
+        public boolean hasNext() {
+            return itr.hasPrevious();
+        }
+        public E next() {
+            return itr.previous();
+        }
+        public void remove() {
+            itr.remove();
+        }
+    }
+
+    /**
      * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
      * themselves are not cloned.)
      *
@@ -806,11 +844,11 @@ public class LinkedList<E>
      */
     public Object clone() {
         LinkedList<E> clone = null;
-	try {
-	    clone = (LinkedList<E>) super.clone();
-	} catch (CloneNotSupportedException e) {
-	    throw new InternalError();
-	}
+        try {
+            clone = (LinkedList<E>) super.clone();
+        } catch (CloneNotSupportedException e) {
+            throw new InternalError();
+        }
 
         // Put clone into "virgin" state
         clone.header = new Entry<E>(null, null, null);
@@ -840,11 +878,11 @@ public class LinkedList<E>
      *         in proper sequence
      */
     public Object[] toArray() {
-	Object[] result = new Object[size];
+        Object[] result = new Object[size];
         int i = 0;
         for (Entry<E> e = header.next; e != header; e = e.next)
             result[i++] = e.element;
-	return result;
+        return result;
     }
 
     /**
@@ -890,7 +928,7 @@ public class LinkedList<E>
             a = (T[])java.lang.reflect.Array.newInstance(
                                 a.getClass().getComponentType(), size);
         int i = 0;
-	Object[] result = a;
+        Object[] result = a;
         for (Entry<E> e = header.next; e != header; e = e.next)
             result[i++] = e.element;
 
@@ -912,13 +950,13 @@ public class LinkedList<E>
      */
     private void writeObject(java.io.ObjectOutputStream s)
         throws java.io.IOException {
-	// Write out any hidden serialization magic
-	s.defaultWriteObject();
+        // Write out any hidden serialization magic
+        s.defaultWriteObject();
 
         // Write out size
         s.writeInt(size);
 
-	// Write out all elements in the proper order.
+        // Write out all elements in the proper order.
         for (Entry e = header.next; e != header; e = e.next)
             s.writeObject(e.element);
     }
@@ -929,8 +967,8 @@ public class LinkedList<E>
      */
     private void readObject(java.io.ObjectInputStream s)
         throws java.io.IOException, ClassNotFoundException {
-	// Read in any hidden serialization magic
-	s.defaultReadObject();
+        // Read in any hidden serialization magic
+        s.defaultReadObject();
 
         // Read in size
         int size = s.readInt();
@@ -939,8 +977,8 @@ public class LinkedList<E>
         header = new Entry<E>(null, null, null);
         header.next = header.previous = header;
 
-	// Read in all elements in the proper order.
-	for (int i=0; i<size; i++)
+        // Read in all elements in the proper order.
+        for (int i=0; i<size; i++)
             addBefore((E)s.readObject(), header);
     }
 }