AbstractCollection.java (addAll): Use size() instead of hasNext() in iterator loop.

2000-10-29  Bryce McKinlay  <bryce@albatross.co.nz>

	* java/util/AbstractCollection.java (addAll): Use size() instead of
	hasNext() in iterator loop.
	(clear): Ditto.
	(contains): Ditto. Simplify loop.
	(containsAll): Ditto.
	(remove): Ditto.
	(removeAll): Ditto.
	(retainAll): Ditto.
	(toArray): Ditto.
	(toString): Ditto. Use string concatenation operators, not
	StringBuffer.
	* java/util/AbstractList.java (addAll): Use size() instead of
	hasNext() in iterator loop.
	(equals): Ditto.
	(hashCode): Ditto.
	(indexOf): Ditto. Don't take null check outside of the loop.
	(iterator): Return an AbstractListItr instead of anonymous class.
	(lastIndexOf): Use a for loop bounded by size() instead of
	hasPrevious() in iterator loop.
	(listIterator): Return an AbstractListItr.
	(removeRange): Remove bounds checking code and docs.
	(AbstractListItr): New inner class. Code moved here from
	listIterator().
	(SubList.iterator): Removed. Use default implementation from
	AbstractList instead.
	(SubList.listIterator): As above.
	* java/util/AbstractMap.java (clear): Use a for loop bounded by size()
	instead of hasNext() in iterator loop.
	(containsValue): Ditto.
	(equals): Ditto.
	(get): Ditto.
	(put): Ditto.
	(putAll): Ditto.
	(remove): Ditto.
	(toString): Ditto. Use string concatenation operators, not
	StringBuffer.
	* java/util/AbstractSequentialList.java (addAll): Use a for loop
	bounded by size() instead of hasNext() in iterator loop.
	* java/util/AbstractSet.java (hashCode): Don't catch exception as
	part of normal execution flow. Do an explicit null check instead.
	* java/util/ArrayList.java (_iSize): Rename to `size'.
	(_arData): Rename to `data'.
	(get): Check lower bounds also. Simplify IndexOutOfBoundsException
	message.
	(remove): Ditto.
	(removeRange): Make protected. Don't check bounds.
	(add): Check lower bounds also. Simplify IndexOutOfBoundsException
	message.
	(addAll (Collection)): Use a size-bounded for loop instead of hasNext()
	check.
	(addAll (int, Collection)): Check lower bounds. Simplify exception
	string.
	(clone): Clone the data array too.
	(indexOf): Inline doesEqual().
	(lastIndexOf): Ditto.
	(clear): Don't set array data to null.
	(set): Check lower bounds. Simplify exception string.
	(toArray): Correct comment.
	(trimToSize): Don't update modCount, this is not a structural change.
	Add comment.

	* java/util/BitSet.java: Merged with classpath, new JDK 1.2 methods
	implemented.
	(toString): Declare `bit' as long, not int.
	(data): Made package-private, not private.

From-SVN: r37116

8 files changed, 979 insertions, 891 deletions

diff --git a/libjava/ChangeLog b/libjava/ChangeLog
index fb17da3..3a58979 100644
--- a/libjava/ChangeLog
+++ b/libjava/ChangeLog
@@ -1,3 +1,71 @@
+2000-10-29  Bryce McKinlay  <bryce@albatross.co.nz>
+
+	* java/util/AbstractCollection.java (addAll): Use size() instead of
+	hasNext() in iterator loop.
+	(clear): Ditto.
+	(contains): Ditto. Simplify loop.
+	(containsAll): Ditto.
+	(remove): Ditto.
+	(removeAll): Ditto.
+	(retainAll): Ditto.
+	(toArray): Ditto.
+	(toString): Ditto. Use string concatenation operators, not
+	StringBuffer.
+	* java/util/AbstractList.java (addAll): Use size() instead of
+	hasNext() in iterator loop.
+	(equals): Ditto.
+	(hashCode): Ditto.
+	(indexOf): Ditto. Don't take null check outside of the loop.
+	(iterator): Return an AbstractListItr instead of anonymous class.
+	(lastIndexOf): Use a for loop bounded by size() instead of 
+	hasPrevious() in iterator loop.
+	(listIterator): Return an AbstractListItr.
+	(removeRange): Remove bounds checking code and docs.
+	(AbstractListItr): New inner class. Code moved here from 
+	listIterator().
+	(SubList.iterator): Removed. Use default implementation from 
+	AbstractList instead.
+	(SubList.listIterator): As above.
+	* java/util/AbstractMap.java (clear): Use a for loop bounded by size() 
+	instead of hasNext() in iterator loop.
+	(containsValue): Ditto.
+	(equals): Ditto.
+	(get): Ditto.
+	(put): Ditto.
+	(putAll): Ditto.
+	(remove): Ditto.
+	(toString): Ditto. Use string concatenation operators, not
+	StringBuffer.
+	* java/util/AbstractSequentialList.java (addAll): Use a for loop 
+	bounded by size() instead of hasNext() in iterator loop.
+	* java/util/AbstractSet.java (hashCode): Don't catch exception as
+	part of normal execution flow. Do an explicit null check instead.
+	* java/util/ArrayList.java (_iSize): Rename to `size'.
+	(_arData): Rename to `data'.
+	(get): Check lower bounds also. Simplify IndexOutOfBoundsException
+	message.
+	(remove): Ditto.
+	(removeRange): Make protected. Don't check bounds.
+	(add): Check lower bounds also. Simplify IndexOutOfBoundsException
+	message.
+	(addAll (Collection)): Use a size-bounded for loop instead of hasNext() 
+	check.
+	(addAll (int, Collection)): Check lower bounds. Simplify exception
+	string.
+	(clone): Clone the data array too.
+	(indexOf): Inline doesEqual().
+	(lastIndexOf): Ditto.
+	(clear): Don't set array data to null.
+	(set): Check lower bounds. Simplify exception string.
+	(toArray): Correct comment.
+	(trimToSize): Don't update modCount, this is not a structural change.
+	Add comment.
+	
+	* java/util/BitSet.java: Merged with classpath, new JDK 1.2 methods
+	implemented.
+	(toString): Declare `bit' as long, not int.
+	(data): Made package-private, not private.	
+
 2000-10-27  Warren Levy  <warrenl@cygnus.com>
 
 	* java/util/natGregorianCalendar.cc (computeFields): Set the isSet__
diff --git a/libjava/java/util/AbstractCollection.java b/libjava/java/util/AbstractCollection.java
index 8002044..d75aff9 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 Free Software Foundation, Inc.
+   Copyright (C) 1998, 2000 Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -7,7 +7,7 @@ GNU Classpath is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.
- 
+
 GNU Classpath is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
@@ -43,8 +43,8 @@ import java.lang.reflect.Array;
  * precise implementation used by AbstractCollection is documented, so that
  * subclasses can tell which methods could be implemented more efficiently.
  */
