Collections drop from Classpath:

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/BitSet.java (and): Fix off-by-one bug, don't skip part of
	the bitset.
	(andNot): Likewise.
	(xor): Likewise.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/LinkedList.java (LinkedListItr.add): Don't skip the next
	entry.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/TreeMap.java (removeNode): Fix bug in node removal.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/AbstractCollection.java (containsAll): Use size of the
	correct collection for loop bound.
	* java/util/AbstractList.java (iterator.next): Increment pos after
	calling get on backing list.
	(listIterator.next): Likewise.
	* java/util/LinkedList.java (addLastEntry): Don't increment size before
	checking for size == 0.
	(addFirstEntry): Rearrange to match addLastEntry.
	(add): Do not increment size before inserting the new entry.

	* java/util/AbstractCollection.java (addAll): Use size of the
	correct collection for loop bound.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/AbstractSet.java (removeAll): Fix scoping thinko.
	* java/util/HashMap.java (putAllInternal): Set size here.
	* java/util/Hashtable.java (putAllInternal): New method. Copy contents
	of a map efficiently without calling put() or putAll().
	(Hashtable (map)): Use putAllInternal.
	(clone): Likewise.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/Collections.java:
	* java/util/Vector.java:
	* java/util/WeakHashMap.java: Fix spelling errors.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractCollection.java (removeAllInternal),
	(retainAllInternal): Add hooks for use by ArrayList.
	* java/util/AbstractList.java: Minor code updates. Fix some
	scoping.
	* java/util/AbstractMap.java: ditto
	* java/util/ArrayList.java (readObject, writeObject): ditto
	(removeAllInternal, retainAllInternal): Optimize.
	* java/util/Arrays.java: ditto
	* java/util/Collections.java: ditto. Change order of parameters
	to equals(Object, Object) to match specs.
	* java/util/Dictionary.java: Improve javadoc.
	(Dictionary): Add explicit constructor.
	* java/util/HashMap.java: Improve javadoc. Rearrange methods to
	follow order in JDK. Cleanups related to recent code migration to
	AbstractMap. Fix some scoping.
	(entrySet): Cache the result.
	(modCount): Ensure that this is updated correctly.
	* java/util/HashSet.java: Improve javadoc. Fix some scoping.
	(init): Add hooks for LinkedHashSet.
	(map): Use "" instead of Boolean.TRUE in backing map. Use
	package-private API where possible for less overhead.
	(readObject, writeObject): Fix serialization.
	* java/util/Hashtable.java: Improve javadoc. Fix some scoping.
	(entrySet, keySet, values): Cache the result.
	(modCount): Ensure that this is updated correctly.
	(contains, remove): Fix NullPointer checking to match specs.
	(class Enumeration): Make more like HashIterator.
	* java/util/IdentityHashMap.java: Minor code updates.
	(modCount): Ensure that this is updated correctly.
	(readObject, writeObject): Fix serialization.
	* java/util/LinkedHashMap.java: Minor code updates. Cleanups
	related to recent code migration to AbstractMap.
	* java/util/LinkedHashSet.java: New file.
	* java/util/LinkedList.java:
	(readObject, writeObject): Fix serialization.
	* java/util/Makefile.am: List recently added files.
	* java/util/Stack.java: Minor code updates.
	* java/util/TreeMap.java: Improve javadoc. Overhaul the class to
	be more efficient. Fix some scoping. Rearrange the methods.
	(nil): Ensure that this can be thread-safe, and make it a static
	final. Initialize it to be more useful as a sentinal node.
	(Node): Specify color in constructor.
	(deleteFixup, insertFixup): Improve comments and algorithm.
	(fabricateTree): Redesign with less overhead.
	(lowestGreaterThan): Add parameter first to make SubMap easier.
	(removeNode): Patch hole where nil was being modified. Choose
	predecessor instead of successor so in-place swap works.
	(class VerifyResult, verifyTree, verifySub, verifyError): Remove
	this dead code after verifying the class works.
	(class SubMap): Rewrite several algorithms to avoid problems with
	comparing nil.
	* java/util/TreeSet.java: Improve javadoc. Fix some scoping.
	(clone): Fix ClassCastException when cloning subSet().
	(readObject, writeObject): Fix serialization.
	* java/util/WeakHashMap.java: Improve javadoc. Fix some scoping.
	(NULL_KEY): Make it compare as null, for ease elsewhere.
	(Class WeakEntry): Rename from Entry, to avoid shadowing
	Map.Entry. Add missing toString.
	(modCount): Ensure that this is updated correctly.
	(clear, containsValue, keySet, putAll, values, WeakHashMap(Map)):
	Add missing methods and constructor.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/ArrayList.java (checkBoundExclusive),
	(checkBoundInclusive): Rename from range??clusive, to match
	AbstractList.
	* java/util/LinkedList.java (checkBoundsExclusive),
	(checkBoundsInclusive): ditto
	* java/util/Vector.java (checkBoundExclusive),
	(checkBoundInclusive): Move bounds checking into common methods.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractList.java:
	(modCount): Make sure it is updated in all needed places.
	* java/util/ArrayList.java: Improve javadoc. Implements
	RandomAccess. Add serialVersionUID. Reorder methods.
	(modCount): Make sure it is updated in all needed places.
	(rangeExclusive, rangeInclusive): Add common methods for bounds
	check.
	(isEmpty): Add missing method.
	* java/util/Collections.java: (class SynchronizedList): Make
	package visible.
	* java/util/ConcurrentModificationException.java: Improve
	javadoc.
	* java/util/EmptyStackException.java: Improve javadoc.
	* java/util/LinkedList.java: Improve javadoc.
	(modCount): Make sure it is updated in all needed places.
	(rangeExclusive, rangeInclusive): Add common methods for bounds
	check.
	* java/util/NoSuchElementException.java: Improve javadoc.
	* java/util/Stack.java: Improve javadoc. Fix synchronization
	issues.
	(modCount): Make sure it is updated in all needed places.
	* java/util/Vector.java: Improve javadoc. Fix synchronization
	issues. Implements RandomAccess. Reorder methods.
	(modCount): Make sure it is updated in all needed places.
	(setSize): Fix according to specifications: this does not dictate
	the backing array size.
	(removeAll, retainAll): Faster implementations.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/BitSet.java: Improve javadoc.
	(cardinality(), clear(), clear(int, int), flip(int)),
	(flip(int, int), get(int, int), intersects(BitSet), isEmpty()),
	(nextClearBit(int), nextSetBit(int), set(int, boolean)),
	(set(int, int), set(int, int, boolean)): Add new JDK 1.4 methods.
	(clone): Fix so subclasses clone correctly.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractCollection.java: Improve javadoc.
	(AbstractCollection()): Make constructor protected.
	(equals(Object, Object), hashCode(Object)): Add utility methods.
	* java/util/AbstractList.java: Improve javadoc.
	(AbstractList()): Make constructor protected.
	(indexOf(Object)): Call listIterator(), not listIterator(int).
	(iterator()): Follow Sun's requirement to not use listIterator(0).
	(listIterator(int)): Make AbstractListItr anonymous.
	(subList(int, int)): Add support for RandomAccess.
	(SubList.add(int, Object), SubList.remove(Object)): Fix bug with
	modCount tracking.
	(SubList.addAll(Collection)): Add missing method.
	(SubList.listIterator(int)): Fix bugs in indexing, modCount
	tracking.
	(class RandomAccessSubList): Add new class.
	* java/util/AbstractMap.java: Improve javadoc.
	(keys, values, KEYS, VALUES, ENTRIES): Consolidate common map
	fields.
	(AbstractMap()): Make constructor protected.
	(equals(Object, Object), hashCode(Object)): Add utility methods.
	(equals(Object)): Change algorithm to
	entrySet().equals(m.entrySet()), as documented by Sun.
	(keySet(), values()): Cache the collections.
	* java/util/AbstractSequentialList.java: Improve javadoc.
	(AbstractSequentialList()): Make constructor protected.
	* java/util/AbstractSet.java: Improve javadoc.
	(AbstractSet()): Make constructor protected.
	(removeAll(Collection)): Add missing method.
	* java/util/Arrays.java: Improve javadoc, rearrange method orders.
	(defaultComparator): Remove, in favor of
	Collections.compare(Object, Object, Comparator).
	(binarySearch, equals, sort): Fix natural order comparison of
	floats and doubles. Also improve Object comparison - when
	comparator is null, use natural order.
	(fill, sort): Add missing checks for IllegalArgumentException.
	(sort, qsort): Fix sorting bugs, rework the code for more
	legibility.
	(mergeSort): Inline into sort(Object[], int, int, Comparator).
	(class ArrayList): Rename from ListImpl, and make compatible with
	JDK serialization. Add methods which more efficiently override
	those of AbstractList.
	* java/util/Collections: Improve javadoc.
	(isSequential(List)): Add and use a method for deciding between
	RandomAccess and sequential algorithms on lists.
	(class Empty*, class Synchronized*, class Unmodifiable*): Make
	compliant with JDK serializability.
	(class Singleton*, class CopiesList, class RevereseComparator),
	(class UnmodifiableMap.UnmodifiableEntrySet),
	(class *RandomAccessList): New classes for serial compatibility.
	(class Empty*, class Singleton*, class CopiesList): Add methods
	which more efficiently override those of Abstract*.
	(search): Inline into binarySearch(List, Object, Comparator).
	(binarySearch): Make sequential search only do log(n) comparisons,
	instead of n.
	(copy(List, List)): Do bounds checking before starting.
	(indexOfSubList, lastIndexOfSubList, list, replaceAll, rotate),
	(swap):	Add new JDK 1.4 methods.
	(binarySearch, max, min, sort): Allow null comparator to represent
	natural ordering.
	(reverse(List)): Avoid unnecessary swap.
	(shuffle(List, Random)): Do shuffle in-place for RandomAccess
	lists.
	(SingletonList.get): Fix logic bug.
	(SingletonMap.entrySet): Make the entry immutable, and cache the
	returned set.
	(SynchronizedCollection, SynchronizedMap, UnmodifiableCollection),
	(UnmodifiableMap): Detect null pointer in construction.
	(SynchronizedMap, UnmodifiableMap): Cache collection views.
	* java/util/BasicMapEntry: Improve javadoc.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@48035 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 595 insertions, 214 deletions

