ArrayList.java, [...]: Imported from GNU Classpath.

2000-08-27  Anthony Green  <green@redhat.com>

	* java/util/ArrayList.java, java/util/Timer.java,
	java/util/LinkedList.java, java/util/TimerTask.java,
	java/util/HashMap.java, java/util/AbstractMap.java,
	java/util/SortedMap.java, java/util/AbstractSequentialList.java,
	java/util/SortedSet.java: Imported from GNU Classpath.
	* Makefile.in: Rebuilt.
	* Makefile.am: Added new files.

From-SVN: r36006

12 files changed, 3112 insertions, 10 deletions

diff --git a/libjava/ChangeLog b/libjava/ChangeLog
index 8356ea3..222bb3c 100644
--- a/libjava/ChangeLog
+++ b/libjava/ChangeLog
@@ -1,3 +1,13 @@
+2000-08-27  Anthony Green  <green@redhat.com>
+
+	* java/util/ArrayList.java, java/util/Timer.java,
+	java/util/LinkedList.java, java/util/TimerTask.java,
+	java/util/HashMap.java, java/util/AbstractMap.java,
+	java/util/SortedMap.java, java/util/AbstractSequentialList.java,
+	java/util/SortedSet.java: Imported from GNU Classpath.
+	* Makefile.in: Rebuilt.
+	* Makefile.am: Added new files.
+	
 2000-08-26  Anthony Green  <green@redhat.com>
 
 	* Makefile.in: Rebuilt.
diff --git a/libjava/Makefile.am b/libjava/Makefile.am
index 7413f26..403333a 100644
--- a/libjava/Makefile.am
+++ b/libjava/Makefile.am
@@ -1030,7 +1030,10 @@ java/text/SimpleDateFormat.java	\
 java/text/StringCharacterIterator.java \
 java/util/AbstractCollection.java \
 java/util/AbstractList.java \
+java/util/AbstractMap.java \
+java/util/AbstractSequentialList.java \
 java/util/AbstractSet.java \
+java/util/ArrayList.java \
 java/util/Arrays.java \
 java/util/BasicMapEntry.java \
 java/util/BitSet.java \
@@ -1046,6 +1049,7 @@ java/util/Enumeration.java \
 java/util/EventListener.java \
 java/util/EventObject.java \
 java/util/GregorianCalendar.java \
+java/util/HashMap.java \
 java/util/Hashtable.java \
 java/util/Iterator.java	\
 java/util/List.java \
@@ -1064,9 +1068,13 @@ java/util/Random.java \
 java/util/ResourceBundle.java \
 java/util/Set.java \
 java/util/SimpleTimeZone.java \
+java/util/SortedMap.java \
+java/util/SortedSet.java \
 java/util/Stack.java \
 java/util/StringTokenizer.java \
 java/util/TimeZone.java	\
+java/util/Timer.java \
+java/util/TimerTask.java \
 java/util/TooManyListenersException.java \
 java/util/Vector.java \
 java/util/jar/Attributes.java \
diff --git a/libjava/Makefile.in b/libjava/Makefile.in
index 3ed381f..afa1383 100644
--- a/libjava/Makefile.in
+++ b/libjava/Makefile.in
@@ -799,7 +799,10 @@ java/text/SimpleDateFormat.java	\
 java/text/StringCharacterIterator.java \
 java/util/AbstractCollection.java \
 java/util/AbstractList.java \
+java/util/AbstractMap.java \
+java/util/AbstractSequentialList.java \
 java/util/AbstractSet.java \
+java/util/ArrayList.java \
 java/util/Arrays.java \
 java/util/BasicMapEntry.java \
 java/util/BitSet.java \
@@ -815,6 +818,7 @@ java/util/Enumeration.java \
 java/util/EventListener.java \
 java/util/EventObject.java \
 java/util/GregorianCalendar.java \
+java/util/HashMap.java \
 java/util/Hashtable.java \
 java/util/Iterator.java	\
 java/util/List.java \
@@ -833,9 +837,13 @@ java/util/Random.java \
 java/util/ResourceBundle.java \
 java/util/Set.java \
 java/util/SimpleTimeZone.java \
+java/util/SortedMap.java \
+java/util/SortedSet.java \
 java/util/Stack.java \
 java/util/StringTokenizer.java \
 java/util/TimeZone.java	\
+java/util/Timer.java \
+java/util/TimerTask.java \
 java/util/TooManyListenersException.java \
 java/util/Vector.java \
 java/util/jar/Attributes.java \
@@ -1429,26 +1437,30 @@ DEP_FILES =  .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.P \
 .deps/java/text/RuleBasedCollator.P .deps/java/text/SimpleDateFormat.P \
 .deps/java/text/StringCharacterIterator.P \
 .deps/java/util/AbstractCollection.P .deps/java/util/AbstractList.P \
-.deps/java/util/AbstractSet.P .deps/java/util/Arrays.P \
-.deps/java/util/BasicMapEntry.P .deps/java/util/BitSet.P \
-.deps/java/util/Bucket.P .deps/java/util/Calendar.P \
-.deps/java/util/Collection.P .deps/java/util/Comparator.P \
+.deps/java/util/AbstractMap.P .deps/java/util/AbstractSequentialList.P \
+.deps/java/util/AbstractSet.P .deps/java/util/ArrayList.P \
+.deps/java/util/Arrays.P .deps/java/util/BasicMapEntry.P \
+.deps/java/util/BitSet.P .deps/java/util/Bucket.P \
+.deps/java/util/Calendar.P .deps/java/util/Collection.P \
+.deps/java/util/Comparator.P \
 .deps/java/util/ConcurrentModificationException.P \
 .deps/java/util/Date.P .deps/java/util/Dictionary.P \
 .deps/java/util/EmptyStackException.P .deps/java/util/Enumeration.P \
 .deps/java/util/EventListener.P .deps/java/util/EventObject.P \
-.deps/java/util/GregorianCalendar.P .deps/java/util/Hashtable.P \
-.deps/java/util/Iterator.P .deps/java/util/List.P \
-.deps/java/util/ListIterator.P .deps/java/util/ListResourceBundle.P \
-.deps/java/util/Locale.P .deps/java/util/Map.P \
-.deps/java/util/MissingResourceException.P \
+.deps/java/util/GregorianCalendar.P .deps/java/util/HashMap.P \
+.deps/java/util/Hashtable.P .deps/java/util/Iterator.P \
+.deps/java/util/List.P .deps/java/util/ListIterator.P \
+.deps/java/util/ListResourceBundle.P .deps/java/util/Locale.P \
+.deps/java/util/Map.P .deps/java/util/MissingResourceException.P \
 .deps/java/util/NoSuchElementException.P .deps/java/util/Observable.P \
 .deps/java/util/Observer.P .deps/java/util/Properties.P \
 .deps/java/util/PropertyPermission.P \
 .deps/java/util/PropertyResourceBundle.P .deps/java/util/Random.P \
 .deps/java/util/ResourceBundle.P .deps/java/util/Set.P \
-.deps/java/util/SimpleTimeZone.P .deps/java/util/Stack.P \
+.deps/java/util/SimpleTimeZone.P .deps/java/util/SortedMap.P \
+.deps/java/util/SortedSet.P .deps/java/util/Stack.P \
 .deps/java/util/StringTokenizer.P .deps/java/util/TimeZone.P \
+.deps/java/util/Timer.P .deps/java/util/TimerTask.P \
 .deps/java/util/TooManyListenersException.P .deps/java/util/Vector.P \
 .deps/java/util/jar/Attributes.P .deps/java/util/jar/JarEntry.P \
 .deps/java/util/jar/JarException.P .deps/java/util/jar/JarFile.P \
