From a142a996267f9c8adf239a565725174265c67749 Mon Sep 17 00:00:00 2001 From: Bryce McKinlay Date: Wed, 14 Feb 2001 04:44:21 +0000 Subject: [PATCH] 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 --- libjava/ChangeLog | 12 + libjava/Makefile.am | 6 +- libjava/Makefile.in | 15 +- libjava/java/util/HashMap.java | 21 +- libjava/java/util/HashSet.java | 7 +- libjava/java/util/SortedSet.java | 5 +- libjava/java/util/TreeMap.java | 1450 ++++++++++++++++++++++++++++++ libjava/java/util/TreeSet.java | 289 ++++++ 8 files changed, 1781 insertions(+), 24 deletions(-) create mode 100644 libjava/java/util/TreeMap.java create mode 100644 libjava/java/util/TreeSet.java 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 + + * 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 * 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 Introduction to Algorithms. In other words, + * I cribbed from the same pseudocode as Sun. 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. + * + * 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; + } +} -- 2.30.2