* java/util/TreeMap.java: New file.

        * java/util/TreeSet.java: New file.
        * Makefile.am: Add TreeMap and TreeSet. Enable WeakHashMap.
        * Makefile.in: Rebuilt.
        * java/util/HashSet.java (clone): Use constructor instead of calling
        clone on itself.
        * java/util/SortedSet.java: Sync with classpath.
        * java/util/HashMap.java (hash): Use if statement instead of ternary,
        for clarity.
	Resolves PR libgcj/1758.
	Resolves PR java/1684.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@39657 138bc75d-0d04-0410-961f-82ee72b054a4

8 files changed, 1781 insertions, 24 deletions

diff --git a/libjava/ChangeLog b/libjava/ChangeLog
index 70ccbd2fce2..6e8a5a4063f 100644
--- a/libjava/ChangeLog
+++ b/libjava/ChangeLog
@@ -1,3 +1,15 @@
+2001-02-14  Bryce McKinlay  <bryce@albatross.co.nz>
+
+	* java/util/TreeMap.java: New file.
+	* java/util/TreeSet.java: New file.
+	* Makefile.am: Add TreeMap and TreeSet. Enable WeakHashMap.
+	* Makefile.in: Rebuilt.
+	* java/util/HashSet.java (clone): Use constructor instead of calling
+	clone on itself.
+	* java/util/SortedSet.java: Sync with classpath.
+	* java/util/HashMap.java (hash): Use if statement instead of ternary,
+	for clarity.
+
 2001-02-13  Tom Tromey  <tromey@redhat.com>
 
 	* java/io/PipedReader.java (ready): Throw IOException if pipe
diff --git a/libjava/Makefile.am b/libjava/Makefile.am
index e9c4b882c24..73d3b3a4464 100644
--- a/libjava/Makefile.am
+++ b/libjava/Makefile.am
@@ -980,9 +980,11 @@ java/util/StringTokenizer.java \
 java/util/TimeZone.java	\
 java/util/Timer.java \
 java/util/TimerTask.java \
+java/util/TreeMap.java \
+java/util/TreeSet.java \
 java/util/TooManyListenersException.java \
-java/util/Vector.java
-#java/util/WeakHashMap.java \
+java/util/Vector.java \
+java/util/WeakHashMap.java
 
 
 ## List of all .java files to be compiled.  Please keep this list
diff --git a/libjava/Makefile.in b/libjava/Makefile.in
index 516f1a28018..be75b67c9d9 100644
--- a/libjava/Makefile.in
+++ b/libjava/Makefile.in
@@ -724,10 +724,12 @@ java/util/StringTokenizer.java \
 java/util/TimeZone.java	\
 java/util/Timer.java \
 java/util/TimerTask.java \
+java/util/TreeMap.java \
+java/util/TreeSet.java \
 java/util/TooManyListenersException.java \
-java/util/Vector.java
+java/util/Vector.java \
+java/util/WeakHashMap.java
 
-#java/util/WeakHashMap.java \
 
 ordinary_java_source_files = $(core_java_source_files) \
 gnu/gcj/RawData.java \
@@ -1702,10 +1704,11 @@ DEP_FILES =  .deps/$(srcdir)/$(CONVERT_DIR)/gen-from-JIS.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 \
-.deps/java/util/jar/JarInputStream.P \
+.deps/java/util/TooManyListenersException.P .deps/java/util/TreeMap.P \
+.deps/java/util/TreeSet.P .deps/java/util/Vector.P \
+.deps/java/util/WeakHashMap.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 .deps/java/util/jar/JarInputStream.P \
 .deps/java/util/jar/JarOutputStream.P .deps/java/util/jar/Manifest.P \
 .deps/java/util/natGregorianCalendar.P .deps/java/util/zip/Adler32.P \
 .deps/java/util/zip/CRC32.P .deps/java/util/zip/CheckedInputStream.P \
diff --git a/libjava/java/util/HashMap.java b/libjava/java/util/HashMap.java
index b7ec3b49f4d..6304333295e 100644
--- a/libjava/java/util/HashMap.java
+++ b/libjava/java/util/HashMap.java
@@ -60,8 +60,8 @@ import java.io.ObjectOutputStream;
  * @author         Jon Zeppieri
  * @author         Jochen Hoenicke
  * @author	   Bryce McKinlay
- * @version        $Revision: 1.3 $
- * @modified       $Id: HashMap.java,v 1.3 2000/12/17 09:15:51 bryce Exp $
+ * @version        $Revision: 1.4 $
+ * @modified       $Id: HashMap.java,v 1.4 2000/12/21 02:00:15 bryce Exp $
  */
 public class HashMap extends AbstractMap
   implements Map, Cloneable, Serializable