diff --git a/libjava/java/util/AbstractMap.java b/libjava/java/util/AbstractMap.java
new file mode 100644
index 0000000..4935afe
--- /dev/null
+++ b/libjava/java/util/AbstractMap.java
@@ -0,0 +1,283 @@
+/* AbstractMap.java -- Abstract implementation of most of Map
+   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+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
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+// TO DO:
+// comments
+// test suite
+
+package java.util;
+
+public abstract class AbstractMap implements Map {
+  
+  public void clear()
+  {
+    entrySet().clear();
+  }
+
+  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;
+    }
+
+    return false;
+  }
+
+  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; 
+  }
+
+  public abstract Set entrySet();
+
+  public boolean equals( Object o )
+  {
+    if( this == o )
+      return true;
+    
+    if( o == null || !( o instanceof Map ) )
+      return false;
+    
+    Map m = (Map)o;
+    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;    
+  }
+
+  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();
+    }
+
+    return null;
+  }
+
+  public int hashCode()
+  {
+    int hashcode = 0;
+    Iterator entries = entrySet().iterator();
+  
+    while( entries.hasNext() )
+      hashcode += entries.next().hashCode();
+
+    return hashcode;
+  }
+
+  public boolean isEmpty()
+  {
+    return size() == 0;
+  }
+
+  public Set keySet()
+  {
+    if( this.keySet == null )
+    {
+      this.keySet =
+	new AbstractSet()
+	{
+	  public int size()
+          {
+	    return AbstractMap.this.size();
+	  }
+
+	  public boolean contains(Object key)
+	  {
+	    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();
+	      }
+	      
+	      public void remove()
+              {
+		map_iterator.remove();
+	      }
+	    };
+	  }
+	};
+    }
+    
+    return this.keySet;    
+  }
+
+  public Object put( Object key, Object value )
+  {
+    throw new UnsupportedOperationException();
+  }
+
+  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() );
+    }
+  }
+
+  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 ) )
+      {
+	value = entry.getValue();
+	entries.remove();
+	return value;
+      }
+    }
+
+    return null;    
+  }
+
+  public int size()
+  {
+    return entrySet().size();
+  }
+
+  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();
+  }
+
+  public Collection values()
+  {
+    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();
+	      }
+	      
+	      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
new file mode 100644
index 0000000..69bdc4a
--- /dev/null
+++ b/libjava/java/util/AbstractSequentialList.java
@@ -0,0 +1,113 @@
+/* AbstractSequentialList.java -- List implementation for sequential access
+   Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+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
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+// TO DO:
+// ~ Lots of doc comments still missing.
+// ~ The class comment should include a description of what should be overridden
+//   to provide what features, as should the listIterator comment.
+
+package java.util;
+
+/**
+ * Abstract superclass to make it easier to implement the List interface when
+ * backed by a sequential-access store, such as a linked list.
+ */
+public abstract class AbstractSequentialList extends AbstractList {
+
+  /**
+   * Returns a ListIterator over the list, starting from position index.
+   * Subclasses must provide an implementation of this method.
+   *
+   * @exception IndexOutOfBoundsException if index < 0 || index > size()
+   */
+  public abstract ListIterator listIterator(int index);
+
+  /**
+   * Add an element to the list at a given index. This implementation obtains a
+   * ListIterator positioned at the specified index, and then adds the element
+   * using the ListIterator's add method.
+   *
+   * @param index the position to add the element
+   * @param o the element to insert
+   * @exception IndexOutOfBoundsException if index < 0 || index > size()
+   * @exception UnsupportedOperationException if the iterator returned by
+   *   listIterator(index) does not support the add method.
+   */
+  public void add(int index, Object o) {
+    ListIterator i = listIterator(index);
+    i.add(o);
+  }
+
+  public boolean addAll(int index, Collection c) {
+    boolean changed = false;
+    Iterator ci = c.iterator();
+    ListIterator i = listIterator(index);
+    while (ci.hasNext()) {
+      i.add(ci.next());
+      changed = true;
+    }
+    return changed;
+  }
+
+  public Object get(int index) {
+    ListIterator i = listIterator(index);
+    if (!i.hasNext()) {
+      throw new IndexOutOfBoundsException();
+    }
+    return i.next();
+  }
+
+  /**
+   * Return an Iterator over this List. This implementation returns
+   * listIterator().
+   *
+   * @return an Iterator over this List
+   */
+  public Iterator iterator() {
+    return listIterator();
+  }
+
+  public Object remove(int index) {
+    ListIterator i = listIterator(index);
+    if (!i.hasNext()) {
+      throw new IndexOutOfBoundsException();
+    }
+    Object removed = i.next();
+    i.remove();
+    return removed;
+  }
+
+  public Object set(int index, Object o) {
+    ListIterator i = listIterator(index);
+    if (!i.hasNext()) {
+      throw new IndexOutOfBoundsException();
+    }
+    Object old = i.next();
+    i.set(o);
+    return old;
+  }
+}
diff --git a/libjava/java/util/ArrayList.java b/libjava/java/util/ArrayList.java
new file mode 100644
index 0000000..7e6562c
--- /dev/null
+++ b/libjava/java/util/ArrayList.java
@@ -0,0 +1,497 @@
+/* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed
+   implementation of the List interface
+   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+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
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.util;
+
+import java.lang.reflect.Array;
+import java.io.Serializable;
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.ObjectStreamField;
+
+/**
+ * An array-backed implementation of the List interface.  ArrayList
+ * performs well on simple tasks:  random access into a list, appending
+ * 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 $
+ * @see           java.util.AbstractList
+ * @see           java.util.List
+ */
+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;
+
+  /** where the data is stored */
+  Object[] _arData;
+
+  /** used for serialization -- denotes which fields are serialized */
+  private static final ObjectStreamField[] serialPersistentFields =
+  {new ObjectStreamField("size", int.class)};
+
+  /** 
+   * Construct a new ArrayList with the supplied initial capacity. 
+   *
+   * @param     iCapacity
+   */
+  public ArrayList(int iCapacity)
+  {
+    _arData = new Object[iCapacity];
+  }
+
+
+  /**
+   * Construct a new ArrayList with the default capcity 
+   */
+  public ArrayList()
+  {
+    this(DEFAULT_CAPACITY);
+  }
+
+  /** 
+   * Construct a new ArrayList, and initialize it with the elements
+   * 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
+   */
+  public ArrayList(Collection oCollection)
+  {
+    this((int) (oCollection.size() * 1.1));
+    addAll(oCollection);
+  }
+
+  /**
+   * Guarantees that this list will have at least enough capacity to
+   * hold iMinCapacity elements.
+   *
+   * @param      iMinCapacity     the minimum guaranteed capacity
+   */
+  public void ensureCapacity(int iMinCapacity)
+  {
+    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;
+    }
+  }
+
+  /**
+   * Appends the supplied element to the end of this list.
+   *
+   * @param       oElement      the element to be appended to this list
+   */
+  public boolean add(Object oElement)
+  {
+    ensureCapacity(_iSize + 1);
+    _arData[_iSize++] = oElement;
+    modCount++;
+    return true;
+  }
+
+  /**
+   * Retrieves the element at the user-supplied index.
+   *
+   * @param    iIndex        the index of the element we are fetching
+   * @throws   IndexOutOfBoundsException  (iIndex < 0) || (iIndex >= size())
+   */
+  public Object get(int iIndex)
+  {
+    if (iIndex >= _iSize)
+      throw new IndexOutOfBoundsException("ArrayList size=" +
+                                          String.valueOf(_iSize) + "; " +
+                                          "index=" + String.valueOf(iIndex));
+    return _arData[iIndex];
+  }
+
+  /**
+   * Returns the number of elements in this list 
+   */
+  public int size()
+  {
+    return _iSize;
+  }
+
+  /**
+   * Removes the element at the user-supplied index
+   *
+   * @param     iIndex      the index of the element to be removed
+   * @return    the removed Object
+   * @throws    IndexOutOfBoundsException  (iIndex < 0) || (iIndex >= size())
+   */
+  public Object remove(int iIndex)
+  {
+    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;
+  }
+
+  /**
+   * 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 
+   *                         removed
+   */
+  public void removeRange(int iFromIndex, int iToIndex)
+  {
+    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;
+    }
+  }
+
+  /**
+   * 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
+   */
+  public void add(int iIndex, Object oElement)
+  {
+    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++;
+  }
+
+  /** 
+   * Add each element in the supplied Collection to this List.
+   *
+   * @param        oCollection     a Collection containing elements to be 
+   *                               added to this List
+   */
+  public boolean addAll(Collection oCollection)
+  {
+    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;
+  }
+
+  /** 
+   * 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
+   */
+  public boolean addAll(int iIndex, Collection oCollection)
+  {
+    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;
+
+      itElements = oCollection.iterator();
+      while (itElements.hasNext())
+        _arData[iIndex++] = itElements.next();
+
+      return true;
+   }
+    return false;
+  }
+
+  /**
+   * Creates a shallow copy of this ArrayList
+   */
+  public Object clone()
+  {
+    ArrayList oClone;
+
+    try
+    {
+      oClone = (ArrayList) super.clone();
+      oClone._arData = _arData;
+      oClone._iSize = _iSize;
+    }
+    catch(CloneNotSupportedException e)
+    {
+      oClone = null;
+    }
+    return oClone;
+  }
+
+  /** 
+   * Returns true iff oElement is in this ArrayList.
+   *
+   * @param     oElement     the element whose inclusion in the List is being
+   *                         tested
+   */
+  public boolean contains(Object oElement)
+  {
+    return (indexOf(oElement) != -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
+   */
+  public int indexOf(Object oElement)
+  {
+    int i;
+
+    for (i = 0; i < _iSize; i++)
+    {
+      if (doesEqual(oElement, _arData[i]))
+        return i;
+    }
+    return -1;
+  }
+
+  /**
+   * 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
+   */
+  public int lastIndexOf(Object oElement)
+  {
+    int i;
+
+    for (i = _iSize - 1; i >= 0; i--)
+    {
+      if (doesEqual(oElement, _arData[i]))
+        return i;
+    }
+    return -1;
+  }
+
+  /**
+   * Removes all elements from this List
+   */
+  public void clear()
+  {
+    int i;
+
+    if (_iSize > 0)
+    {
+      modCount++;
+      _iSize = 0;
+
+      for (i = 0; i < _iSize; i++)
+        _arData[i] = null;
+    }      
+  }
+
+  /**
+   * 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
+   * @return    the element previously at the specified index, or null if
+   *            none was there
+   */
+  public Object set(int iIndex, Object oElement)
+  {
+    Object oResult;
+
+    if (iIndex >= _iSize)
+      throw new IndexOutOfBoundsException("ArrayList size=" +
+                                          String.valueOf(_iSize) + "; " +
+                                          "index=" + String.valueOf(iIndex));
+    oResult = _arData[iIndex];
+    // SEH: no structural change, so don't update modCount
+    _arData[iIndex] = oElement;
+
+    return oResult;
+  }
+
+  /**
+   * Returns an Object Array containing all of the elements in this ArrayList
+   */
+  public Object[] toArray()
+  {
+    Object[] arObjects = new Object[_iSize];
+    System.arraycopy(_arData, 0, arObjects, 0, _iSize);
+    return arObjects;
+  }
+
+  /**
+   * Returns an Array whse component type is the runtime component type of
+   * the passes-in Array.  The returned Array is populated with all of the
+   * 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.
+   *
+   * @param      arObjects      the passed-in Array
+   */
+  public Object[] toArray(Object[] arObjects)
+  {
+    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;
+  }
+
+  /**
+   * Trims the capacity of tjis 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;
+  }
+
+  private void writeObject(ObjectOutputStream oOut)
+    throws IOException
+  {
+    int i;
+
+    ObjectOutputStream.PutField oFields = oOut.putFields();
+    oFields.put("size", _iSize);
+    oOut.writeFields();
+
+    oOut.writeInt(_arData.length);
+    for (i = 0; i < _arData.length; i++)
+      oOut.writeObject(_arData[i]);
+  }
+
+  private void readObject(ObjectInputStream oIn)
+    throws IOException, ClassNotFoundException
+  {
+    int i;
+    int iCapacity;
+
+    ObjectInputStream.GetField oFields = oIn.readFields();
+    _iSize = oFields.get("size", 0);
+
+    iCapacity = oIn.readInt();
+    _arData = new Object[iCapacity];
+
+    for (i = 0; i < iCapacity; i++)
+      _arData[i] = oIn.readObject();
+  }
+
+  private static final boolean doesEqual(Object oOne, Object oTwo)
+  {
+    return ((oOne == null) ? (oTwo == null) : oOne.equals(oTwo));
+  }
+}
diff --git a/libjava/java/util/HashMap.java b/libjava/java/util/HashMap.java
new file mode 100644
index 0000000..5d50660
--- /dev/null
+++ b/libjava/java/util/HashMap.java
@@ -0,0 +1,858 @@
+/* HashMap.java -- a class providing a basic hashtable data structure,
+   mapping Object --> Object
+   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+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
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.util;
+
+import java.io.IOException;
+import java.io.Serializable;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.ObjectStreamField;
+
+/**
+ * This class provides a hashtable-backed implementation of the
+ * Map interface.  
+ *
+ * It uses a hash-bucket approach; that is, hash
+ * collisions are handled by linking the new node off of the
+ * pre-existing node (or list of nodes).  In this manner, techniques 
+ * such as linear probing (which can casue primary clustering) and 
+ * rehashing (which does not fit very well with Java's method of 
+ * precomputing hash codes) are avoided.  
+ *
+ * Under ideal circumstances (no collisions, HashMap offers O(1) 
+ * performance on most operations (<pre>containsValue()</pre> is,
+ * of course, O(n)).  In the worst case (all keys map to the same 
+ * hash code -- very unlikely), most operations are O(n).
+ *
+ * HashMap is part of the JDK1.2 Collections API.  It differs from 
+ * Hashtable in that it accepts the null key and null values, and it
+ * does not support "Enumeration views."
+ *
+ * @author         Jon Zeppieri
+ * @version        $Revision: 1.6 $
+ * @modified       $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+ */
+public class HashMap extends AbstractMap 
+    implements Map, Cloneable, Serializable
+{
+    // STATIC (CLASS) VARIABLES ------------------------------------------
+
+    /** 
+     * the default capacity for an instance of HashMap -- I think this
+     * is low, and perhaps it shoudl be raised; Sun's documentation mildly
+     * suggests that this (11) is the correct value, though
+     */
+    private static final int DEFAULT_CAPACITY = 11;
+
+    /** the default load factor of a HashMap */
+    private static final float DEFAULT_LOAD_FACTOR = 0.75F;
+
+    /** used internally to represent the null key */
+    private static final HashMap.Null NULL_KEY = new HashMap.Null();
+
+    /** used internally to parameterize the creation of set/collection views */
+    private static final int KEYS = 0;
+
+    /** used internally to parameterize the creation of set/collection views */
+    private static final int VALUES = 1;
+
+    /** used internally to parameterize the creation of set/collection views */
+    private static final int ENTRIES = 2;
+
+    private static final long serialVersionUID = 362498820763181265L;
+
+    // INSTANCE VARIABLES -------------------------------------------------
+
+    /** the capacity of this HashMap:  denotes the size of the bucket array */
+    transient int capacity;
+
+    /** the size of this HashMap:  denotes the number of key-value pairs */
+    private transient int size;
+
+    /** the load factor of this HashMap:  used in computing the threshold 
+     * @serial
+     */
+    float loadFactor;
+
+    /* the rounded product of the capacity and the load factor; when the number of
+     * elements exceeds the threshold, the HashMap calls <pre>rehash()</pre>
+     * @serial
+     */
+    private int threshold;
+
+    /** 
+     * this data structure contains the actual key-value mappings; a
+     * <pre>BucketList</pre> is a lightweight linked list of "Buckets",
+     * which, in turn, are linked nodes containing a key-value mapping 
+     * and a reference to the "next" Bucket in the list
+     */
+    private transient Bucket[] buckets;
+
+    /** 
+     * counts the number of modifications this HashMap has undergone; used by Iterators
+     * to know when to throw ConcurrentModificationExceptions (idea ripped-off from
+     * Stuart Ballard's AbstractList implementation) 
+     */
+    private transient int modCount;
+
+
+    // CONSTRUCTORS ---------------------------------------------------------
+    
+    /**
+     * construct a new HashMap with the default capacity and the default
+     * load factor
+     */
+    public HashMap()
+    {
+	init(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
+    }
+
+    /**
+     * construct a new HashMap with a specific inital capacity and load factor
+     *
+     * @param   initialCapacity     the initial capacity of this HashMap (>=0)
+     * @param   initialLoadFactor   the load factor of this HashMap 
+     *                              (a misnomer, really, since the load factor of
+     *                              a HashMap does not change)
+     * 
+     * @throws   IllegalArgumentException    if (initialCapacity < 0) ||
+     *                                          (initialLoadFactor > 1.0) ||
+     *                                          (initialLoadFactor <= 0.0)
+     */
+    public HashMap(int initialCapacity, float initialLoadFactor)
+	throws IllegalArgumentException
+    {
+	if (initialCapacity < 0 || initialLoadFactor <= 0 || initialLoadFactor > 1)
+	    throw new IllegalArgumentException();
+	else
+	    init(initialCapacity, initialLoadFactor);
+    }
+
+    /**
+     * construct a new HashMap with a specific inital capacity 
+     *
+     * @param   initialCapacity     the initial capacity of this HashMap (>=0)
+     *
+     * @throws   IllegalArgumentException    if (initialCapacity < 0)
+     */
+    public HashMap(int initialCapacity)	
+	throws IllegalArgumentException 
+    {
+	if (initialCapacity < 0)
+	    throw new IllegalArgumentException();
+	else
+	    init(initialCapacity, DEFAULT_LOAD_FACTOR);
+    }
+
+    /**
+     * construct a new HashMap from the given Map
+     * 
+     * every element in Map t will be put into this new HashMap
+     *
+     * @param     t        a Map whose key / value pairs will be put into
+     *                     the new HashMap.  <b>NOTE: key / value pairs
+     *                     are not cloned in this constructor</b>
+     */
+    public HashMap(Map t)
+    {
+	int mapSize = t.size() * 2;
+	init(((mapSize > DEFAULT_CAPACITY) ? mapSize : DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
+	putAll(t);
+    }
+
+
+    // PUBLIC METHODS ---------------------------------------------------------
+
+    /** returns the number of kay-value mappings currently in this Map */
+    public int size()
+    {
+	return size;
+    }
+
+    /** returns true if there are no key-value mappings currently in this Map */
+    public boolean isEmpty()
+    {
+	return size == 0;
+    }
+
+    /** empties this HashMap of all elements */
+    public void clear()
+    {
+	size = 0;
+	modCount++;
+	buckets = new Bucket[capacity];
+    }
+
+    /** 
+     * returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but
+     * its contents are not)
+     */
+    public Object clone()
+    {
+	Map.Entry entry;
+	Iterator it = entrySet().iterator();
+	HashMap clone = new HashMap(capacity, loadFactor);
+	while (it.hasNext())
+	    {
+		entry = (Map.Entry) it.next();
+		clone.internalPut(entry.getKey(), entry.getValue());
+	    }
+	return clone;
+    }
+
+    /** returns a "set view" of this HashMap's keys */
+    public Set keySet()
+    {
+	return new HashMapSet(KEYS);
+    }
+
+    /** returns a "set view" of this HashMap's entries */
+    public Set entrySet()
+    {
+	return new HashMapSet(ENTRIES);
+    }
+
+    /** returns a "collection view" (or "bag view") of this HashMap's values */
+    public Collection values()
+    {
+	return new HashMapCollection();
+    }
+
+    /** 
+     * returns true if the supplied object equals (<pre>equals()</pre>) a key
+     * in this HashMap 
+     *
+     * @param       key        the key to search for in this HashMap
+     */
+    public boolean containsKey(Object key)
+    {
+	return (internalGet(key) != null);
+    }
+    
+    /**
+     * returns true if this HashMap contains a value <pre>o</pre>, such that
+     * <pre>o.equals(value)</pre>.
+     *
+     * @param      value       the value to search for in this Hashtable
+     */
+    public boolean containsValue(Object value)
+    {
+	int i;
+	Bucket list;
+
+	for (i = 0; i < capacity; i++)
+	    {
+		list = buckets[i];
+		if (list != null && list.containsValue(value))
+		    return true;
+	    }
+	return false;
+    }
+    
+    /*
+     * return the value in this Hashtable associated with the supplied key, or <pre>null</pre>
+     * if the key maps to nothing
+     *
+     * @param     key      the key for which to fetch an associated value
+     */
+    public Object get(Object key)
+    {
+	Map.Entry oResult = internalGet(key);
+	return (oResult == null) ? null : oResult.getValue();
+    }
+
+    /**
+     * puts the supplied value into the Map, mapped by the supplied key
+     *
+     * @param       key        the HashMap key used to locate the value
+     * @param       value      the value to be stored in the HashMap
+     */
+    public Object put(Object key, Object value)
+    {
+	return internalPut(key, value);
+    }
+
+    /**
+     * removes from the HashMap and returns the value which is mapped by the 
+     * supplied key; if the key maps to nothing, then the HashMap remains unchanged,
+     * and <pre>null</pre> is returned
+     *
+     * @param    key     the key used to locate the value to remove from the HashMap
+     */
+    public Object remove(Object key)
+    {
+	Bucket list;
+	int index;
+	Object result = null;
+	if (size > 0)
+	    {
+		index = hash(((key == null) ? NULL_KEY : key));
+		list = buckets[index];
+		if (list != null)
+		    {
+			result = list.removeByKey(key);
+			if (result != null)
+			    {
+				size--;
+				modCount++;
+				if (list.first == null)
+				    buckets[index] = null;
+			    }
+		    }
+	    }
+	return result;
+    }
+
+
+    // PRIVATE METHODS -----------------------------------------------------------
+
+    /** 
+     * puts the given key-value pair into this HashMap; a private method is used
+     * because it is called by the rehash() method as well as the put() method,
+     * and if a subclass overrides put(), then rehash would do funky things
+     * if it called put()
+     *
+     * @param       key        the HashMap key used to locate the value
+     * @param       value      the value to be stored in the HashMap
+     */
+  private Object internalPut(Object key, Object value)
+    {
+	HashMapEntry entry;
+	Bucket list;
+	int hashIndex;
+	Object oResult;
+	Object oRealKey = ((key == null) ? NULL_KEY : key);
+
+	entry = new HashMapEntry(oRealKey, value);
+	hashIndex = hash(oRealKey);
+	list = buckets[hashIndex];
+	if (list == null)
+	  {
+	    list = new Bucket();
+	    buckets[hashIndex] = list;
+	  }
+	oResult = list.add(entry);
+	if (oResult == null)
+	    {
+	        modCount++;
+		if (size++ == threshold)
+		    rehash();
+		return null;
+	    }
+	else
+	    {
+		// SEH: if key already exists, we don't rehash & we don't update the modCount
+		// because it is not a "structural" modification
+		return oResult;
+	    }
+    }
+
+    /** 
+     * a private method, called by all of the constructors to initialize a new HashMap
+     *
+     * @param   initialCapacity     the initial capacity of this HashMap (>=0)
+     * @param   initialLoadFactor   the load factor of this HashMap 
+     *                              (a misnomer, really, since the load factor of
+     *                              a HashMap does not change)
+     */ 
+    private void init(int initialCapacity, float initialLoadFactor)
+    {
+	size = 0;
+	modCount = 0;
+	capacity = initialCapacity;
+	loadFactor = initialLoadFactor;
+	threshold = (int) ((float) capacity * loadFactor);
+	buckets = new Bucket[capacity];
+    }
+
+    /** private -- simply hashes a non-null Object to its array index */
+    private int hash(Object key)
+    {
+	return Math.abs(key.hashCode() % capacity);
+    }
+
+    /** 
+     * increases the size of the HashMap and rehashes all keys to new array indices;
+     * this is called when the addition of a new value would cause size() > threshold
+     */
+    private void rehash()
+    {
+	int i;
+	Bucket[] data = buckets;
+	Bucket.Node node;
+
+	modCount++;
+	capacity = (capacity * 2) + 1;
+	size = 0;
+	threshold = (int) ((float) capacity * loadFactor);
+	buckets = new Bucket[capacity];
+	for (i = 0; i < data.length; i++)
+	    {
+		if (data[i] != null)
+		    {
+			node = data[i].first;
+			while (node != null)
+			    {
+				internalPut(node.getKey(), node.getValue());
+				node = node.next;
+			    }
+		    }
+	    }
+    }
+
+    /** 
+     * a private method which does the "dirty work" (or some of it anyway) of fetching a value
+     * with a key
+     *
+     *  @param     key      the key for which to fetch an associated value
+     */    
+    private Map.Entry internalGet(Object key)
+    {
+	Bucket list;
+	if (size == 0)
+	    {
+		return null;
+	    }
+	else
+	    {
+		list = buckets[hash(((key == null) ? NULL_KEY : key))];
+		return (list == null) ? null : list.getEntryByKey(key);
+	    }
+    }
+
+    /**
+     * a private method used by inner class HashMapSet to implement its own 
+     * <pre>contains(Map.Entry)</pre> method; returns true if the supplied
+     * key / value pair is found in this HashMap (again, using <pre>equals()</pre>,
+     * rather than <pre>==</pre>)
+     *
+     * @param      entry      a Map.Entry to match against key / value pairs in 
+     *                        this HashMap
+     */
+    private boolean containsEntry(Map.Entry entry)
+    {
+	Map.Entry oInternalEntry;
+	if (entry == null)
+	    {
+		return false;
+	    }
+	else
+	    {
+		oInternalEntry = internalGet(entry.getKey());
+		return (oInternalEntry != null && oInternalEntry.equals(entry));
+	    }
+    }
+
+    /**
+     * Serializes this object to the given stream.
+     * @serialdata the <i>capacity</i>(int) that is the length of the
+     * bucket array, the <i>size</i>(int) of the hash map are emitted
+     * first.  They are followed by size entries, each consisting of
+     * a key (Object) and a value (Object).
+     */
+    private void writeObject(ObjectOutputStream s) 
+      throws IOException
+    {
+        // the fields
+        s.defaultWriteObject();
+
+	s.writeInt(capacity);
+	s.writeInt(size);
+	Iterator it = entrySet().iterator();
+	while (it.hasNext())
+	    {
+		Map.Entry oEntry = (Map.Entry) it.next();
+		s.writeObject(oEntry.getKey());
+		s.writeObject(oEntry.getValue());
+	    }
+    }
+
+    /**
+     * Deserializes this object from the given stream.
+     * @serialdata the <i>capacity</i>(int) that is the length of the
+     * bucket array, the <i>size</i>(int) of the hash map are emitted
+     * first.  They are followed by size entries, each consisting of
+     * a key (Object) and a value (Object).
+     */
+    private void readObject(ObjectInputStream s)
+      throws IOException, ClassNotFoundException
+    {
+      // the fields
+      s.defaultReadObject();
+
+      capacity = s.readInt();
+      int iLen = s.readInt();
+      size = 0;
+      modCount = 0;
+      buckets = new Bucket[capacity];
+
+      for (int i = 0; i < iLen; i++)
+	{
+	  Object oKey = s.readObject();
+	  Object oValue = s.readObject();
+	  internalPut(oKey, oValue);
+	}
+    }
+
+    // INNER CLASSES -------------------------------------------------------------
+    // ---------------------------------------------------------------------------
+    
+    /**
+     * an inner class providing a Set view of a HashMap; this implementation is 
+     * parameterized to view either a Set of keys or a Set of Map.Entry objects
+     *
+     * Note:  a lot of these methods are implemented by AbstractSet, and would work 
+     * just fine without any meddling, but far greater efficiency can be gained by
+     * overriding a number of them.  And so I did.
+     *
+     * @author      Jon Zeppieri
+     * @version     $Revision: 1.6 $
+     * @modified    $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+     */
+    private class HashMapSet extends AbstractSet
+	implements Set
+    {
+	/** the type of this Set view:  KEYS or ENTRIES */
+	private int setType;
+
+	/** construct a new HashtableSet with the supplied view type */
+	HashMapSet(int type)
+	{
+	    setType = type;
+	}
+
+	/**
+	 * adding an element is unsupported; this method simply throws an exception 
+	 *
+	 * @throws       UnsupportedOperationException
+	 */
+	public boolean add(Object o) throws UnsupportedOperationException
+	{
+	    throw new UnsupportedOperationException();
+	}
+
+	/**
+	 * adding an element is unsupported; this method simply throws an exception 
+	 *
+	 * @throws       UnsupportedOperationException
+	 */
+	public boolean addAll(Collection c) throws UnsupportedOperationException
+	{
+	    throw new UnsupportedOperationException();
+	}
+
+	/**
+	 * clears the backing HashMap; this is a prime example of an overridden implementation
+	 * which is far more efficient than its superclass implementation (which uses an iterator
+	 * and is O(n) -- this is an O(1) call)
+	 */
+	public void clear()
+	{
+	    HashMap.this.clear();
+	}
+
+	/**
+	 * returns true if the supplied object is contained by this Set
+	 *
+	 * @param     o       an Object being testing to see if it is in this Set
+	 */
+	public boolean contains(Object o)
+	{
+	    if (setType == KEYS)
+		return HashMap.this.containsKey(o);
+	    else
+		return (o instanceof Map.Entry) ? HashMap.this.containsEntry((Map.Entry) o) : false;
+	}
+
+	/** 
+	 * returns true if the backing HashMap is empty (which is the only case either a KEYS
+	 * Set or an ENTRIES Set would be empty)
+	 */
+	public boolean isEmpty()
+	{
+	    return HashMap.this.isEmpty();
+	}
+
+	/**
+	 * removes the supplied Object from the Set
+	 *
+	 * @param      o       the Object to be removed
+	 */
+	public boolean remove(Object o)
+	{
+	    if (setType == KEYS)
+		return (HashMap.this.remove(o) != null);
+	    else
+		return (o instanceof Map.Entry) ? 
+		    (HashMap.this.remove(((Map.Entry) o).getKey()) != null) : false;
+	}
+
+	/** returns the size of this Set (always equal to the size of the backing Hashtable) */
+	public int size()
+	{
+	    return HashMap.this.size();
+	}
+
+	/** returns an Iterator over the elements of this Set */
+	public Iterator iterator()
+	{
+	    return new HashMapIterator(setType);
+	}
+    }
+    
+    /**
+     * Like the above Set view, except this one if for values, which are not
+     * guaranteed to be unique in a Map; this prvides a Bag of values
+     * in the HashMap
+     *
+     * @author       Jon Zeppieri
+     * @version      $Revision: 1.6 $
+     * @modified     $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+     */
+    private class HashMapCollection extends AbstractCollection
+	implements Collection
+    {
+	/** a trivial contructor for HashMapCollection */
+	HashMapCollection()
+	{
+	}
+
+	/** 
+	 * adding elements is not supported by this Collection;
+	 * this method merely throws an exception
+	 *
+	 * @throws     UnsupportedOperationException
+	 */
+	public boolean add(Object o) throws UnsupportedOperationException
+	{
+	    throw new UnsupportedOperationException();
+	}
+
+	/** 
+	 * adding elements is not supported by this Collection;
+	 * this method merely throws an exception
+	 *
+	 * @throws     UnsupportedOperationException
+	 */
+	public boolean addAll(Collection c) throws UnsupportedOperationException
+	{
+	    throw new UnsupportedOperationException();
+	}
+
+	/** removes all elements from this Collection (and from the backing HashMap) */
+	public void clear()
+	{
+	    HashMap.this.clear();
+	}
+
+	/** 
+	 * returns true if this Collection contains at least one Object which equals() the
+	 * supplied Object
+	 *
+	 * @param         o        the Object to compare against those in the Set
+	 */
+	public boolean contains(Object o)
+	{
+	    return HashMap.this.containsValue(o);
+	}
+
+	/** returns true IFF the Collection has no elements */
+	public boolean isEmpty()
+	{
+	    return HashMap.this.isEmpty();
+	}
+
+	/** returns the size of this Collection */
+	public int size()
+	{
+	    return HashMap.this.size();
+	}
+
+	/** returns an Iterator over the elements in this Collection */
+	public Iterator iterator()
+	{
+	    return new HashMapIterator(VALUES);
+	}
+    }
+
+    /**
+     * a class which implements the Iterator interface and is used for
+     * iterating over HashMaps;
+     * this implementation is parameterized to give a sequential view of
+     * keys, values, or entries; it also allows the removal of elements, 
+     * as per the Javasoft spec.
+     *
+     * @author       Jon Zeppieri
+     * @version      $Revision: 1.6 $
+     * @modified     $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+     */
+    class HashMapIterator implements Iterator
+    {
+	/** the type of this Iterator: KEYS, VALUES, or ENTRIES */
+	private int myType;
+	/** 
+	 * the number of modifications to the backing Hashtable for which
+	 * this Iterator can account (idea ripped off from Stuart Ballard)
+	 */
+	private int knownMods;
+	/** the location of our sequential "cursor" */
+	private int position;
+	/** the current index of the BucketList array */
+	private int bucketIndex;
+	/** a reference, originally null, to the specific Bucket our "cursor" is pointing to */
+	private Bucket.Node currentNode;
+	/** a reference to the current key -- used fro removing elements via the Iterator */
+	private Object currentKey;
+
+	/** construct a new HashtableIterator with the supllied type: KEYS, VALUES, or ENTRIES */
+	HashMapIterator(int type)
+	{
+	    myType = type;
+	    knownMods = HashMap.this.modCount;
+	    position = 0;
+	    bucketIndex = -1;
+	    currentNode = null;
+	    currentKey = null;
+	}
+
+	/** 
+	 * Stuart Ballard's code:  if the backing HashMap has been altered through anything 
+	 * but <i>this</i> Iterator's <pre>remove()</pre> method, we will give up right here,
+	 * rather than risking undefined behavior
+	 *
+	 * @throws    ConcurrentModificationException
+	 */
+	private void checkMod() 
+	{
+	    if (knownMods != HashMap.this.modCount)
+		throw new ConcurrentModificationException();
+	}
+
+	/** returns true if the Iterator has more elements */
+	public boolean hasNext()
+	{
+	    checkMod();
+	    return position < HashMap.this.size();
+	}
+
+	/** returns the next element in the Iterator's sequential view */
+	public Object next()
+	{
+	    Bucket list = null;
+	    Object result;
+	    checkMod();	    
+	    try
+		{
+		    while (currentNode == null)
+			{
+			    while (list == null)
+				list = HashMap.this.buckets[++bucketIndex];
+			    currentNode = list.first;
+			}
+		    currentKey = currentNode.getKey();
+		    result = (myType == KEYS) ? currentKey : 
+			((myType == VALUES) ? currentNode.getValue() : currentNode);
+		    currentNode = currentNode.next;
+		}
+	    catch(Exception e)
+		{
+		    throw new NoSuchElementException();
+		}
+	    position++;
+	    return result;
+	}
+
+	/** 
+	 * removes from the backing HashMap the last element which was fetched with the
+	 * <pre>next()</pre> method
+	 */
+	public void remove()
+	{
+	    checkMod();
+	    if (currentKey == null)
+		{
+		    throw new IllegalStateException();
+		}
+	    else
+		{
+		    HashMap.this.remove(currentKey);
+		    knownMods++;
+		    position--;
+		    currentKey = null;
+		}
+	}
+    }
+
+    /**
+     * a singleton instance of this class (HashMap.NULL_KEY)
+     * is used to represent the null key in HashMap objects
+     *
+     * @author     Jon Zeppieri
+     * @version    $Revision: 1.6 $
+     * @modified   $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+     */
+    private static class Null
+    {
+	/** trivial constructor */
+	Null()
+	{
+	}
+    }
+
+    /**
+     * a HashMap version of Map.Entry -- one thing in this implementation is
+     * HashMap-specific:  if the key is HashMap.NULL_KEY, getKey() will return
+     * null
+     *
+     * Simply, a key / value pair
+     *
+     * @author      Jon Zeppieri
+     * @version     $Revision: 1.6 $
+     * @modified    $Id: HashMap.java,v 1.6 2000/03/15 21:59:13 rao Exp $
+     */
+    private static class HashMapEntry extends Bucket.Node implements Map.Entry
+    {
+	/** construct a new HashMapEntry with the given key and value */
+	public HashMapEntry(Object key, Object value)
+	{
+	    super(key, value);
+	}
+
+	/**
+	 * if the key == HashMap.NULL_KEY, null is returned, otherwise the actual
+	 * key is returned
+	 */
+	public Object getKey()
+	{
+	    Object oResult = super.getKey();
+	    return (oResult == HashMap.NULL_KEY) ? null : oResult;
+	}
+    }
+    // EOF -----------------------------------------------------------------------
+}
diff --git a/libjava/java/util/LinkedList.java b/libjava/java/util/LinkedList.java
new file mode 100644
index 0000000..41f1ab4
--- /dev/null
+++ b/libjava/java/util/LinkedList.java
@@ -0,0 +1,584 @@
+/* LinkedList.java -- Linked list implementation of the List interface
+   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+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
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+package java.util;
+import java.io.Serializable;
+import java.io.ObjectOutputStream;
+import java.io.ObjectInputStream;
+import java.io.IOException;
+
+// TO DO:
+// ~ Doc comment for the class.
+// ~ Doc comments for the non-list methods.
+// ~ Some commenting on the Backing API and other general implementation notes.
+
+/**
+ * Linked list implementation of the List interface.
+ */
+public class LinkedList extends AbstractSequentialList 
+  implements Serializable, Cloneable
+{
+  static final long serialVersionUID = 876323262645176354L;
+
+  /**
+   * An Entry containing the head (in the next field) and the tail (in the
+   * previous field) of the list. The data field is null. If the list is empty,
+   * both the head and the tail point to ends itself.
+   */
+  transient Entry ends = new Entry();
+
+  /**
+   * The current length of the list.
+   */
+  transient int size = 0;
+
+  /**
+   * Class to represent an entry in the list. Holds a single element.
+   */
+  private static class Entry {
+
+    /**
+     * The list element.
+     */
+    Object data = null;
+
+    /**
+     * The next entry in the list. If this is the last entry in the list, the
+     * ends field of the list is held here.
+     */
+    Entry next;
+
+    /**
+     * The previous entry in the list. If this is the first entry in the list,
+     * the ends field of the list is held here.
+     */
+    Entry previous;
+
+    /**
+     * Create an entry with given data and linkage.
+     */
+    Entry(Object d, Entry n, Entry p) {
+      data = d;
+      next = n;
+      previous = p;
+    }
+
+    /**
+     * Create an entry with no data and linking to itself, for use as the ends
+     * field of the list.
+     */
+    Entry() {
+      next = previous = this;
+    }
+
+    /**
+     * Remove this entry.
+     */
+    Object remove() {
+      previous.next = next;
+      next.previous = previous;
+      return data;
+    }
+  }
+
+  private static interface Backing {
+    void checkMod(int known);
+    void upMod();
+    void incSize(int by);
+    void decSize(int by);
+  }
+
+  private final Backing back = new Backing() {
+    public void checkMod(int known) {
+      if (known != modCount) {
+	throw new ConcurrentModificationException();
+      }
+    }
+    public void upMod() {
+      modCount++;
+    }
+    public void incSize(int by) {
+      size += by;
+    }
+    public void decSize(int by) {
+      size -= by;
+    }
+  };
+
+  /** A ListIterator over the list. This class keeps track of its
+   * position in the list, the size of the list, and the two list
+   * entries it is between.  This enables it to be used identically
+   * for both the list itself and a sublist of the list.
+   */
+  private static class Iter implements ListIterator {
+
+    /**
+     * The index of the element that will be returned by next().
+     */
+    int pos;
+
+    /**
+     * The size of the backing list.
+     */
+    int size;
+
+    /**
+     * The entry containing the element that will be returned by next().
+     */
+    Entry next;
+
+    /**
+     * The entry containing the element that will be returned by previous().
+     */
+    Entry previous;
+
+    /**
+     * The entry that will be affected by remove() or set().
+     */
+    Entry recent;
+
+    /**
+     * The known value of the modCount of the backing list.
+     */
+    int knownMod;
+
+    private final Backing b;
+
+    /**
+     * Create a new Iter starting at a given Entry within the list, at a given
+     * position, in a list of given size.
+     *
+     * @param index the index to begin iteration.
+     * @exception IndexOutOfBoundsException if index < 0 || index > size.
+     */
+    Iter(Backing backing, Entry n, int index, int s, int modCount) {
+      b = backing;
+      pos = index;
+      size = s;
+      next = n;
+      previous = n.previous;
+      knownMod = modCount;
+    }
+
+    public int nextIndex() {
+      b.checkMod(knownMod);
+      return pos;
+    }
+
+    public int previousIndex() {
+      b.checkMod(knownMod);
+      return pos - 1;
+    }
+
+    public boolean hasNext() {
+      b.checkMod(knownMod);
+      return pos < size;
+    }
+
+    public boolean hasPrevious() {
+      b.checkMod(knownMod);
+      return pos > 0;
+    }
+
+    public Object next() {
+      b.checkMod(knownMod);
+      if (pos >= size) {
+	throw new NoSuchElementException();
+      } else {
+	pos++;
+	recent = previous = next;
+	next = recent.next;
+	return recent.data;
+      }
+    }
+
+    public Object previous() {
+      b.checkMod(knownMod);
+      if (pos <= 0) {
+	throw new NoSuchElementException();
+      } else {
+	pos--;
+	recent = next = previous;
+	previous = recent.previous;
+	return recent.data;
+      }
+    }
+
+    public void remove() {
+      b.checkMod(knownMod);
+      if (recent == null) {
+	throw new IllegalStateException();
+      }
+
+      // Adjust the position to before the removed element
+      if (recent == previous) pos--;
+
+      // Could use recent.remove() but this way is quicker, and also correctly
+      // fixes next and previous.
+      next = recent.previous.next = recent.next;
+      previous = recent.next.previous = recent.previous;
+      size--;
+      b.decSize(1);
+      knownMod++;
+      b.upMod();
+      recent = null;
+    }
+
+    public void add(Object o) {
+      b.checkMod(knownMod);
+      previous.next = next.previous = new Entry(o, next, previous);
+
+      // New for 1.2RC1 - the semantics changed so that the iterator is
+      // positioned *after* the new element.
+      previous = previous.next;
+      pos++;
+
+      size++;
+      b.incSize(1);
+      knownMod++;
+      b.upMod();
+      recent = null;
+    }
+
+    public void set(Object o) {
+      b.checkMod(knownMod);
+      if (recent == null) {
+	throw new IllegalStateException();
+      }
+      recent.data = o;
+    }
+  }
+
+  /**
+   * Obtain the Entry at a given position in a list. This method of course
+   * takes linear time, but it is intelligent enough to take the shorter of the
+   * paths to get to the Entry required. This implies that the first or last
+   * entry in the list is obtained in constant time, which is a very desirable
+   * property.
+   * For speed and flexibility in which ranges are valid, range checking is not
+   * done in this method, and if n is outside the range -1 <= n <= size, the
+   * result will be wrong (but no exception will be thrown).
+   * Note that you *can* obtain entries at position -1 and size, which are
+   * equal to prehead and posttail respectively.
+   * This method is static so that it can also be used in subList.
+   *
+   * @param n the number of the entry to get.
+   * @param size the size of the list to get the entry in.
+   * @param head the entry before the first element of the list (usually ends).
+   * @param tail the entry after the last element of the list (usually ends).
+   */
+  static Entry getEntry(int n, int size, Entry head, Entry tail) {
+
+    // n less than size/2, iterate from start
+    if (n < size >> 1) {
+      while (n-- >= 0) {
+	head = head.next;
+      }
+      return head;
+
+    // n greater than size/2, iterate from end
+    } else {
+      while (++n <= size) {
+	tail = tail.previous;
+      }
+      return tail;
+    }
+  }
+
+  /**
+   * Create an empty linked list.
+   */
+  public LinkedList() {
+    super();
+  }
+
+  /**
+   * Create a linked list containing the elements, in order, of a given
+   * collection.
+   *
+   * @param c the collection to populate this list from.
+   */
+  public LinkedList(Collection c) {
+    super();
+    // Note: addAll could be made slightly faster, but not enough so to justify
+    // re-implementing it from scratch. It is just a matter of a relatively
+    // small constant factor.
+    addAll(c);
+  }
+
+  public Object getFirst() {
+    if (size == 0) {
+      throw new NoSuchElementException();
+    }
+    return ends.next.data;
+  }
+
+  public Object getLast() {
+    if (size == 0) {
+      throw new NoSuchElementException();
+    }
+    return ends.previous.data;
+  }
+
+  public Object removeFirst() {
+    if (size == 0) {
+      throw new NoSuchElementException();
+    }
+    size--;
+    modCount++;
+    return ends.next.remove();
+  }
+
+  public Object removeLast() {
+    if (size == 0) {
+      throw new NoSuchElementException();
+    }
+    size--;
+    modCount++;
+    return ends.previous.remove();
+  }
+
+  public void addFirst(Object o) {
+    ends.next.previous = ends.next = new Entry(o, ends.next, ends);
+    size++;
+    modCount++;
+  }
+
+  public void addLast(Object o) {
+    ends.previous.next = ends.previous = new Entry(o, ends, ends.previous);
+    size++;
+    modCount++;
+  }
+
+  /**
+   * Obtain the number of elements currently in this list.
+   *
+   * @returns the number of elements currently in this list.
+   */
+  public int size() {
+    return size;
+  }
+
+  /**
+   * Remove a range of elements from this list.
+   *
+   * @param fromIndex the index, inclusive, to remove from.
+   * @param toIndex the index, exclusive, to remove to.
+   * @exception IndexOutOfBoundsException if fromIndex > toIndex || fromIndex <
+   *   0 || toIndex > size().
+   */
+  // Note: normally removeRange is provided to allow efficient ways to
+  // implement clear() on subLists. However, in this case clear on subLists
+  // works anyway, so this implementation is included just for completeness
+  // and because subclasses might try to use it.
+  protected void removeRange(int fromIndex, int toIndex) {
+    subList(fromIndex, toIndex).clear();
+  }
+
+  /**
+   * Clear the list.
+   */
+  public void clear() {
+    ends.next = ends.previous = ends;
+    modCount++;
+    size = 0;
+  }
+
+  /**
+   * Obtain a ListIterator over this list, starting at a given index. The
+   * ListIterator returned by this method supports the add, remove and set
+   * methods.
+   *
+   * @param index the index of the element to be returned by the first call to
+   *   next(), or size() to be initially positioned at the end of the list.
+   * @exception IndexOutOfBoundsException if index < 0 || index > size().
+   */
+  public ListIterator listIterator(int index) {
+
+    // Check bounds
+    if (index < 0 || index > size) {
+      throw new IndexOutOfBoundsException();
+    }
+
+    return new Iter(back, getEntry(index, size, ends, ends), 
+		    index, size, modCount);
+  }
+
+  /**
+   * Obtain a List view of a subsection of this list, from fromIndex
+   * (inclusive) to toIndex (exclusive). The returned list is modifiable in
+   * every respect. Changes to the returned list are reflected in this list. If
+   * this list is structurally modified is any way other than through the
+   * returned list, any subsequent operations on the returned list will result
+   * in a ConcurrentModificationException (that is, the returned list is
+   * fail-fast).
+   *
+   * @param fromIndex the index that the returned list should start from
+   *    (inclusive).
+   * @param toIndex the index that the returned list should go to (exclusive).
+   * @returns a List backed by a subsection of this list.
+   * @exception IndexOutOfBoundsException if fromIndex < 0 || toIndex > size()
+   *   || fromIndex > toIndex.
+   */
+  public List subList(int fromIndex, int toIndex) {
+
+    // Check bounds
+    if (fromIndex > toIndex || fromIndex < 0 || toIndex > size) {
+      throw new IndexOutOfBoundsException();
+    }
+
+    return new SubLinkedList(back, modCount,
+			     getEntry(fromIndex - 1, size, ends, ends),
+			     getEntry(toIndex, size, ends, ends),
+			     toIndex - fromIndex);
+  }
+
+  private static class SubLinkedList extends AbstractSequentialList {
+
+    Entry head; // entry before the beginning
+    Entry tail; // entry after the end
+    int size;
+    private final Backing b;
+
+    private final Backing back = new Backing() {
+      public void checkMod(int known) {
+	if (known != modCount) {
+	  throw new ConcurrentModificationException();
+	}
+      }
+      public void upMod() {
+	modCount++;
+      }
+      public void incSize(int by) {
+	size += by;
+      }
+      public void decSize(int by) {
+	size -= by;
+      }
+    };
+
+    SubLinkedList(Backing backing, int knownMod, Entry h, Entry t, int s) {
+      this.modCount = knownMod;
+      b = backing;
+      head = h;
+      tail = t;
+      size = s;
+    }
+
+    public int size() {
+      b.checkMod(this.modCount);
+      return size;
+    }
+
+    public ListIterator listIterator(int index) {
+      b.checkMod(this.modCount);
+
+      // Check bounds
+      if (index < 0 || index > size) {
+	throw new IndexOutOfBoundsException();
+      }
+
+      return new Iter(back, getEntry(index, size, head, tail), 
+		      index, size, modCount);
+    }
+
+    public void clear() {
+      b.checkMod(this.modCount);
+      head.next = tail;
+      tail.previous = head;
+      size = 0;
+      b.decSize(size);
+      modCount++;
+      b.upMod();
+    }
+
+    // No removeRange because this class cannot be publically subclassed.
+
+    public List subList(int fromIndex, int toIndex) {
+      b.checkMod(this.modCount);
+
+      // Check bounds
+      if (fromIndex > toIndex || fromIndex < 0 || toIndex > size) {
+	throw new IndexOutOfBoundsException();
+      }
+
+      return new SubLinkedList(back, this.modCount,
+			       getEntry(fromIndex - 1, size, head, tail),
+			       getEntry(toIndex, size, head, tail),
+			       toIndex - fromIndex);
+    }
+  }
+
+  /**
+   * Create a shallow copy of this LinkedList.
+   * @return an object of the same class as this object, containing the
+   * same elements in the same order.
+   */
+  public Object clone() 
+  {
+    LinkedList copy;
+    try
+      {
+	copy = (LinkedList) super.clone();
+      }
+    catch (CloneNotSupportedException ex)
+      {
+	throw new InternalError(ex.getMessage());
+      }
+    copy.size = 0;
+    copy.ends = new Entry();
+    copy.addAll(this);
+    return copy;
+  }
+
+  /**
+   * Serialize an object to a stream.
+   * @serialdata the size of the list (int), followed by all the elements
+   * (Object) in proper order.
+   */
+  private void writeObject(ObjectOutputStream s)
+    throws IOException
+  {
+    s.writeInt(size);
+    for (Iterator i = iterator(); i.hasNext(); )
+      s.writeObject(i.next());
+  }
+
+  /**
+   * Deserialize an object from a stream.
+   * @serialdata the size of the list (int), followed by all the elements
+   * (Object) in proper order.
+   */
+  private void readObject(ObjectInputStream s)
+    throws IOException, ClassNotFoundException
+  {
+    int serialSize = s.readInt();
+    ends = new Entry();
+    for (int i=0; i< serialSize; i++)
+      addLast(s.readObject());
+  }
+}
diff --git a/libjava/java/util/SortedMap.java b/libjava/java/util/SortedMap.java
new file mode 100644
index 0000000..594f188
--- /dev/null
+++ b/libjava/java/util/SortedMap.java
@@ -0,0 +1,40 @@
+/* SortedMap.java -- A map that makes guarantees about the order of its keys
+   Copyright (C) 1998 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+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
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+// TO DO:
+// ~ Doc comments for everything.
+
+package java.util;
+
+public interface SortedMap extends Map {
+  Comparator comparator();
+  Object firstKey();
+  SortedMap headMap(Object toKey);
+  Object lastKey();
+  SortedMap subMap(Object fromKey, Object toKey);
+  SortedMap tailMap(Object fromKey);
+}
diff --git a/libjava/java/util/SortedSet.java b/libjava/java/util/SortedSet.java
new file mode 100644
index 0000000..ede6503
--- /dev/null
+++ b/libjava/java/util/SortedSet.java
@@ -0,0 +1,41 @@
+/* SortedSet.java -- A set that makes guarantees about the order of its 
+   elements
+   Copyright (C) 1998 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+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
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+
+// TO DO:
+// ~ Doc comments for everything.
+
+package java.util;
+
+public interface SortedSet extends Set {
+  Comparator comparator();
+  Object first();
+  SortedSet headSet(Object toElement);
+  Object last();
+  SortedSet subSet(Object fromElement, Object toElement);
+  SortedSet tailSet(Object fromElement);
+}
diff --git a/libjava/java/util/Timer.java b/libjava/java/util/Timer.java
new file mode 100644
index 0000000..8c3e993
--- /dev/null
+++ b/libjava/java/util/Timer.java
@@ -0,0 +1,525 @@
+/* Timer.java -- Timer that runs TimerTasks at a later time.
+   Copyright (C) 2000 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+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
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+package java.util;
+
+/**
+ * Timer that can run TimerTasks at a later time.
+ * TimerTasks can be scheduled for one time execution at some time in the
+ * future. They can be scheduled to be rescheduled at a time period after the
+ * task was last executed. Or they can be scheduled to be executed repeatedly
+ * at a fixed rate.
+ * <p>
+ * The normal scheduling will result in a more or less even delay in time
+ * between successive executions, but the executions could drift in time if
+ * the task (or other tasks) takes a long time to execute. Fixed delay
+ * scheduling guarantees more or less that the task will be executed at a
+ * specific time, but if there is ever a delay in execution then the period
+ * between successive executions will be shorter. The first method of
+ * repeated scheduling is prefered for repeated tasks in response to user
+ * interaction, the second method of repeated scheduling is prefered for tasks
+ * that act like alarms.
+ * <p>
+ * The Timer keeps a binary heap as a task priority queue which means that
+ * scheduling and serving of a task in a queue of n tasks costs O(log n).
+ *
+ * @see TimerTask
+ * @since 1.3
+ * @author Mark Wielaard (mark@klomp.org)
+ */
+public class Timer {
+
+    /**
+     * Priority Task Queue.
+     * TimerTasks are kept in a binary heap.
+     * The scheduler calls sleep() on the queue when it has nothing to do or
+     * has to wait. A sleeping scheduler can be notified by calling interrupt()
+     * which is automatically called by the enqueue(), cancel() and
+     * timerFinalized() methods.
+     */
+    private static final class TaskQueue {
+
+        /** Default size of this queue */
+        private final int DEFAULT_SIZE = 32;
+
+        /** Wheter to return null when there is nothing in the queue */
+        private boolean nullOnEmpty;
+
+        /**
+         * The heap containing all the scheduled TimerTasks
+         * sorted by the TimerTask.scheduled field.
+         * Null when the stop() method has been called.
+         */
+        private TimerTask heap[];
+
+        /**
+         * The actual number of elements in the heap
+         * Can be less then heap.length.
+         * Note that heap[0] is used as a sentinel.
+         */
+        private int elements;
+
+        /**
+         * Creates a TaskQueue of default size without any elements in it.
+         */
+        public TaskQueue() {
+            heap = new TimerTask[DEFAULT_SIZE];
+            elements = 0;
+            nullOnEmpty = false;
+        }
+
+        /**
+         * Adds a TimerTask at the end of the heap.
+         * Grows the heap if necessary by doubling the heap in size.
+         */
+        private void add(TimerTask task) {
+            elements++;
+            if (elements == heap.length) {
+                TimerTask new_heap[] = new TimerTask[heap.length*2];
+                System.arraycopy(heap, 0, new_heap, 0, heap.length);
+                heap = new_heap;
+            }
+            heap[elements] = task;
+        }
+
+        /**
+         * Removes the last element from the heap.
+         * Shrinks the heap in half if
+         * elements+DEFAULT_SIZE/2 <= heap.length/4.
+         */
+        private void remove() {
+            // clear the entry first
+            heap[elements] = null;
+            elements--;
+            if (elements+DEFAULT_SIZE/2 <= (heap.length/4)) {
+                TimerTask new_heap[] = new TimerTask[heap.length/2];
+                System.arraycopy(heap, 0, new_heap, 0, elements+1);
+            }
+        }
+
+        /**
+         * Adds a task to the queue and puts it at the correct place
+         * in the heap.
+         */
+        public synchronized void enqueue(TimerTask task) {
+ 
+           // Check if it is legal to add another element
+            if (heap == null) {
+                throw new IllegalStateException
+                    ("cannot enqueue when stop() has been called on queue");
+            }
+
+            heap[0] = task; // sentinel
+            add(task); // put the new task at the end
+            // Now push the task up in the heap until it has reached its place
+            int child = elements;
+            int parent = child / 2;
+            while (heap[parent].scheduled > task.scheduled) {
+                heap[child] = heap[parent];
+                child = parent;
+                parent = child / 2;
+            }
+            // This is the correct place for the new task
+            heap[child] = task;
+            heap[0] = null; // clear sentinel
+            // Maybe sched() is waiting for a new element
+            this.notify();
+        }
+
+        /**
+         * Returns the top element of the queue.
+         * Can return null when no task is in the queue.
+         */
+        private TimerTask top() {
+            if (elements == 0) {
+                return null;
+            } else {
+                return heap[1];
+            }
+        }
+
+        /**
+         * Returns the top task in the Queue.
+         * Removes the element from the heap and reorders the heap first.
+         * Can return null when there is nothing in the queue.
+         */
+        public synchronized TimerTask serve() {
+            // The task to return
+            TimerTask task = null;
+            
+            while (task == null) {
+                // Get the next task
+                task = top();
+                
+                // return null when asked to stop
+                // or if asked to return null when the queue is empty
+                if ((heap == null) || (task == null && nullOnEmpty)) {
+                    return null;
+                }
+                
+                // Do we have a task?
+                if (task != null) {
+                    // The time to wait until the task should be served
+                    long time = task.scheduled-System.currentTimeMillis();
+                    if (time > 0) {
+                        // This task should not yet be served
+                        // So wait until this task is ready
+                        // or something else happens to the queue
+                        task = null; // set to null to make sure we call top()
+                        try {
+                            this.wait(time);
+                        } catch (InterruptedException _) {}
+                    }
+                } else {
+                    // wait until a task is added
+                    // or something else happens to the queue
+                    try {
+                        this.wait();
+                    } catch (InterruptedException _) {}
+                }
+            }
+            
+            // reconstruct the heap
+            TimerTask lastTask = heap[elements];
+            remove();
+            
+            // drop lastTask at the beginning and move it down the heap
+            int parent = 1;
+            int child = 2;
+            heap[1] = lastTask;
+            while(child <= elements) {
+                if (child < elements) {
+                    if (heap[child].scheduled > heap[child+1].scheduled) {
+                        child++;
+                    }
+                }
+                
+                if (lastTask.scheduled <= heap[child].scheduled)
+                    break; // found the correct place (the parent) - done
+                
+                heap[parent] = heap[child];
+                parent = child;
+                child = parent*2;
+            }
+
+            // this is the correct new place for the lastTask
+            heap[parent] = lastTask;
+
+            // return the task
+            return task;
+        }
+
+    
+        /**
+         * When nullOnEmpty is true the serve() method will return null when
+         * there are no tasks in the queue, otherwise it will wait until
+         * a new element is added to the queue. It is used to indicate to
+         * the scheduler that no new tasks will ever be added to the queue.
+         */
+        public synchronized void setNullOnEmpty(boolean nullOnEmpty) {
+            this.nullOnEmpty = nullOnEmpty;
+            this.notify();
+        }
+
+        /**
+         * When this method is called the current and all future calls to
+         * serve() will return null. It is used to indicate to the Scheduler
+         * that it should stop executing since no more tasks will come.
+         */
+        public synchronized void stop() {
+            this.heap = null;
+            this.notify();
+        }
+        
+    } // TaskQueue
+
+    /**
+     * The scheduler that executes all the tasks on a particular TaskQueue,
+     * reschedules any repeating tasks and that waits when no task has to be
+     * executed immediatly. Stops running when canceled or when the parent
+     * Timer has been finalized and no more tasks have to be executed.
+     */
+    private static final class Scheduler implements Runnable {
+
+        // The priority queue containing all the TimerTasks.
+        private TaskQueue queue;
+
+        /**
+         * Creates a new Scheduler that will schedule the tasks on the
+         * given TaskQueue.
+         */
+        public Scheduler(TaskQueue queue) {
+            this.queue = queue;
+        }
+
+        public void run() {
+            TimerTask task;
+            while((task = queue.serve()) != null) {
+                // If this task has not been canceled
+                if (task.scheduled >= 0) {
+
+                    // Mark execution time
+                    task.lastExecutionTime = task.scheduled;
+
+                    // Repeatable task?
+                    if (task.period < 0) {
+                        // Last time this task is executed
+                        task.scheduled = -1;
+                    }
+
+                    // Run the task
+                    try {
+                        task.run();
+                    } catch (Throwable t) {/* ignore all errors */}
+                }
+
+                // Calculate next time and possibly re-enqueue
+                if (task.scheduled >= 0) {
+                    if (task.fixed) {
+                        task.scheduled += task.period;
+                    } else {
+                        task.scheduled = task.period +
+                            System.currentTimeMillis();
+                    }
+                    queue.enqueue(task);
+                }
+            }
+        }
+    } // Scheduler
+
+    // Number of Timers created.
+    // Used for creating nice Thread names.
+    private static int  nr = 0;
+
+    // The queue that all the tasks are put in.
+    // Given to the scheduler
+    private TaskQueue queue;
+
+    // The Scheduler that does all the real work
+    private Scheduler scheduler;
+
+    // Used to run the scheduler.
+    // Also used to checked if the Thread is still running by calling
+    // thread.isAlive(). Sometimes a Thread is suddenly killed by the system
+    // (if it belonged to an Applet).
+    private Thread thread;
+    
+    // When cancelled we don't accept any more TimerTasks.
+    private boolean canceled;
+
+    /**
+     * Creates a new Timer with a non deamon Thread as Scheduler, with normal
+     * priority and a default name.
+     */
+    public Timer() {
+        this(false);
+    }
+
+    /**
+     * Creates a new Timer with a deamon Thread as scheduler if deamon is true,
+     * with normal priority and a default name.
+     */
+    public Timer(boolean daemon) {
+        this(daemon, Thread.NORM_PRIORITY);
+    }
+
+    /**
+     * Creates a new Timer with a deamon Thread as scheduler if deamon is true,
+     * with the priority given and a default name.
+     */
+    private Timer(boolean daemon, int priority) {
+        this(daemon, priority, "Timer-" + (++nr));
+    }
+
+    /**
+     * Creates a new Timer with a deamon Thread as scheduler if deamon is true,
+     * with the priority and name given.E
+     */
+    private Timer(boolean daemon, int priority, String name) {
+        canceled = false;
+        queue = new TaskQueue();
+        scheduler = new Scheduler(queue);
+        thread = new Thread(scheduler, name);
+        thread.setDaemon(daemon);
+        thread.setPriority(priority);
+        thread.start();
+    }
+
+    /**
+     * Cancels the execution of the scheduler. If a task is executing it will
+     * normally finish execution, but no other tasks will be executed and no
+     * more tasks can be scheduled.
+     */
+    public void cancel() {
+        canceled = true;
+        queue.stop();
+    }
+
+    /**
+     * Schedules the task at Time time, repeating every period
+     * milliseconds if period is positive and at a fixed rate if fixed is true.
+     *
+     * @exception IllegalArgumentException if time is negative
+     * @exception IllegalStateException if the task was already scheduled or
+     * canceled or this Timer is canceled or the scheduler thread has died
+     */
+    private void schedule(TimerTask task,
+                          long time,
+                          long period,
+                          boolean fixed) {
+
+        if (time < 0)
+            throw new IllegalArgumentException("negative time");
+
+        if (task.scheduled == 0 && task.lastExecutionTime == -1) {
+            task.scheduled = time;
+            task.period = period;
+            task.fixed = fixed;
+        } else {
+            throw new IllegalStateException
+                ("task was already scheduled or canceled");
+        }
+
+        if (!this.canceled && this.thread != null) {
+            queue.enqueue(task);
+        } else {
+            throw new IllegalStateException
+                ("timer was canceled or scheduler thread has died");
+        }
+    }
+
+    private static void positiveDelay(long delay) {
+        if (delay < 0) {
+            throw new IllegalArgumentException("delay is negative");
+        }
+    }
+
+    private static void positivePeriod(long period) {
+        if (period < 0) {
+            throw new IllegalArgumentException("period is negative");
+        }
+    }
+
+    /**
+     * Schedules the task at the specified data for one time execution.
+     *
+     * @exception IllegalArgumentException if date.getTime() is negative
+     * @exception IllegalStateException if the task was already scheduled or
+     * canceled or this Timer is canceled or the scheduler thread has died
+     */
+    public void schedule(TimerTask task, Date date) {
+        long time = date.getTime();
+        schedule(task, time, -1, false);
+    }
+
+    /**
+     * Schedules the task at the specified date and reschedules the task every
+     * period milliseconds after the last execution of the task finishes until
+     * this timer or the task is canceled.
+     *
+     * @exception IllegalArgumentException if period or date.getTime() is
+     * negative
+     * @exception IllegalStateException if the task was already scheduled or
+     * canceled or this Timer is canceled or the scheduler thread has died
+     */
+    public void schedule(TimerTask task, Date date, long period) {
+        positivePeriod(period);
+        long time = date.getTime();
+        schedule(task, time, period, false);
+    }
+
+    /**
+     * Schedules the task after the specified delay milliseconds for one time
+     * execution.
+     *
+     * @exception IllegalArgumentException if delay or
+     * System.currentTimeMillis + delay is negative
+     * @exception IllegalStateException if the task was already scheduled or
+     * canceled or this Timer is canceled or the scheduler thread has died
+     */
+    public void schedule(TimerTask task, long delay) {
+        positiveDelay(delay);
+        long time = System.currentTimeMillis() + delay;
+        schedule(task, time, -1, false);
+    }
+
+    /**
+     * Schedules the task after the delay milliseconds and reschedules the
+     * task every period milliseconds after the last execution of the task
+     * finishes until this timer or the task is canceled.
+     *
+     * @exception IllegalArgumentException if delay or period is negative
+     * @exception IllegalStateException if the task was already scheduled or
+     * canceled or this Timer is canceled or the scheduler thread has died
+     */
+    public void schedule(TimerTask task, long delay, long period) {
+        positiveDelay(delay);
+        positivePeriod(period);
+        long time = System.currentTimeMillis() + delay;
+        schedule(task, time, period, false);
+    }
+
+    /**
+     * Schedules the task at the specified date and reschedules the task at a
+     * fixed rate every period milliseconds until this timer or the task is
+     * canceled.
+     *
+     * @exception IllegalArgumentException if period or date.getTime() is
+     * negative
+     * @exception IllegalStateException if the task was already scheduled or
+     * canceled or this Timer is canceled or the scheduler thread has died
+     */
+    public void scheduleAtFixedRate(TimerTask task, Date date, long period) {
+        positivePeriod(period);
+        long time = date.getTime();
+        schedule(task, time, period, true);
+    }
+
+    /**
+     * Schedules the task after the delay milliseconds and reschedules the task
+     * at a fixed rate every period milliseconds until this timer or the task
+     * is canceled.
+     *
+     * @exception IllegalArgumentException if delay or
+     * System.currentTimeMillis + delay is negative
+     * @exception IllegalStateException if the task was already scheduled or
+     * canceled or this Timer is canceled or the scheduler thread has died
+     */
+    public void scheduleAtFixedRate(TimerTask task, long delay, long period) {
+        positiveDelay(delay);
+        positivePeriod(period);
+        long time = System.currentTimeMillis() + delay;
+        schedule(task, time, period, true);
+    }
+
+    /**
+     * Tells the scheduler that the Timer task died
+     * so there will be no more new tasks scheduled.
+     */
+    protected void finalize() {
+        queue.setNullOnEmpty(true);
+    }
+}
diff --git a/libjava/java/util/TimerTask.java b/libjava/java/util/TimerTask.java
new file mode 100644
index 0000000..29ffe34
--- /dev/null
+++ b/libjava/java/util/TimerTask.java
@@ -0,0 +1,131 @@
+/* TimerTask.java -- Task that can be run at a later time if given to a Timer.
+   Copyright (C) 2000 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+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
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+As a special exception, if you link this library with other files to
+produce an executable, this library does not by itself cause the
+resulting executable to be covered by the GNU General Public License.
+This exception does not however invalidate any other reasons why the
+executable file might be covered by the GNU General Public License. */
+
+package java.util;
+
+/**
+ * Task that can be run at a later time if given to a Timer.
+ * The TimerTask must implement a run method that will be called by the
+ * Timer when the task is scheduled for execution. The task can check when
+ * it should have been scheduled and cancel itself when no longer needed.
+ * <p>
+ * Example:
+ * <code>
+ *  Timer timer = new Timer();
+ *  TimerTask task = new TimerTask() {
+ *      public void run() {
+ *      if (this.scheduledExecutionTime() < System.currentTimeMillis() + 500)
+ *          // Do something
+ *      else
+ *          // Complain: We are more then half a second late!
+ *      if (someStopCondition)
+ *          this.cancel(); // This was our last execution
+ *  };
+ *  timer.scheduleAtFixedRate(task, 1000, 1000); // schedule every second
+ * </code>
+ * <p>
+ * Note that a TimerTask object is a one shot object and can only given once
+ * to a Timer. (The Timer will use the TimerTask object for bookkeeping,
+ * in this implementation).
+ * <p>
+ * This class also implements <code>Runnable</code> to make it possible to
+ * give a TimerTask directly as a target to a <code>Thread</code>.
+ *
+ * @see Timer
+ * @since 1.3
+ * @author Mark Wielaard (mark@klomp.org)
+ */
+public abstract class TimerTask implements Runnable {
+
+    /**
+     * If positive the next time this task should be run.
+     * If negative this TimerTask is canceled or executed for the last time.
+     */
+    long scheduled;
+
+    /**
+     * If positive the last time this task was run.
+     * If negative this TimerTask has not yet been scheduled.
+     */
+    long lastExecutionTime;
+
+    /**
+     * If positive the number of milliseconds between runs of this task.
+     * If -1 this task doesn't have to be run more then once.
+     */
+    long period;
+
+    /**
+     * If true the next time this task should be run is relative to
+     * the last scheduled time, otherwise it can drift in time.
+     */
+    boolean fixed;
+
+    /**
+     * Creates a TimerTask and marks it as not yet scheduled.
+     */
+    protected TimerTask() {
+        this.scheduled = 0;
+        this.lastExecutionTime = -1;
+    }
+
+    /**
+     * Marks the task as canceled and prevents any further execution.
+     * Returns true if the task was scheduled for any execution in the future
+     * and this cancel operation prevents that execution from happening.
+     * <p>
+     * A task that has been canceled can never be scheduled again.
+     * <p>
+     * In this implementation the TimerTask it is possible that the Timer does
+     * keep a reference to the TimerTask until the first time the TimerTask
+     * is actually scheduled. But the reference will disappear immediatly when
+     * cancel is called from within the TimerTask run method.
+     */
+    public boolean cancel() {
+        boolean prevented_execution = (this.scheduled >= 0);
+        this.scheduled = -1;
+        return prevented_execution;
+    }
+
+    /**
+     * Method that is called when this task is scheduled for execution.
+     */
+    public abstract void run();
+
+    /**
+     * Returns the last time this task was scheduled or (when called by the
+     * task from the run method) the time the current execution of the task
+     * was scheduled. When the task has not yet run the return value is
+     * undefined.
+     * <p>
+     * Can be used (when the task is scheduled at fixed rate) to see the
+     * difference between the requested schedule time and the actual time
+     * that can be found with <code>System.currentTimeMillis()</code>.
+     */
+    public long scheduledExecutionTime() {
+        return lastExecutionTime;
+    }
+}