[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Large collections update
|
From: |
Bryce McKinlay |
|
Subject: |
Large collections update |
|
Date: |
Thu, 15 Feb 2001 19:29:03 +1300 |
I'm checking in a patch which re-syncs classpath with the collections
code that I've been working on in the GCJ tree.
One change worth noting is the code to build a TreeMap from sorted
input in linear time (used for deserialization, clone, etc) - now done
without recursion and without any temporary storage! The trick in this
case turned out to be to first construct a perfectly balanced,
properly linked and "colored" tree with the correct number of nodes,
and then then go back and fill in the keys and values on each node
from the bottom up using the standard "successor" logic. Seems easy in
retrospect, but it took me a while to nail this one ;-)
These implementations pass all the example cases from the JCL as well
as MapBash and SetBash from javacollections.org,
GCJ<->JDK serialization interoperability tests, MapTest from Kaffe,
etc. In addition, with the exception of TreeMap/TreeSet which I just
completed recently, most of this code has been in the GCJ tree for
some time and so should be fairly well tested with "real" apps.
Because TreeMap, HashMap, and Hashtable were largely rewritten, I've
included classes themselves here rather diffs, which are huge and
ugly.
regards
[ bryce ]
2001-02-15 Bryce McKinlay <address@hidden>
* java/util/HashMap.java: Rewritten.
* java/util/Hashtable.java: Rewritten based on new HashMap code.
* java/util/TreeMap.java: Rewritten.
* java/util/Bucket.java: Deleted.
* java/util/BasicMapEntry.java: Remove unneccessary comments.
(equals): Simplified. Made final.
(getKey): Made final.
(getValue): Likewise.
(toString): New method.
* java/util/Collections.java (search): Use a for-loop, not iterator
hasNext().
(copy): Use a for-loop. Throw an IndexOutOfBoundsException if run out
of elements in source.
(max): Use a for-loop.
(min): Ditto.
(reverse): Keep track of positions instead of using Iterator's
nextIndex() and previousIndex().
(shuffle(List)): Initialize defaultRandom if required using
double-check thread safety idiom. Call two-argument shuffle method
using defaultRandom.
(defaultRandom): New field.
(shuffle(List, Random)): Use a for-loop. Keep track of pos instead of
using previousIndex() and nextIndex().
(singletonMap(iterator)): Use a HashMap.Entry, not BasicMapEntry.
(ReverseComparator): New static class.
(reverseOrder): Return static instance of ReverseComparator.
* java/util/AbstractCollection.java (toString): Use a StringBuffer.
* java/util/AbstractMap.java (toString): Use StringBuffer.
Index: java/util/AbstractCollection.java
===================================================================
RCS file: /cvs/classpath/java/util/AbstractCollection.java,v
retrieving revision 1.8
diff -u -r1.8 AbstractCollection.java
--- java/util/AbstractCollection.java 2000/10/30 02:02:48 1.8
+++ java/util/AbstractCollection.java 2001/02/15 06:00:03
@@ -332,14 +332,14 @@
{
Iterator itr = iterator();
int size = size();
- String r = "[";
+ StringBuffer r = new StringBuffer("[");
for (int pos = 0; pos < size; pos++)
{
- r += itr.next();
+ r.append(itr.next());
if (pos < size - 1)
- r += ", ";
+ r.append(", ");
}
- r += "]";
- return r;
+ r.append("]");
+ return r.toString();
}
}
Index: java/util/AbstractMap.java
===================================================================
RCS file: /cvs/classpath/java/util/AbstractMap.java,v
retrieving revision 1.13
diff -u -r1.13 AbstractMap.java
--- java/util/AbstractMap.java 2000/10/30 02:02:48 1.13
+++ java/util/AbstractMap.java 2001/02/15 06:00:03
@@ -227,15 +227,18 @@
{
Iterator entries = entrySet().iterator();
int size = size();
- String r = "{";
+ StringBuffer r = new StringBuffer("{");
for (int pos = 0; pos < size; pos++)
{
- r += entries.next();
+ // Append the toString value of the entries rather than calling
+ // getKey/getValue. This is more efficient and it matches the JDK
+ // behaviour.
+ r.append(entries.next());
if (pos < size - 1)
- r += ", ";
+ r.append(", ");
}
- r += "}";
- return r;
+ r.append("}");
+ return r.toString();
}
public Collection values()
Index: java/util/AbstractSequentialList.java
===================================================================
RCS file: /cvs/classpath/java/util/AbstractSequentialList.java,v
retrieving revision 1.11
diff -u -r1.11 AbstractSequentialList.java
--- java/util/AbstractSequentialList.java 2000/11/02 10:12:57 1.11
+++ java/util/AbstractSequentialList.java 2001/02/15 06:00:03
@@ -38,7 +38,6 @@
*/
public abstract class AbstractSequentialList extends AbstractList
{
-
/**
* Returns a ListIterator over the list, starting from position index.
* Subclasses must provide an implementation of this method.
Index: java/util/AbstractSet.java
===================================================================
RCS file: /cvs/classpath/java/util/AbstractSet.java,v
retrieving revision 1.9
diff -u -r1.9 AbstractSet.java
--- java/util/AbstractSet.java 2000/10/30 02:02:48 1.9
+++ java/util/AbstractSet.java 2001/02/15 06:00:03
@@ -38,7 +38,6 @@
*/
public abstract class AbstractSet extends AbstractCollection implements Set
{
-
/**
* Tests whether the given object is equal to this Set. This implementation
* first checks whether this set <em>is</em> the given object, and returns
Index: java/util/ArrayList.java
===================================================================
RCS file: /cvs/classpath/java/util/ArrayList.java,v
retrieving revision 1.13
diff -u -r1.13 ArrayList.java
--- java/util/ArrayList.java 2000/12/17 11:52:36 1.13
+++ java/util/ArrayList.java 2001/02/15 06:00:03
@@ -40,7 +40,7 @@
* to or removing from the end of a list, checking the size, &c.
*
* @author Jon A. Zeppieri
- * @version $Id: ArrayList.java,v 1.13 2000/12/17 11:52:36 bryce Exp $
+ * @version $Id: ArrayList.java,v 1.6 2000/12/17 11:51:14 bryce Exp $
* @see java.util.AbstractList
* @see java.util.List
*/
Index: java/util/BasicMapEntry.java
===================================================================
RCS file: /cvs/classpath/java/util/BasicMapEntry.java,v
retrieving revision 1.5
diff -u -r1.5 BasicMapEntry.java
--- java/util/BasicMapEntry.java 2000/10/26 10:19:00 1.5
+++ java/util/BasicMapEntry.java 2001/02/15 06:00:03
@@ -1,6 +1,6 @@
/* BasicMapEntry.java -- a class providing a plain-vanilla implementation of
the Map.Entry interface; could be used anywhere in java.util
- Copyright (C) 1998 Free Software Foundation, Inc.
+ Copyright (C) 1998, 2000 Free Software Foundation, Inc.
This file is part of GNU Classpath.
@@ -29,108 +29,64 @@
package java.util;
/**
- * a class which implements Map.Entry
+ * A class which implements Map.Entry. It is shared by HashMap, TreeMap, and
+ * Hashtable.
*
* @author Jon Zeppieri
- * @version $Revision: 1.5 $
- * @modified $Id: BasicMapEntry.java,v 1.5 2000/10/26 10:19:00 bryce Exp $
+ * @version $Revision: 1.3 $
+ * @modified $Id: BasicMapEntry.java,v 1.3 2000/12/21 02:00:15 bryce Exp $
*/
class BasicMapEntry implements Map.Entry
{
- /** the key */
Object key;
- /** the value */
Object value;
- /**
- * construct a new BasicMapEntry with the given key and value
- *
- * @param newKey the key of this Entry
- * @param newValue the value of this Entry
- */
BasicMapEntry(Object newKey, Object newValue)
{
key = newKey;
value = newValue;
}
- /**
- * returns true if <pre>o</pre> is a Map.Entry and
- * <pre>
- * (((o.getKey == null) ? (key == null) :
- * o.getKey().equals(key)) &&
- * ((o.getValue() == null) ? (value == null) :
- * o.getValue().equals(value)))
- * </pre>
- *
- * NOTE: the calls to getKey() and getValue() in this implementation
- * are <i>NOT</i> superfluous and should not be removed. They insure
- * that subclasses such as HashMapEntry work correctly
- *
- * @param o the Object being tested for equality
- */
- public boolean equals(Object o)
+ public final boolean equals(Object o)
{
- Map.Entry tester;
- Object oTestingKey, oTestingValue;
- Object oKey, oValue;
- if (o instanceof Map.Entry)
- {
- tester = (Map.Entry) o;
- oKey = getKey();
- oValue = getValue();
- oTestingKey = tester.getKey();
- oTestingValue = tester.getValue();
- return (((oTestingKey == null) ? (oKey == null) :
- oTestingKey.equals(oKey)) &&
- ((oTestingValue == null) ? (oValue == null) :
- oTestingValue.equals(oValue)));
- }
- return false;
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry e = (Map.Entry) o;
+ return (key == null ? e.getKey() == null : key.equals(e.getKey())
+ && value == null ? e.getValue() == null
+ : value.equals(e.getValue()));
}
- /** returns the key */
- public Object getKey()
+ public final Object getKey()
{
return key;
}
- /** returns the value */
- public Object getValue()
+ public final Object getValue()
{
return value;
}
- /** the hashCode() for a Map.Entry is
- * <pre>
- * ((getKey() == null) ? 0 : getKey().hashCode()) ^
- * ((getValue() == null) ? 0 : getValue().hashCode());
- * </pre>
- *
- * NOTE: the calls to getKey() and getValue() in this implementation
- * are <i>NOT</i> superfluous and should not be removed. They insure
- * that subclasses such as HashMapEntry work correctly
- */
- public int hashCode()
+ public final int hashCode()
{
- Object oKey = getKey();
- Object oValue = getValue();
- return ((oKey == null) ? 0 : oKey.hashCode()) ^
- ((oValue == null) ? 0 : oValue.hashCode());
+ int kc = (key == null ? 0 : key.hashCode());
+ int vc = (value == null ? 0 : value.hashCode());
+ return kc ^ vc;
}
/**
- * sets the value of this Map.Entry
- *
- * @param newValue the new value of this Map.Entry
+ * sets the value of this Map.Entry. Note that this is overriden by
+ * Hashtable.Entry, which does not permit a null value.
*/
- public Object setValue(Object newValue)
- throws UnsupportedOperationException, ClassCastException,
- IllegalArgumentException, NullPointerException
+ public Object setValue(Object newVal)
{
- Object oVal = value;
- value = newValue;
- return oVal;
+ Object r = value;
+ value = newVal;
+ return r;
}
-}
+ public final String toString()
+ {
+ return key + "=" + value;
+ }
+}
Index: java/util/Collections.java
===================================================================
RCS file: /cvs/classpath/java/util/Collections.java,v
retrieving revision 1.16
diff -u -r1.16 Collections.java
--- java/util/Collections.java 2000/11/27 08:28:47 1.16
+++ java/util/Collections.java 2001/02/15 06:00:03
@@ -149,10 +149,10 @@
// is sequential-access.
if (l instanceof AbstractSequentialList)
{
- ListIterator i = l.listIterator();
- while (i.hasNext())
+ ListIterator itr = l.listIterator();
+ for (int i = l.size() - 1; i >= 0; --i)
{
- final int d = compare(key, i.next(), c);
+ final int d = compare(key, itr.next(), c);
if (d == 0)
{
return pos;
@@ -264,10 +264,18 @@
{
Iterator i1 = source.iterator();
ListIterator i2 = dest.listIterator();
- while (i1.hasNext())
+
+ try
+ {
+ for (int i = source.size() - 1; i >= 0; --i)
+ {
+ i2.next();
+ i2.set(i1.next());
+ }
+ }
+ catch (NoSuchElementException x)
{
- i2.next();
- i2.set(i1.next());
+ throw new IndexOutOfBoundsException("Source doesn't fit in dest.");
}
}
@@ -305,11 +313,11 @@
*/
public static void fill(List l, Object val)
{
- ListIterator i = l.listIterator();
- while (i.hasNext())
+ ListIterator itr = l.listIterator();
+ for (int i = l.size() - 1; i >= 0; --i)
{
- i.next();
- i.set(val);
+ itr.next();
+ itr.set(val);
}
}
@@ -326,11 +334,12 @@
*/
public static Object max(Collection c)
{
- Iterator i = c.iterator();
- Comparable max = (Comparable) i.next(); // throws NoSuchElementException
- while (i.hasNext())
+ Iterator itr = c.iterator();
+ Comparable max = (Comparable) itr.next(); // throws NoSuchElementException
+ int csize = c.size();
+ for (int i = 1; i < csize; i++)
{
- Object o = i.next();
+ Object o = itr.next();
if (max.compareTo(o) < 0)
{
max = (Comparable) o;
@@ -352,15 +361,14 @@
*/
public static Object max(Collection c, Comparator order)
{
- Iterator i = c.iterator();
- Object max = i.next(); // throws NoSuchElementException
- while (i.hasNext())
+ Iterator itr = c.iterator();
+ Object max = itr.next(); // throws NoSuchElementException
+ int csize = c.size();
+ for (int i = 1; i < csize; i++)
{
- Object o = i.next();
+ Object o = itr.next();
if (order.compare(max, o) < 0)
- {
- max = o;
- }
+ max = o;
}
return max;
}
@@ -378,15 +386,14 @@
*/
public static Object min(Collection c)
{
- Iterator i = c.iterator();
- Comparable min = (Comparable) i.next(); // throws NoSuchElementException
- while (i.hasNext())
+ Iterator itr = c.iterator();
+ Comparable min = (Comparable) itr.next(); // throws NoSuchElementException
+ int csize = c.size();
+ for (int i = 1; i < csize; i++)
{
- Object o = i.next();
+ Object o = itr.next();
if (min.compareTo(o) > 0)
- {
- min = (Comparable) o;
- }
+ min = (Comparable) o;
}
return min;
}
@@ -404,15 +411,14 @@
*/
public static Object min(Collection c, Comparator order)
{
- Iterator i = c.iterator();
- Object min = i.next(); // throws NoSuchElementExcception
- while (i.hasNext())
+ Iterator itr = c.iterator();
+ Object min = itr.next(); // throws NoSuchElementExcception
+ int csize = c.size();
+ for (int i = 1; i < csize; i++)
{
- Object o = i.next();
+ Object o = itr.next();
if (order.compare(min, o) > 0)
- {
- min = o;
- }
+ min = o;
}
return min;
}
@@ -441,7 +447,6 @@
// Create a minimal implementation of List
return new AbstractList()
{
-
public int size()
{
return n;
@@ -468,31 +473,38 @@
public static void reverse(List l)
{
ListIterator i1 = l.listIterator();
- ListIterator i2 = l.listIterator(l.size());
- while (i1.nextIndex() < i2.previousIndex())
+ int pos1 = 0;
+ int pos2 = l.size();
+ ListIterator i2 = l.listIterator(pos2);
+ while (pos1 < pos2)
{
Object o = i1.next();
i1.set(i2.previous());
i2.set(o);
+ ++pos1;
+ --pos2;
}
}
+ static class ReverseComparator implements Comparator, Serializable
+ {
+ public int compare(Object a, Object b)
+ {
+ return -((Comparable) a).compareTo(b);
+ }
+ }
+
+ static ReverseComparator rcInstance = new ReverseComparator();
+
/**
* Get a comparator that implements the reverse of natural ordering. This is
* intended to make it easy to sort into reverse order, by simply passing
* Collections.reverseOrder() to the sort method. The return value of this
* method is Serializable.
*/
- // The return value isn't Serializable, because the spec is broken.
public static Comparator reverseOrder()
{
- return new Comparator()
- {
- public int compare(Object a, Object b)
- {
- return -((Comparable) a).compareTo(b);
- }
- };
+ return rcInstance;
}
/**
@@ -513,9 +525,24 @@
*/
public static void shuffle(List l)
{
- shuffle(l, new Random());
+ if (defaultRandom == null)
+ {
+ synchronized (Collections.class)
+ {
+ if (defaultRandom == null)
+ defaultRandom = new Random();
+ }
+ }
+ shuffle(l, defaultRandom);
}
+ /** Cache a single Random object for use by shuffle(List). This improves
+ * performance as well as ensuring that sequential calls to shuffle() will
+ * not result in the same shuffle order occuring: the resolution of
+ * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
+ */
+ private static Random defaultRandom = null;
+
/**
* Shuffle a list according to a given source of randomness. The algorithm
* used iterates backwards over the list, swapping each element with an
@@ -541,20 +568,21 @@
public static void shuffle(List l, Random r)
{
Object[] a = l.toArray(); // Dump l into an array
- ListIterator i = l.listIterator(l.size());
+ int lsize = l.size();
+ ListIterator i = l.listIterator(lsize);
// Iterate backwards over l
- while (i.hasPrevious())
+ for (int pos = lsize - 1; pos >= 0; --pos)
{
- // Obtain a random position to swap with. nextIndex is used so that the
+ // Obtain a random position to swap with. pos + 1 is used so that the
// range of the random number includes the current position.
- int swap = r.nextInt(i.nextIndex());
+ int swap = r.nextInt(pos + 1);
// Swap the swapth element of the array with the next element of the
// list.
Object o = a[swap];
- a[swap] = a[i.previousIndex()];
- a[i.previousIndex()] = o;
+ a[swap] = a[pos];
+ a[pos] = o;
// Set the element in the original list accordingly.
i.previous();
@@ -658,7 +686,7 @@
{
public Set entrySet()
{
- return singleton(new BasicMapEntry(key, value));
+ return singleton(new HashMap.Entry(key, value));
}
};
}
Index: java/util/HashSet.java
===================================================================
RCS file: /cvs/classpath/java/util/HashSet.java,v
retrieving revision 1.5
diff -u -r1.5 HashSet.java
--- java/util/HashSet.java 2000/10/26 10:19:00 1.5
+++ java/util/HashSet.java 2001/02/15 06:00:03
@@ -45,19 +45,16 @@
* 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.2 $
+ * @modified $Id: HashSet.java,v 1.2 2001/02/14 04:44:21 bryce Exp $
*/
public class HashSet extends AbstractSet
implements Set, Cloneable, Serializable
{
- // INSTANCE VARIABLES -------------------------------------------------
/** the HashMap which backs this Set */
- private transient HashMap map;
+ transient HashMap map;
static final long serialVersionUID = -5024744406713321676L;
- // CONSTRUCTORS ---------------------------------------------------------
-
/**
* construct a new, empty HashSet whose backing HashMap has the default
* capacity and loadFacor
@@ -106,9 +103,6 @@
addAll(c);
}
-
- // PUBLIC METHODS ---------------------------------------------------------
-
/**
* adds the given Object to the set if it is not already in the Set,
* returns true if teh element was added, false otherwise
@@ -117,15 +111,7 @@
*/
public boolean add(Object o)
{
- if (map.containsKey(o))
- {
- return false;
- }
- else
- {
- internalAdd(o);
- return true;
- }
+ return (map.put(o, Boolean.TRUE) == null);
}
/**
@@ -142,11 +128,9 @@
*/
public Object clone()
{
- Iterator it = iterator();
- HashSet clone = new HashSet(map.capacity, map.loadFactor);
- while (it.hasNext())
- clone.internalAdd(it.next());
- return clone;
+ HashSet copy = new HashSet();
+ copy.map = (HashMap) map.clone();
+ return copy;
}
/**
@@ -192,51 +176,38 @@
{
return map.size();
}
-
-
- // PRIVATE METHODS
-----------------------------------------------------------
-
- /**
- * adds the supplied element to this Set; this private method is used
- * internally [clone()] instead of add(), because add() can be overridden
- * to do unexpected things
- *
- * @param o the Object to add to this Set
- */
- private void internalAdd(Object o)
- {
- map.put(o, Boolean.TRUE);
- }
- /** Serialize this Object in a manner which is binary-compatible with the
JDK */
+ /** Serialize this Object in a manner which is binary-compatible with the
+ * JDK */
private void writeObject(ObjectOutputStream s) throws IOException
{
Iterator it = iterator();
- s.writeInt(map.capacity);
+ s.writeInt(map.buckets.length);
s.writeFloat(map.loadFactor);
- s.writeInt(size());
+ s.writeInt(map.size);
while (it.hasNext())
s.writeObject(it.next());
}
- /** Deserialize this Object in a manner which is binary-compatible with the
JDK */
+ /** Deserialize this Object in a manner which is binary-compatible with
+ * the JDK */
private void readObject(ObjectInputStream s) throws IOException,
ClassNotFoundException
{
- int i, iSize, iCapacity;
- float fLoadFactor;
- Object oElement;
+ int i, size, capacity;
+ float loadFactor;
+ Object element;
- iCapacity = s.readInt();
- fLoadFactor = s.readFloat();
- iSize = s.readInt();
+ capacity = s.readInt();
+ loadFactor = s.readFloat();
+ size = s.readInt();
- map = new HashMap(iCapacity, fLoadFactor);
+ map = new HashMap(capacity, loadFactor);
- for (i = 0; i < iSize; i++)
+ for (i = 0; i < size; i++)
{
- oElement = s.readObject();
- internalAdd(oElement);
+ element = s.readObject();
+ map.put(element, Boolean.TRUE);
}
}
}
Index: java/util/Set.java
===================================================================
RCS file: /cvs/classpath/java/util/Set.java,v
retrieving revision 1.4
diff -u -r1.4 Set.java
--- java/util/Set.java 2000/10/26 10:19:01 1.4
+++ java/util/Set.java 2001/02/15 06:00:03
@@ -45,5 +45,5 @@
boolean removeAll(Collection c);
boolean retainAll(Collection c);
int size();
- Object[]toArray();
+ Object[] toArray();
}
Index: java/util/TreeSet.java
===================================================================
RCS file: /cvs/classpath/java/util/TreeSet.java,v
retrieving revision 1.7
diff -u -r1.7 TreeSet.java
--- java/util/TreeSet.java 2000/10/26 10:19:01 1.7
+++ java/util/TreeSet.java 2001/02/15 06:00:03
@@ -1,5 +1,5 @@
/* TreeSet.java -- a class providing a TreeMap-backet SortedSet
- Copyright (C) 1999, 2000 Free Software Foundation, Inc.
+ Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
This file is part of GNU Classpath.
@@ -44,29 +44,25 @@
* 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 $
+ * @version $Revision: 1.2 $
+ * @modified $Id: TreeSet.java,v 1.2 2001/02/15 03:59:57 bryce Exp $
*/
public class TreeSet extends AbstractSet
implements SortedSet, Cloneable, Serializable
{
- // INSTANCE VARIABLES -------------------------------------------------
-
/** The TreeMap which backs this Set */
- transient SortedMap _oMap;
- static final long serialVersionUID = -2479143000061671589L;
-
+ transient SortedMap map;
- // CONSTRUCTORS -------------------------------------------------------
+ static final long serialVersionUID = -2479143000061671589L;
/**
- * Construct a new TreeSet whose backing TreeMap using the "natural" ordering
- * of keys.
+ * Construct a new TreeSet whose backing TreeMap using the "natural"
+ * ordering of keys.
*/
public TreeSet()
{
- this((Comparator) null);
+ map = new TreeMap();
}
/**
@@ -75,9 +71,9 @@
*
* @param oComparator the Comparator this Set will use
*/
- public TreeSet(Comparator oComparator)
+ public TreeSet(Comparator comparator)
{
- _oMap = new TreeMap(oComparator);
+ map = new TreeMap(comparator);
}
/**
@@ -88,10 +84,10 @@
* @param oCollection the new Set will be initialized with all
* of the elements in this Collection
*/
- public TreeSet(Collection oCollection)
+ public TreeSet(Collection collection)
{
- this((Comparator) null);
- addAll(oCollection);
+ map = new TreeMap();
+ addAll(collection);
}
/**
@@ -99,68 +95,55 @@
* SortedSet and containing all of the elements in the supplied SortedSet.
* This constructor runs in linear time.
*
- * @param oSortedSet the new TreeSet will use this SortedSet's
- * comparator and will initialize itself
- * with all of the elements in this SortedSet
+ * @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 oSortedSet)
+ public TreeSet(SortedSet sortedSet)
{
- TreeMap oMap = new TreeMap(oSortedSet.comparator());
- _oMap = oMap;
+ TreeMap map = new TreeMap(sortedSet.comparator());
int i = 0;
- Map.Entry[]arEntries = new Map.Entry[oSortedSet.size()];
- Iterator itEntries = oSortedSet.iterator();
-
- while (itEntries.hasNext())
- arEntries[i++] = new BasicMapEntry(itEntries.next(), Boolean.TRUE);
-
- oMap._iSize = i;
- oMap.putAllLinear(arEntries);
- }
-
- TreeSet(SortedMap oMap)
+ 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)
{
- _oMap = oMap;
+ map = backingMap;
}
- // METHODS -----------------------------------------------------------
-
/**
* 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 oObject the Object to be added to this Set
+ * @param obj the Object to be added to this Set
*/
- public boolean add(Object oObject)
+ public boolean add(Object obj)
{
- if (_oMap.containsKey(oObject))
- {
- return false;
- }
- else
- {
- internalAdd(_oMap, oObject);
- return true;
- }
+ return (map.put(obj, Boolean.TRUE) == null);
}
/**
* Adds all of the elements in the supplied Collection to this TreeSet.
*
- * @param oCollection All of the elements in this Collection
- * will be added to the Set.
+ * @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 oCollection)
+ public boolean addAll(Collection c)
{
- boolean boResult = false;
- Iterator itElements = oCollection.iterator();
+ boolean result = false;
+ int size = c.size();
+ Iterator itr = c.iterator();
- while (itElements.hasNext())
- boResult |= add(itElements.next());
+ for (int i = 0; i < size; i++)
+ result |= (map.put(itr.next(), Boolean.TRUE) == null);
- return boResult;
+ return result;
}
/**
@@ -168,30 +151,21 @@
*/
public void clear()
{
- _oMap.clear();
+ map.clear();
}
/** Returns a shallow copy of this Set. */
public Object clone()
{
- TreeSet oClone;
-
- try
- {
- oClone = (TreeSet) super.clone();
- oClone._oMap = new TreeMap(_oMap);
- }
- catch (CloneNotSupportedException e)
- {
- throw new InternalError(e.toString());
- }
- return oClone;
+ TreeSet copy = new TreeSet();
+ copy.map = (SortedMap) ((TreeMap) map).clone();
+ return copy;
}
/** Returns this Set's comparator */
public Comparator comparator()
{
- return _oMap.comparator();
+ return map.comparator();
}
/**
@@ -201,133 +175,108 @@
* @param oObject the Object whose existence in the Set is
* being tested
*/
- public boolean contains(Object oObject)
+ public boolean contains(Object obj)
{
- return _oMap.containsKey(oObject);
+ return map.containsKey(obj);
}
/** Returns true if this Set has size 0, false otherwise */
public boolean isEmpty()
{
- return _oMap.isEmpty();
+ return map.isEmpty();
}
/** Returns the number of elements in this Set */
public int size()
{
- return _oMap.size();
+ return map.size();
}
/**
* If the supplied Object is in this Set, it is removed, and true is
* returned; otherwise, false is returned.
*
- * @param oObject the Object we are attempting to remove
- * from this Set
+ * @param obj the Object we are attempting to remove
+ * from this Set
*/
- public boolean remove(Object oObject)
+ public boolean remove(Object obj)
{
- return (_oMap.remove(oObject) != null);
+ return (map.remove(obj) != null);
}
/** Returns the first (by order) element in this Set */
public Object first()
{
- return _oMap.firstKey();
+ return map.firstKey();
}
/** Returns the last (by order) element in this Set */
public Object last()
{
- return _oMap.lastKey();
+ return map.lastKey();
}
/**
* Returns a view of this Set including all elements in the interval
* [oFromElement, oToElement).
*
- * @param oFromElement the resultant view will contain all
- * elements greater than or equal to this
- * element
- * @param oToElement the resultant view will contain all
- * elements less than this element
+ * @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 oFromElement, Object oToElement)
+ public SortedSet subSet(Object from, Object to)
{
- return new TreeSet(_oMap.subMap(oFromElement, oToElement));
+ return new TreeSet(map.subMap(from, to));
}
/**
* Returns a view of this Set including all elements less than oToElement
*
- * @param oToElement the resultant view will contain all
+ * @param toElement the resultant view will contain all
* elements less than this element
*/
- public SortedSet headSet(Object oToElement)
+ public SortedSet headSet(Object to)
{
- return new TreeSet(_oMap.headMap(oToElement));
+ return new TreeSet(map.headMap(to));
}
/**
* Returns a view of this Set including all elements greater than or
* equal to oFromElement.
*
- * @param oFromElement the resultant view will contain all
- * elements greater than or equal to this
- * element
+ * @param from the resultant view will contain all
+ * elements greater than or equal to this element
*/
- public SortedSet tailSet(Object oFromElement)
+ public SortedSet tailSet(Object from)
{
- return new TreeSet(_oMap.tailMap(oFromElement));
+ return new TreeSet(map.tailMap(from));
}
-
/** Returns in Iterator over the elements in this TreeSet */
public Iterator iterator()
{
- return _oMap.keySet().iterator();
+ return map.keySet().iterator();
}
- private void writeObject(ObjectOutputStream oOut) throws IOException
+ private void writeObject(ObjectOutputStream out) throws IOException
{
- Iterator itElements = iterator();
+ Iterator itr = map.keySet().iterator();
- oOut.writeObject(comparator());
- oOut.writeInt(size());
+ out.writeObject(map.comparator());
+ out.writeInt(map.size());
- while (itElements.hasNext())
- oOut.writeObject(itElements.next());
+ while (itr.hasNext())
+ out.writeObject(itr.next());
}
- private void readObject(ObjectInputStream oIn)
+ private void readObject(ObjectInputStream in)
throws IOException, ClassNotFoundException
- {
- int i;
- Map.Entry[]arEntries;
- TreeMap oMap;
- Comparator oComparator = (Comparator) oIn.readObject();
- int iSize = oIn.readInt();
-
- arEntries = new Map.Entry[iSize];
-
- for (i = 0; i < iSize; i++)
- arEntries[iSize] = new BasicMapEntry(oIn.readObject(), Boolean.TRUE);
-
- oMap = new TreeMap(oComparator);
- oMap._iSize = iSize;
- oMap.putAllLinear(arEntries);
- _oMap = oMap;
- }
-
- /**
- * adds the supplied element to this Set; this private method is used
- * internally instead of add(), because add() can be overridden
- * to do unexpected things
- *
- * @param o the Object to add to this Set
- */
- private static final void internalAdd(Map oMap, Object oObject)
{
- oMap.put(oObject, Boolean.TRUE);
+ Comparator comparator = (Comparator) in.readObject();
+ int size = in.readInt();
+ TreeMap map = new TreeMap(comparator);
+ map.putFromObjStream(in, size, false);
+ this.map = map;
}
}
/* 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.2 2001/02/14 05:32:31 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 (next == nil)
throw new NoSuchElementException();
if (knownMod != TreeMap.this.modCount)
throw new ConcurrentModificationException();
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 (last == null)
throw new IllegalStateException();
if (knownMod != TreeMap.this.modCount)
throw new ConcurrentModificationException();
/*
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);
if (node == nil || !keyInRange(node.key))
throw new NoSuchElementException ("empty");
return node.key;
}
public Object lastKey()
{
Node node = highestLessThan(maxKey);
if (node == nil || !keyInRange(node.key))
throw new NoSuchElementException ("empty");
return node.key;
}
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);
}
}
}
/* HashMap.java -- a class providing a basic hashtable data structure,
mapping Object --> Object
Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU Classpath.
GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING. If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.
As a special exception, if you link this library with other files to
produce an executable, this library does not by itself cause the
resulting executable to be covered by the GNU General Public License.
This exception does not however invalidate any other reasons why the
executable file might be covered by the GNU General Public License. */
package java.util;
import java.io.IOException;
import java.io.Serializable;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
// NOTE: This implementation is very similar to that of Hashtable. If you fix
// a bug in here, chances are you should make a similar change to the Hashtable
// code.
/**
* This class provides a hashtable-backed implementation of the
* Map interface.
*
* It uses a hash-bucket approach; that is, hash
* collisions are handled by linking the new node off of the
* pre-existing node (or list of nodes). In this manner, techniques
* such as linear probing (which can casue primary clustering) and
* rehashing (which does not fit very well with Java's method of
* precomputing hash codes) are avoided.
*
* Under ideal circumstances (no collisions, HashMap offers O(1)
* performance on most operations (<pre>containsValue()</pre> is,
* of course, O(n)). In the worst case (all keys map to the same
* hash code -- very unlikely), most operations are O(n).
*
* HashMap is part of the JDK1.2 Collections API. It differs from
* Hashtable in that it accepts the null key and null values, and it
* does not support "Enumeration views."
*
* @author Jon Zeppieri
* @author Jochen Hoenicke
* @author Bryce McKinlay
* @version $Revision: 1.5 $
* @modified $Id: HashMap.java,v 1.5 2001/02/14 04:44:21 bryce Exp $
*/
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable
{
/** Default number of buckets. This is the value the JDK 1.3 uses. Some
* early documentation specified this value as 101. That is incorrect. */
private static final int DEFAULT_CAPACITY = 11;
/** The defaulty load factor; this is explicitly specified by the spec. */
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private static final long serialVersionUID = 362498820763181265L;
/**
* The rounded product of the capacity and the load factor; when the number
* of elements exceeds the threshold, the HashMap calls <pre>rehash()</pre>.
* @serial
*/
int threshold;
/** Load factor of this HashMap: used in computing the threshold.
* @serial
*/
float loadFactor = DEFAULT_LOAD_FACTOR;
/**
* Array containing the actual key-value mappings
*/
transient Entry[] buckets;
/**
* counts the number of modifications this HashMap has undergone, used
* by Iterators to know when to throw ConcurrentModificationExceptions.
*/
transient int modCount;
/** the size of this HashMap: denotes the number of key-value pairs */
transient int size;
/**
* Class to represent an entry in the hash table. Holds a single key-value
* pair.
*/
static class Entry extends BasicMapEntry
{
Entry next;
Entry(Object key, Object value)
{
super(key, value);
}
}
/**
* construct a new HashMap with the default capacity (11) and the default
* load factor (0.75).
*/
public HashMap()
{
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* construct a new HashMap from the given Map
*
* every element in Map t will be put into this new HashMap
*
* @param t a Map whose key / value pairs will be put into
* the new HashMap. <b>NOTE: key / value pairs
* are not cloned in this constructor</b>
*/
public HashMap(Map m)
{
int size = Math.max(m.size() * 2, DEFAULT_CAPACITY);
buckets = new Entry[size];
threshold = (int) (size * loadFactor);
putAll(m);
}
/**
* construct a new HashMap with a specific inital capacity
*
* @param initialCapacity the initial capacity of this HashMap (>=0)
*
* @throws IllegalArgumentException if (initialCapacity < 0)
*/
public HashMap(int initialCapacity) throws IllegalArgumentException
{
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* construct a new HashMap with a specific inital capacity and load factor
*
* @param initialCapacity the initial capacity (>=0)
* @param loadFactor the load factor
*
* @throws IllegalArgumentException if (initialCapacity < 0) ||
* (initialLoadFactor > 1.0) ||
* (initialLoadFactor <= 0.0)
*/
public HashMap(int initialCapacity, float loadFactor)
throws IllegalArgumentException
{
if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1)
throw new IllegalArgumentException();
buckets = new Entry[initialCapacity];
this.loadFactor = loadFactor;
this.threshold = (int) (initialCapacity * loadFactor);
}
/** returns the number of kay-value mappings currently in this Map */
public int size()
{
return size;
}
/** returns true if there are no key-value mappings currently in this Map */
public boolean isEmpty()
{
return size == 0;
}
/**
* returns true if this HashMap contains a value <pre>o</pre>, such that
* <pre>o.equals(value)</pre>.
*
* @param value the value to search for in this Hashtable
*/
public boolean containsValue(Object value)
{
for (int i = 0; i < buckets.length; i++)
{
Entry e = buckets[i];
while (e != null)
{
if (value == null ? e.value == null : value.equals(e.value))
return true;
e = e.next;
}
}
return false;
}
/**
* returns true if the supplied object equals (<pre>equals()</pre>) a key
* in this HashMap
*
* @param key the key to search for in this HashMap
*/
public boolean containsKey(Object key)
{
int idx = hash(key);
Entry e = buckets[idx];
while (e != null)
{
if (key == null ? e.key == null : key.equals(e.key))
return true;
e = e.next;
}
return false;
}
/**
* return the value in this Hashtable associated with the supplied key, or
<pre>null</pre>
* if the key maps to nothing
*
* @param key the key for which to fetch an associated value
*/
public Object get(Object key)
{
int idx = hash(key);
Entry e = buckets[idx];
while (e != null)
{
if (key == null ? e.key == null : key.equals(e.key))
return e.value;
e = e.next;
}
return null;
}
/**
* puts the supplied value into the Map, mapped by the supplied key
*
* @param key the HashMap key used to locate the value
* @param value the value to be stored in the HashMap
*/
public Object put(Object key, Object value)
{
modCount++;
int idx = hash(key);
Entry e = buckets[idx];
while (e != null)
{
if (key == null ? e.key == null : key.equals(e.key))
{
Object r = e.value;
e.value = value;
return r;
}
else
{
e = e.next;
}
}
// At this point, we know we need to add a new entry.
if (++size > threshold)
{
rehash();
// Need a new hash value to suit the bigger table.
idx = hash(key);
}
e = new Entry(key, value);
e.next = buckets[idx];
buckets[idx] = e;
return null;
}
/**
* removes from the HashMap and returns the value which is mapped by the
* supplied key; if the key maps to nothing, then the HashMap remains
unchanged,
* and <pre>null</pre> is returned
*
* @param key the key used to locate the value to remove from the
HashMap
*/
public Object remove(Object key)
{
modCount++;
int idx = hash(key);
Entry e = buckets[idx];
Entry last = null;
while (e != null)
{
if (key == null ? e.key == null : key.equals(e.key))
{
if (last == null)
buckets[idx] = e.next;
else
last.next = e.next;
size--;
return e.value;
}
last = e;
e = e.next;
}
return null;
}
public void putAll(Map m)
{
int msize = m.size();
Iterator itr = m.entrySet().iterator();
for (int i=0; i < msize; i++)
{
Map.Entry e = (Map.Entry) itr.next();
// Optimize in case the Entry is one of our own.
if (e instanceof BasicMapEntry)
{
BasicMapEntry entry = (BasicMapEntry) e;
put(entry.key, entry.value);
}
else
{
put(e.getKey(), e.getValue());
}
}
}
public void clear()
{
modCount++;
for (int i=0; i < buckets.length; i++)
{
buckets[i] = null;
}
size = 0;
}
/**
* returns a shallow clone of this HashMap (i.e. the Map itself is cloned, but
* its contents are not)
*/
public Object clone()
{
HashMap copy = null;
try
{
copy = (HashMap) super.clone();
}
catch (CloneNotSupportedException x)
{
}
copy.buckets = new Entry[buckets.length];
for (int i=0; i < buckets.length; i++)
{
Entry e = buckets[i];
Entry last = null;
while (e != null)
{
if (last == null)
{
copy.buckets[i] = new Entry(e.key, e.value);
last = copy.buckets[i];
}
else
{
last.next = new Entry(e.key, e.value);
last = last.next;
}
e = e.next;
}
}
return copy;
}
/** returns a "set view" of this HashMap's keys */
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 HashIterator(HashIterator.KEYS);
}
public void clear()
{
HashMap.this.clear();
}
public boolean contains(Object o)
{
return HashMap.this.containsKey(o);
}
public boolean remove(Object o)
{
// Test against the size of the HashMap to determine if anything
// really got removed. This is neccessary because the return value of
// HashMap.remove() is ambiguous in the null case.
int oldsize = size;
HashMap.this.remove(o);
return (oldsize != size);
}
};
}
/** Returns a "collection view" (or "bag view") of this HashMap'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 HashIterator(HashIterator.VALUES);
}
public void clear()
{
HashMap.this.clear();
}
};
}
/** Returns a "set view" of this HashMap's entries. */
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 HashIterator(HashIterator.ENTRIES);
}
public void clear()
{
HashMap.this.clear();
}
public boolean contains(Object o)
{
if (!(o instanceof Map.Entry))
return false;
Map.Entry me = (Map.Entry) o;
Entry e = getEntry(me);
return (e != null);
}
public boolean remove(Object o)
{
if (!(o instanceof Map.Entry))
return false;
Map.Entry me = (Map.Entry) o;
Entry e = getEntry(me);
if (e != null)
{
HashMap.this.remove(e.key);
return true;
}
return false;
}
};
}
/** Return an index in the buckets array for `key' based on its hashCode() */
private int hash(Object key)
{
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.
* This is used by entrySet's contains() and remove() methods. They can't
* use contains(key) and remove(key) directly because that would result
* in entries with the same key but a different value being matched. */
private Entry getEntry(Map.Entry me)
{
int idx = hash(me.getKey());
Entry e = buckets[idx];
while (e != null)
{
if (e.equals(me))
return e;
e = e.next;
}
return null;
}
/**
* increases the size of the HashMap and rehashes all keys to new array
* indices; this is called when the addition of a new value would cause
* size() > threshold. Note that the existing Entry objects are reused in
* the new hash table.
*/
private void rehash()
{
Entry[] oldBuckets = buckets;
int newcapacity = (buckets.length * 2) + 1;
threshold = (int) (newcapacity * loadFactor);
buckets = new Entry[newcapacity];
for (int i = 0; i < oldBuckets.length; i++)
{
Entry e = oldBuckets[i];
while (e != null)
{
int idx = hash(e.key);
Entry dest = buckets[idx];
if (dest != null)
{
while (dest.next != null)
dest = dest.next;
dest.next = e;
}
else
{
buckets[idx] = e;
}
Entry next = e.next;
e.next = null;
e = next;
}
}
}
/**
* Serializes this object to the given stream.
* @serialdata the <i>capacity</i>(int) that is the length of the
* bucket array, the <i>size</i>(int) of the hash map are emitted
* first. They are followed by size entries, each consisting of
* a key (Object) and a value (Object).
*/
private void writeObject(ObjectOutputStream s) throws IOException
{
// the threshold and loadFactor fields
s.defaultWriteObject();
s.writeInt(buckets.length);
s.writeInt(size);
Iterator it = entrySet().iterator();
while (it.hasNext())
{
Map.Entry entry = (Map.Entry) it.next();
s.writeObject(entry.getKey());
s.writeObject(entry.getValue());
}
}
/**
* Deserializes this object from the given stream.
* @serialdata the <i>capacity</i>(int) that is the length of the
* bucket array, the <i>size</i>(int) of the hash map are emitted
* first. They are followed by size entries, each consisting of
* a key (Object) and a value (Object).
*/
private void readObject(ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// the threshold and loadFactor fields
s.defaultReadObject();
int capacity = s.readInt();
int len = s.readInt();
size = 0;
modCount = 0;
buckets = new Entry[capacity];
for (int i = 0; i < len; i++)
{
Object key = s.readObject();
Object value = s.readObject();
put(key, value);
}
}
/**
* 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.5 $
* @modified $Id: HashMap.java,v 1.5 2001/02/14 04:44:21 bryce Exp $
*/
class HashIterator implements Iterator
{
static final int KEYS = 0,
VALUES = 1,
ENTRIES = 2;
// the type of this Iterator: KEYS, VALUES, or ENTRIES.
int type;
// the number of modifications to the backing Hashtable that we know about.
int knownMod;
// The total number of elements returned by next(). Used to determine if
// there are more elements remaining.
int count;
// Current index in the physical hash table.
int idx;
// The last Entry returned by a next() call.
Entry last;
// The next entry that should be returned by next(). It is set to something
// if we're iterating through a bucket that contains multiple linked
// entries. It is null if next() needs to find a new bucket.
Entry next;
/* construct a new HashtableIterator with the supllied type:
KEYS, VALUES, or ENTRIES */
HashIterator(int type)
{
this.type = type;
knownMod = HashMap.this.modCount;
count = 0;
idx = buckets.length;
}
/** returns true if the Iterator has more elements */
public boolean hasNext()
{
if (knownMod != HashMap.this.modCount)
throw new ConcurrentModificationException();
return count < size;
}
/** returns the next element in the Iterator's sequential view */
public Object next()
{
if (knownMod != HashMap.this.modCount)
throw new ConcurrentModificationException();
if (count == size)
throw new NoSuchElementException();
count++;
Entry e = null;
if (next != null)
e = next;
while (e == null)
{
e = buckets[--idx];
}
next = e.next;
last = e;
if (type == VALUES)
return e.value;
else if (type == KEYS)
return e.key;
return e;
}
/**
* removes from the backing HashMap the last element which was fetched with
the
* <pre>next()</pre> method
*/
public void remove()
{
if (knownMod != HashMap.this.modCount)
throw new ConcurrentModificationException();
if (last == null)
{
throw new IllegalStateException();
}
else
{
HashMap.this.remove(last.key);
knownMod++;
count--;
last = null;
}
}
}
}
/* Hashtable.java -- a class providing a basic hashtable data structure,
mapping Object --> Object
Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU Classpath.
GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING. If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.
As a special exception, if you link this library with other files to
produce an executable, this library does not by itself cause the
resulting executable to be covered by the GNU General Public License.
This exception does not however invalidate any other reasons why the
executable file might be covered by the GNU General Public License. */
package java.util;
import java.io.IOException;
import java.io.Serializable;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
// NOTE: This implementation is very similar to that of HashMap. If you fix
// a bug in here, chances are you should make a similar change to the HashMap
// code.
/**
* a class which implements a Hashtable data structure
*
* This implementation of Hashtable uses a hash-bucket approach. That is:
* linear probing and rehashing is avoided; instead, each hashed value maps
* to a simple linked-list which, in the best case, only has one node.
* Assuming a large enough table, low enough load factor, and / or well
* implemented hashCode() methods, Hashtable should provide O(1)
* insertion, deletion, and searching of keys. Hashtable is O(n) in
* the worst case for all of these (if all keys has to the same bucket).
*
* This is a JDK-1.2 compliant implementation of Hashtable. As such, it
* belongs, partially, to the Collections framework (in that it implements
* Map). For backwards compatibility, it inherits from the obsolete and
* utterly useless Dictionary class.
*
* Being a hybrid of old and new, Hashtable has methods which provide redundant
* capability, but with subtle and even crucial differences.
* For example, one can iterate over various aspects of a Hashtable with
* either an Iterator (which is the JDK-1.2 way of doing things) or with an
* Enumeration. The latter can end up in an undefined state if the Hashtable
* changes while the Enumeration is open.
*
* Unlike HashMap, Hashtable does not accept `null' as a key value.
*
* @author Jon Zeppieri
* @author Warren Levy
* @author Bryce McKinlay
* @version $Revision: 1.10 $
* @modified $Id: Hashtable.java,v 1.10 2000/12/21 02:00:15 bryce Exp $
*/
public class Hashtable extends Dictionary
implements Map, Cloneable, Serializable
{
/** Default number of buckets. This is the value the JDK 1.3 uses. Some
* early documentation specified this value as 101. That is incorrect. */
private static final int DEFAULT_CAPACITY = 11;
/** The defaulty load factor; this is explicitly specified by the spec. */
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private static final long serialVersionUID = 1421746759512286392L;
/**
* The rounded product of the capacity and the load factor; when the number
* of elements exceeds the threshold, the Hashtable calls <pre>rehash()</pre>.
* @serial
*/
int threshold;
/** Load factor of this Hashtable: used in computing the threshold.
* @serial
*/
float loadFactor = DEFAULT_LOAD_FACTOR;
/**
* Array containing the actual key-value mappings
*/
transient Entry[] buckets;
/**
* counts the number of modifications this Hashtable has undergone, used
* by Iterators to know when to throw ConcurrentModificationExceptions.
*/
transient int modCount;
/** the size of this Hashtable: denotes the number of key-value pairs */
transient int size;
/**
* Class to represent an entry in the hash table. Holds a single key-value
* pair. A Hashtable Entry is identical to a HashMap Entry, except that
* `null' is not allowed for keys and values.
*/
static class Entry extends BasicMapEntry
{
Entry next;
Entry(Object key, Object value)
{
super(key, value);
}
public final Object setValue(Object newVal)
{
if (newVal == null)
throw new NullPointerException();
return super.setValue(newVal);
}
}
/**
* construct a new Hashtable with the default capacity (11) and the default
* load factor (0.75).
*/
public Hashtable()
{
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* construct a new Hashtable from the given Map
*
* every element in Map t will be put into this new Hashtable
*
* @param t a Map whose key / value pairs will be put into
* the new Hashtable. <b>NOTE: key / value pairs
* are not cloned in this constructor</b>
*/
public Hashtable(Map m)
{
int size = Math.max(m.size() * 2, DEFAULT_CAPACITY);
buckets = new Entry[size];
threshold = (int) (size * loadFactor);
putAll(m);
}
/**
* construct a new Hashtable with a specific inital capacity
*
* @param initialCapacity the initial capacity of this Hashtable (>=0)
*
* @throws IllegalArgumentException if (initialCapacity < 0)
*/
public Hashtable(int initialCapacity) throws IllegalArgumentException
{
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* construct a new Hashtable with a specific inital capacity and load factor
*
* @param initialCapacity the initial capacity (>=0)
* @param loadFactor the load factor
*
* @throws IllegalArgumentException if (initialCapacity < 0) ||
* (initialLoadFactor > 1.0) ||
* (initialLoadFactor <= 0.0)
*/
public Hashtable(int initialCapacity, float loadFactor)
throws IllegalArgumentException
{
if (initialCapacity < 0 || loadFactor <= 0 || loadFactor > 1)
throw new IllegalArgumentException();
buckets = new Entry[initialCapacity];
this.loadFactor = loadFactor;
this.threshold = (int) (initialCapacity * loadFactor);
}
/** Returns the number of key-value mappings currently in this Map */
public int size()
{
return size;
}
/** returns true if there are no key-value mappings currently in this Map */
public boolean isEmpty()
{
return size == 0;
}
public synchronized Enumeration keys()
{
return new Enumerator(Enumerator.KEYS);
}
public synchronized Enumeration elements()
{
return new Enumerator(Enumerator.VALUES);
}
/**
* returns true if this Hashtable contains a value <pre>o</pre>,
* such that <pre>o.equals(value)</pre>.
*
* Note: this is one of the <i>old</i> Hashtable methods which does
* not like null values; it throws NullPointerException if the
* supplied parameter is null.
*
* @param value the value to search for in this Hashtable
*
* @throws NullPointerException if <pre>value</pre> is null
*/
public synchronized boolean contains(Object value)
{
for (int i = 0; i < buckets.length; i++)
{
Entry e = buckets[i];
while (e != null)
{
if (value.equals(e.value))
return true;
e = e.next;
}
}
return false;
}
/**
* returns true if this Hashtable contains a value <pre>o</pre>, such that
* <pre>o.equals(value)</pre>.
*
* @param value the value to search for in this Hashtable
*
* @throws NullPointerException if <pre>value</pre> is null
*/
public boolean containsValue(Object value)
{
return contains(value);
}
/**
* returns true if the supplied object equals (<pre>equals()</pre>) a key
* in this Hashtable
*
* @param key the key to search for in this Hashtable
*/
public synchronized boolean containsKey(Object key)
{
int idx = hash(key);
Entry e = buckets[idx];
while (e != null)
{
if (key.equals(e.key))
return true;
e = e.next;
}
return false;
}
/**
* return the value in this Hashtable associated with the supplied key, or
<pre>null</pre>
* if the key maps to nothing
*
* @param key the key for which to fetch an associated value
*/
public synchronized Object get(Object key)
{
int idx = hash(key);
Entry e = buckets[idx];
while (e != null)
{
if (key.equals(e.key))
return e.value;
e = e.next;
}
return null;
}
/**
* puts the supplied value into the Map, mapped by the supplied key
*
* @param key the key used to locate the value
* @param value the value to be stored in the table
*/
public synchronized Object put(Object key, Object value)
{
modCount++;
int idx = hash(key);
Entry e = buckets[idx];
// Hashtable does not accept null values. This method doesn't dereference
// `value' anywhere, so check for it explicitly.
if (value == null)
throw new NullPointerException();
while (e != null)
{
if (key.equals(e.key))
{
Object r = e.value;
e.value = value;
return r;
}
else
{
e = e.next;
}
}
// At this point, we know we need to add a new entry.
if (++size > threshold)
{
rehash();
// Need a new hash value to suit the bigger table.
idx = hash(key);
}
e = new Entry(key, value);
e.next = buckets[idx];
buckets[idx] = e;
return null;
}
/**
* removes from the table and returns the value which is mapped by the
* supplied key; if the key maps to nothing, then the table remains
* unchanged, and <pre>null</pre> is returned
*
* @param key the key used to locate the value to remove
*/
public synchronized Object remove(Object key)
{
modCount++;
int idx = hash(key);
Entry e = buckets[idx];
Entry last = null;
while (e != null)
{
if (key.equals(e.key))
{
if (last == null)
buckets[idx] = e.next;
else
last.next = e.next;
size--;
return e.value;
}
last = e;
e = e.next;
}
return null;
}
public synchronized void putAll(Map m)
{
int msize = m.size();
Iterator itr = m.entrySet().iterator();
for (int i=0; i < msize; i++)
{
Map.Entry e = (Map.Entry) itr.next();
// Optimize in case the Entry is one of our own.
if (e instanceof BasicMapEntry)
{
BasicMapEntry entry = (BasicMapEntry) e;
put(entry.key, entry.value);
}
else
{
put(e.getKey(), e.getValue());
}
}
}
public synchronized void clear()
{
modCount++;
for (int i=0; i < buckets.length; i++)
{
buckets[i] = null;
}
size = 0;
}
/**
* returns a shallow clone of this Hashtable (i.e. the Map itself is cloned,
* but its contents are not)
*/
public synchronized Object clone()
{
Hashtable copy = null;
try
{
copy = (Hashtable) super.clone();
}
catch (CloneNotSupportedException x)
{
}
copy.buckets = new Entry[buckets.length];
for (int i=0; i < buckets.length; i++)
{
Entry e = buckets[i];
Entry last = null;
while (e != null)
{
if (last == null)
{
copy.buckets[i] = new Entry(e.key, e.value);
last = copy.buckets[i];
}
else
{
last.next = new Entry(e.key, e.value);
last = last.next;
}
e = e.next;
}
}
return copy;
}
public synchronized String toString()
{
Iterator entries = entrySet().iterator();
StringBuffer r = new StringBuffer("{");
for (int pos = 0; pos < size; pos++)
{
r.append(entries.next());
if (pos < size - 1)
r.append(", ");
}
r.append("}");
return r.toString();
}
/** returns a "set view" of this Hashtable's keys */
public Set keySet()
{
// Create a synchronized AbstractSet with custom implementations of those
// methods that can be overriden easily and efficiently.
Set r = new AbstractSet()
{
public int size()
{
return size;
}
public Iterator iterator()
{
return new HashIterator(HashIterator.KEYS);
}
public void clear()
{
Hashtable.this.clear();
}
public boolean contains(Object o)
{
return Hashtable.this.containsKey(o);
}
public boolean remove(Object o)
{
return (Hashtable.this.remove(o) != null);
}
};
return Collections.synchronizedSet(r);
}
/** Returns a "collection view" (or "bag view") of this Hashtable'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.
Collection r = new AbstractCollection()
{
public int size()
{
return size;
}
public Iterator iterator()
{
return new HashIterator(HashIterator.VALUES);
}
public void clear()
{
Hashtable.this.clear();
}
};
return Collections.synchronizedCollection(r);
}
/** Returns a "set view" of this Hashtable's entries. */
public Set entrySet()
{
// Create an AbstractSet with custom implementations of those methods that
// can be overriden easily and efficiently.
Set r = new AbstractSet()
{
public int size()
{
return size;
}
public Iterator iterator()
{
return new HashIterator(HashIterator.ENTRIES);
}
public void clear()
{
Hashtable.this.clear();
}
public boolean contains(Object o)
{
if (!(o instanceof Map.Entry))
return false;
Map.Entry me = (Map.Entry) o;
Entry e = getEntry(me);
return (e != null);
}
public boolean remove(Object o)
{
if (!(o instanceof Map.Entry))
return false;
Map.Entry me = (Map.Entry) o;
Entry e = getEntry(me);
if (e != null)
{
Hashtable.this.remove(e.key);
return true;
}
return false;
}
};
return Collections.synchronizedSet(r);
}
/** returns true if this Hashtable equals the supplied Object <pre>o</pre>;
* that is:
* <pre>
* if (o instanceof Map)
* and
* o.keySet().equals(keySet())
* and
* for each key in o.keySet(), o.get(key).equals(get(key))
*</pre>
*/
public boolean equals(Object o)
{
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map m = (Map) o;
Set s = m.entrySet();
Iterator itr = entrySet().iterator();
if (m.size() != size)
return false;
for (int pos = 0; pos < size; pos++)
{
if (!s.contains(itr.next()))
return false;
}
return true;
}
/** a Map's hashCode is the sum of the hashCodes of all of its
Map.Entry objects */
public int hashCode()
{
int hashcode = 0;
Iterator itr = entrySet().iterator();
for (int pos = 0; pos < size; pos++)
{
hashcode += itr.next().hashCode();
}
return hashcode;
}
/** Return an index in the buckets array for `key' based on its hashCode() */
private int hash(Object key)
{
return Math.abs(key.hashCode() % buckets.length);
}
private Entry getEntry(Map.Entry me)
{
int idx = hash(me.getKey());
Entry e = buckets[idx];
while (e != null)
{
if (e.equals(me))
return e;
e = e.next;
}
return null;
}
/**
* increases the size of the Hashtable and rehashes all keys to new array
* indices; this is called when the addition of a new value would cause
* size() > threshold. Note that the existing Entry objects are reused in
* the new hash table.
*/
protected void rehash()
{
Entry[] oldBuckets = buckets;
int newcapacity = (buckets.length * 2) + 1;
threshold = (int) (newcapacity * loadFactor);
buckets = new Entry[newcapacity];
for (int i = 0; i < oldBuckets.length; i++)
{
Entry e = oldBuckets[i];
while (e != null)
{
int idx = hash(e.key);
Entry dest = buckets[idx];
if (dest != null)
{
while (dest.next != null)
dest = dest.next;
dest.next = e;
}
else
{
buckets[idx] = e;
}
Entry next = e.next;
e.next = null;
e = next;
}
}
}
/**
* Serializes this object to the given stream.
* @serialdata the <i>capacity</i>(int) that is the length of the
* bucket array, the <i>size</i>(int) of the hash map are emitted
* first. They are followed by size entries, each consisting of
* a key (Object) and a value (Object).
*/
private void writeObject(ObjectOutputStream s) throws IOException
{
// the threshold and loadFactor fields
s.defaultWriteObject();
s.writeInt(buckets.length);
s.writeInt(size);
Iterator it = entrySet().iterator();
while (it.hasNext())
{
Map.Entry entry = (Map.Entry) it.next();
s.writeObject(entry.getKey());
s.writeObject(entry.getValue());
}
}
/**
* Deserializes this object from the given stream.
* @serialdata the <i>capacity</i>(int) that is the length of the
* bucket array, the <i>size</i>(int) of the hash map are emitted
* first. They are followed by size entries, each consisting of
* a key (Object) and a value (Object).
*/
private void readObject(ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// the threshold and loadFactor fields
s.defaultReadObject();
int capacity = s.readInt();
int len = s.readInt();
size = 0;
modCount = 0;
buckets = new Entry[capacity];
for (int i = 0; i < len; i++)
{
Object key = s.readObject();
Object value = s.readObject();
put(key, value);
}
}
/**
* a class which implements the Iterator interface and is used for
* iterating over Hashtables;
* this implementation is parameterized to give a sequential view of
* keys, values, or entries; it also allows the removal of elements,
* as per the Javasoft spec.
*
* @author Jon Zeppieri
* @version $Revision: 1.10 $
* @modified $Id: Hashtable.java,v 1.10 2000/12/21 02:00:15 bryce Exp $
*/
class HashIterator implements Iterator
{
static final int KEYS = 0,
VALUES = 1,
ENTRIES = 2;
// The type of this Iterator: KEYS, VALUES, or ENTRIES.
int type;
// The number of modifications to the backing Hashtable that we know about.
int knownMod;
// The total number of elements returned by next(). Used to determine if
// there are more elements remaining.
int count;
// Current index in the physical hash table.
int idx;
// The last Entry returned by a next() call.
Entry last;
// The next entry that should be returned by next(). It is set to something
// if we're iterating through a bucket that contains multiple linked
// entries. It is null if next() needs to find a new bucket.
Entry next;
/* Construct a new HashIterator with the supplied type:
KEYS, VALUES, or ENTRIES */
HashIterator(int type)
{
this.type = type;
knownMod = Hashtable.this.modCount;
count = 0;
idx = buckets.length;
}
/** returns true if the Iterator has more elements */
public boolean hasNext()
{
if (knownMod != Hashtable.this.modCount)
throw new ConcurrentModificationException();
return count < size;
}
/** Returns the next element in the Iterator's sequential view. */
public Object next()
{
if (knownMod != Hashtable.this.modCount)
throw new ConcurrentModificationException();
if (count == size)
throw new NoSuchElementException();
count++;
Entry e = null;
if (next != null)
e = next;
while (e == null)
{
e = buckets[--idx];
}
next = e.next;
last = e;
if (type == VALUES)
return e.value;
else if (type == KEYS)
return e.key;
return e;
}
/**
* Removes from the backing Hashtable the last element which was fetched
* with the <pre>next()</pre> method.
*/
public void remove()
{
if (knownMod != Hashtable.this.modCount)
throw new ConcurrentModificationException();
if (last == null)
{
throw new IllegalStateException();
}
else
{
Hashtable.this.remove(last.key);
knownMod++;
count--;
last = null;
}
}
}
/**
* Enumeration view of this Hashtable, providing sequential access to its
* elements; this implementation is parameterized to provide access either
* to the keys or to the values in the Hashtable.
*
* <b>NOTE: Enumeration is not safe if new elements are put in the table as
* this could cause a rehash and we'd completely lose our place. Even
* without a rehash, it is undetermined if a new element added would
* appear in the enumeration. The spec says nothing about this, but
* the "Java Class Libraries" book infers that modifications to the
* hashtable during enumeration causes indeterminate results. Don't do it!
*
* @author Jon Zeppieri
* @version $Revision: 1.10 $
* @modified $Id: Hashtable.java,v 1.10 2000/12/21 02:00:15 bryce Exp $ */
class Enumerator implements Enumeration
{
static final int KEYS = 0;
static final int VALUES = 1;
int type;
// The total number of elements returned by nextElement(). Used to
// determine if there are more elements remaining.
int count;
// current index in the physical hash table.
int idx;
// the last Entry returned.
Entry last;
Enumerator(int type)
{
this.type = type;
this.count = 0;
this.idx = buckets.length;
}
public boolean hasMoreElements()
{
return count < Hashtable.this.size;
}
public Object nextElement()
{
if (count >= size)
throw new NoSuchElementException();
count++;
Entry e = null;
if (last != null)
e = last.next;
while (e == null)
{
e = buckets[--idx];
}
last = e;
if (type == VALUES)
return e.value;
return e.key;
}
}
}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- Large collections update,
Bryce McKinlay <=