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, 138 insertions, 74 deletions

diff --git a/libjava/java/util/HashSet.java b/libjava/java/util/HashSet.java
index 2b5c31d..9d9c331 100644
--- a/libjava/java/util/HashSet.java
+++ b/libjava/java/util/HashSet.java
@@ -1,5 +1,5 @@
-/* HashSet.java -- a class providing a HashMap-backet Set
-   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+/* HashSet.java -- a class providing a HashMap-backed Set
+   Copyright (C) 1998, 1999, 2001 Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -33,87 +33,115 @@ import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 
 /**
- * This class provides a HashMap-backed implementation of the 
- * Set interface.
- *
- * Each element in the Set is a key in the backing HashMap; each key
- * maps to a static token, denoting that the key does, in fact, exist.
+ * This class provides a HashMap-backed implementation of the Set interface.
+ * <p>
  *
  * Most operations are O(1), assuming no hash collisions.  In the worst
- * case (where all hases collide), operations are O(n).
+ * case (where all hashes collide), operations are O(n). Setting the
+ * initial capacity too low will force many resizing operations, but
+ * setting the initial capacity too high (or loadfactor too low) leads
+ * to wasted memory and slower iteration.
+ * <p>
+ *
+ * HashSet accepts the null key and null values.  It is not synchronized,
+ * so if you need multi-threaded access, consider using:<br>
+ * <code>Set s = Collections.synchronizedSet(new HashSet(...));</code>
+ * <p>
  *
- * HashSet is a part of the JDK1.2 Collections API.
+ * The iterators are <i>fail-fast</i>, meaning that any structural
+ * modification, except for <code>remove()</code> called on the iterator
+ * itself, cause the iterator to throw a
+ * {@link ConcurrentModificationException} rather than exhibit
+ * non-deterministic behavior.
  *
- * @author      Jon Zeppieri
+ * @author Jon Zeppieri
+ * @author Eric Blake <ebb9@email.byu.edu>
+ * @see Collection
+ * @see Set
+ * @see TreeSet
+ * @see Collections#synchronizedSet(Set)
+ * @see HashMap
+ * @see LinkedHashSet
+ * @since 1.2
+ * @status updated to 1.4
  */
 public class HashSet extends AbstractSet
   implements Set, Cloneable, Serializable
 {
-  /** the HashMap which backs this Set */
-  transient HashMap map;
-  static final long serialVersionUID = -5024744406713321676L;
+  /**
+   * Compatible with JDK 1.2.
+   */
+  private static final long serialVersionUID = -5024744406713321676L;
 
   /**
-   * construct a new, empty HashSet whose backing HashMap has the default 
-   * capacity and loadFacor
+   * The HashMap which backs this Set.
+   */
+  private transient HashMap map;
+
+  /**
+   * Construct a new, empty HashSet whose backing HashMap has the default
+   * capacity (11) and loadFacor (0.75).
    */
   public HashSet()
   {
-    map = new HashMap();
+    this(HashMap.DEFAULT_CAPACITY, HashMap.DEFAULT_LOAD_FACTOR);
   }
 
   /**
-   * construct a new, empty HashSet whose backing HashMap has the supplied
-   * capacity and the default load factor
+   * Construct a new, empty HashSet whose backing HashMap has the supplied
+   * capacity and the default load factor (0.75).
    *
-   * @param          initialCapacity          the initial capacity of the backing
-   *                                          HashMap
+   * @param initialCapacity the initial capacity of the backing HashMap
+   * @throws IllegalArgumentException if the capacity is negative
    */
   public HashSet(int initialCapacity)
   {
-    map = new HashMap(initialCapacity);
+    this(initialCapacity, HashMap.DEFAULT_LOAD_FACTOR);
   }
 
   /**
-   * construct a new, empty HashSet whose backing HashMap has the supplied
-   * capacity and load factor
+   * Construct a new, empty HashSet whose backing HashMap has the supplied
+   * capacity and load factor.
    *
-   * @param          initialCapacity          the initial capacity of the backing
-   *                                          HashMap
-   * @param          loadFactor               the load factor of the backing HashMap
+   * @param initialCapacity the initial capacity of the backing HashMap
+   * @param loadFactor the load factor of the backing HashMap
+   * @throws IllegalArgumentException if either argument is negative, or
+   *         if loadFactor is POSITIVE_INFINITY or NaN
    */
   public HashSet(int initialCapacity, float loadFactor)
   {
-    map = new HashMap(initialCapacity, loadFactor);
+    map = init(initialCapacity, loadFactor);
   }
 
   /**
-   * construct a new HashSet with the same elements as are in the supplied
-   * collection (eliminating any duplicates, of course; the backing HashMap
-   * will have the default capacity and load factor
+   * Construct a new HashSet with the same elements as are in the supplied
+   * collection (eliminating any duplicates, of course). The backing storage
+   * has twice the size of the collection, or the default size of 11,
+   * whichever is greater; and the default load factor (0.75).
    *
-   * @param          c          a collection containing the elements with
-   *                            which this set will be initialized
+   * @param c a collection of initial set elements
+   * @throws NullPointerException if c is null
    */
   public HashSet(Collection c)
   {
-    map = new HashMap();
+    this(Math.max(2 * c.size(), HashMap.DEFAULT_CAPACITY));
     addAll(c);
   }
 
   /**
-   * adds the given Object to the set if it is not already in the Set,
-   * returns true if teh element was added, false otherwise
+   * Adds the given Object to the set if it is not already in the Set.
+   * This set permits a null element.
    *
-   * @param       o       the Object to add to this Set
+   * @param o the Object to add to this Set
+   * @return true if the set did not already contain o
    */
   public boolean add(Object o)
   {
-    return (map.put(o, Boolean.TRUE) == null);
+    return map.put(o, "") == null;
   }
 
   /**
-   * empties this Set of all elements; this is a fast operation [O(1)]
+   * Empties this Set of all elements; this takes constant time.
    */
   public void clear()
   {
@@ -121,53 +149,67 @@ public class HashSet extends AbstractSet
   }
 
   /**
-   * returns a shallow copy of this Set (the Set itself is cloned; its 
-   * elements are not)
+   * Returns a shallow copy of this Set. The Set itself is cloned; its
+   * elements are not.
+   *
+   * @return a shallow clone of the set
    */
   public Object clone()
   {
     HashSet copy = null;
     try
       {
-	copy = (HashSet) super.clone();
+        copy = (HashSet) super.clone();
       }
     catch (CloneNotSupportedException x)
       {
+        // Impossible to get here.
       }
     copy.map = (HashMap) map.clone();
     return copy;
   }
 
   /**
-   * returns true if the supplied element is in this Set, false otherwise
+   * Returns true if the supplied element is in this Set.
    *
-   * @param        o         the Object whose presence in this Set we are testing for
+   * @param o the Object to look for
+   * @return true if it is in the set
    */
   public boolean contains(Object o)
   {
     return map.containsKey(o);
   }
 
-  /** 
-   * returns true if this set has no elements in it (size() == 0)
+  /**
+   * Returns true if this set has no elements in it.
+   *
+   * @return <code>size() == 0</code>.
    */
   public boolean isEmpty()
   {
-    return map.isEmpty();
+    return map.size == 0;
   }
 
   /**
-   * returns an Iterator over the elements of this Set; the Iterator allows
-   * removal of elements
+   * Returns an Iterator over the elements of this Set, which visits the
+   * elements in no particular order.  For this class, the Iterator allows
+   * removal of elements. The iterator is fail-fast, and will throw a
+   * ConcurrentModificationException if the set is modified externally.
+   *
+   * @return a set iterator
+   * @see ConcurrentModificationException
    */
   public Iterator iterator()
   {
-    return map.keySet().iterator();
+    // Avoid creating intermediate keySet() object by using non-public API.
+    return map.iterator(HashMap.KEYS);
   }
 
   /**
-   * removes the supplied Object from this Set if it is in the Set; returns
-   * true if an element was removed, false otherwise
+   * Removes the supplied Object from this Set if it is in the Set.
+   *
+   * @param o the object to remove
+   * @return true if an element was removed
    */
   public boolean remove(Object o)
   {
@@ -175,18 +217,42 @@ public class HashSet extends AbstractSet
   }
 
   /**
-   * returns the number of elements in this Set
+   * Returns the number of elements in this Set (its cardinality).
+   *
+   * @return the size of the set
    */
   public int size()
   {
-    return map.size();
+    return map.size;
   }
 
-  /** Serialize this Object in a manner which is binary-compatible with the 
-    * JDK */
+  /**
+   * Helper method which initializes the backing Map. Overridden by
+   * LinkedHashSet for correct semantics.
+   *
+   * @param capacity the initial capacity
+   * @param load the initial load factor
+   * @return the backing HashMap
+   */
+  HashMap init(int capacity, float load)
+  {
+    return new HashMap(capacity, load);
+  }
+
+  /**
+   * Serializes this object to the given stream.
+   *
+   * @param s the stream to write to
+   * @throws IOException if the underlying stream fails
+   * @serialData the <i>capacity</i> (int) and <i>loadFactor</i> (float)
+   *             of the backing store, followed by the set size (int),
+   *             then a listing of its elements (Object) in no order
+   */
   private void writeObject(ObjectOutputStream s) throws IOException
   {
-    Iterator it = iterator();
+    s.defaultWriteObject();
+    // Avoid creating intermediate keySet() object by using non-public API.
+    Iterator it = map.iterator(HashMap.KEYS);
     s.writeInt(map.buckets.length);
     s.writeFloat(map.loadFactor);
     s.writeInt(map.size);
@@ -194,25 +260,23 @@ public class HashSet extends AbstractSet
       s.writeObject(it.next());
   }
 
-  /** Deserialize this Object in a manner which is binary-compatible with 
-    * the JDK */
-  private void readObject(ObjectInputStream s) throws IOException,
-    ClassNotFoundException
+  /**
+   * Deserializes this object from the given stream.
+   *
+   * @param s the stream to read from
+   * @throws ClassNotFoundException if the underlying stream fails
+   * @throws IOException if the underlying stream fails
+   * @serialData the <i>capacity</i> (int) and <i>loadFactor</i> (float)
+   *             of the backing store, followed by the set size (int),
+   *             then a listing of its elements (Object) in no order
+   */
+  private void readObject(ObjectInputStream s)
+    throws IOException, ClassNotFoundException
   {
-    int i, size, capacity;
-    float loadFactor;
-    Object element;
-
-    capacity = s.readInt();
-    loadFactor = s.readFloat();
-    size = s.readInt();
+    s.defaultReadObject();
 
-    map = new HashMap(capacity, loadFactor);
-
-    for (i = 0; i < size; i++)
-      {
-	element = s.readObject();
-	map.put(element, Boolean.TRUE);
-      }
+    map = init(s.readInt(), s.readFloat());
+    for (int size = s.readInt(); size > 0; size--)
+      map.put(s.readObject(), "");
   }
 }