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.

From-SVN: r48035

1 files changed, 224 insertions, 118 deletions

diff --git a/libjava/java/util/AbstractCollection.java b/libjava/java/util/AbstractCollection.java
index 1bb73d7..095e1c4 100644
--- a/libjava/java/util/AbstractCollection.java
+++ b/libjava/java/util/AbstractCollection.java
@@ -1,5 +1,5 @@
 /* AbstractCollection.java -- Abstract implementation of most of Collection
-   Copyright (C) 1998, 2000 Free Software Foundation, Inc.
+   Copyright (C) 1998, 2000, 2001 Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -42,77 +42,119 @@ import java.lang.reflect.Array;
  * backing data structure allows for a more efficient implementation. The
  * precise implementation used by AbstractCollection is documented, so that
  * subclasses can tell which methods could be implemented more efficiently.
+ * <p>
+ *
+ * The programmer should provide a no-argument constructor, and one that
+ * accepts another Collection, as recommended by the Collection interface.
+ * Unfortunately, there is no way to enforce this in Java.
+ *
+ * @author Original author unknown
+ * @author Bryce McKinlay
+ * @author Eric Blake <ebb9@email.byu.edu>
+ * @see Collection
+ * @see AbstractSet
+ * @see AbstractList
+ * @since 1.2
+ * @status updated to 1.4
  */
 public abstract class AbstractCollection implements Collection
 {
   /**
+   * The main constructor, for use by subclasses.
+   */
+  protected AbstractCollection()
+  {
+  }
+
+  /**
    * Return an Iterator over this collection. The iterator must provide the
    * hasNext and next methods and should in addition provide remove if the
    * collection is modifiable.
+   *
+   * @return an iterator
    */
   public abstract Iterator iterator();
 
   /**
-   * Return the number of elements in this collection.
+   * Return the number of elements in this collection. If there are more than
+   * Integer.MAX_VALUE elements, return Integer.MAX_VALUE.
+   *
+   * @return the size
    */
   public abstract int size();
 
   /**
-   * Add an object to the collection. This implementation always throws an
-   * UnsupportedOperationException - it should be overridden if the collection
-   * is to be modifiable.
+   * Add an object to the collection (optional operation). This implementation
+   * always throws an UnsupportedOperationException - it should be
+   * overridden if the collection is to be modifiable. If the collection
+   * does not accept duplicates, simply return false. Collections may specify
+   * limitations on what may be added.
    *
    * @param o the object to add
    * @return true if the add operation caused the Collection to change
-   * @exception UnsupportedOperationException if the add operation is not
-   *   supported on this collection
+   * @throws UnsupportedOperationException if the add operation is not
+   *         supported on this collection
+   * @throws NullPointerException if the collection does not support null
+   * @throws ClassCastException if the object is of the wrong type
+   * @throws IllegalArgumentException if some aspect of the object prevents
+   *         it from being added
    */
   public boolean add(Object o)
   {
-    throw new java.lang.UnsupportedOperationException();
+    throw new UnsupportedOperationException();
   }
 
   /**
-   * Add all the elements of a given collection to this collection. This
-   * implementation obtains an Iterator over the given collection and iterates
-   * over it, adding each element with the add(Object) method (thus this method
-   * will fail with an UnsupportedOperationException if the add method does).
+   * Add all the elements of a given collection to this collection (optional
+   * operation). This implementation obtains an Iterator over the given
+   * collection and iterates over it, adding each element with the
+   * add(Object) method (thus this method will fail with an
+   * UnsupportedOperationException if the add method does). The behavior is
+   * unspecified if the specified collection is modified during the iteration,
+   * including the special case of trying addAll(this) on a non-empty
+   * collection.
    *
    * @param c the collection to add the elements of to this collection
    * @return true if the add operation caused the Collection to change
-   * @exception UnsupportedOperationException if the add operation is not
-   *   supported on this collection
+   * @throws UnsupportedOperationException if the add operation is not
+   *         supported on this collection
+   * @throws NullPointerException if this collection does not support null,
+   *         or if the specified collection is null
+   * @throws ClassCastException if an object in c is of the wrong type
+   * @throws IllegalArgumentException if some aspect of an object in c prevents
+   *         it from being added
+   * @see #add(Object)
    */
   public boolean addAll(Collection c)
   {
     Iterator itr = c.iterator();
-    int size = c.size();
     boolean modified = false;
-    for (int pos = 0; pos < size; pos++)
-      {
-	modified |= add(itr.next());
-      }
+    int pos = c.size();
+    while (--pos >= 0)
+      modified |= add(itr.next());
     return modified;
   }
 
   /**
-   * Remove all elements from the collection. This implementation obtains an
-   * iterator over the collection and calls next and remove on it repeatedly
-   * (thus this method will fail with an UnsupportedOperationException if the
-   * Iterator's remove method does) until there are no more elements to remove.
+   * Remove all elements from the collection (optional operation). This
+   * implementation obtains an iterator over the collection and calls next
+   * and remove on it repeatedly (thus this method will fail with an
+   * UnsupportedOperationException if the Iterator's remove method does)
+   * until there are no more elements to remove.
    * Many implementations will have a faster way of doing this.
    *
-   * @exception UnsupportedOperationException if the Iterator returned by
-   *   iterator does not provide an implementation of remove
+   * @throws UnsupportedOperationException if the Iterator returned by
+   *         iterator does not provide an implementation of remove
+   * @see Iterator#remove()
    */
   public void clear()
   {
     Iterator itr = iterator();
-    int size = size();
-    for (int pos = 0; pos < size; pos++)
+    int pos = size();
+    while (--pos >= 0)
       {
-	itr.next();
-	itr.remove();
+        itr.next();
+        itr.remove();
       }
   }
 
@@ -130,12 +172,10 @@ public abstract class AbstractCollection implements Collection
   public boolean contains(Object o)
   {
     Iterator itr = iterator();
-    int size = size();
-    for (int pos = 0; pos < size; pos++)
-      {
-	if (o == null ? itr.next() == null : o.equals(itr.next()))
-	  return true;
-      }
+    int pos = size();
+    while (--pos >= 0)
+      if (equals(o, itr.next()))
+        return true;
     return false;
   }
 
@@ -147,17 +187,17 @@ public abstract class AbstractCollection implements Collection
    *
    * @param c the collection to test against
    * @return true if this collection contains all the elements in the given
-   *   collection
+   *         collection
+   * @throws NullPointerException if the given collection is null
+   * @see #contains(Object)
    */
   public boolean containsAll(Collection c)
   {
     Iterator itr = c.iterator();
-    int size = c.size();
-    for (int pos = 0; pos < size; pos++)
-      {
-	if (!contains(itr.next()))
-	  return false;
-      }
+    int pos = c.size();
+    while (--pos >= 0)
+      if (!contains(itr.next()))
+        return false;
     return true;
   }
 
@@ -166,6 +206,7 @@ public abstract class AbstractCollection implements Collection
    * size() == 0.
    *
    * @return true if this collection is empty.
+   * @see #size()
    */
   public boolean isEmpty()
   {
@@ -173,92 +214,131 @@ public abstract class AbstractCollection implements Collection
   }
 
   /**
-   * Remove a single instance of an object from this collection. That is,
-   * remove one element e such that (o == null ? e == null : o.equals(e)), if
-   * such an element exists. This implementation obtains an iterator over the
-   * collection and iterates over it, testing each element for equality with
-   * the given object. If it is equal, it is removed by the iterator's remove
-   * method (thus this method will fail with an UnsupportedOperationException
-   * if the Iterator's remove method does). After the first element has been
+   * Remove a single instance of an object from this collection (optional
+   * operation). That is, remove one element e such that
+   * <code>(o == null ? e == null : o.equals(e))</code>, if such an element
+   * exists. This implementation obtains an iterator over the collection
+   * and iterates over it, testing each element for equality with the given
+   * object. If it is equal, it is removed by the iterator's remove method
+   * (thus this method will fail with an UnsupportedOperationException if
+   * the Iterator's remove method does). After the first element has been
    * removed, true is returned; if the end of the collection is reached, false
    * is returned.
    *
    * @param o the object to remove from this collection
    * @return true if the remove operation caused the Collection to change, or
-   *   equivalently if the collection did contain o.
-   * @exception UnsupportedOperationException if this collection's Iterator
-   *   does not support the remove method
+   *         equivalently if the collection did contain o.
+   * @throws UnsupportedOperationException if this collection's Iterator
+   *         does not support the remove method
+   * @see Iterator#remove()
    */
   public boolean remove(Object o)
   {
     Iterator itr = iterator();
-    int size = size();
-    for (int pos = 0; pos < size; pos++)
-      {
-	if (o == null ? itr.next() == null : o.equals(itr.next()))
-	  {
-	    itr.remove();
-	    return true;
-	  }
-      }
+    int pos = size();
+    while (--pos >= 0)
+      if (equals(o, itr.next()))
+        {
+          itr.remove();
+          return true;
+        }
     return false;
   }
 
   /**
    * Remove from this collection all its elements that are contained in a given
-   * collection. This implementation iterates over this collection, and for
-   * each element tests if it is contained in the given collection. If so, it
-   * is removed by the Iterator's remove method (thus this method will fail
-   * with an UnsupportedOperationException if the Iterator's remove method
-   * does).
+   * collection (optional operation). This implementation iterates over this
+   * collection, and for each element tests if it is contained in the given
+   * collection. If so, it is removed by the Iterator's remove method (thus
+   * this method will fail with an UnsupportedOperationException if the
+   * Iterator's remove method does).
    *
    * @param c the collection to remove the elements of
    * @return true if the remove operation caused the Collection to change
-   * @exception UnsupportedOperationException if this collection's Iterator
-   *   does not support the remove method
+   * @throws UnsupportedOperationException if this collection's Iterator
+   *         does not support the remove method
+   * @see Iterator#remove()
    */
   public boolean removeAll(Collection c)
   {
+    return removeAllInternal(c);
+  }
+
+  /**
+   * Remove from this collection all its elements that are contained in a given
+   * collection (optional operation). This implementation iterates over this
+   * collection, and for each element tests if it is contained in the given
+   * collection. If so, it is removed by the Iterator's remove method (thus
+   * this method will fail with an UnsupportedOperationException if the
+   * Iterator's remove method does). This method is necessary for ArrayList,
+   * which cannot publicly override removeAll but can optimize this call.
+   *
+   * @param c the collection to remove the elements of
+   * @return true if the remove operation caused the Collection to change
+   * @throws UnsupportedOperationException if this collection's Iterator
+   *         does not support the remove method
+   * @see Iterator#remove()
+   */
+  boolean removeAllInternal(Collection c)
+  {
     Iterator itr = iterator();
-    int size = size();
     boolean modified = false;
-    for (int pos = 0; pos < size; pos++)
-      {
-	if (c.contains(itr.next()))
-	  {
-	    itr.remove();
-	    modified = true;
-	  }
-      }
+    int pos = size();
+    while (--pos >= 0)
+      if (c.contains(itr.next()))
+        {
+          itr.remove();
+          modified = true;
+        }
     return modified;
   }
 
   /**
    * Remove from this collection all its elements that are not contained in a
-   * given collection. This implementation iterates over this collection, and
-   * for each element tests if it is contained in the given collection. If not,
-   * it is removed by the Iterator's remove method (thus this method will fail
-   * with an UnsupportedOperationException if the Iterator's remove method
-   * does).
+   * given collection (optional operation). This implementation iterates over
+   * this collection, and for each element tests if it is contained in the
+   * given collection. If not, it is removed by the Iterator's remove method
+   * (thus this method will fail with an UnsupportedOperationException if
+   * the Iterator's remove method does).
    *
    * @param c the collection to retain the elements of
    * @return true if the remove operation caused the Collection to change
-   * @exception UnsupportedOperationException if this collection's Iterator
-   *   does not support the remove method
+   * @throws UnsupportedOperationException if this collection's Iterator
+   *         does not support the remove method
+   * @see Iterator#remove()
    */
   public boolean retainAll(Collection c)
   {
+    return retainAllInternal(c);
+  }
+
+  /**
+   * Remove from this collection all its elements that are not contained in a
+   * given collection (optional operation). This implementation iterates over
+   * this collection, and for each element tests if it is contained in the
+   * given collection. If not, it is removed by the Iterator's remove method
+   * (thus this method will fail with an UnsupportedOperationException if
+   * the Iterator's remove method does). This method is necessary for
+   * ArrayList, which cannot publicly override retainAll but can optimize
+   * this call.
+   *
+   * @param c the collection to retain the elements of
+   * @return true if the remove operation caused the Collection to change
+   * @throws UnsupportedOperationException if this collection's Iterator
+   *         does not support the remove method
+   * @see Iterator#remove()
+   */
+  boolean retainAllInternal(Collection c)
+  {
     Iterator itr = iterator();
-    int size = size();
     boolean modified = false;
-    for (int pos = 0; pos < size; pos++)
-      {
-	if (!c.contains(itr.next()))
-	  {
-	    itr.remove();
-	    modified = true;
-	  }
-      }
+    int pos = size();
+    while (--pos >= 0)
+      if (!c.contains(itr.next()))
+        {
+          itr.remove();
+          modified = true;
+        }
     return modified;
   }
 
@@ -266,18 +346,18 @@ public abstract class AbstractCollection implements Collection
    * Return an array containing the elements of this collection. This
    * implementation creates an Object array of size size() and then iterates
    * over the collection, setting each element of the array from the value
-   * returned by the iterator.
+   * returned by the iterator. The returned array is safe, and is not backed
+   * by the collection.
    *
    * @return an array containing the elements of this collection
    */
   public Object[] toArray()
   {
     Iterator itr = iterator();
-    Object[]a = new Object[size()];
-    for (int pos = 0; pos < a.length; pos++)
-      {
-	a[pos] = itr.next();
-      }
+    int size = size();
+    Object[] a = new Object[size];
+    for (int pos = 0; pos < size; pos++)
+      a[pos] = itr.next();
     return a;
   }
 
@@ -293,29 +373,29 @@ public abstract class AbstractCollection implements Collection
    * obtained over the collection and the elements are placed in the array as
    * they are returned by the iterator. Finally the first spare element, if
    * any, of the array is set to null, and the created array is returned.
+   * The returned array is safe; it is not backed by the collection. Note that
+   * null may not mark the last element, if the collection allows null
+   * elements.
    *
    * @param a the array to copy into, or of the correct run-time type
    * @return the array that was produced
-   * @exception ClassCastException if the type of the array precludes holding
-   *   one of the elements of the Collection
+   * @throws NullPointerException if the given array is null
+   * @throws ArrayStoreException if the type of the array precludes holding
+   *         one of the elements of the Collection
    */
-  public Object[] toArray(Object[]a)
+  public Object[] toArray(Object[] a)
   {
     int size = size();
     if (a.length < size)
-      {
-	a = (Object[])Array.newInstance(a.getClass().getComponentType(),
-					size);
-      }
+      a = (Object[]) Array.newInstance(a.getClass().getComponentType(),
+                                       size);
+    else if (a.length > size)
+      a[size] = null;
+
     Iterator itr = iterator();
     for (int pos = 0; pos < size; pos++)
-      {
-	a[pos] = itr.next();
-      }
-    if (a.length > size)
-      {
-	a[size] = null;
-      }
+      a[pos] = itr.next();
+
     return a;
   }
 
@@ -331,15 +411,41 @@ public abstract class AbstractCollection implements Collection
   public String toString()
   {
     Iterator itr = iterator();
-    int size = size();
     StringBuffer r = new StringBuffer("[");
-    for (int pos = 0; pos < size; pos++)
+    for (int pos = size(); pos > 0; pos--)
       {
-	r.append(itr.next());
-	if (pos < size - 1)
-	  r.append(", ");
+        r.append(itr.next());
+        if (pos > 1)
+          r.append(", ");
       }
     r.append("]");
     return r.toString();
   }
+
+  /**
+   * Compare two objects according to Collection semantics.
+   *
+   * @param o1 the first object
+   * @param o2 the second object
+   * @return o1 == null ? o2 == null : o1.equals(o2)
+   */
+  // Package visible for use throughout java.util.
+  // It may be inlined since it is final.
+  static final boolean equals(Object o1, Object o2)
+  {
+    return o1 == null ? o2 == null : o1.equals(o2);
+  }
+
+  /**
+   * Hash an object according to Collection semantics.
+   *
+   * @param o the object to hash
+   * @return o1 == null ? 0 : o1.hashCode()
+   */
+  // Package visible for use throughout java.util.
+  // It may be inlined since it is final.
+  static final int hashCode(Object o)
+  {
+    return o == null ? 0 : o.hashCode();
+  }
 }