re PR libgcj/1758 (java.util package lacks TreeMap)

        * 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.

From-SVN: r39657

1 files changed, 289 insertions, 0 deletions

diff --git a/libjava/java/util/TreeSet.java b/libjava/java/util/TreeSet.java
new file mode 100644
index 0000000..36224aa
--- /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;
+  }
+}