diff --git a/libjava/java/util/AbstractList.java b/libjava/java/util/AbstractList.java
index ba589e335e7..714f92a7bc4 100644
--- a/libjava/java/util/AbstractList.java
+++ b/libjava/java/util/AbstractList.java
@@ -1,5 +1,5 @@
 /* AbstractList.java -- Abstract implementation of most of List
-   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -25,67 +25,192 @@ This exception does not however invalidate any other reasons why the
 executable file might be covered by the GNU General Public License. */
 
 
-// TO DO:
-// ~ Doc comments for almost everything.
-// ~ Better general commenting
-
 package java.util;
 
 /**
  * A basic implementation of most of the methods in the List interface to make
- * it easier to create a List based on a random-access data structure. To
- * create an unmodifiable list, it is only necessary to override the size() and
- * get(int) methods (this contrasts with all other abstract collection classes
- * which require an iterator to be provided). To make the list modifiable, the
- * set(int, Object)  method should also be overridden, and to make the list
- * resizable, the add(int, Object) and remove(int) methods should be overridden
- * too. Other methods should be overridden if the backing data structure allows
- * for a more efficient implementation. The precise implementation used by
- * AbstractList is documented, so that subclasses can tell which methods could
- * be implemented more efficiently.
+ * it easier to create a List based on a random-access data structure. If
+ * the list is sequential (such as a linked list), use AbstractSequentialList.
+ * To create an unmodifiable list, it is only necessary to override the
+ * size() and get(int) methods (this contrasts with all other abstract
+ * collection classes which require an iterator to be provided). To make the
+ * list modifiable, the set(int, Object) method should also be overridden, and
+ * to make the list resizable, the add(int, Object) and remove(int) methods
+ * should be overridden too. Other methods should be overridden if the
+ * backing data structure allows for a more efficient implementation.
+ * The precise implementation used by AbstractList is documented, so that
+ * subclasses can tell which methods could be implemented more efficiently.
+ * <p>
+ *
+ * As recommended by Collection and List, the subclass should provide at
+ * least a no-argument and a Collection constructor. This class is not
+ * synchronized.
+ *
+ * @author Original author unknown
+ * @author Bryce McKinlay
+ * @author Eric Blake <ebb9@email.byu.edu>
+ * @see Collection
+ * @see List
+ * @see AbstractSequentialList
+ * @see AbstractCollection
+ * @see ListIterator
+ * @since 1.2
+ * @status updated to 1.4
  */
 public abstract class AbstractList extends AbstractCollection implements List
 {
   /**
    * A count of the number of structural modifications that have been made to
-   * the list (that is, insertions and removals).
+   * the list (that is, insertions and removals). Structural modifications
+   * are ones which change the list size or affect how iterations would
+   * behave. This field is available for use by Iterator and ListIterator,
+   * in order to throw a {@link ConcurrentModificationException} in response
+   * to the next operation on the iterator. This <i>fail-fast</i> behavior
+   * saves the user from many subtle bugs otherwise possible from concurrent
+   * modification during iteration.
+   * <p>
+   *
+   * To make lists fail-fast, increment this field by just 1 in the
+   * <code>add(int, Object)</code> and <code>remove(int)</code> methods.
+   * Otherwise, this field may be ignored.
+   */
+  protected int modCount;
+
+  /**
+   * The main constructor, for use by subclasses.
    */
-  protected transient int modCount = 0;
+  protected AbstractList()
+  {
+  }
 
+  /**
+   * Returns the elements at the specified position in the list.
+   *
+   * @param index the element to return
+   * @return the element at that position
+   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
+   */
   public abstract Object get(int index);
 
+  /**
+   * Insert an element into the list at a given position (optional operation).
+   * This shifts all existing elements from that position to the end one
+   * index to the right.  This version of add has no return, since it is
+   * assumed to always succeed if there is no exception. This implementation
+   * always throws UnsupportedOperationException, and must be overridden to
+   * make a modifiable List.  If you want fail-fast iterators, be sure to
+   * increment modCount when overriding this.
+   *
+   * @param index the location to insert the item
+   * @param o the object to insert
+   * @throws UnsupportedOperationException if this list does not support the
+   *         add operation
+   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
+   * @throws ClassCastException if o cannot be added to this list due to its
+   *         type
+   * @throws IllegalArgumentException if o cannot be added to this list for
+   *         some other reason
+   * @see #modCount
+   */
   public void add(int index, Object o)
   {
     throw new UnsupportedOperationException();
   }
 
+  /**
+   * Add an element to the end of the list (optional operation). If the list
+   * imposes restraints on what can be inserted, such as no null elements,
+   * this should be documented. This implementation calls
+   * <code>add(size(), o);</code>, and will fail if that version does.
+   *
+   * @param o the object to add
+   * @return true, as defined by Collection for a modified list
+   * @throws UnsupportedOperationException if this list does not support the
+   *         add operation
+   * @throws ClassCastException if o cannot be added to this list due to its
+   *         type
+   * @throws IllegalArgumentException if o cannot be added to this list for
+   *         some other reason
+   * @see #add(int, Object)
+   */
   public boolean add(Object o)
   {
     add(size(), o);
     return true;
   }
 
+  /**
+   * Insert the contents of a collection into the list at a given position
+   * (optional operation). Shift all elements at that position to the right
+   * by the number of elements inserted. This operation is undefined if
+   * this list is modified during the operation (for example, if you try
+   * to insert a list into itself). This implementation uses the iterator of
+   * the collection, repeatedly calling add(int, Object); this will fail
+   * if add does. This can often be made more efficient.
+   *
+   * @param index the location to insert the collection
+   * @param c the collection to insert
+   * @return true if the list was modified by this action, that is, if c is
+   *         non-empty
+   * @throws UnsupportedOperationException if this list does not support the
+   *         addAll operation
+   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
+   * @throws ClassCastException if some element of c cannot be added to this
+   *         list due to its type
+   * @throws IllegalArgumentException if some element of c cannot be added
+   *         to this list for some other reason
+   * @throws NullPointerException if the specified collection is null
+   * @see #add(int, Object)
+   */
   public boolean addAll(int index, Collection c)
   {
     Iterator itr = c.iterator();
     int size = c.size();
-    for (int pos = 0; pos < size; pos++)
-      {
-	add(index++, itr.next());
-      }
-    return (size > 0);
+    for (int pos = size; pos > 0; pos--)
+      add(index++, itr.next());
+    return size > 0;
   }
 
+  /**
+   * Clear the list, such that a subsequent call to isEmpty() would return
+   * true (optional operation). This implementation calls
+   * <code>removeRange(0, size())</code>, so it will fail unless remove
+   * or removeRange is overridden.
+   *
+   * @throws UnsupportedOperationException if this list does not support the
+   *         clear operation
+   * @see #remove(int)
+   * @see #removeRange(int, int)
+   */
   public void clear()
   {
     removeRange(0, size());
   }
 
+  /**
+   * Test whether this list is equal to another object. A List is defined to be
+   * equal to an object if and only if that object is also a List, and the two
+   * lists have the same sequence. Two lists l1 and l2 are equal if and only
+   * if <code>l1.size() == l2.size()</code>, and for every integer n between 0
+   * and <code>l1.size() - 1</code> inclusive, <code>l1.get(n) == null ?
+   * l2.get(n) == null : l1.get(n).equals(l2.get(n))</code>.
+   * <p>
+   *
+   * This implementation returns true if the object is this, or false if the
+   * object is not a List.  Otherwise, it iterates over both lists (with
+   * iterator()), returning false if two elements compare false or one list
+   * is shorter, and true if the iteration completes successfully.
+   *
+   * @param o the object to test for equality with this list
+   * @return true if o is equal to this list
+   * @see Object#equals(Object)
+   * @see #hashCode()
+   */
   public boolean equals(Object o)
   {
     if (o == this)
       return true;
-    if (!(o instanceof List))
+    if (! (o instanceof List))
       return false;
     int size = size();
     if (size != ((List) o).size())
@@ -94,77 +219,272 @@ public abstract class AbstractList extends AbstractCollection implements List
     Iterator itr1 = iterator();
     Iterator itr2 = ((List) o).iterator();
 
-    for (int pos = 0; pos < size; pos++)
-      {
-	Object e = itr1.next();
-	if (e == null ? itr2.next() != null : !e.equals(itr2.next()))
-	  return false;
-      }
+    while (--size >= 0)
+      if (! equals(itr1.next(), itr2.next()))
+        return false;
     return true;
   }
 
+  /**
+   * Obtain a hash code for this list. In order to obey the general contract of
+   * the hashCode method of class Object, this value is calculated as follows:
+   * <pre>
+   *   hashCode = 1;
+   *   Iterator i = list.iterator();
+   *   while (i.hasNext())
+   *     {
+   *       Object obj = i.next();
+   *       hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
+   *     }
+   * </pre>
+   * This ensures that the general contract of Object.hashCode() is adhered to.
+   *
+   * @return the hash code of this list
+   * @see Object#hashCode()
+   * @see #equals(Object)
+   */
   public int hashCode()
   {
     int hashCode = 1;
     Iterator itr = iterator();
-    int size = size();
-    for (int pos = 0; pos < size; pos++)
-      {
-	Object obj = itr.next();
-	hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
-      }
+    int pos = size();
+    while (--pos >= 0)
+      hashCode = 31 * hashCode + hashCode(itr.next());
     return hashCode;
   }
 
+  /**
+   * Obtain the first index at which a given object is to be found in this
+   * list. This implementation follows a listIterator() until a match is found,
+   * or returns -1 if the list end is reached.
+   *
+   * @param o the object to search for
+   * @return the least integer n such that <code>o == null ? get(n) == null :
+   *         o.equals(get(n))</code>, or -1 if there is no such index
+   */
   public int indexOf(Object o)
   {
-    ListIterator itr = listIterator(0);
+    ListIterator itr = listIterator();
     int size = size();
     for (int pos = 0; pos < size; pos++)
-      {
-	if (o == null ? itr.next() == null : o.equals(itr.next()))
-	  return pos;
-      }
+      if (equals(o, itr.next()))
+        return pos;
     return -1;
   }
 
+  /**
+   * Obtain an Iterator over this list, whose sequence is the list order.
+   * This implementation uses size(), get(int), and remove(int) of the
+   * backing list, and does not support remove unless the list does. This
+   * implementation is fail-fast if you correctly maintain modCount.
+   * Also, this implementation is specified by Sun to be distinct from
+   * listIterator, although you could easily implement it as
+   * <code>return listIterator(0)</code>.
+   *
+   * @return an Iterator over the elements of this list, in order
+   * @see #modCount
+   */
   public Iterator iterator()
   {
-    return new AbstractListItr(0);
+    // Bah, Sun's implementation forbids using listIterator(0).
+    return new Iterator()
+    {
+      private int pos = 0;
+      private int size = size();
+      private int last = -1;
+      private int knownMod = modCount;
+
+      // This will get inlined, since it is private.
+      private void checkMod()
+      {
+        if (knownMod != modCount)
+          throw new ConcurrentModificationException();
+      }
+
+      public boolean hasNext()
+      {
+        checkMod();
+        return pos < size;
+      }
+
+      public Object next()
+      {
+        checkMod();
+        if (pos == size)
+          throw new NoSuchElementException();
+        last = pos;
+        return get(pos++);
+      }
+
+      public void remove()
+      {
+        checkMod();
+        if (last < 0)
+          throw new IllegalStateException();
+        AbstractList.this.remove(last);
+        pos--;
+        size--;
+        last = -1;
+        knownMod = modCount;
+      }
+    };
   }
 
+  /**
+   * Obtain the last index at which a given object is to be found in this
+   * list. This implementation grabs listIterator(size()), then searches
+   * backwards for a match or returns -1.
+   *
+   * @return the greatest integer n such that <code>o == null ? get(n) == null
+   *         : o.equals(get(n))</code>, or -1 if there is no such index
+   */
   public int lastIndexOf(Object o)
   {
-    int size = size();
-    ListIterator itr = listIterator(size);
-    for (int pos = size; pos > 0; pos--)
-      {
-	if (o == null ? itr.previous() == null : o.equals(itr.previous()))
-	  return pos - 1;
-      }
+    int pos = size();
+    ListIterator itr = listIterator(pos);
+    while (--pos >= 0)
+      if (equals(o, itr.previous()))
+        return pos;
     return -1;
   }
 
   /**
-   * Return an Iterator over this List. This implementation calls
-   * listIterator(0).
+   * Obtain a ListIterator over this list, starting at the beginning. This
+   * implementation returns listIterator(0).
    *
-   * @return an Iterator over this List
+   * @return a ListIterator over the elements of this list, in order, starting
+   *         at the beginning
    */
   public ListIterator listIterator()
   {
     return listIterator(0);
   }
 
-  public ListIterator listIterator(int index)
+  /**
+   * Obtain a ListIterator over this list, starting at a given position.
+   * A first call to next() would return the same as get(index), and a
+   * first call to previous() would return the same as get(index - 1).
+   * <p>
+   *
+   * This implementation uses size(), get(int), set(int, Object),
+   * add(int, Object), and remove(int) of the backing list, and does not
+   * support remove, set, or add unless the list does. This implementation
+   * is fail-fast if you correctly maintain modCount.
+   *
+   * @param index the position, between 0 and size() inclusive, to begin the
+   *        iteration from
+   * @return a ListIterator over the elements of this list, in order, starting
+   *         at index
+   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
+   * @see #modCount
+   */
+  public ListIterator listIterator(final int index)
   {
     if (index < 0 || index > size())
-      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
-                                          size());
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
+                                          + size());
 