@@ -500,7 +500,10 @@ public class HashMap extends AbstractMap
   /** Return an index in the buckets array for `key' based on its hashCode() */
   private int hash(Object key)
   {
-    return (key == null ? 0 : Math.abs(key.hashCode() % buckets.length));
+    if (key == null)
+      return 0;
+    else
+      return Math.abs(key.hashCode() % buckets.length);
   }
 
   /** Return an Entry who's key and value equal the supplied Map.Entry. 
@@ -611,15 +614,13 @@ public class HashMap extends AbstractMap
   }
 
   /**
-   * 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.
+   * Iterate over HashMap's entries.
+   * This implementation is parameterized to give a sequential view of
+   * keys, values, or entries.
    *
    * @author       Jon Zeppieri
-   * @version      $Revision: 1.3 $
-   * @modified     $Id: HashMap.java,v 1.3 2000/12/17 09:15:51 bryce Exp $
+   * @version      $Revision: 1.4 $
+   * @modified     $Id: HashMap.java,v 1.4 2000/12/21 02:00:15 bryce Exp $
    */
   class HashIterator implements Iterator
   {
diff --git a/libjava/java/util/HashSet.java b/libjava/java/util/HashSet.java
index f7cb326e59c..1d1f106637e 100644
--- a/libjava/java/util/HashSet.java
+++ b/libjava/java/util/HashSet.java
@@ -45,8 +45,8 @@ import java.io.ObjectOutputStream;
  * HashSet is a part of the JDK1.2 Collections API.
  *
  * @author      Jon Zeppieri
- * @version     $Revision: 1.5 $
- * @modified    $Id: HashSet.java,v 1.5 2000/10/26 10:19:00 bryce Exp $
+ * @version     $Revision: 1.1 $
+ * @modified    $Id: HashSet.java,v 1.1 2000/12/11 03:47:47 bryce Exp $
  */
 public class HashSet extends AbstractSet
   implements Set, Cloneable, Serializable
@@ -128,10 +128,9 @@ public class HashSet extends AbstractSet
    */
   public Object clone()
   {
-    HashSet copy = null;
+    HashSet copy = new HashSet();
     try
       {
-	copy = (HashSet) super.clone();
 	copy.map = (HashMap) map.clone();
       }
     catch (CloneNotSupportedException ex)
diff --git a/libjava/java/util/SortedSet.java b/libjava/java/util/SortedSet.java
index ede65032b52..f72dd66ef97 100644
--- a/libjava/java/util/SortedSet.java
+++ b/libjava/java/util/SortedSet.java
@@ -8,7 +8,7 @@ GNU Classpath is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2, or (at your option)
 any later version.
- 
+
 GNU Classpath is distributed in the hope that it will be useful, but
 WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
@@ -31,7 +31,8 @@ executable file might be covered by the GNU General Public License. */
 
 package java.util;
 
-public interface SortedSet extends Set {
+public interface SortedSet extends Set
+{
   Comparator comparator();
   Object first();
   SortedSet headSet(Object toElement);
diff --git a/libjava/java/util/TreeMap.java b/libjava/java/util/TreeMap.java
new file mode 100644
index 00000000000..ce111053299
--- /dev/null
+++ b/libjava/java/util/TreeMap.java
@@ -0,0 +1,1450 @@
+/* TreeMap.java -- a class providing a basic Red-Black Tree data structure,
+   mapping Object --> Object
+   Copyright (C) 1998, 1999, 2000, 2001 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;
+
+/**
+ * This class provides a red-black tree implementation of the SortedMap
+ * interface.  Elements in the Map will be sorted by either a user-provided
+ * Comparator object, or by the natural ordering of the keys.
+ *
+ * The algorithms are adopted from Corman, Leiserson,
+ * and Rivest's <i>Introduction to Algorithms.<i>  In other words,
+ * I cribbed from the same pseudocode as Sun.  <em>Any similarity
+ * between my code and Sun's (if there is any -- I have never looked
+ * at Sun's) is a result of this fact.</em>
+ *
+ * TreeMap guarantees O(log n) insertion and deletion of elements.  That 
+ * being said, there is a large enough constant coefficient in front of 
+ * that "log n" (overhead involved in keeping the tree 
+ * balanced), that TreeMap may not be the best choice for small
+ * collections.
+ *
+ * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
+ * only if a Comparator is used which can deal with them.  Null values are 
+ * always allowed.
+ *
+ * @author           Jon Zeppieri
+ * @author	     Bryce McKinlay
+ * @modified         $Id: TreeMap.java,v 1.8 2000/10/26 10:19:01 bryce Exp $
+ */
+public class TreeMap extends AbstractMap
+  implements SortedMap, Cloneable, Serializable
+{
+  private static final int RED = -1,
+                           BLACK = 1;
+
+  /** Sentinal node, used to avoid null checks for corner cases and make the
+      delete rebalance code simpler. Note that this must not be static, due 
+      to thread-safety concerns. */
+  transient final Node nil = new Node(null, null);
+
+  /** The root node of this TreeMap */
+  transient Node root = nil;
+
+  /** The size of this TreeMap */
+  transient int size = 0;
+
+  /** Number of modifications */
+  transient int modCount = 0;
+
+  /** This TreeMap's comparator, if any. */
+  Comparator comparator = null;
+
+  static final long serialVersionUID = 919286545866124006L;
+
+  private static class Node extends BasicMapEntry implements Map.Entry
+  {
+    int color;
+    Node left;
+    Node right;
+    Node parent;
+
+    Node(Object key, Object value)
+    {
+      super(key, value);
+      this.color = BLACK;
+    }
+  }
+
+  /**
+   * Instantiate a new TreeMap with no elements, using the keys'
+   * natural ordering to sort.
+   *
+   * @see java.lang.Comparable
+   */
+  public TreeMap()
+  {
+  }
+
+  /**
+   * Instantiate a new TreeMap with no elements, using the provided
+   * comparator to sort.
+   *
+   * @param        oComparator        a Comparator object, used to sort 
+   *                                  the keys of this SortedMap
+   */
+  public TreeMap(Comparator c)
+  {
+    comparator = c;
+  }
+
+  /**
+   * Instantiate a new TreeMap, initializing it with all of the
+   * elements in the provided Map.  The elements will be sorted 
+   * using the natural ordering of the keys.
+   *
+   * @param              map         a Map, whose keys will be put into
+   *                                  this TreeMap
+   *
+   * @throws             ClassCastException     if the keys in the provided
+   *                                            Map do not implement 
+   *                                            Comparable
+   *
+   * @see                java.lang.Comparable
+   */
+  public TreeMap(Map map)
+  {
+    putAll(map);
+  }
+
+  /** 
+   * Instantiate a new TreeMap, initializing it with all of the
+   * elements in the provided SortedMap.  The elements will be sorted 
+   * using the same method as in the provided SortedMap.
+   */
+  public TreeMap(SortedMap sm)
+  {
+    this(sm.comparator());
+
+    int sm_size = sm.size();
+    Iterator itr = sm.entrySet().iterator();
+
+    fabricateTree(sm_size);
+    Node node = firstNode();
+    
+    for (int i = 0; i < sm_size; i++)
+      {
+	Map.Entry me = (Map.Entry) itr.next();
+	node.key = me.getKey();
+	node.value = me.getValue();	
+	node = successor(node);
+      }
+  }
+
+  public int size()
+  {
+    return size;
+  }
+
+  public void clear()
+  {
+    modCount++;
+    root = nil;
+    // nil node could have a residual parent reference, clear it for GC.
+    nil.parent = null;
+    size = 0;
+  }
+
+  public Object clone()
+  {
+    TreeMap copy = new TreeMap();
+    copy.comparator = comparator;
+    copy.fabricateTree(size);
+
+    Node node = firstNode();
+    Node cnode = copy.firstNode();
+    
+    while (node != nil)
+      {
+        cnode.key = node.key;
+	cnode.value = node.value;
+	node = successor(node);
+	cnode = copy.successor(cnode);
+      }
+    return copy;
+  }
+  
+  public Comparator comparator()
+  {
+    return comparator;
+  }
+
+  public boolean containsKey(Object key)
+  {
+    return getNode(key) != nil;
+  }
+
+  public boolean containsValue(Object value)
+  {
+    Node node = firstNode();
+    Object currentVal;
+
+    while (node != nil)
+      {
+	currentVal = node.getValue();
+
+        if (value == null ? currentVal == null : value.equals (currentVal))
+	  return true;
+
+	node = successor(node);
+      }
+    return false;
+  }
+
+  public Set entrySet()
+  {
+    // Create an AbstractSet with custom implementations of those methods that 
+    // can be overriden easily and efficiently.
+    return new AbstractSet()
+    {
+      public int size()
+      {
+        return size;
+      }
+      
+      public Iterator iterator()
+      {
+        return new TreeIterator(TreeIterator.ENTRIES);
+      }
+            
+      public void clear()
+      {
+        TreeMap.this.clear();
+      }
+
+      public boolean contains(Object o)
+      {
+        if (!(o instanceof Map.Entry))
+	  return false;
+	Map.Entry me = (Map.Entry) o;
+	Node n = getNode(me.getKey());
+	return (n != nil && me.getValue().equals(n.value));
+      }
+      
+      public boolean remove(Object o)
+      {
+        if (!(o instanceof Map.Entry))
+	  return false;
+	Map.Entry me = (Map.Entry) o;
+	Node n = getNode(me.getKey());
+	if (n != nil && me.getValue().equals(n.value))
+	  {
+	    removeNode(n);
+	    return true;
+	  }
+	return false;
+      }
+    };
+  }
+
+  public Object firstKey()
+  {
+    if (root == nil)
+      throw new NoSuchElementException("empty");
+    return firstNode().getKey();
+  }
+  
+  private Node firstNode()
+  {
+    if (root == nil)
+      return nil;
+    Node node = root;
+    while (node.left != nil)
+      node = node.left;
+    return node;
+  }
+
+  public Object lastKey()
+  {
+    if (root == nil)
+      throw new NoSuchElementException("empty");
+    return lastNode().getKey();
+  }
+  
+  private Node lastNode()
+  {
+    if (root == nil)
+      return nil;
+    Node node = root;
+    while (node.right != nil)
+      node = node.right;
+    return node;  
+  }
+  
+  public Object get(Object key)
+  {
+    return getNode(key).value;
+  }
+  
+  /** Return the TreeMap.Node associated with KEY, or the nil node if no such
+      node exists in the tree. */
+  private Node getNode(Object key)
+  {
+    int comparison;
+    Node current = root;
+
+    while (current != nil)
+      {
+        comparison = compare(key, current.key);
+	if (comparison > 0)
+	  current = current.right;
+	else if (comparison < 0)
+	  current = current.left;
+	else
+	  return current;
+      }
+    return current; 
+  }
+
+  public Set keySet()
+  {
+    // Create an AbstractSet with custom implementations of those methods that 
+    // can be overriden easily and efficiently.
+    return new AbstractSet()
+    {
+      public int size()
+      {
+        return size;
+      }
+      
+      public Iterator iterator()
+      {
+        return new TreeIterator(TreeIterator.KEYS);
+      }
+
+      public void clear()
+      {
+        TreeMap.this.clear();
+      }
+
+      public boolean contains(Object o)
+      {
+        return TreeMap.this.containsKey(o);
+      }
+      
+      public boolean remove(Object key)
+      {
+        Node n = getNode(key);
+	if (n == nil)
+	  return false;
+        TreeMap.this.removeNode(n);
+	return true;
+      }
+    };
+  }
+
+  public Object put(Object key, Object value)
+  {
+    modCount++;
+    Node current = root;
+    Node parent = nil;
+    int comparison = 0;
+    
+    // Find new node's parent.
+    while (current != nil)
+      {
+	parent = current;
+	comparison = compare(key, current.key);
+	if (comparison > 0)
+	  current = current.right;
+	else if (comparison < 0)
+	  current = current.left;
+	else
+	  {
+	    // Key already in tree.
+	    Object r = current.value;
+	    current.value = value;
+	    return r;
+	  }
+      }
+    
+    // Set up new node.
+    Node n = new Node(key, value);
+    n.color = RED;
+    n.parent = parent;
+    n.left = nil;
+    n.right = nil;
+    
+    // Insert node in tree.
+    size++;
+    if (parent == nil)
+      {
+        // Special case: inserting into an empty tree.
+	root = n;
+	n.color = BLACK;
+	return null;
+      }
+    else if (comparison > 0)
+      parent.right = n;
+    else
+      parent.left = n;   
+    
+    // Rebalance after insert.
+    insertFixup(n);
+    //verifyTree();
+    return null;
+  }
+
+  /** Maintain red-black balance after inserting a new node. */
+  private void insertFixup(Node n)
+  {
+    // Only need to rebalance when parent is a RED node, and while at least
+    // 2 levels deep into the tree (ie: node has a grandparent).
+    while (n != root && n.parent.parent != nil && n.parent.color == RED)
+      {
+	if (n.parent == n.parent.parent.left)
+	  {
+            Node uncle = n.parent.parent.right;
+            if (uncle != nil && uncle.color == RED) 
+	      {
+        	n.parent.color = BLACK;
+        	uncle.color = BLACK;
+        	n.parent.parent.color = RED;
+        	n = n.parent.parent;
+              }
+	    else // Uncle is BLACK.
+	      {                
+                if (n == n.parent.right)
+		  {
+                    // Make n a left child.
+                    n = n.parent;
+                    rotateLeft(n);
+                  }
+
+                // Recolor and rotate.
+                n.parent.color = BLACK;
+                n.parent.parent.color = RED;
+                rotateRight(n.parent.parent);
+              }
+	  }
+	else
+	  {
+	    // Mirror image of above code.
+	    Node uncle = n.parent.parent.left;
+            if (uncle != nil && uncle.color == RED)
+	      {
+                n.parent.color = BLACK;
+                uncle.color = BLACK;
+                n.parent.parent.color = RED;
+                n = n.parent.parent;
+              }
+	    else
+	      {
+                if (n == n.parent.left)
+		  {
+                    n = n.parent;
+                    rotateRight(n);
+                  }
+                n.parent.color = BLACK;
+                n.parent.parent.color = RED;
+                rotateLeft(n.parent.parent);
+	      }
+	  }
+      }
+    root.color = BLACK;
+  }
+
+  public void putAll(Map m)
+  {
+    Iterator itr = m.entrySet().iterator();
+    int msize = m.size();
+    Map.Entry e;
+
+    for (int i = 0; i < msize; i++)
+      {
+	e = (Map.Entry) itr.next();
+	put(e.getKey(), e.getValue());
+      }
+  }
+
+  public Object remove(Object key)
+  {
+    Node n = getNode(key);
+    if (n != nil)
+      {
+        removeNode(n);
+	return n.value;
+      }
+    return null;
+  }
+  
+  // Remove node from tree. This will increment modCount and decrement size. 
+  // Node must exist in the tree.
+  private void removeNode(Node node) // z
+  {
+    Node splice; // y
+    Node child;  // x
+    
+    modCount++;
+    size--;
+
+    // Find splice, the node at the position to actually remove from the tree. 
+    if (node.left == nil || node.right == nil)
+      {
+	// Node to be deleted has 0 or 1 children.
+        splice = node;
+	if (node.left == nil)
+	  child = node.right;
+	else
+	  child = node.left;
+      }
+    else
+      {
+	// Node has 2 children. Splice is node's successor, and will be 
+	// swapped with node since we can't remove node directly.
+        splice = node.right;
+        while (splice.left != nil)
+	  splice = splice.left;
+	child = splice.right;
+      }
+
+    // Unlink splice from the tree.
+    Node parent = splice.parent;
+    child.parent = parent;
+    if (parent != nil)
+      {
+	if (splice == parent.left)
+          parent.left = child;
+	else
+          parent.right = child;
+      }
+    else
+      root = child;
+
+    // Keep track of splice's color in case it gets changed in the swap.
+    int spliceColor = splice.color;
+
+/*
+    if (splice != node)
+      {
+        node.key = splice.key;
+	node.value = splice.value;
+      }
+*/
+    if (splice != node)
+      {
+        // Swap SPLICE for NODE. Some implementations optimize here by simply
+	// swapping the values, but we can't do that: if an iterator was
+	// referencing a node in its "next" field, and that node got swapped, 
+	// things would get confused.
+	if (node == root)
+	  {
+	    root = splice;
+	  }
+	else
+	  {
+	    if (node.parent.left == node)
+	      node.parent.left = splice;
+	    else
+	      node.parent.right = splice;
+          }
+	splice.parent = node.parent;
+	splice.left = node.left;
+	splice.right = node.right;
+	splice.left.parent = splice;
+	splice.right.parent = splice;
+	splice.color = node.color;
+      }
+
+    if (spliceColor == BLACK)
+      deleteFixup (child);
+    
+    //verifyTree();      
+  }
+
+  /** Maintain red-black balance after deleting a node. */
+  private void deleteFixup (Node node)
+  {
+    // A black node has been removed, so we need to rebalance to avoid 
+    // violating the "same number of black nodes on any path" rule. If
+    // node is red, we can simply recolor it black and all is well. 
+    while (node != root && node.color == BLACK)
+      {
+        if (node == node.parent.left)
+	  {
+	    // Rebalance left side.
+	    Node sibling = node.parent.right;
+	    if (sibling.color == RED)
+	      {
+                sibling.color = BLACK;
+                node.parent.color = RED;
+                rotateLeft(node.parent);
+                sibling = node.parent.right;
+	      }
+
+	    if (sibling.left.color == BLACK && sibling.right.color == BLACK)
+              {
+	        // Case 2: Sibling has no red children.
+		sibling.color = RED;
+		// Black height has been decreased, so move up the tree and 
+		// repeat.
+		node = node.parent;
+              }
+	    else
+	      {	      
+	        if (sibling.right.color == BLACK)
+		  {
+		    // Case 3: Sibling has red left child.
+		    sibling.left.color = BLACK;
+		    sibling.color = RED;
+                    rotateRight(sibling);
+                    sibling = node.parent.right;
+		  }		  
+		
+		// Case 4: Sibling has red right child.
+		sibling.color = sibling.parent.color;
+		sibling.parent.color = BLACK;
+		sibling.right.color = BLACK;
+                rotateLeft(node.parent);
+                node = root; // Finished.
+	      }
+	  }
+	else
+	  {
+	    // Symmetric "mirror" of left-side case.
+	    Node sibling = node.parent.left;
+	    if (sibling.color == RED)
+	      {
+                sibling.color = BLACK;
+                node.parent.color = RED;
+                rotateRight(node.parent);
+                sibling = node.parent.left;
+	      }
+
+	    if (sibling.left.color == BLACK && sibling.right.color == BLACK)
+              {
+		sibling.color = RED;
+		node = node.parent;
+              }
+	    else
+	      {	      
+	        if (sibling.left.color == BLACK)
+		  {
+		    sibling.right.color = BLACK;
+		    sibling.color = RED;
+                    rotateLeft(sibling);
+                    sibling = node.parent.left;
+		  }		  
+		
+		sibling.color = sibling.parent.color;
+		sibling.parent.color = BLACK;
+		sibling.left.color = BLACK;
+                rotateRight(node.parent);
+                node = root;
+	      }
+	  }
+      }
+    node.color = BLACK;
+  }
+
+  public SortedMap subMap(Object fromKey, Object toKey)
+  {
+    if (compare(fromKey, toKey) <= 0)
+      return new SubMap(fromKey, toKey);
+    else
+      throw new IllegalArgumentException("fromKey > toKey");
+  }
+
+  public SortedMap headMap(Object toKey)
+  {
+    return new SubMap(nil, toKey);
+  }
+
+  public SortedMap tailMap(Object fromKey)
+  {
+    return new SubMap(fromKey, nil);
+  }
+
+  /** Returns a "collection view" (or "bag view") of this TreeMap's values. */
+  public Collection values()
+  {
+    // We don't bother overriding many of the optional methods, as doing so
+    // wouldn't provide any significant performance advantage.
+    return new AbstractCollection()
+    {
+      public int size()
+      {
+        return size;
+      }
+      
+      public Iterator iterator()
+      {
+        return new TreeIterator(TreeIterator.VALUES);
+      }
+      
+      public void clear()
+      {
+        TreeMap.this.clear();
+      }
+    };
+  }
+
+  // Find the "highest" node which is < key. If key is nil, return last node.
+  // Note that highestLessThan is exclusive (it won't return a key which is
+  // equal to "key"), while lowestGreaterThan is inclusive, in order to be 
+  // consistent with the semantics of subMap().
+  private Node highestLessThan(Object key)
+  {
+    if (key == nil)
+      return lastNode();
+  
+    Node last = nil;
+    Node current = root;
+    int comparison = 0;
+
+    while (current != nil)
+      {
+        last = current;
+        comparison = compare(key, current.key);
+	if (comparison > 0)
+	  current = current.right;
+	else if (comparison < 0)
+	  current = current.left;
+	else /* Exact match. */
+	  return predecessor(last);
+      }
+    if (comparison <= 0)
+      return predecessor(last);
+    else
+      return last;
+  }
+
+  // Find the "lowest" node which is >= key. If key is nil, return first node.
+  private Node lowestGreaterThan(Object key)
+  {
+    if (key == nil)
+      return firstNode();
+
+    Node last = nil;
+    Node current = root;
+    int comparison = 0;
+
+    while (current != nil)
+      {
+        last = current;
+        comparison = compare(key, current.key);
+	if (comparison > 0)
+	  current = current.right;
+	else if (comparison < 0)
+	  current = current.left;
+	else
+	  return current;
+      }
+    if (comparison > 0)
+      return successor(last);
+    else
+      return last;
+  }  
+
+  private void writeObject(ObjectOutputStream out) throws IOException
+  {
+    ObjectOutputStream.PutField fields = out.putFields();
+    fields.put("comparator", comparator);
+    out.writeFields();
+
+    Node node = firstNode();
+    out.writeInt(size);
+    
+    while (node != nil)
+      {
+        out.writeObject(node.key);
+	out.writeObject(node.value);
+	node = successor(node);
+      }
+  }
+
+  private void readObject(ObjectInputStream in)
+    throws IOException, ClassNotFoundException
+  {
+    ObjectInputStream.GetField fields = in.readFields();
+    comparator = (Comparator) fields.get("comparator", null);
+    int size = in.readInt();
+    putFromObjStream(in, size, true);
+  }
+
+  private int compare(Object o1, Object o2)
+  {
+    if (comparator == null)
+      return ((Comparable) o1).compareTo(o2);
+    else
+      return comparator.compare(o1, o2);
+  }
+
+  /* Return the node following Node, or nil if there isn't one. */
+  private Node successor(Node node)
+  {
+    if (node.right != nil)
+      {
+        node = node.right;
+	while (node.left != nil)
+	  node = node.left;
+	return node;
+      }
+
+    Node parent = node.parent;
+    while (parent != nil && node == parent.right)
+      {
+	node = parent;
+	parent = parent.parent;
+      }
+    return parent;
+  }
+
+  /* Return the node preceeding Node, or nil if there isn't one. */
+  private Node predecessor(Node node)
+  {
+    if (node.left != nil)
+      {
+        node = node.left;
+	while (node.right != nil)
+	  node = node.right;
+	return node;
+      }
+      
+    Node parent = node.parent;
+    while (parent != nil && node == parent.left)
+      {
+	node = parent;
+	parent = parent.parent;
+      }
+    return parent;
+  }
+
+  /** Rotate node n to the left. */
+  private void rotateLeft(Node node)
+  {
+    Node child = node.right;
+    
+    // Establish node.right link.
+    node.right = child.left;
+    if (child.left != nil)
+      child.left.parent = node;
+
+    // Establish child->parent link.
+    child.parent = node.parent;
+    if (node.parent != nil)
+      {
+        if (node == node.parent.left)
+	  node.parent.left = child;
+	else
+	  node.parent.right = child;
+      }
+    else
+      root = child;
+
+    // Link n and child.
+    child.left = node;
+    if (node != nil)
+      node.parent = child;
+  }
+
+  /** Rotate node n to the right. */
+  private void rotateRight(Node node)
+  {
+    Node child = node.left;
+    
+    // Establish node.left link.
+    node.left = child.right;
+    if (child.right != nil)
+      child.right.parent = node;
+      
+    // Establish child->parent link.
+    child.parent = node.parent;
+    if (node.parent != nil)
+      {
+        if (node == node.parent.right)
+	  node.parent.right = child;
+	else
+	  node.parent.left = child;
+      }
+    else
+      root = child;
+    
+    // Link n and child.
+    child.right = node;
+    if (node != nil)
+      node.parent = child;
+  }
+  
+  /* Construct a tree from sorted keys in linear time. This is used to
+     implement TreeSet's SortedSet constructor. */
+  void putKeysLinear(Iterator keys, int count)
+  {
+    fabricateTree(count);    
+    Node node = firstNode();
+    
+    for (int i = 0; i < count; i++)
+      {
+	node.key = keys.next();
+	node.value = Boolean.TRUE;
+	node = successor(node);
+      }
+  }
+  
+  /* As above, but load keys from an ObjectInputStream. Used by readObject()
+     methods. If "readValues" is set, entry values will also be read from the 
+     stream. If not, only keys will be read. */
+  void putFromObjStream(ObjectInputStream in, int count, boolean readValues) 
+    throws IOException, ClassNotFoundException
+  {
+    fabricateTree(count);    
+    Node node = firstNode();
+    
+    for (int i = 0; i < count; i++)
+      {
+	node.key = in.readObject();
+	if (readValues)
+	  node.value = in.readObject();
+	else
+	  node.value = Boolean.TRUE;	  
+	node = successor(node);
+      }
+  }
+     
+  /* Construct a perfectly balanced tree consisting of n "blank" nodes. 
+     This permits a tree to be generated from pre-sorted input in linear 
+     time. */
+  private void fabricateTree(int count)
+  {
+    if (count == 0)
+      return;
+    // Calculate the (maximum) depth of the perfectly balanced tree.
+    double ddepth = (Math.log (count + 1) / Math.log (2));
+    int maxdepth = (int) Math.ceil (ddepth);
+    
+    // The number of nodes which can fit in a perfectly-balanced tree of 
+    // height "depth - 1".
+    int max = (int) Math.pow (2, maxdepth - 1) - 1;
+    
+    // Number of nodes which spill over into the deepest row of the tree.
+    int overflow = (int) count - max;
+    
+    size = count;
+    // Make the root node.
+    root = new Node(null, null);
+    root.parent = nil;
+    root.left = nil;
+    root.right = nil;
+    
+    Node row = root;
+    for (int depth = 2; depth <= maxdepth; depth++)  // each row
+      {	
+	// Number of nodes at this depth
+	int rowcap = (int) Math.pow (2, depth - 1);
+	Node parent = row;
+	Node last = null;
+	
+	// Actual number of nodes to create in this row
+	int rowsize;
+	if (depth == maxdepth)
+	  rowsize = overflow;
+	else
+	  rowsize = rowcap;
+	
+	// The bottom most row of nodes is coloured red, as is every second row 
+	// going up, except the root node (row 1). I'm not sure if this is the 
+	// optimal configuration for the tree, but it seems logical enough.
+	// We just need to honour the black-height and red-parent rules here.
+	boolean colorRowRed = (depth % 2 == maxdepth % 2);
+	
+	int i;
+	for (i = 1; i <= rowsize; i++)  // each node in row
+	  {
+	    Node node = new Node(null, null);
+	    node.parent = parent;
+	    if (i % 2 == 1)
+	      parent.left = node;
+	    else
+	      {
+		Node nextparent = parent.right;
+		parent.right = node;
+		parent = nextparent;
+	      }
+	    if (last != null)
+	      last.right = node;
+	    last = node;
+	    
+	    if (colorRowRed)
+	      node.color = RED;
+	    
+	    if (i == 1)
+	      row = node;
+	  }
+
+        // Set nil child pointers on leaf nodes.
+	if (depth == maxdepth)
+	  {
+	    // leaf nodes at maxdepth-1.
+	    if (parent != null)
+	      {
+		if (i % 2 == 0)
+		  {
+	            // Current "parent" has "left" set already.
+		    Node next = parent.right;
+		    parent.right = nil;
+		    parent = next;
+		  }		  		  
+		while (parent != null)
+		  {
+		    parent.left = nil;
+		    Node next = parent.right;
+		    parent.right = nil;
+		    parent = next;
+		  }
+	      }
+	    // leaf nodes at maxdepth.
+	    Node node = row;
+	    Node next;
+	    while (node != null)
+	      {
+	        node.left = nil;
+		next = node.right;
+		node.right = nil;
+		node = next;
+	      }
+	  }
+      }
+  }
+  
+  private class VerifyResult
+  {
+    int count; // Total number of nodes.
+    int black; // Black height/depth.
+    int maxdepth; // Maximum depth of branch.
+  }
+
+  /* Check that red-black properties are consistent for the tree. */
+  private void verifyTree()
+  {
+    if (root == nil)
+      {
+        System.err.println ("Verify: empty tree");
+	if (size != 0)
+	  verifyError (this, "no root node but size=" + size);
+	return;
+      }
+    VerifyResult vr = verifySub (root);
+    if (vr.count != size)
+      {
+	verifyError (this, "Tree size not consistent with actual nodes counted. "
+                     + "counted " + vr.count + ", size=" + size);
+        System.exit(1);
+      }
+    System.err.println ("Verify: " + vr.count + " nodes, black height=" + vr.black
+                        + ", maxdepth=" + vr.maxdepth);
+  }
+  
+  /* Recursive call to check that rbtree rules hold. Returns total node count
+     and black height of the given branch. */
+  private VerifyResult verifySub(Node n)
+  {
+    VerifyResult vr1 = null;
+    VerifyResult vr2 = null;
+    
+    if (n.left == nil && n.right == nil)
+      {
+        // leaf node
+	VerifyResult r = new VerifyResult();
+	r.black = (n.color == BLACK ? 1 : 0);
+	r.count = 1;
+	r.maxdepth = 1;
+	return r;
+      }
+    
+    if (n.left != nil)
+      {
+        if (n.left.parent != n)
+	  verifyError(n.left, "Node's parent link does not point to " + n);
+	
+	if (n.color == RED && n.left.color == RED)
+	  verifyError(n, "Red node has red left child");
+	
+	vr1 = verifySub (n.left);
+	if (n.right == nil)
+	  {
+	    if (n.color == BLACK)
+	      vr1.black++;
+	    vr1.count++;
+	    vr1.maxdepth++;
+	    return vr1;
+	  }
+      }
+
+    if (n.right != nil)
+      {
+        if (n.right.parent != n)
+	  verifyError(n.right, "Node's parent link does not point to " + n);
+
+	if (n.color == RED && n.right.color == RED)
+	  verifyError(n, "Red node has red right child");
+
+	vr2 = verifySub (n.right);
+	if (n.left == nil)
+	  {
+	    if (n.color == BLACK)
+	      vr2.black++;
+	    vr2.count++;
+	    vr2.maxdepth++;
+	    return vr2;
+	  }
+      }
+    
+    if (vr1.black != vr2.black)
+      verifyError (n, "Black heights: " + vr1.black + "," + vr2.black + " don't match.");
+    vr1.count += vr2.count + 1;
+    vr1.maxdepth = Math.max(vr1.maxdepth, vr2.maxdepth) + 1;
+    if (n.color == BLACK)
+      vr1.black++;
+    return vr1;
+  }
+  
+  private void verifyError (Object obj, String msg)
+  {
+    System.err.print ("Verify error: ");
+    try
+      {
+        System.err.print (obj);
+      }
+    catch (Exception x)
+      {
+        System.err.print ("(error printing obj): " + x);
+      }
+    System.err.println();
+    System.err.println (msg);
+    Thread.dumpStack();
+    System.exit(1);
+  }
+
+  /**
+   * Iterate over HashMap's entries.
+   * This implementation is parameterized to give a sequential view of
+   * keys, values, or entries.
+   */   
+  class TreeIterator implements Iterator
+  {
+    static final int ENTRIES = 0,
+                     KEYS = 1,
+                     VALUES = 2;  
+  
+    // the type of this Iterator: KEYS, VALUES, or ENTRIES.
+    int type;
+    // the number of modifications to the backing Map that we know about.
+    int knownMod = TreeMap.this.modCount;
+    // The last Entry returned by a next() call.
+    Node last;
+    // The next entry that should be returned by next().
+    Node next;
+    // The last node visible to this iterator. This is used when iterating
+    // on a SubMap.
+    Node max;
+
+    /* Create Iterator with the supplied type: KEYS, VALUES, or ENTRIES */
+    TreeIterator(int type)
+    {
+      this.type = type;
+      this.next = firstNode();
+    }
+    
+    /* Construct an interator for a SubMap. Iteration will begin at node
+       "first", and stop when "max" is reached. */    
+    TreeIterator(int type, Node first, Node max)
+    {
+      this.type = type;
+      this.next = first;
+      this.max = max;
+    }
+
+    public boolean hasNext()
+    {
+      if (knownMod != TreeMap.this.modCount)
+	throw new ConcurrentModificationException();
+      return (next != nil);
+    }
+
+    public Object next()
+    {
+      if (knownMod != TreeMap.this.modCount)
+	throw new ConcurrentModificationException();
+      if (next == nil)
+	throw new NoSuchElementException();
+      Node n = next;
+
+      // Check limit in case we are iterating through a submap.
+      if (n != max)
+	next = successor(n);
+      else
+        next = nil;
+      
+      last = n;
+      
+      if (type == VALUES)
+        return n.value;
+      else if (type == KEYS)
+        return n.key;
+      return n;
+    }
+
+    public void remove()
+    {
+      if (knownMod != TreeMap.this.modCount)
+	throw new ConcurrentModificationException();
+
+      if (last == null)
+	throw new IllegalStateException();
+/*
+      Object key = null;
+      if (next != nil)
+        key = next.key;
+*/
+      TreeMap.this.removeNode(last);
+      knownMod++;
+/*
+      if (key != null)
+        next = getNode(key);
+*/	
+      last = null;
+    }
+  }
+
+  class SubMap extends AbstractMap implements SortedMap
+  {
+    Object minKey;
+    Object maxKey;
+
+    /* Create a SubMap representing the elements between minKey and maxKey
+       (inclusive). If minKey is nil, SubMap has no lower bound (headMap).
+       If maxKey is nil, the SubMap has no upper bound (tailMap). */
+    SubMap(Object minKey, Object maxKey)
+    {
+      this.minKey = minKey;
+      this.maxKey = maxKey;
+    }
+
+    public void clear()
+    {
+      Node current;
+      Node next = lowestGreaterThan(minKey);
+      Node max = highestLessThan(maxKey);
+      
+      if (compare(next.key, max.key) > 0)
+        // Nothing to delete.
+	return;
+        
+      do
+        {
+	  current = next;
+	  next = successor(current);
+	  remove(current);
+	}
+      while (current != max);
+    }
+    
+    /* Check if "key" is in within the range bounds for this SubMap. 
+       The lower ("from") SubMap range is inclusive, and the upper (to) bound
+       is exclusive. */
+    private boolean keyInRange(Object key)
+    {
+      return ((minKey == nil || compare(key, minKey) >= 0)
+	      && (maxKey == nil || compare(key, maxKey) < 0));
+    }
+
+    public boolean containsKey(Object key)
+    {
+      return (keyInRange(key) && TreeMap.this.containsKey(key));
+    }
+
+    public boolean containsValue(Object value)
+    {
+      Node node = lowestGreaterThan(minKey);
+      Node max = highestLessThan(maxKey);
+      Object currentVal;
+
+      if (node == nil || max == nil || compare(node.key, max.key) > 0)
+        // Nothing to search.
+	return false;
+
+      while (true)
+	{
+	  currentVal = node.getValue();
+          if (value == null ? currentVal == null : value.equals (currentVal))
+	    return true;
+	  if (node == max)
+	    return false;
+	  node = successor(node);
+	}
+    }
+
+    public Object get(Object key)
+    {
+      if (keyInRange(key))
+	return TreeMap.this.get(key);
+      return null;
+    }
+
+    public Object put(Object key, Object value)
+    {
+      if (keyInRange(key))
+	return TreeMap.this.put(key, value);
+      else
+	throw new IllegalArgumentException("Key outside range");
+    }
+
+    public Object remove(Object key)
+    {
+      if (keyInRange(key))
+	return TreeMap.this.remove(key);
+      else
+        return null;
+    }
+
+    public int size()
+    {
+      Node node = lowestGreaterThan(minKey);
+      Node max = highestLessThan(maxKey);
+
+      if (node == nil || max == nil || compare(node.key, max.key) > 0)
+	return 0;  // Empty.
+
+      int count = 1;
+      while (node != max)
+        {
+	  count++;
+	  node = successor(node);
+	}
+
+      return count;
+    }
+
+    public Set entrySet()
+    {
+      // Create an AbstractSet with custom implementations of those methods that 
+      // can be overriden easily and efficiently.
+      return new AbstractSet()
+      {
+	public int size()
+	{
+          return SubMap.this.size();
+	}
+
+	public Iterator iterator()
+	{
+	  Node first = lowestGreaterThan(minKey);
+	  Node max = highestLessThan(maxKey);
+          return new TreeIterator(TreeIterator.ENTRIES, first, max);
+	}
+
+	public void clear()
+	{
+          this.clear();
+	}
+
+	public boolean contains(Object o)
+	{
+          if (!(o instanceof Map.Entry))
+	    return false;
+	  Map.Entry me = (Map.Entry) o;
+	  Object key = me.getKey();
+	  if (!keyInRange(key))
+	    return false;
+	  Node n = getNode(key);
+	  return (n != nil && me.getValue().equals(n.value));
+	}
+
+	public boolean remove(Object o)
+	{
+          if (!(o instanceof Map.Entry))
+	    return false;
+	  Map.Entry me = (Map.Entry) o;
+	  Object key = me.getKey();
+	  if (!keyInRange(key))
+	    return false;
+	  Node n = getNode(key);
+	  if (n != nil && me.getValue().equals(n.value))
+	    {
+	      removeNode(n);
+	      return true;
+	    }
+	  return false;
+	}
+      };    
+    }
+
+    public Comparator comparator()
+    {
+      return comparator;
+    }
+
+    public Object firstKey()
+    {
+      Node node = lowestGreaterThan(minKey);
+      // Do a range check in case SubMap is empty.
+      if (keyInRange(node.key))
+        return node.key;
+      return null;
+    }
+
+    public Object lastKey()
+    {
+      Node node = highestLessThan(maxKey);
+      // Do a range check in case SubMap is empty.
+      if (keyInRange(node.key))
+        return node.key;
+      return null;
+    }
+
+    public SortedMap subMap(Object fromKey, Object toKey)
+    {
+      if (!keyInRange(fromKey) || !keyInRange(toKey))
+        throw new IllegalArgumentException("key outside range");
+
+      return TreeMap.this.subMap(fromKey, toKey);
+    }
+
+    public SortedMap headMap(Object toKey)
+    {
+      if (!keyInRange(toKey))
+        throw new IllegalArgumentException("key outside range");
+
+      return TreeMap.this.subMap(minKey, toKey);
+    }
+
+    public SortedMap tailMap(Object fromKey)
+    {
+      if (!keyInRange(fromKey))
+        throw new IllegalArgumentException("key outside range");
+
+      return TreeMap.this.subMap(fromKey, maxKey);
+    }
+  }
+}
diff --git a/libjava/java/util/TreeSet.java b/libjava/java/util/TreeSet.java
new file mode 100644
index 00000000000..36224aab852
--- /dev/null
+++ b/libjava/java/util/TreeSet.java
@@ -0,0 +1,289 @@
+/* TreeSet.java -- a class providing a TreeMap-backet SortedSet
+   Copyright (C) 1999, 2000, 2001 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;
+
+/**
+ * This class provides a TreeMap-backed implementation of the 
+ * SortedSet interface.
+ *
+ * Each element in the Set is a key in the backing TreeMap; each key
+ * maps to a static token, denoting that the key does, in fact, exist.
+ *
+ * Most operations are O(log n).
+ *
+ * TreeSet is a part of the JDK1.2 Collections API.
+ *
+ * @author      Jon Zeppieri
+ * @version     $Revision: 1.7 $
+ * @modified    $Id: TreeSet.java,v 1.7 2000/10/26 10:19:01 bryce Exp $
+ */
+
+public class TreeSet extends AbstractSet
+  implements SortedSet, Cloneable, Serializable
+{
+  /** The TreeMap which backs this Set */
+  transient SortedMap map;
+
+  static final long serialVersionUID = -2479143000061671589L;
+
+  /**
+   * Construct a new TreeSet whose backing TreeMap using the "natural" 
+   * ordering of keys.
+   */
+  public TreeSet()
+  {
+    map = new TreeMap();
+  }
+
+  /** 
+   * Construct a new TreeSet whose backing TreeMap uses the supplied 
+   * Comparator.
+   *
+   * @param     oComparator      the Comparator this Set will use
+   */
+  public TreeSet(Comparator comparator)
+  {
+    map = new TreeMap(comparator);
+  }
+
+  /** 
+   * Construct a new TreeSet whose backing TreeMap uses the "natural"
+   * orering of the keys and which contains all of the elements in the
+   * supplied Collection.
+   *
+   * @param     oCollection      the new Set will be initialized with all
+   *                             of the elements in this Collection
+   */
+  public TreeSet(Collection collection)
+  {
+    map = new TreeMap();
+    addAll(collection);
+  }
+
+  /**
+   * Construct a new TreeSet, using the same key ordering as the supplied
+   * SortedSet and containing all of the elements in the supplied SortedSet.
+   * This constructor runs in linear time.
+   *
+   * @param     sortedSet       the new TreeSet will use this SortedSet's
+   *                            comparator and will initialize itself
+   *                            with all of the elements in this SortedSet
+   */
+  public TreeSet(SortedSet sortedSet)
+  {
+    TreeMap map = new TreeMap(sortedSet.comparator());
+    int i = 0;
+    Iterator itr = sortedSet.iterator();
+    map.putKeysLinear(itr, sortedSet.size());
+    this.map = map;
+  }
+  
+  /* This private constructor is used to implement the subSet() calls around
+    a backing TreeMap.SubMap. */
+  TreeSet(SortedMap backingMap)
+  {
+    map = backingMap;
+  }
+
+  /** 
+   * Adds the spplied Object to the Set if it is not already in the Set;
+   * returns true if the element is added, false otherwise
+   *
+   * @param       obj       the Object to be added to this Set
+   */
+  public boolean add(Object obj)
+  {
+    return (map.put(obj, Boolean.TRUE) == null);
+  }
+
+  /**
+   * Adds all of the elements in the supplied Collection to this TreeSet.
+   *
+   * @param        c         All of the elements in this Collection
+   *                         will be added to the Set.
+   *
+   * @return       true if the Set is altered, false otherwise
+   */
+  public boolean addAll(Collection c)
+  {
+    boolean result = false;
+    int size = c.size();
+    Iterator itr = c.iterator();
+
+    for (int i = 0; i < size; i++)
+      result |= (map.put(itr.next(), Boolean.TRUE) == null);
+
+    return result;
+  }
+
+  /**
+   * Removes all elements in this Set.
+   */
+  public void clear()
+  {
+    map.clear();
+  }
+
+  /** Returns a shallow copy of this Set. */
+  public Object clone()
+  {
+    TreeSet copy = new TreeSet();
+    try
+      {
+	copy.map = (TreeMap) map.clone();
+      }
+    catch (CloneNotSupportedException ex)
+      {
+      }
+
+    return copy;
+  }
+
+  /** Returns this Set's comparator */
+  public Comparator comparator()
+  {
+    return map.comparator();
+  }
+
+  /** 
+   * Returns true if this Set contains the supplied Object, 
+   * false otherwise 
+   *
+   * @param       oObject        the Object whose existence in the Set is
+   *                             being tested
+   */
+  public boolean contains(Object obj)
+  {
+    return map.containsKey(obj);
+  }
+
+  /** Returns true if this Set has size 0, false otherwise */
+  public boolean isEmpty()
+  {
+    return map.isEmpty();
+  }
+
+  /** Returns the number of elements in this Set */
+  public int size()
+  {
+    return map.size();
+  }
+
+  /** 
+   * If the supplied Object is in this Set, it is removed, and true is
+   * returned; otherwise, false is returned.
+   *
+   * @param         obj        the Object we are attempting to remove
+   *                           from this Set
+   */
+  public boolean remove(Object obj)
+  {
+    return (map.remove(obj) != null);
+  }
+
+  /** Returns the first (by order) element in this Set */
+  public Object first()
+  {
+    return map.firstKey();
+  }
+
+  /** Returns the last (by order) element in this Set */
+  public Object last()
+  {
+    return map.lastKey();
+  }
+
+  /**
+   * Returns a view of this Set including all elements in the interval
+   * [oFromElement, oToElement).
+   *
+   * @param       from  the resultant view will contain all
+   *                    elements greater than or equal to this element
+   * @param       to    the resultant view will contain all
+   *                    elements less than this element
+   */
+  public SortedSet subSet(Object from, Object to)
+  {
+    return new TreeSet(map.subMap(from, to));
+  }
+
+  /**
+   * Returns a view of this Set including all elements less than oToElement
+   *
+   * @param       toElement    the resultant view will contain all
+   *                            elements less than this element
+   */
+  public SortedSet headSet(Object to)
+  {
+    return new TreeSet(map.headMap(to));
+  }
+
+  /**
+   * Returns a view of this Set including all elements greater than or
+   * equal to oFromElement.
+   *
+   * @param       from  the resultant view will contain all
+   *              elements greater than or equal to this element
+   */
+  public SortedSet tailSet(Object from)
+  {
+    return new TreeSet(map.tailMap(from));
+  }
+
+  /** Returns in Iterator over the elements in this TreeSet */
+  public Iterator iterator()
+  {
+    return map.keySet().iterator();
+  }
+
+  private void writeObject(ObjectOutputStream out) throws IOException
+  {
+    Iterator itr = map.keySet().iterator();
+
+    out.writeObject(map.comparator());
+    out.writeInt(map.size());
+
+    while (itr.hasNext())
+      out.writeObject(itr.next());
+  }
+
+  private void readObject(ObjectInputStream in)
+    throws IOException, ClassNotFoundException
+  {
+    Comparator comparator = (Comparator) in.readObject();
+    int size = in.readInt();
+    TreeMap map = new TreeMap(comparator);    
+    map.putFromObjStream(in, size, false);
+    this.map = map;
+  }
+}