-public abstract class AbstractCollection implements Collection {
-
+public abstract class AbstractCollection implements Collection
+{
   /**
    * Return an Iterator over this collection. The iterator must provide the
    * hasNext and next methods and should in addition provide remove if the
@@ -67,7 +67,8 @@ public abstract class AbstractCollection implements Collection {
    * @exception UnsupportedOperationException if the add operation is not
    *   supported on this collection
    */
-  public boolean add(Object o) {
+  public boolean add(Object o)
+  {
     throw new java.lang.UnsupportedOperationException();
   }
 
@@ -82,12 +83,15 @@ public abstract class AbstractCollection implements Collection {
    * @exception UnsupportedOperationException if the add operation is not
    *   supported on this collection
    */
-  public boolean addAll(Collection c) {
-    Iterator i = c.iterator();
+  public boolean addAll(Collection c)
+  {
+    Iterator itr = c.iterator();
+    int size = c.size();
     boolean modified = false;
-    while (i.hasNext()) {
-      modified |= add(i.next());
-    }
+    for (int pos = 0; pos < size; pos++)
+      {
+	modified |= add(itr.next());
+      }
     return modified;
   }
 
@@ -101,12 +105,15 @@ public abstract class AbstractCollection implements Collection {
    * @exception UnsupportedOperationException if the Iterator returned by
    *   iterator does not provide an implementation of remove
    */
-  public void clear() {
-    Iterator i = iterator();
-    while (i.hasNext()) {
-      i.next();
-      i.remove();
-    }
+  public void clear()
+  {
+    Iterator itr = iterator();
+    int size = size();
+    for (int pos = 0; pos < size; pos++)
+      {
+	itr.next();
+	itr.remove();
+      }
   }
 
   /**
@@ -120,25 +127,15 @@ public abstract class AbstractCollection implements Collection {
    * @param o the object to remove from this collection
    * @return true if this collection contains an object equal to o
    */
-  public boolean contains(Object o) {
-    Iterator i = iterator();
-
-    // This looks crazily inefficient, but it takes the test o==null outside
-    // the loop, saving time, and also saves needing to store the result of
-    // i.next() each time.
-    if (o == null) {
-      while (i.hasNext()) {
-        if (i.next() == null) {
-          return true;
-        }
-      }
-    } else {
-      while (i.hasNext()) {
-        if (o.equals(i.next())) {
-          return true;
-        }
+  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;
       }
-    }
     return false;
   }
 
@@ -152,13 +149,15 @@ public abstract class AbstractCollection implements Collection {
    * @return true if this collection contains all the elements in the given
    *   collection
    */
-  public boolean containsAll(Collection c) {
-    Iterator i = c.iterator();
-    while (i.hasNext()) {
-      if (!contains(i.next())) {
-        return false;
+  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;
       }
-    }
     return true;
   }
 
@@ -168,7 +167,8 @@ public abstract class AbstractCollection implements Collection {
    *
    * @return true if this collection is empty.
    */
-  public boolean isEmpty() {
+  public boolean isEmpty()
+  {
     return size() == 0;
   }
 
@@ -189,27 +189,18 @@ public abstract class AbstractCollection implements Collection {
    * @exception UnsupportedOperationException if this collection's Iterator
    *   does not support the remove method
    */
-  public boolean remove(Object o) {
-    Iterator i = iterator();
-
-    // This looks crazily inefficient, but it takes the test o==null outside
-    // the loop, saving time, and also saves needing to store the result of
-    // i.next() each time.
-    if (o == null) {
-      while (i.hasNext()) {
-        if (i.next() == null) {
-          i.remove();
-	  return true;
-        }
+  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;
+	  }
       }
-    } else {
-      while (i.hasNext()) {
-        if (o.equals(i.next())) {
-          i.remove();
-          return true;
-        }
-      }
-    }
     return false;
   }
 
@@ -226,16 +217,20 @@ public abstract class AbstractCollection implements Collection {
    * @exception UnsupportedOperationException if this collection's Iterator
    *   does not support the remove method
    */
-  public boolean removeAll(Collection c) {
-    Iterator i = iterator();
-    boolean changed = false;
-    while (i.hasNext()) {
-      if (c.contains(i.next())) {
-        i.remove();
-        changed = true;
+  public boolean removeAll(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;
+	  }
       }
-    }
-    return changed;
+    return modified;
   }
 
   /**
@@ -251,16 +246,20 @@ public abstract class AbstractCollection implements Collection {
    * @exception UnsupportedOperationException if this collection's Iterator
    *   does not support the remove method
    */
-  public boolean retainAll(Collection c) {
-    Iterator i = iterator();
-    boolean changed = false;
-    while (i.hasNext()) {
-      if (!c.contains(i.next())) {
-        i.remove();
-        changed = true;
+  public boolean retainAll(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;
+	  }
       }
-    }
-    return changed;
+    return modified;
   }
 
   /**
@@ -271,12 +270,14 @@ public abstract class AbstractCollection implements Collection {
    *
    * @return an array containing the elements of this collection
    */
-  public Object[] toArray() {
-    Object[] a = new Object[size()];
-    Iterator i = iterator();
-    for (int pos = 0; pos < a.length; pos++) {
-      a[pos] = i.next();
-    }
+  public Object[] toArray()
+  {
+    Iterator itr = iterator();
+    Object[]a = new Object[size()];
+    for (int pos = 0; pos < a.length; pos++)
+      {
+	a[pos] = itr.next();
+      }
     return a;
   }
 
@@ -298,18 +299,23 @@ public abstract class AbstractCollection implements Collection {
    * @exception ClassCastException if the type of the array precludes holding
    *   one of the elements of the Collection
    */
-  public Object[] toArray(Object[] a) {
-    final int n = size();
-    if (a.length < n) {
-      a = (Object[])Array.newInstance(a.getClass().getComponentType(), n);
-    }
-    Iterator i = iterator();
-    for (int pos = 0; pos < n; pos++) {
-      a[pos] = i.next();
-    }
-    if (a.length > n) {
-      a[n] = null;
-    }
+  public Object[] toArray(Object[]a)
+  {
+    int size = size();
+    if (a.length < size)
+      {
+	a = (Object[])Array.newInstance(a.getClass().getComponentType(),
+					size);
+      }
+    Iterator itr = iterator();
+    for (int pos = 0; pos < size; pos++)
+      {
+	a[pos] = itr.next();
+      }
+    if (a.length > size)
+      {
+	a[size] = null;
+      }
     return a;
   }
 
@@ -322,18 +328,18 @@ public abstract class AbstractCollection implements Collection {
    *
    * @return a String representation of the Collection
    */
-  public String toString() {
-    StringBuffer s = new StringBuffer();
-    s.append('[');
-    Iterator i = iterator();
-    boolean more = i.hasNext();
-    while(more) {
-      s.append(i.next());
-      if (more = i.hasNext()) {
-        s.append(", ");
+  public String toString()
+  {
+    Iterator itr = iterator();
+    int size = size();
+    String r = "[";
+    for (int pos = 0; pos < size; pos++)
+      {
+	r += itr.next();
+	if (pos < size - 1)
+	  r += ", ";
       }
-    }
-    s.append(']');
-    return s.toString();
+    r += "]";
+    return r;
   }
 }
diff --git a/libjava/java/util/AbstractList.java b/libjava/java/util/AbstractList.java
index da76a8b..89d9a1e 100644
--- a/libjava/java/util/AbstractList.java
+++ b/libjava/java/util/AbstractList.java
@@ -7,7 +7,7 @@ GNU Classpath is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.
- 
+
 GNU Classpath is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
@@ -44,8 +44,8 @@ package java.util;
  * AbstractList is documented, so that subclasses can tell which methods could
  * be implemented more efficiently.
  */
-public abstract class AbstractList extends AbstractCollection implements List {
-
+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).
@@ -54,238 +54,112 @@ public abstract class AbstractList extends AbstractCollection implements List {
 
   public abstract Object get(int index);
 
-  public void add(int index, Object o) {
+  public void add(int index, Object o)
+  {
     throw new UnsupportedOperationException();
   }
 
-  public boolean add(Object o) {
+  public boolean add(Object o)
+  {
     add(size(), o);
     return true;
   }
 
-  public boolean addAll(int index, Collection c) {
-    Iterator i = c.iterator();
-    if (i.hasNext()) {
-      do {
-        add(index++, i.next());
-      } while (i.hasNext());
-      return true;
-    } else {
-      return false;
-    }
+  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);
   }
 
-  public void clear() {
+  public void clear()
+  {
     removeRange(0, size());
   }
 
-  public boolean equals(Object o) {
-    if (o == this) {
+  public boolean equals(Object o)
+  {
+    if (o == this)
       return true;
-    } else if (!(o instanceof List)) {
+    if (!(o instanceof List))
       return false;
-    } else {
-      Iterator i1 = iterator();
-      Iterator i2 = ((List)o).iterator();
-      while (i1.hasNext()) {
-        if (!i2.hasNext()) {
-          return false;
-        } else {
-          Object e = i1.next();
-          if (e == null ? i2.next() != null : !e.equals(i2.next())) {
-            return false;
-          }
-        }
-      }
-      if (i2.hasNext()) {
-        return false;
-      } else {
-        return true;
+    int size = size();
+    if (size != ((List) o).size())
+      return false;
+
+    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;
       }
-    }
+    return true;
   }
 
-  public int hashCode() {
+  public int hashCode()
+  {
     int hashCode = 1;
-    Iterator i = iterator();
-    while (i.hasNext()) {
-      Object obj = i.next();
-      hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
-    }
+    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());
+      }
     return hashCode;
   }
 
-  public int indexOf(Object o) {
-    int index = 0;
-    ListIterator i = listIterator();
-    if (o == null) {
-      while (i.hasNext()) {
-        if (i.next() == null) {
-          return index;
-        }
-        index++;
-      }
-    } else {
-      while (i.hasNext()) {
-        if (o.equals(i.next())) {
-          return index;
-        }
-        index++;
+  public int indexOf(Object o)
+  {
+    ListIterator itr = listIterator(0);
+    int size = size();
+    for (int pos = 0; pos < size; pos++)
+      {
+	if (o == null ? itr.next() == null : o.equals(itr.next()))
+	  return pos;
       }
-    }
     return -1;
   }
 
-  public Iterator iterator() {
-    return new Iterator() {
-      private int knownMod = modCount;
-      private int position = 0;
-      boolean removed = true;
-
-      private void checkMod() {
-        if (knownMod != modCount) {
-          throw new ConcurrentModificationException();
-        }
-      }
-
-      public boolean hasNext() {
-        checkMod();
-        return position < size();
-      }
-
-      public Object next() {
-        checkMod();
-        removed = false;
-        try {
-          return get(position++);
-        } catch (IndexOutOfBoundsException e) {
-          throw new NoSuchElementException();
-        }
-      }
-
-      public void remove() {
-        checkMod();
-        if (removed) {
-          throw new IllegalStateException();
-        }
-        AbstractList.this.remove(--position);
-        knownMod = modCount;
-        removed = true;
-      }
-    };
+  public Iterator iterator()
+  {
+    return new AbstractListItr(0);
   }
 
-  public int lastIndexOf(Object o) {
-    int index = size();
-    ListIterator i = listIterator(index);
-    if (o == null) {
-      while (i.hasPrevious()) {
-        index--;
-        if (i.previous() == null) {
-          return index;
-        }
-      }
-    } else {
-      while (i.hasPrevious()) {
-        index--;
-        if (o.equals(i.previous())) {
-          return 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;
       }
-    }
     return -1;
   }
 
-  public ListIterator listIterator() {
-    return listIterator(0);
+  public ListIterator listIterator()
+  {
+    return new AbstractListItr(0);
   }
 
-  public ListIterator listIterator(final int index) {
-
-    if (index < 0 || index > size()) {
+  public ListIterator listIterator(int index)
+  {
+    if (index < 0 || index > size())
       throw new IndexOutOfBoundsException();
-    }
-
-    return new ListIterator() {
-      private int knownMod = modCount;
-      private int position = index;
-      private int lastReturned = -1;
 
-      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 (hasNext()) {
-          lastReturned = position++;
-          return get(lastReturned);
-        } else {
-          throw new NoSuchElementException();
-        }
-      }
-
-      public Object previous() {
-        checkMod();
-        if (hasPrevious()) {
-          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 = modCount;
-        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 = modCount;
-      }
-    };
+    return new AbstractListItr(index);
   }
 
-  public Object remove(int index) {
+  public Object remove(int index)
+  {
     throw new UnsupportedOperationException();
   }
 
@@ -303,59 +177,145 @@ public abstract class AbstractList extends AbstractCollection implements List {
    *
    * @param fromIndex the index, inclusive, to remove from.
    * @param toIndex the index, exclusive, to remove to.
-   * @exception UnsupportedOperationException if this list does not support
-   *   the removeRange operation.
-   * @exception IndexOutOfBoundsException if fromIndex > toIndex || fromIndex <
-   *   0 || toIndex > size().
    */
-  protected void removeRange(int fromIndex, int toIndex) {
-    if (fromIndex > toIndex) {
-      throw new IllegalArgumentException();
-    } else if (fromIndex < 0 || toIndex > size()) {
-      throw new IndexOutOfBoundsException();
-    } else {
-      ListIterator i = listIterator(fromIndex);
-      for (int index = fromIndex; index < toIndex; index++) {
-        i.next();
-        i.remove();
+  protected void removeRange(int fromIndex, int toIndex)
+  {
+    ListIterator itr = listIterator(fromIndex);
+    for (int index = fromIndex; index < toIndex; index++)
+      {
+	itr.next();
+	itr.remove();
       }
-    }
   }
 
-  public Object set(int index, Object o) {
+  public Object set(int index, Object o)
+  {
     throw new UnsupportedOperationException();
   }
 
-  public List subList(final int fromIndex, final int toIndex) {
+  public List subList(final int fromIndex, final int toIndex)
+  {
     if (fromIndex > toIndex)
       throw new IllegalArgumentException();
     if (fromIndex < 0 || toIndex > size())
       throw new IndexOutOfBoundsException();
+
     return new SubList(this, fromIndex, toIndex);
   }
 
-  static class SubList extends AbstractList {
+  class AbstractListItr implements ListIterator
+  {
+    private int knownMod = modCount;
+    private int position;
+    private int lastReturned = -1;
 
+    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 = modCount;
+      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 = modCount;
+    }
+  }				// AbstractList.Iterator
+
+  static class SubList extends AbstractList
+  {
     private AbstractList backingList;
     private int offset;
     private int size;
 
-    public SubList(AbstractList backing, int fromIndex, int toIndex) {
+    public SubList(AbstractList backing, int fromIndex, int toIndex)
+    {
       backingList = backing;
       upMod();
       offset = fromIndex;
       size = toIndex - fromIndex;
     }
 
-    // Note that within this class two fields called modCount are inherited -
-    // one from the superclass, and one from the outer class. 
-    // The code uses both these two fields and *no other* to provide fail-fast
-    // behaviour. For correct operation, the two fields should contain equal
-    // values. Therefore, if this.modCount != backingList.modCount, there
-    // has been a concurrent modification. This is all achieved purely by using
-    // the modCount field, precisely according to the docs of AbstractList.
-    // See the methods upMod and checkMod.
-
     /**
      * This method checks the two modCount fields to ensure that there has
      * not been a concurrent modification. It throws an exception if there
@@ -365,22 +325,23 @@ public abstract class AbstractList extends AbstractCollection implements List {
      * @exception ConcurrentModificationException if there has been a
      *   concurrent modification.
      */
-    private void checkMod() {
-      if (this.modCount != backingList.modCount) {
+    private void checkMod()
+    {
+      if (this.modCount != backingList.modCount)
 	throw new ConcurrentModificationException();
-      }
     }
-    
+
     /**
      * This method is called after every method that causes a structural
      * modification to the backing list. It updates the local modCount field
      * to match that of the backing list.
      * Note that since this method is private, it will be inlined.
      */
-    private void upMod() {
+    private void upMod()
+    {
       this.modCount = backingList.modCount;
     }
-    
+
     /**
      * This method checks that a value is between 0 and size (inclusive). If
      * it is not, an exception is thrown.
@@ -388,12 +349,12 @@ public abstract class AbstractList extends AbstractCollection implements List {
      *
      * @exception IndexOutOfBoundsException if the value is out of range.
      */
-    private void checkBoundsInclusive(int index) {
-      if (index < 0 || index > size) {
+    private void checkBoundsInclusive(int index)
+    {
+      if (index < 0 || index > size)
 	throw new IndexOutOfBoundsException();
-      }
     }
-    
+
     /**
      * This method checks that a value is between 0 (inclusive) and size
      * (exclusive). If it is not, an exception is thrown.
@@ -401,131 +362,45 @@ public abstract class AbstractList extends AbstractCollection implements List {
      *
      * @exception IndexOutOfBoundsException if the value is out of range.
      */
-    private void checkBoundsExclusive(int index) {
-      if (index < 0 || index >= size) {
+    private void checkBoundsExclusive(int index)
+    {
+      if (index < 0 || index >= size)
 	throw new IndexOutOfBoundsException();
-      }
     }
-    
-    public int size() {
+
+    public int size()
+    {
       checkMod();
       return size;
     }
-    
-    public Iterator iterator() {
-      return listIterator();
-    }
-    
-    public ListIterator listIterator(final int index) {
-      
-      checkMod();
-      checkBoundsInclusive(index);
-      
-      return new ListIterator() {
-	ListIterator i = backingList.listIterator(index + offset);
-	int position = index;
-	
-	public boolean hasNext() {
-	  checkMod();
-	  return position < size;
-	}
-	
-	public boolean hasPrevious() {
-	  checkMod();
-	  return position > 0;
-	}
-	
-	public Object next() {
-	  if (position < size) {
-	    Object o = i.next();
-	    position++;
-	    return o;
-	  } else {
-	    throw new NoSuchElementException();
-	  }
-	}
-	
-	public Object previous() {
-	  if (position > 0) {
-	    Object o = i.previous();
-	    position--;
-	    return o;
-	  } else {
-	    throw new NoSuchElementException();
-	  }
-	}
-	
-	public int nextIndex() {
-	  return offset + i.nextIndex();
-	}
-	
-	public int previousIndex() {
-	  return offset + i.previousIndex();
-	}
-
-	public void remove() {
-	  i.remove();
-	  upMod();
-	  size--;
-	  position = nextIndex();
-	}
-	
-	public void set(Object o) {
-	  i.set(o);
-	}
-	
-	public void add(Object o) {
-	  i.add(o);
-	  upMod();
-	  size++;
-	  position++;
-	}
 
-	// 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:
-	//   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
-	//   when this listIterator comes to use the backing one. So it is
-	//   implicitly failfast.
-	// If the backing listIterator is NOT failfast, then the whole of
-	//   this list isn't failfast, because the modCount field of the
-	//   backing list is not valid. It would still be *possible* to
-	//   make the iterator failfast wrt modifications of the sublist
-	//   only, but somewhat pointless when the list can be changed under
-	//   us.
-	// Either way, no explicit handling of modCount is needed.
-	// However upMod() must be called 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.
-
-      };
-    }
-
-    public Object set(int index, Object o) {
+    public Object set(int index, Object o)
+    {
       checkMod();
       checkBoundsExclusive(index);
       o = backingList.set(index + offset, o);
       upMod();
       return o;
     }
-    
-    public Object get(int index) {
+
+    public Object get(int index)
+    {
       checkMod();
       checkBoundsExclusive(index);
       return backingList.get(index + offset);
     }
 
-    public void add(int index, Object o) {
+    public void add(int index, Object o)
+    {
       checkMod();
       checkBoundsInclusive(index);
       backingList.add(index + offset, o);
       upMod();
       size++;
     }
-    
-    public Object remove(int index) {
+
+    public Object remove(int index)
+    {
       checkMod();
       checkBoundsExclusive(index);
       Object o = backingList.remove(index + offset);
@@ -534,18 +409,20 @@ public abstract class AbstractList extends AbstractCollection implements List {
       return o;
     }
 
-    public void removeRange(int fromIndex, int toIndex) {
+    public 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);
       upMod();
       size -= toIndex - fromIndex;
     }
-    
-    public boolean addAll(int index, Collection c) {
+
+    public boolean addAll(int index, Collection c)
+    {
       checkMod();
       checkBoundsInclusive(index);
       int s = backingList.size();
@@ -554,5 +431,5 @@ public abstract class AbstractList extends AbstractCollection implements List {
       size += backingList.size() - s;
       return result;
     }
-  }
+  }				// AbstractList.SubList
 }
diff --git a/libjava/java/util/AbstractMap.java b/libjava/java/util/AbstractMap.java
index 4935afe..c4f9df0 100644
--- a/libjava/java/util/AbstractMap.java
+++ b/libjava/java/util/AbstractMap.java
@@ -7,7 +7,7 @@ GNU Classpath is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.
- 
+
 GNU Classpath is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
@@ -31,88 +31,90 @@ executable file might be covered by the GNU General Public License. */
 
 package java.util;
 
-public abstract class AbstractMap implements Map {
-  
+public abstract class AbstractMap implements Map
+{
+  /**
+   * Remove all entries from this Map. This default implementation calls
+   * entrySet().clear().
+   *
+   * @throws UnsupportedOperationException
+   * @specnote The JCL book claims that this implementation always throws 
+   *           UnsupportedOperationException, while the online docs claim it
+   *           calls entrySet().clear(). We take the later to be correct.
+   */
   public void clear()
   {
     entrySet().clear();
   }
 
-  public boolean containsKey( Object key )
+  public boolean containsKey(Object key)
   {
     Object k;
-    Iterator entries = entrySet().iterator();
-  
-    while( entries.hasNext() )
-    {
-      k = ((Map.Entry)entries.next()).getKey();
-      if( key == null ? k == null : key.equals( k ) )
-	return true;
-    }
-
+    Set es = entrySet();
+    Iterator entries = es.iterator();
+    int size = size();
+    for (int pos = 0; pos < size; pos++)
+      {
+	k = ((Map.Entry) entries.next()).getKey();
+	if (key == null ? k == null : key.equals(k))
+	  return true;
+      }
     return false;
   }
 
-  public boolean containsValue( Object value )
+  public boolean containsValue(Object value)
   {
     Object v;
-    Iterator entries = entrySet().iterator();
-  
-    while( entries.hasNext() )
-    {
-      v = ((Map.Entry)entries.next()).getValue();
-      if( value == null ? v == null : value.equals( v ) )
-	return true;
-    }
-
-    return false; 
+    Set es = entrySet();
+    Iterator entries = es.iterator();
+    int size = size();
+    for (int pos = 0; pos < size; pos++)
+      {
+	v = ((Map.Entry) entries.next()).getValue();
+	if (value == null ? v == null : value.equals(v))
+	  return true;
+      }
+    return false;
   }
 
   public abstract Set entrySet();
 
-  public boolean equals( Object o )
+  public boolean equals(Object o)
   {
-    if( this == o )
+    if (o == this)
       return true;
-    
-    if( o == null || !( o instanceof Map ) )
+    if (!(o instanceof Map))
       return false;
-    
-    Map m = (Map)o;
-    if( m.size() != size() )
+
+    Map m = (Map) o;
+    Set s = m.entrySet();
+    Iterator itr = entrySet().iterator();
+    int size = size();
+
+    if (m.size() != size)
       return false;
-    
-    Object key, value1, value2;
-    Map.Entry entry;
-    Iterator entries = entrySet().iterator();
-    while( entries.hasNext() )
-    {
-      entry = (Map.Entry)entries.next();
-      key = entry.getKey();
-      value1 = entry.getValue();
-      value2 = m.get( key );
-      
-      if( !( ( value1 == null && value2 == null )
-	     || value1.equals( value2 ) ) )
-	return false;
-    }
-
-    return true;    
+
+    for (int pos = 0; pos < size; pos++)
+      {
+	if (!s.contains(itr.next()))
+	  return false;
+      }
+    return true;
   }
 
-  public Object get( Object key )
+  public Object get(Object key)
   {
-    Object k;
-    Map.Entry entry;
-    Iterator entries = entrySet().iterator();
-  
-    while( entries.hasNext() )
-    {
-      entry = (Map.Entry)entries.next();
-      k = entry.getKey();
-      if( key == null ? k == null : key.equals( k ) )
-	return entry.getValue();
-    }
+    Set s = entrySet();
+    Iterator entries = s.iterator();
+    int size = size();
+
+    for (int pos = 0; pos < size; pos++)
+      {
+	Map.Entry entry = (Map.Entry) entries.next();
+	Object k = entry.getKey();
+	if (key == null ? k == null : key.equals(k))
+	  return entry.getValue();
+      }
 
     return null;
   }
@@ -120,11 +122,12 @@ public abstract class AbstractMap implements Map {
   public int hashCode()
   {
     int hashcode = 0;
-    Iterator entries = entrySet().iterator();
-  
-    while( entries.hasNext() )
-      hashcode += entries.next().hashCode();
-
+    Iterator itr = entrySet().iterator();
+    int size = size();
+    for (int pos = 0; pos < size; pos++)
+      {
+	hashcode += itr.next().hashCode();
+      }
     return hashcode;
   }
 
@@ -135,13 +138,12 @@ public abstract class AbstractMap implements Map {
 
   public Set keySet()
   {
-    if( this.keySet == null )
-    {
-      this.keySet =
-	new AbstractSet()
+    if (this.keySet == null)
+      {
+	this.keySet = new AbstractSet()
 	{
 	  public int size()
-          {
+	  {
 	    return AbstractMap.this.size();
 	  }
 
@@ -149,70 +151,71 @@ public abstract class AbstractMap implements Map {
 	  {
 	    return AbstractMap.this.containsKey(key);
 	  }
-	  
+
 	  public Iterator iterator()
-          {
+	  {
 	    return new Iterator()
-            {
+	    {
 	      Iterator map_iterator = AbstractMap.this.entrySet().iterator();
-	      
+
 	      public boolean hasNext()
-              {
+	      {
 		return map_iterator.hasNext();
 	      }
 
 	      public Object next()
-              {
-		return ((Map.Entry)map_iterator.next()).getKey();
+	      {
+		return ((Map.Entry) map_iterator.next()).getKey();
 	      }
-	      
+
 	      public void remove()
-              {
+	      {
 		map_iterator.remove();
 	      }
 	    };
 	  }
 	};
-    }
-    
-    return this.keySet;    
+      }
+
+    return this.keySet;
   }
 
-  public Object put( Object key, Object value )
+  public Object put(Object key, Object value)
   {
     throw new UnsupportedOperationException();
   }
 
-  public void putAll( Map m )
+  public void putAll(Map m)
   {
     Map.Entry entry;
     Iterator entries = m.entrySet().iterator();
-    while( entries.hasNext() )
-    {
-      entry = (Map.Entry)entries.next();
-      put( entry.getKey(), entry.getValue() );
-    }
+    int size = m.size();
+
+    for (int pos = 0; pos < size; pos++)
+      {
+	entry = (Map.Entry) entries.next();
+	put(entry.getKey(), entry.getValue());
+      }
   }
 
-  public Object remove( Object key )
+  public Object remove(Object key)
   {
-    Object k, value;
-    Map.Entry entry;
     Iterator entries = entrySet().iterator();
-  
-    while( entries.hasNext() )
-    {
-      entry = (Map.Entry)entries.next();
-      k = entry.getKey();
-      if( key == null ? k == null : key.equals( k ) )
+    int size = size();
+
+    for (int pos = 0; pos < size; pos++)
       {
-	value = entry.getValue();
-	entries.remove();
-	return value;
+	Map.Entry entry = (Map.Entry) entries.next();
+	Object k = entry.getKey();
+	if (key == null ? k == null : key.equals(k))
+	  {
+	    Object value = entry.getValue();
+	    entries.remove();
+	    return value;
+	  }
       }
-    }
 
-    return null;    
+    return null;
   }
 
   public int size()
@@ -222,62 +225,58 @@ public abstract class AbstractMap implements Map {
 
   public String toString()
   {
-    StringBuffer sb = new StringBuffer("{");
-    String comma = "";
     Iterator entries = entrySet().iterator();
-  
-    while( entries.hasNext() )
-    {
-      Map.Entry entry = (Map.Entry)entries.next();
-      sb.append(comma).append(entry.getKey())
-	.append('=').append(entry.getValue());
-      comma = ", ";
-    }
-
-    return sb.append('}').toString();
+    int size = size();
+    String r = "{";
+    for (int pos = 0; pos < size; pos++)
+      {
+	r += entries.next();
+	if (pos < size - 1)
+	  r += ", ";
+      }
+    r += "}";
+    return r;
   }
 
   public Collection values()
   {
-    if( this.valueCollection == null )
-    {
-      this.valueCollection =
-	new AbstractCollection()
+    if (this.valueCollection == null)
+      {
+	this.valueCollection = new AbstractCollection()
 	{
 	  public int size()
-          {
+	  {
 	    return AbstractMap.this.size();
 	  }
-	  
+
 	  public Iterator iterator()
-          {
+	  {
 	    return new Iterator()
-            {
+	    {
 	      Iterator map_iterator = AbstractMap.this.entrySet().iterator();
-	      
+
 	      public boolean hasNext()
-              {
+	      {
 		return map_iterator.hasNext();
 	      }
 
 	      public Object next()
-              {
-		return ((Map.Entry)map_iterator.next()).getValue();
+	      {
+		return ((Map.Entry) map_iterator.next()).getValue();
 	      }
-	      
+
 	      public void remove()
-              {
+	      {
 		map_iterator.remove();
 	      }
 	    };
 	  }
 	};
-    }
-    
+      }
+
     return this.valueCollection;
   }
 
-
   private Collection valueCollection = null;
   private Set keySet = null;
 }
diff --git a/libjava/java/util/AbstractSequentialList.java b/libjava/java/util/AbstractSequentialList.java
index 69bdc4a..07809da 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 Free Software Foundation, Inc.
+   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -7,7 +7,7 @@ GNU Classpath is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.
- 
+
 GNU Classpath is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
@@ -36,7 +36,8 @@ 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.
  */
-public abstract class AbstractSequentialList extends AbstractList {
+public abstract class AbstractSequentialList extends AbstractList
+{
 
   /**
    * Returns a ListIterator over the list, starting from position index.
@@ -57,27 +58,30 @@ public abstract class AbstractSequentialList extends AbstractList {
    * @exception UnsupportedOperationException if the iterator returned by
    *   listIterator(index) does not support the add method.
    */
-  public void add(int index, Object o) {
+  public void add(int index, Object o)
+  {
     ListIterator i = listIterator(index);
     i.add(o);
   }
 
-  public boolean addAll(int index, Collection c) {
-    boolean changed = false;
+  public boolean addAll(int index, Collection c)
+  {
+    boolean modified = false;
     Iterator ci = c.iterator();
+    int size = c.size();
     ListIterator i = listIterator(index);
-    while (ci.hasNext()) {
-      i.add(ci.next());
-      changed = true;
-    }
-    return changed;
+    for (int pos = 0; pos < size; pos++)
+      {
+	i.add(ci.next());
+      }
+    return (size > 0);
   }
 
-  public Object get(int index) {
+  public Object get(int index)
+  {
     ListIterator i = listIterator(index);
-    if (!i.hasNext()) {
+    if (index < 0 || index > size())
       throw new IndexOutOfBoundsException();
-    }
     return i.next();
   }
 
@@ -87,25 +91,26 @@ public abstract class AbstractSequentialList extends AbstractList {
    *
    * @return an Iterator over this List
    */
-  public Iterator iterator() {
+  public Iterator iterator()
+  {
     return listIterator();
   }
 
-  public Object remove(int index) {
+  public Object remove(int index)
+  {
     ListIterator i = listIterator(index);
-    if (!i.hasNext()) {
+    if (index < 0 || index > size())
       throw new IndexOutOfBoundsException();
-    }
     Object removed = i.next();
     i.remove();
     return removed;
   }
 
-  public Object set(int index, Object o) {
+  public Object set(int index, Object o)
+  {
     ListIterator i = listIterator(index);
-    if (!i.hasNext()) {
+    if (index < 0 || index > size())
       throw new IndexOutOfBoundsException();
-    }
     Object old = i.next();
     i.set(o);
     return old;
diff --git a/libjava/java/util/AbstractSet.java b/libjava/java/util/AbstractSet.java
index 0c81e6e..1014e43 100644
--- a/libjava/java/util/AbstractSet.java
+++ b/libjava/java/util/AbstractSet.java
@@ -1,5 +1,5 @@
 /* AbstractSet.java -- Abstract implementation of most of Set
-   Copyright (C) 1998 Free Software Foundation, Inc.
+   Copyright (C) 1998, 2000 Free Software Foundation, Inc.
 
 This file is part of GNU Classpath.
 
@@ -7,7 +7,7 @@ GNU Classpath is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.
- 
+
 GNU Classpath is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
@@ -36,7 +36,8 @@ package java.util;
  * class simply provides implementations of equals() and hashCode() to fulfil
  * the requirements placed on them by the Set interface.
  */
-public abstract class AbstractSet extends AbstractCollection implements Set {
+public abstract class AbstractSet extends AbstractCollection implements Set
+{
 
   /**
    * Tests whether the given object is equal to this Set. This implementation
@@ -48,14 +49,14 @@ public abstract class AbstractSet extends AbstractCollection implements Set {
    * @param o the Object to be tested for equality with this Set
    * @return true if the given object is equal to this Set
    */
-  public boolean equals(Object o) {
-    if (o == this) {
+  public boolean equals(Object o)
+  {
+    if (o == this)
       return true;
-    } else if (o instanceof Set && ((Set)o).size() == size()) {
-      return containsAll((Collection)o);
-    } else {
+    else if (o instanceof Set && ((Set) o).size() == size())
+      return containsAll((Collection) o);
+    else
       return false;
-    }
   }
 
   /**
@@ -66,15 +67,17 @@ public abstract class AbstractSet extends AbstractCollection implements Set {
    *
    * @return a hash code for this Set
    */
-  public int hashCode() {
+  public int hashCode()
+  {
+    Iterator itr = iterator();
+    int size = size();
     int hash = 0;
-    Iterator i = iterator();
-    while (i.hasNext()) {
-      try {
-        hash += i.next().hashCode();
-      } catch (NullPointerException e) {
+    for (int pos = 0; pos < size; pos++)
+      {
+	Object obj = itr.next();
+	if (obj != null)
+	  hash += obj.hashCode();
       }
-    }
     return hash;
   }
 }
diff --git a/libjava/java/util/ArrayList.java b/libjava/java/util/ArrayList.java
index 7e6562c..75d4b40 100644
--- a/libjava/java/util/ArrayList.java
+++ b/libjava/java/util/ArrayList.java
@@ -8,7 +8,7 @@ GNU Classpath is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.
- 
+
 GNU Classpath is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
@@ -33,6 +33,8 @@ import java.io.Serializable;
 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
+import java.io.ObjectInputStream.GetField;
+import java.io.ObjectOutputStream.PutField;
 import java.io.ObjectStreamField;
 
 /**
@@ -41,34 +43,34 @@ import java.io.ObjectStreamField;
  * to or removing from the end of a list, checking the size, &c.
  *
  * @author        Jon A. Zeppieri
- * @version       $Id: ArrayList.java,v 1.4 2000/03/15 21:59:06 rao Exp $
+ * @version       $Id: ArrayList.java,v 1.6 2000/10/26 10:19:00 bryce Exp $
  * @see           java.util.AbstractList
  * @see           java.util.List
  */
-public class ArrayList extends AbstractList 
+public class ArrayList extends AbstractList
   implements List, Cloneable, Serializable
 {
   /** the default capacity for new ArrayLists */
   private static final int DEFAULT_CAPACITY = 16;
 
   /** the number of elements in this list */
-  int _iSize;
+  int size;
 
   /** where the data is stored */
-  Object[] _arData;
+  Object[] data;
 
   /** used for serialization -- denotes which fields are serialized */
   private static final ObjectStreamField[] serialPersistentFields =
-  {new ObjectStreamField("size", int.class)};
+    { new ObjectStreamField("size", int.class) };
 
   /** 
    * Construct a new ArrayList with the supplied initial capacity. 
    *
-   * @param     iCapacity
+   * @param capacity Initial capacity of this ArrayList
    */
-  public ArrayList(int iCapacity)
+  public ArrayList(int capacity)
   {
-    _arData = new Object[iCapacity];
+    data = new Object[capacity];
   }
 
 
@@ -85,60 +87,63 @@ public class ArrayList extends AbstractList
    * in the supplied Collection; Sun specs say that the initial 
    * capacity is 110% of the Collection's size.
    *
-   * @param        oCollection     the collection whose elements will
-   *                               initialize this list
+   * @param c the collection whose elements will initialize this list
    */
-  public ArrayList(Collection oCollection)
+  public ArrayList(Collection c)
   {
-    this((int) (oCollection.size() * 1.1));
-    addAll(oCollection);
+    this((int) (c.size() * 1.1));
+    addAll(c);
   }
 
   /**
    * Guarantees that this list will have at least enough capacity to
-   * hold iMinCapacity elements.
+   * hold minCapacity elements. 
    *
-   * @param      iMinCapacity     the minimum guaranteed capacity
+   * @specnote This implementation will grow the list to 
+   *   max(current * 2, minCapacity) if (minCapacity > current). The JCL says
+   *   explictly that "this method increases its capacity to minCap", while
+   *   the JDK 1.3 online docs specify that the list will grow to at least the
+   *   size specified.
+   * @param minCapacity the minimum guaranteed capacity
    */
-  public void ensureCapacity(int iMinCapacity)
+  public void ensureCapacity(int minCapacity)
   {
-    Object[] arNewData;
-    int iCapacity = _arData.length;
-
-    if (iMinCapacity > iCapacity)
-    {
-      arNewData = new Object[Math.max((iCapacity * 2), iMinCapacity)];
-      System.arraycopy(_arData, 0, arNewData, 0, iCapacity);
-      _arData = arNewData;
-    }
+    Object[] newData;
+    int current = data.length;
+
+    if (minCapacity > current)
+      {
+	newData = new Object[Math.max((current * 2), minCapacity)];
+	System.arraycopy(data, 0, newData, 0, size);
+	data = newData;
+      }
   }
 
   /**
    * Appends the supplied element to the end of this list.
    *
-   * @param       oElement      the element to be appended to this list
+   * @param       e      the element to be appended to this list
    */
-  public boolean add(Object oElement)
+  public boolean add(Object e)
   {
-    ensureCapacity(_iSize + 1);
-    _arData[_iSize++] = oElement;
     modCount++;
+    ensureCapacity(size + 1);
+    data[size++] = e;
     return true;
   }
 
   /**
    * Retrieves the element at the user-supplied index.
    *
-   * @param    iIndex        the index of the element we are fetching
+   * @param    index        the index of the element we are fetching
    * @throws   IndexOutOfBoundsException  (iIndex < 0) || (iIndex >= size())
    */
-  public Object get(int iIndex)
+  public Object get(int index)
   {
-    if (iIndex >= _iSize)
-      throw new IndexOutOfBoundsException("ArrayList size=" +
-                                          String.valueOf(_iSize) + "; " +
-                                          "index=" + String.valueOf(iIndex));
-    return _arData[iIndex];
+    if (index < 0 || index >= size)
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
+                                          size);
+    return data[index];
   }
 
   /**
@@ -146,7 +151,7 @@ public class ArrayList extends AbstractList
    */
   public int size()
   {
-    return _iSize;
+    return size;
   }
 
   /**
@@ -156,152 +161,102 @@ public class ArrayList extends AbstractList
    * @return    the removed Object
    * @throws    IndexOutOfBoundsException  (iIndex < 0) || (iIndex >= size())
    */
-  public Object remove(int iIndex)
+  public Object remove(int index)
   {
-    Object oResult;
-
-    if (iIndex >= _iSize)
-      throw new IndexOutOfBoundsException("ArrayList size=" +
-                                          String.valueOf(_iSize) + "; " +
-                                          "index=" + String.valueOf(iIndex));
-
-    oResult = _arData[iIndex];
-
-    if (iIndex != --_iSize)
-      System.arraycopy(_arData, (iIndex + 1), _arData, iIndex, 
-                       (_iSize - iIndex));
-  
     modCount++;
-    _arData[_iSize] = null;
-
-    return oResult;
+    if (index < 0 || index > size)
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
+                                          size);
+    Object r = data[index];
+    if (index != --size)
+      System.arraycopy(data, (index + 1), data, index, (size - index));
+    data[size] = null;
+    return r;
   }
 
   /**
    * Removes all elements in the half-open interval [iFromIndex, iToIndex).
    *
-   * @param     iFromIndex   the first index which will be removed
-   * @param     iToIndex     one greater than the last index which will be 
+   * @param     fromIndex   the first index which will be removed
+   * @param     toIndex     one greater than the last index which will be 
    *                         removed
    */
-  public void removeRange(int iFromIndex, int iToIndex)
+  protected void removeRange(int fromIndex, int toIndex)
   {
-    int iReduction;
-    int i;
-
-    if ((iFromIndex >= _iSize) || (iToIndex >= _iSize))
-    {
-      throw new IndexOutOfBoundsException("ArrayList size=" +
-                                          String.valueOf(_iSize) + "; " +
-                                          "indices=" + 
-                                          String.valueOf(iFromIndex) + "," +
-                                          String.valueOf(iToIndex));
-    }
-    else if (iFromIndex > iToIndex)
-    {
-      throw new IllegalArgumentException("fromIndex(" + 
-                                         String.valueOf(iFromIndex) + 
-                                         ") > toIndex(" +
-                                         String.valueOf(iToIndex) + ")");
-    }
-    else if (iFromIndex != iToIndex)
-    {
-      iReduction = iToIndex - iFromIndex;
-      System.arraycopy(_arData, (iFromIndex + iReduction), _arData,
-                       iFromIndex, (_iSize - iFromIndex - iReduction));
-      modCount++;
-
-      for (i = (iFromIndex + iReduction); i < _iSize; i++)
-        _arData[i] = null;
-
-      _iSize -= iReduction;
-    }
+    modCount++;
+    if (fromIndex != toIndex)
+      {
+	System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
+	size -= (fromIndex - toIndex);
+      }
   }
 
   /**
    * Adds the supplied element at the specified index, shifting all
    * elements currently at that index or higher one to the right.
    *
-   * @param     iIndex      the index at which the element is being added
-   * @param     oElement    the element being added
+   * @param     index      the index at which the element is being added
+   * @param     e          the item being added
    */
-  public void add(int iIndex, Object oElement)
+  public void add(int index, Object e)
   {
-    if (iIndex > _iSize)
-      throw new IndexOutOfBoundsException("ArrayList size=" +
-                                          String.valueOf(_iSize) + "; " +
-                                          "index=" + String.valueOf(iIndex));
-
-    ensureCapacity(_iSize + 1);
-    System.arraycopy(_arData, iIndex, _arData, 
-                      (iIndex + 1), (_iSize - iIndex));
-    _arData[iIndex] = oElement;
-    _iSize++;
     modCount++;
+    if (index < 0 || index > size)
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
+                                          size);
+    ensureCapacity(size + 1);
+    if (index != size)
+      System.arraycopy(data, index, data, index + 1, size - index);    
+    data[index] = e;
+    size++;
   }
 
   /** 
    * Add each element in the supplied Collection to this List.
    *
-   * @param        oCollection     a Collection containing elements to be 
-   *                               added to this List
+   * @param        c          a Collection containing elements to be 
+   *                          added to this List
    */
-  public boolean addAll(Collection oCollection)
+  public boolean addAll(Collection c)
   {
-    Iterator itElements;
-    int iLen = oCollection.size();
-
-    if (iLen > 0)
-    {
-      ensureCapacity(_iSize + iLen);
-      modCount++;
-
-      itElements = oCollection.iterator();
-
-      while (itElements.hasNext())
-        _arData[_iSize++] = itElements.next();
-
-      return true;
-    }
-    return false;
+    Iterator itr = c.iterator();
+    int csize = c.size();
+    modCount++;
+    ensureCapacity(size + csize);
+    for (int pos = 0; pos < csize; pos++)
+      {
+	data[size++] = itr.next();
+      }
+    return (csize > 0);
   }
 
   /** 
    * Add all elements in the supplied collection, inserting them beginning
    * at the specified index.
    *
-   * @param     iIndex       the index at which the elements will be inserted
-   * @param     oCollection  the Collection containing the elements to be
-   *                         inserted
+   * @param     index       the index at which the elements will be inserted
+   * @param     c           the Collection containing the elements to be
+   *                        inserted
    */
-  public boolean addAll(int iIndex, Collection oCollection)
+  public boolean addAll(int index, Collection c)
   {
-    Iterator itElements;
-    int iLen;
-
-    if (iIndex > _iSize)
-      throw new IndexOutOfBoundsException("ArrayList size=" +
-                                          String.valueOf(_iSize) + "; " +
-                                          "index=" + String.valueOf(iIndex));
-
-    iLen = oCollection.size();
-
-    if (iLen > 0)
-    {
-      ensureCapacity(_iSize + iLen);
-
-      System.arraycopy(_arData, iIndex, _arData, 
-                       (iIndex + iLen), (_iSize - iIndex));
-      modCount++;
-      _iSize += iLen;
+    Iterator itr = c.iterator();
+    int csize = c.size();
 
-      itElements = oCollection.iterator();
-      while (itElements.hasNext())
-        _arData[iIndex++] = itElements.next();
-
-      return true;
-   }
-    return false;
+    modCount++;
+    if (index < 0 || index > size)
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
+                                          size);
+    ensureCapacity(size + csize);
+    int end = index + csize;
+    if (size > 0 && index != size)
+      System.arraycopy(data, index, data, end, csize);
+    size += csize;
+    for (; index < end; index++)
+      {
+        data[index] = itr.next();
+      }
+    return (csize > 0);
   }
 
   /**
@@ -309,48 +264,44 @@ public class ArrayList extends AbstractList
    */
   public Object clone()
   {
-    ArrayList oClone;
-
+    ArrayList clone = null;
     try
-    {
-      oClone = (ArrayList) super.clone();
-      oClone._arData = _arData;
-      oClone._iSize = _iSize;
-    }
-    catch(CloneNotSupportedException e)
-    {
-      oClone = null;
-    }
-    return oClone;
+      {
+	clone = (ArrayList) super.clone();
+	clone.data = new Object[data.length];
+	System.arraycopy(data, 0, clone.data, 0, size);
+      }
+    catch (CloneNotSupportedException e) {}
+    return clone;
   }
 
   /** 
    * Returns true iff oElement is in this ArrayList.
    *
-   * @param     oElement     the element whose inclusion in the List is being
-   *                         tested
+   * @param     e     the element whose inclusion in the List is being
+   *                  tested
    */
-  public boolean contains(Object oElement)
+  public boolean contains(Object e)
   {
-    return (indexOf(oElement) != -1);
+    return (indexOf(e) != -1);
   }
 
   /**
    * Returns the lowest index at which oElement appears in this List, or 
    * -1 if it does not appear.
    *
-   * @param    oElement       the element whose inclusion in the List is being
-   *                          tested
+   * @param    e       the element whose inclusion in the List is being
+   *                   tested
    */
-  public int indexOf(Object oElement)
+  public int indexOf(Object e)
   {
     int i;
 
-    for (i = 0; i < _iSize; i++)
-    {
-      if (doesEqual(oElement, _arData[i]))
-        return i;
-    }
+    for (i = 0; i < size; i++)
+      {
+	if (e == null ? data[i] == null : e.equals(data[i]))
+	  return i;
+      }
     return -1;
   }
 
@@ -358,18 +309,18 @@ public class ArrayList extends AbstractList
    * Returns the highest index at which oElement appears in this List, or 
    * -1 if it does not appear.
    *
-   * @param    oElement       the element whose inclusion in the List is being
-   *                          tested
+   * @param    e       the element whose inclusion in the List is being
+   *                   tested
    */
-  public int lastIndexOf(Object oElement)
+  public int lastIndexOf(Object e)
   {
     int i;
 
-    for (i = _iSize - 1; i >= 0; i--)
-    {
-      if (doesEqual(oElement, _arData[i]))
-        return i;
-    }
+    for (i = size - 1; i >= 0; i--)
+      {
+	if (e == null ? data[i] == null : e.equals(data[i]))
+	  return i;
+      }
     return -1;
   }
 
@@ -378,39 +329,28 @@ public class ArrayList extends AbstractList
    */
   public void clear()
   {
-    int i;
-
-    if (_iSize > 0)
-    {
-      modCount++;
-      _iSize = 0;
-
-      for (i = 0; i < _iSize; i++)
-        _arData[i] = null;
-    }      
+    modCount++;
+    size = 0;
   }
 
   /**
    * Sets the element at the specified index.
    *
-   * @param     iIndex     the index at which the element is being set
-   * @param     oElement   the element to be set
+   * @param     index   the index at which the element is being set
+   * @param     e       the element to be set
    * @return    the element previously at the specified index, or null if
    *            none was there
    */
-  public Object set(int iIndex, Object oElement)
+  public Object set(int index, Object e)
   {
-    Object oResult;
-
-    if (iIndex >= _iSize)
-      throw new IndexOutOfBoundsException("ArrayList size=" +
-                                          String.valueOf(_iSize) + "; " +
-                                          "index=" + String.valueOf(iIndex));
-    oResult = _arData[iIndex];
+    Object result;
+    if (index < 0 || index >= size)
+      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
+                                          size);
+    result = data[index];
     // SEH: no structural change, so don't update modCount
-    _arData[iIndex] = oElement;
-
-    return oResult;
+    data[index] = e;
+    return result;
   }
 
   /**
@@ -418,9 +358,9 @@ public class ArrayList extends AbstractList
    */
   public Object[] toArray()
   {
-    Object[] arObjects = new Object[_iSize];
-    System.arraycopy(_arData, 0, arObjects, 0, _iSize);
-    return arObjects;
+    Object[] array = new Object[size];
+    System.arraycopy(data, 0, array, 0, size);
+    return array;
   }
 
   /**
@@ -429,69 +369,61 @@ public class ArrayList extends AbstractList
    * elements in this ArrayList.  If the passed-in Array is not large enough
    * to store all of the elements in this List, a new Array will be created 
    * and returned; if the passed-in Array is <i>larger</i> than the size
-   * of this List, then size() + 1 index will be set to null.
+   * of this List, then size() index will be set to null.
    *
-   * @param      arObjects      the passed-in Array
+   * @param      array      the passed-in Array
    */
-  public Object[] toArray(Object[] arObjects)
+  public Object[] toArray(Object[] array)
   {
-    Object[] arReturn = (arObjects.length >= _iSize)
-      ? arObjects 
-      : (Object[])
-      Array.newInstance(arObjects.getClass().getComponentType(), _iSize);
-
-    System.arraycopy(_arData, 0, arReturn, 0, _iSize);
-
-    if (arReturn.length > _iSize)
-      arReturn[_iSize] = null;
-
-    return arReturn;
+    if (array.length < size)
+      array = (Object[]) Array.newInstance(array.getClass().getComponentType(), 
+        				   size);
+    else if (array.length > size)
+      array[size] = null;
+    System.arraycopy(data, 0, array, 0, size);
+    return array;
   }
 
   /**
-   * Trims the capacity of tjis List to be equal to its size; 
-   * a memory saver. 
+   * Trims the capacity of this List to be equal to its size; 
+   * a memory saver.   
    */
   public void trimToSize()
   {
-    Object[] arNewData = new Object[_iSize];
-    System.arraycopy(_arData, 0, arNewData, 0, _iSize);
-    modCount++;
-    _arData = arNewData;
+    // not a structural change from the perspective of iterators on this list, 
+    // so don't update modCount
+    Object[] newData = new Object[size];
+    System.arraycopy(data, 0, newData, 0, size);
+    data = newData;
   }
 
-  private void writeObject(ObjectOutputStream oOut)
-    throws IOException
+  private void writeObject(ObjectOutputStream out) throws IOException
   {
     int i;
 
-    ObjectOutputStream.PutField oFields = oOut.putFields();
-    oFields.put("size", _iSize);
-    oOut.writeFields();
+    ObjectOutputStream.PutField fields = out.putFields();
+    fields.put("size", size);
+    out.writeFields();
 
-    oOut.writeInt(_arData.length);
-    for (i = 0; i < _arData.length; i++)
-      oOut.writeObject(_arData[i]);
+    // FIXME: Do we really want to serialize unused list entries??
+    out.writeInt(data.length);
+    for (i = 0; i < data.length; i++)
+      out.writeObject(data[i]);
   }
 
-  private void readObject(ObjectInputStream oIn)
+  private void readObject(ObjectInputStream in)
     throws IOException, ClassNotFoundException
   {
     int i;
-    int iCapacity;
-
-    ObjectInputStream.GetField oFields = oIn.readFields();
-    _iSize = oFields.get("size", 0);
+    int capacity;
 
-    iCapacity = oIn.readInt();
-    _arData = new Object[iCapacity];
+    ObjectInputStream.GetField fields = in.readFields();
+    size = fields.get("size", 0);
 
-    for (i = 0; i < iCapacity; i++)
-      _arData[i] = oIn.readObject();
-  }
+    capacity = in.readInt();
+    data = new Object[capacity];
 
-  private static final boolean doesEqual(Object oOne, Object oTwo)
-  {
-    return ((oOne == null) ? (oTwo == null) : oOne.equals(oTwo));
+    for (i = 0; i < capacity; i++)
+      data[i] = in.readObject();
   }
 }
diff --git a/libjava/java/util/BitSet.java b/libjava/java/util/BitSet.java
index c382bea..5a2dd44 100644
--- a/libjava/java/util/BitSet.java
+++ b/libjava/java/util/BitSet.java
@@ -2,7 +2,7 @@
 
 /* Copyright (C) 1998, 1999, 2000  Free Software Foundation
 
-This file is part of libgcj.
+   This file is part of libgcj.
 
 This software is copyrighted work licensed under the terms of the
 Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
@@ -11,32 +11,64 @@ details.  */
 package java.util;
 import java.io.Serializable;
 
-/**
- * @author Tom Tromey <tromey@cygnus.com>
- * @date October 23, 1998.
- */
-
 /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3
  * hashCode algorithm taken from JDK 1.2 docs.
  */
 
+/**
+ * This class can be thought of in two ways.  You can see it as a
+ * vector of bits or as a set of non-negative integers.  The name
+ * <code>BitSet</code> is a bit misleading.
+ *
+ * It is implemented by a bit vector, but its equally possible to see
+ * it as set of non-negative integer; each integer in the set is
+ * represented by a set bit at the corresponding index.  The size of
+ * this structure is determined by the highest integer in the set.
+ *
+ * You can union, intersect and build (symmetric) remainders, by
+ * invoking the logical operations and, or, andNot, resp. xor.
+ *
+ * This implementation is NOT synchronized against concurrent access from
+ * multiple threads. Specifically, if one thread is reading from a bitset
+ * while another thread is simultaneously modifying it, the results are
+ * undefined.
+ *
+ * @specnote There is some confusion as to whether or not this class should
+ *           be synchronized. JDK 1.1 javadocs explicitly state that the 
+ *           class is NOT synchronized, however the code listed in the JDK 1.3
+ *           javadoc for the hashCode() method implies that it is. It is not
+ *           stated elsewhere in the 1.2 javadoc that the class is 
+ *           synchronized, unlike Hashtable and Vector. From an efficiency 
+ *           perspective, it is very undesirable to synchronize this class
+ *           because multiple locks and explicit lock ordering are required
+ *           to safely synchronize some methods. For this reason we're going
+ *           with the unsynchronized implementation unless the specs are 
+ *           changed to explicitly say otherwise.
+ *
+ * @author Jochen Hoenicke
+ * @author Tom Tromey <tromey@cygnus.com>
+ * @date October 23, 1998.
+ * @status API complete to JDK 1.3.
+ */
 public final class BitSet implements Cloneable, Serializable
 {
-  public void and(BitSet bs)
-  {
-    int max = Math.min(bits.length, bs.bits.length);
-    int i;
-    for (i = 0; i < max; ++i)
-      bits[i] &= bs.bits[i];
-    for (; i < bits.length; ++i)
-      bits[i] = 0;
-  }
-
+  /**
+   * Create a new empty bit set.
+   */
   public BitSet()
   {
     this(64);
   }
 
+  /**
+   * Create a new empty bit set, with a given size.  This
+   * constructor reserves enough space to represent the integers
+   * from <code>0</code> to <code>nbits-1</code>.  
+   * @param nbits the initial size of the bit set.
+   * @throws NegativeArraySizeException if the specified initial
+   * size is negative.  
+   * @require nbits >= 0
+   */
   public BitSet(int nbits)
   {
     if (nbits < 0)
@@ -47,6 +79,49 @@ public final class BitSet implements Cloneable, Serializable
     bits = new long[length];
   }
 
+  /**
+   * Performs the logical AND operation on this bit set and the
+   * given <code>set</code>.  This means it builds the intersection
+   * of the two sets.  The result is stored into this bit set.
+   * @param set the second bit set.
+   * @require set != null
+   */
+  public void and(BitSet bs)
+  {
+    int max = Math.min(bits.length, bs.bits.length);
+    int i;
+    for (i = 0; i < max; ++i)
+      bits[i] &= bs.bits[i];
+    for (; i < bits.length; ++i)
+      bits[i] = 0;
+  }
+
+  /**
+   * Performs the logical AND operation on this bit set and the
+   * complement of the given <code>set</code>.  This means it
+   * selects every element in the first set, that isn't in the
+   * second set.  The result is stored into this bit set.  
+   * @param set the second bit set.  
+   * @require set != null
+   * @since JDK1.2
+   */
+  public void andNot(BitSet bs)
+  {
+    int max = Math.min(bits.length, bs.bits.length);
+    int i;
+    for (i = 0; i < max; ++i)
+      bits[i] &= ~bs.bits[i];
+  }
+
+  /**
+   * Removes the integer <code>bitIndex</code> from this set. That is
+   * the corresponding bit is cleared.  If the index is not in the set,
+   * this method does nothing.
+   * @param bitIndex a non-negative integer.
+   * @exception ArrayIndexOutOfBoundsException if the specified bit index
+   * is negative.
+   * @require bitIndex >= 0
+   */
   public void clear(int pos)
   {
     if (pos < 0)
@@ -57,6 +132,12 @@ public final class BitSet implements Cloneable, Serializable
     bits[offset] &= ~(1L << bit);
   }
 
+  /**
+   * Create a clone of this bit set, that is an instance of the same
+   * class and contains the same elements.  But it doesn't change when
+   * this bit set changes.
+   * @return the clone of this object.
+   */
   public Object clone()
   {
     BitSet bs = new BitSet(bits.length * 64);
@@ -64,6 +145,11 @@ public final class BitSet implements Cloneable, Serializable
     return bs;
   }
 
+  /**
+   * Returns true if the <code>obj</code> is a bit set that contains
+   * exactly the same elements as this bit set, otherwise false.
+   * @return true if obj equals this bit set.
+   */
   public boolean equals(Object obj)
   {
     if (!(obj instanceof BitSet))
@@ -84,6 +170,15 @@ public final class BitSet implements Cloneable, Serializable
     return true;
   }
 
+  /**
+   * Returns true if the integer <code>bitIndex</code> is in this bit
+   * set, otherwise false.
+   * @param bitIndex a non-negative integer
+   * @return the value of the bit at the specified index.
+   * @exception ArrayIndexOutOfBoundsException if the specified bit index
+   * is negative.
+   * @require bitIndex >= 0
+   */
   public boolean get(int pos)
   {
     if (pos < 0)
@@ -98,6 +193,36 @@ public final class BitSet implements Cloneable, Serializable
     return (bits[offset] & (1L << bit)) == 0 ? false : true;
   }
 
+  /**
+   * Returns a hash code value for this bit set.  The hash code of 
+   * two bit sets containing the same integers is identical.  The algorithm
+   * used to compute it is as follows:
+   *
+   * Suppose the bits in the BitSet were to be stored in an array of
+   * long integers called <code>bits</code>, in such a manner that
+   * bit <code>k</code> is set in the BitSet (for non-negative values
+   * of <code>k</code>) if and only if
+   *
+   * <pre>
+   * ((k/64) < bits.length) && ((bits[k/64] & (1L << (bit % 64))) != 0)
+   * </pre>
+   *
+   * Then the following definition of the hashCode method
+   * would be a correct implementation of the actual algorithm:
+   *
+   * <pre>
+   * public int hashCode() {
+   *     long h = 1234;
+   *     for (int i = bits.length-1; i>=0; i--) {
+   *         h ^= bits[i] * (i + 1);
+   *     }
+   *     return (int)((h >> 32) ^ h);
+   * }
+   * </pre>
+   *
+   * Note that the hash code values changes, if the set is changed.
+   * @return the hash code value for this bit set.
+   */
   public int hashCode()
   {
     long h = 1234;
@@ -106,6 +231,45 @@ public final class BitSet implements Cloneable, Serializable
     return (int) ((h >> 32) ^ h);
   }
 
+  /**
+   * Returns the logical number of bits actually used by this bit
+   * set.  It returns the index of the highest set bit plus one.
+   * Note that this method doesn't return the number of set bits.
+   * @return the index of the highest set bit plus one.  
+   */
+  public int length()
+  {
+    // Set i to highest index that contains a non-zero value.
+    int i;
+    for (i = bits.length - 1; i >= 0 && bits[i] == 0; --i)
+      ;
+
+    // if i < 0 all bits are cleared.
+    if (i < 0)
+      return 0;
+
+    // Now determine the exact length.
+    long b = bits[i];
+    int len = (i + 1) * 64;
+    // b >= 0 checks if the highest bit is zero.
+    while (b >= 0)
+      {
+	--len;
+	b <<= 1;
+      }
+
+    return len;
+  }
+
+  /**
+   * Performs the logical OR operation on this bit set and the
+   * given <code>set</code>.  This means it builds the union
+   * of the two sets.  The result is stored into this bit set, which
+   * grows as necessary.
+   * @param set the second bit set.
+   * @exception OutOfMemoryError if the current set can't grow.
+   * @require set != null
+   */
   public void or(BitSet bs)
   {
     ensure(bs.bits.length - 1);
@@ -114,6 +278,16 @@ public final class BitSet implements Cloneable, Serializable
       bits[i] |= bs.bits[i];
   }
 
+  /**
+   * Add the integer <code>bitIndex</code> to this set.  That is 
+   * the corresponding bit is set to true.  If the index was already in
+   * the set, this method does nothing.  The size of this structure
+   * is automatically increased as necessary.
+   * @param bitIndex a non-negative integer.
+   * @exception ArrayIndexOutOfBoundsException if the specified bit index
+   * is negative.
+   * @require bitIndex >= 0
+   */
   public void set(int pos)
   {
     if (pos < 0)
@@ -124,35 +298,58 @@ public final class BitSet implements Cloneable, Serializable
     bits[offset] |= 1L << bit;
   }
 
+  /**
+   * Returns the number of bits actually used by this bit set.  Note
+   * that this method doesn't return the number of set bits.
+   * @returns the number of bits currently used.  
+   */
   public int size()
   {
     return bits.length * 64;
   }
 
+  /**
+   * Returns the string representation of this bit set.  This
+   * consists of a comma separated list of the integers in this set
+   * surrounded by curly braces.  There is a space after each comma.
+   * @return the string representation.
+   */
   public String toString()
   {
-    StringBuffer result = new StringBuffer("{");
+    String r = "{";
     boolean first = true;
     for (int i = 0; i < bits.length; ++i)
       {
-	int bit = 1;
+	long bit = 1;
 	long word = bits[i];
+	if (word == 0)
+	  continue;
 	for (int j = 0; j < 64; ++j)
 	  {
 	    if ((word & bit) != 0)
 	      {
 		if (!first)
-		  result.append(", ");
-		result.append(64 * i + j);
+		  r += ", ";
+		r += Integer.toString(64 * i + j);
 		first = false;
 	      }
 	    bit <<= 1;
 	  }
       }
 
-    return result.append("}").toString();
+    return r += "}";
   }
 
+  /**
+   * Performs the logical XOR operation on this bit set and the
+   * given <code>set</code>.  This means it builds the symmetric
+   * remainder of the two sets (the elements that are in one set,
+   * but not in the other).  The result is stored into this bit set,
+   * which grows as necessary.  
+   * @param set the second bit set.
+   * @exception OutOfMemoryError if the current set can't grow.  
+   * @require set != null
+   */
   public void xor(BitSet bs)
   {
     ensure(bs.bits.length - 1);
@@ -173,6 +370,7 @@ public final class BitSet implements Cloneable, Serializable
   }
 
   // The actual bits.
-  private long[] bits;
+  long[] bits;
+
   private static final long serialVersionUID = 7997698588986878753L;
 }