-    return new AbstractListItr(index);
+    return new ListIterator()
+    {
+      private int knownMod = modCount;
+      private int position = index;
+      private int lastReturned = -1;
+      private int size = size();
+
+      // This will get inlined, since it is private.
+      private void checkMod()
+      {
+        if (knownMod != modCount)
+          throw new ConcurrentModificationException();
+      }
+
+      public boolean hasNext()
+      {
+        checkMod();
+        return position < size;
+      }
+
+      public boolean hasPrevious()
+      {
+        checkMod();
+        return position > 0;
+      }
+
+      public Object next()
+      {
+        checkMod();
+        if (position == size)
+          throw new NoSuchElementException();
+        lastReturned = position;
+        return get(position++);
+      }
+
+      public Object previous()
+      {
+        checkMod();
+        if (position == 0)
+          throw new NoSuchElementException();
+        lastReturned = --position;
+        return get(lastReturned);
+      }
+
+      public int nextIndex()
+      {
+        checkMod();
+        return position;
+      }
+
+      public int previousIndex()
+      {
+        checkMod();
+        return position - 1;
+      }
+
+      public void remove()
+      {
+        checkMod();
+        if (lastReturned < 0)
+          throw new IllegalStateException();
+        AbstractList.this.remove(lastReturned);
+        size--;
+        position = lastReturned;
+        lastReturned = -1;
+        knownMod = modCount;
+      }
+
+      public void set(Object o)
+      {
+        checkMod();
+        if (lastReturned < 0)
+          throw new IllegalStateException();
+        AbstractList.this.set(lastReturned, o);
+      }
+
+      public void add(Object o)
+      {
+        checkMod();
+        AbstractList.this.add(position++, o);
+        size++;
+        lastReturned = -1;
+        knownMod = modCount;
+      }
+    };
   }
 
