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, 134 insertions, 42 deletions

diff --git a/libjava/java/util/AbstractSequentialList.java b/libjava/java/util/AbstractSequentialList.java
index 81481be0466..2267b02e523 100644
--- a/libjava/java/util/AbstractSequentialList.java
+++ b/libjava/java/util/AbstractSequentialList.java
@@ -1,5 +1,5 @@
 /* AbstractSequentialList.java -- List implementation for sequential access
-   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,100 +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:
-// ~ Lots of doc comments still missing.
-// ~ The class comment should include a description of what should be overridden
-//   to provide what features, as should the listIterator comment.
-
 package java.util;
 
 /**
  * Abstract superclass to make it easier to implement the List interface when
- * backed by a sequential-access store, such as a linked list.
+ * backed by a sequential-access store, such as a linked list. For random
+ * access data, use AbstractList. This class implements the random access
+ * methods (<code>get</code>, <code>set</code>, <code>add</code>, and
+ * <code>remove</code>) atop the list iterator, opposite of AbstractList's
+ * approach of implementing the iterator atop random access.
+ * <p>
+ *
+ * To implement a list, you need an implementation for <code>size()</code>
+ * and <code>listIterator</code>.  With just <code>hasNext</code>,
+ * <code>next</code>, <code>hasPrevious</code>, <code>previous</code>,
+ * <code>nextIndex</code>, and <code>previousIndex</code>, you have an
+ * unmodifiable list. For a modifiable one, add <code>set</code>, and for
+ * a variable-size list, add <code>add</code> and <code>remove</code>.
+ * <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 List
+ * @see AbstractList
+ * @see AbstractCollection
+ * @see ListIterator
+ * @see LinkedList
+ * @since 1.2
+ * @status updated to 1.4
  */
 public abstract class AbstractSequentialList extends AbstractList
 {
   /**
+   * The main constructor, for use by subclasses.
+   */
+  protected AbstractSequentialList()
+  {
+  }
+
+  /**
    * Returns a ListIterator over the list, starting from position index.
    * Subclasses must provide an implementation of this method.
    *
-   * @exception IndexOutOfBoundsException if index < 0 || index > size()
+   * @param index the starting position of the list
+   * @return the list iterator
+   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
    */
   public abstract ListIterator listIterator(int index);
 
   /**
-   * Add an element to the list at a given index. This implementation obtains a
-   * ListIterator positioned at the specified index, and then adds the element
-   * using the ListIterator's add method.
+   * 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 iteration
+   * uses listIterator(index).add(o).
    *
-   * @param index the position to add the element
-   * @param o the element to insert
-   * @exception IndexOutOfBoundsException if index < 0 || index > size()
-   * @exception UnsupportedOperationException if the iterator returned by
-   *   listIterator(index) does not support the add method.
+   * @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
    */
   public void add(int index, Object o)
   {
-    ListIterator i = listIterator(index);
-    i.add(o);
+    listIterator(index).add(o);
   }
 
   /**
-   * @specnote The spec in the JDK1.3 online docs is wrong. The implementation
-   *           should not call next() to skip over new elements as they are
-   *           added, because iterator.add() should add new elements BEFORE
-   *           the cursor.
+   * 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).
+   * <p>
+   *
+   * This implementation grabs listIterator(index), then proceeds to use add
+   * for each element returned by c's iterator. Sun's online specs are wrong,
+   * claiming that this also calls next(): listIterator.add() correctly
+   * skips the added element.
+   *
+   * @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)
   {
-    boolean modified = false;
     Iterator ci = c.iterator();
     int size = c.size();
     ListIterator i = listIterator(index);
-    for (int pos = 0; pos < size; pos++)
-      {
-	i.add(ci.next());
-      }
-    return (size > 0);
+    for (int pos = size; pos > 0; pos--)
+      i.add(ci.next());
+    return size > 0;
   }
 
+  /**
+   * Get the element at a given index in this list. This implementation
+   * returns listIterator(index).next().
+   *
+   * @param index the index of the element to be returned
+   * @return the element at index index in this list
+   * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
+   */
   public Object get(int index)
   {
-    ListIterator i = listIterator(index);
-    if (index < 0 || index > size())
-      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
-                                          size());
-    return i.next();
+    // This is a legal listIterator position, but an illegal get.
+    if (index == size())
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
+                                          + size());
+    return listIterator(index).next();
   }
 
   /**
-   * Return an Iterator over this List. This implementation returns
-   * listIterator().
+   * Obtain an Iterator over this list, whose sequence is the list order. This
+   * implementation returns listIterator().
    *
-   * @return an Iterator over this List
+   * @return an Iterator over the elements of this list, in order
    */
   public Iterator iterator()
   {
     return listIterator();
   }
 
+  /**
+   * 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 uses listIterator(index) and ListIterator.remove().
+   *
+   * @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()
+   */
   public Object remove(int index)
   {
+    // This is a legal listIterator position, but an illegal remove.
+    if (index == size())
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
+                                          + size());
     ListIterator i = listIterator(index);
-    if (index < 0 || index > size())
-      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
-                                          size());
     Object removed = i.next();
     i.remove();
     return removed;
   }
 
+  /**
+   * Replace an element of this list with another object (optional operation).
+   * This implementation uses listIterator(index) and ListIterator.set(o).
+   *
+   * @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)
   {
+    // This is a legal listIterator position, but an illegal set.
+    if (index == size())
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
+                                          + size());
     ListIterator i = listIterator(index);
-    if (index < 0 || index > size())
-      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
-                                          size());
     Object old = i.next();
     i.set(o);
     return old;