+  /**
+   * Remove the element at a given position in this list (optional operation).
+   * Shifts all remaining elements to the left to fill the gap. This
+   * implementation always throws an UnsupportedOperationException.
+   * If you want fail-fast iterators, be sure to increment modCount when
+   * overriding this.
+   *
+   * @param index the position within the list of the object to remove
+   * @return the object that was removed
+   * @throws UnsupportedOperationException if this list does not support the
+   *         remove operation
+   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
+   * @see #modCount
+   */
   public Object remove(int index)
   {
     throw new UnsupportedOperationException();
@@ -175,8 +495,10 @@ public abstract class AbstractList extends AbstractCollection implements List
    * removeRange methods of the class which implements subList, which are
    * difficult for subclasses to override directly. Therefore, this method
    * should be overridden instead by the more efficient implementation, if one
-   * exists.
+   * exists. Overriding this can reduce quadratic efforts to constant time
+   * in some cases!
    * <p>
+   *
    * This implementation first checks for illegal or out of range arguments. It
    * then obtains a ListIterator over the list using listIterator(fromIndex).
    * It then calls next() and remove() on this iterator repeatedly, toIndex -
@@ -190,152 +512,131 @@ public abstract class AbstractList extends AbstractCollection implements List
     ListIterator itr = listIterator(fromIndex);
     for (int index = fromIndex; index < toIndex; index++)
       {
-	itr.next();
-	itr.remove();
+        itr.next();
+        itr.remove();
       }
   }
 
+  /**
+   * Replace an element of this list with another object (optional operation).
+   * This implementation always throws an UnsupportedOperationException.
+   *
+   * @param index the position within this list of the element to be replaced
+   * @param o the object to replace it with
+   * @return the object that was replaced
+   * @throws UnsupportedOperationException if this list does not support the
+   *         set operation
+   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
+   * @throws ClassCastException if o cannot be added to this list due to its
+   *         type
+   * @throws IllegalArgumentException if o cannot be added to this list for
+   *         some other reason
+   */
   public Object set(int index, Object o)
   {
     throw new UnsupportedOperationException();
   }
 
+  /**
+   * Obtain a List view of a subsection of this list, from fromIndex
+   * (inclusive) to toIndex (exclusive). If the two indices are equal, the
+   * sublist is empty. The returned list should be modifiable if and only
+   * if this list is modifiable. Changes to the returned list should be
+   * reflected in this list. If this list is structurally modified in
+   * any way other than through the returned list, the result of any subsequent
+   * operations on the returned list is undefined.
+   * <p>
+   *
+   * This implementation returns a subclass of AbstractList. It stores, in
+   * private fields, the offset and size of the sublist, and the expected
+   * modCount of the backing list. If the backing list implements RandomAccess,
+   * the sublist will also.
+   * <p>
+   *
+   * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
+   * <code>add(int, Object)</code>, <code>remove(int)</code>,
+   * <code>addAll(int, Collection)</code> and
+   * <code>removeRange(int, int)</code> methods all delegate to the
+   * corresponding methods on the backing abstract list, after
+   * bounds-checking the index and adjusting for the offset. The
+   * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
+   * The <code>listIterator(int)</code> method returns a "wrapper object"
+   * over a list iterator on the backing list, which is created with the
+   * corresponding method on the backing list. The <code>iterator()</code>
+   * method merely returns listIterator(), and the <code>size()</code> method
+   * merely returns the subclass's size field.
+   * <p>
+   *
+   * All methods first check to see if the actual modCount of the backing
+   * list is equal to its expected value, and throw a
+   * ConcurrentModificationException if it is not. 
+   *
+   * @param fromIndex the index that the returned list should start from
+   *        (inclusive)
+   * @param toIndex the index that the returned list should go to (exclusive)
+   * @return a List backed by a subsection of this list
+   * @throws IndexOutOfBoundsException if fromIndex &lt; 0
+   *         || toIndex &gt; size()
+   * @throws IllegalArgumentException if fromIndex &gt; toIndex
+   * @see ConcurrentModificationException
+   * @see RandomAccess
+   */
   public List subList(int fromIndex, int toIndex)
   {
+    // This follows the specification of AbstractList, but is inconsistent
+    // with the one in List. Don't you love Sun's inconsistencies?
     if (fromIndex > toIndex)
       throw new IllegalArgumentException(fromIndex + " > " + toIndex);
     if (fromIndex < 0 || toIndex > size())
       throw new IndexOutOfBoundsException();
 
+    if (this instanceof RandomAccess)
+      return new RandomAccessSubList(this, fromIndex, toIndex);
     return new SubList(this, fromIndex, toIndex);
   }
 
-  class AbstractListItr implements ListIterator
-  {
-    private int knownMod = modCount;
-    private int position;
-    private int lastReturned = -1;
-    private int size = size();
-
-    AbstractListItr(int start_pos)
-    {
-      this.position = start_pos;
-    }
-
-    private void checkMod()
-    {
-      if (knownMod != modCount)
-	throw new ConcurrentModificationException();
-    }
-
-    public boolean hasNext()
-    {
-      checkMod();
-      return position < size;
-    }
-
-    public boolean hasPrevious()
-    {
-      checkMod();
-      return position > 0;
-    }
-
-    public Object next()
-    {
-      checkMod();
-      if (position < size)
-	{
-	  lastReturned = position++;
-	  return get(lastReturned);
-	}
-      else
-	{
-	  throw new NoSuchElementException();
-	}
-    }
-
-    public Object previous()
-    {
-      checkMod();
-      if (position > 0)
-	{
-	  lastReturned = --position;
-	  return get(lastReturned);
-	}
-      else
-	{
-	  throw new NoSuchElementException();
-	}
-    }
-
-    public int nextIndex()
-    {
-      checkMod();
-      return position;
-    }
-
-    public int previousIndex()
-    {
-      checkMod();
-      return position - 1;
-    }
-
-    public void remove()
-    {
-      checkMod();
-      if (lastReturned < 0)
-	{
-	  throw new IllegalStateException();
-	}
-      AbstractList.this.remove(lastReturned);
-      knownMod++;
-      position = lastReturned;
-      lastReturned = -1;
-    }
-
-    public void set(Object o)
-    {
-      checkMod();
-      if (lastReturned < 0)
-	throw new IllegalStateException();
-      AbstractList.this.set(lastReturned, o);
-    }
-
-    public void add(Object o)
-    {
-      checkMod();
-      AbstractList.this.add(position++, o);
-      lastReturned = -1;
-      knownMod++;
-    }
-  }				// AbstractList.Iterator
-}
-
+} // class AbstractList
 
 
+/**
+ * This class follows the implementation requirements set forth in
+ * {@link AbstractList#subList(int, int)}. Some compilers have problems
+ * with AbstractList.this.modCount if this class is nested in AbstractList,
+ * even though the JLS defines that to be legal, so we make it a top-level
+ * class.
+ *
+ * @author Original author unknown
+ * @author Eric Blake <ebb9@email.byu.edu>
+ */
 class SubList extends AbstractList
 {
-  private AbstractList backingList;
-  private int offset;
+  private final AbstractList backingList;
+  private final int offset;
   private int size;
 
-  public SubList(AbstractList backing, int fromIndex, int toIndex)
+  /**
+   * Construct the sublist.
+   *
+   * @param backing the list this comes from
+   * @param fromIndex the lower bound, inclusive
+   * @param toIndex the upper bound, exclusive
+   */
+  SubList(AbstractList backing, int fromIndex, int toIndex)
   {
     backingList = backing;
-    modCount = backingList.modCount;
+    modCount = backing.modCount;
     offset = fromIndex;
     size = toIndex - fromIndex;
   }
 
   /**
    * This method checks the two modCount fields to ensure that there has
-   * not been a concurrent modification. It throws an exception if there
-   * has been, and otherwise returns normally.
-   * Note that since this method is private, it will be inlined.
+   * not been a concurrent modification, returning if all is okay.
    *
-   * @exception ConcurrentModificationException if there has been a
-   *   concurrent modification.
+   * @throws ConcurrentModificationException if the backing list has been
+   *         modified externally to this sublist
    */
+  // This will get inlined, since it is private.
   private void checkMod()
   {
     if (modCount != backingList.modCount)
@@ -345,45 +646,64 @@ class SubList extends AbstractList
   /**
    * This method checks that a value is between 0 and size (inclusive). If
    * it is not, an exception is thrown.
-   * Note that since this method is private, it will be inlined.
    *
-   * @exception IndexOutOfBoundsException if the value is out of range.
+   * @param index the value to check
+   * @throws IndexOutOfBoundsException if the value is out of range
    */
+  // This will get inlined, since it is private.
   private void checkBoundsInclusive(int index)
   {
     if (index < 0 || index > size)
-      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
-                                          size);
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
+                                          + size);
   }
 
   /**
    * This method checks that a value is between 0 (inclusive) and size
    * (exclusive). If it is not, an exception is thrown.
-   * Note that since this method is private, it will be inlined.
    *
-   * @exception IndexOutOfBoundsException if the value is out of range.
+   * @param index the value to check
+   * @throws IndexOutOfBoundsException if the value is out of range
    */
+  // This will get inlined, since it is private.
   private void checkBoundsExclusive(int index)
   {
     if (index < 0 || index >= size)
-      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
-                                          size);
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
+                                          + size);
   }
 
+  /**
+   * Specified by AbstractList.subList to return the private field size.
+   *
+   * @return the sublist size
+   */
   public int size()
   {
     checkMod();
     return size;
   }
 
+  /**
+   * Specified by AbstractList.subList to delegate to the backing list.
+   *
+   * @param index the location to modify
+   * @param o the new value
+   * @return the old value
+   */
   public Object set(int index, Object o)
   {
     checkMod();
     checkBoundsExclusive(index);
-    o = backingList.set(index + offset, o);
-    return o;
+    return backingList.set(index + offset, o);
   }
 
+  /**
+   * Specified by AbstractList.subList to delegate to the backing list.
+   *
+   * @param index the location to get from
+   * @return the object at that location
+   */
   public Object get(int index)
   {
     checkMod();
@@ -391,62 +711,109 @@ class SubList extends AbstractList
     return backingList.get(index + offset);
   }
 
+  /**
+   * Specified by AbstractList.subList to delegate to the backing list.
+   *
+   * @param index the index to insert at
+   * @param o the object to add
+   */
   public void add(int index, Object o)
   {
     checkMod();
     checkBoundsInclusive(index);
     backingList.add(index + offset, o);
-    this.modCount++;
     size++;
+    modCount = backingList.modCount;
   }
 
+  /**
+   * Specified by AbstractList.subList to delegate to the backing list.
+   *
+   * @param index the index to remove
+   * @return the removed object
+   */
   public Object remove(int index)
   {
     checkMod();
     checkBoundsExclusive(index);
     Object o = backingList.remove(index + offset);
-    this.modCount++;
     size--;
+    modCount = backingList.modCount;
     return o;
   }
 
-  public void removeRange(int fromIndex, int toIndex)
+  /**
+   * Specified by AbstractList.subList to delegate to the backing list.
+   * This does no bounds checking, as it assumes it will only be called
+   * by trusted code like clear() which has already checked the bounds.
+   *
+   * @param fromIndex the lower bound, inclusive
+   * @param toIndex the upper bound, exclusive
+   */
+  protected void removeRange(int fromIndex, int toIndex)
   {
     checkMod();
-    checkBoundsExclusive(fromIndex);
-    checkBoundsInclusive(toIndex);
 
-    // this call will catch the toIndex < fromIndex condition
     backingList.removeRange(offset + fromIndex, offset + toIndex);
-    this.modCount = backingList.modCount;
     size -= toIndex - fromIndex;
+    modCount = backingList.modCount;
   }
 
+  /**
+   * Specified by AbstractList.subList to delegate to the backing list.
+   *
+   * @param index the location to insert at
+   * @param c the collection to insert
+   * @return true if this list was modified, in other words, c is non-empty
+   */
   public boolean addAll(int index, Collection c)
   {
     checkMod();
     checkBoundsInclusive(index);
     int csize = c.size();
     boolean result = backingList.addAll(offset + index, c);
-    this.modCount = backingList.modCount;
     size += csize;
+    modCount = backingList.modCount;
     return result;
   }
 
+  /**
+   * Specified by AbstractList.subList to return addAll(size, c).
+   *
+   * @param c the collection to insert
+   * @return true if this list was modified, in other words, c is non-empty
+   */
+  public boolean addAll(Collection c)
+  {
+    return addAll(size, c);
+  }
+
+  /**
+   * Specified by AbstractList.subList to return listIterator().
+   *
+   * @return an iterator over the sublist
+   */
   public Iterator iterator()
   {
-    return listIterator(0);
+    return listIterator();
   }
 
+  /**
+   * Specified by AbstractList.subList to return a wrapper around the
+   * backing list's iterator.
+   *
+   * @param index the start location of the iterator
+   * @return a list iterator over the sublist
+   */
   public ListIterator listIterator(final int index)
-  {      
+  {
     checkMod();
     checkBoundsInclusive(index);
 
-    return new ListIterator() 
+    return new ListIterator()
     {
-      ListIterator i = backingList.listIterator(index + offset);
-      int position = index;
+      private final ListIterator i = backingList.listIterator(index + offset);
+      private int position = index;
 
       public boolean hasNext()
       {
@@ -462,44 +829,36 @@ class SubList extends AbstractList
 
       public Object next()
       {
-        if (position < size)
-	  {
-            Object o = i.next();
-            position++;
-            return o;
-          }
-	else
+        if (position == size)
           throw new NoSuchElementException();
+        position++;
+        return i.next();
       }
 
       public Object previous()
       {
-        if (position > 0)
-	  {
-            Object o = i.previous();
-            position--;
-            return o;
-          }
-	else
+        if (position == 0)
           throw new NoSuchElementException();
+        position--;
+        return i.previous();
       }
 
       public int nextIndex()
       {
-        return offset + i.nextIndex();
+        return i.nextIndex() - offset;
       }
 
       public int previousIndex()
       {
-        return offset + i.previousIndex();
+        return i.previousIndex() - offset;
       }
 
       public void remove()
       {
         i.remove();
-	modCount++;
         size--;
         position = nextIndex();
+        modCount = backingList.modCount;
       }
 
       public void set(Object o)
@@ -510,14 +869,14 @@ class SubList extends AbstractList
       public void add(Object o)
       {
         i.add(o);
-	modCount++;
         size++;
         position++;
+        modCount = backingList.modCount;
       }
 
       // Here is the reason why the various modCount fields are mostly
       // ignored in this wrapper listIterator.
-      // IF the backing listIterator is failfast, then the following holds:
+      // If the backing listIterator is failfast, then the following holds:
       //   Using any other method on this list will call a corresponding
       //   method on the backing list *after* the backing listIterator
       //   is created, which will in turn cause a ConcurrentModException
@@ -530,9 +889,31 @@ class SubList extends AbstractList
       //   only, but somewhat pointless when the list can be changed under
       //   us.
       // Either way, no explicit handling of modCount is needed.
-      // However modCount++ must be executed in add and remove, and size
-      // must also be updated in these two methods, since they do not go
-      // through the corresponding methods of the subList.
+      // However modCount = backingList.modCount must be executed in add
+      // and remove, and size must also be updated in these two methods,
+      // since they do not go through the corresponding methods of the subList.
     };
   }
-}  // SubList
+} // class SubList
+
+/**
+ * This class is a RandomAccess version of SubList, as required by
+ * {@link AbstractList#subList(int, int)}.
+ *
+ * @author Eric Blake <ebb9@email.byu.edu>
+ */
+final class RandomAccessSubList extends SubList
+  implements RandomAccess
+{
+  /**
+   * Construct the sublist.
+   *
+   * @param backing the list this comes from
+   * @param fromIndex the lower bound, inclusive
+   * @param toIndex the upper bound, exclusive
+   */
+  RandomAccessSubList(AbstractList backing, int fromIndex, int toIndex)
+  {
+    super(backing, fromIndex, toIndex);
+  }
+} // class RandomAccessSubList