*
* This implementation is not synchronized. If you need to share this between
* multiple threads, do something like:
* SortedMap m
* = Collections.synchronizedSortedMap(new TreeMap(...));
*
* The iterators are fail-fast, meaning that any structural
* modification, except for remove() called on the iterator
* itself, cause the iterator to throw a
* ConcurrentModificationException rather than exhibit
* non-deterministic behavior.
*
* @author Jon Zeppieri
* @author Bryce McKinlay
* @author Eric Blake (ebb9@email.byu.edu)
* @see Map
* @see HashMap
* @see Hashtable
* @see LinkedHashMap
* @see Comparable
* @see Comparator
* @see Collection
* @see Collections#synchronizedSortedMap(SortedMap)
* @since 1.2
* @status updated to 1.4
*/
public class TreeMap extends AbstractMap
implements SortedMap, Cloneable, Serializable
{
// Implementation note:
// A red-black tree is a binary search tree with the additional properties
// that all paths to a leaf node visit the same number of black nodes,
// and no red node has red children. To avoid some null-pointer checks,
// we use the special node nil which is always black, has no relatives,
// and has key and value of null (but is not equal to a mapping of null).
/**
* Compatible with JDK 1.2.
*/
private static final long serialVersionUID = 919286545866124006L;
/**
* Color status of a node. Package visible for use by nested classes.
*/
static final int RED = -1,
BLACK = 1;
/**
* Sentinal node, used to avoid null checks for corner cases and make the
* delete rebalance code simpler. The rebalance code must never assign
* the parent, left, or right of nil, but may safely reassign the color
* to be black. This object must never be used as a key in a TreeMap, or
* it will break bounds checking of a SubMap.
*/
static final Node nil = new Node(null, null, BLACK);
static
{
// Nil is self-referential, so we must initialize it after creation.
nil.parent = nil;
nil.left = nil;
nil.right = nil;
}
/**
* The root node of this TreeMap.
*/
private transient Node root;
/**
* The size of this TreeMap. Package visible for use by nested classes.
*/
transient int size;
/**
* The cache for {@link #entrySet()}.
*/
private transient Set entries;
/**
* Counts the number of modifications this TreeMap has undergone, used
* by Iterators to know when to throw ConcurrentModificationExceptions.
* Package visible for use by nested classes.
*/
transient int modCount;
/**
* This TreeMap's comparator, or null for natural ordering.
* Package visible for use by nested classes.
* @serial the comparator ordering this tree, or null
*/
final Comparator comparator;
/**
* Class to represent an entry in the tree. Holds a single key-value pair,
* plus pointers to parent and child nodes.
*
* @author Eric Blake (ebb9@email.byu.edu)
*/
private static final class Node extends AbstractMap.BasicMapEntry
{
// All fields package visible for use by nested classes.
/** The color of this node. */
int color;
/** The left child node. */
Node left = nil;
/** The right child node. */
Node right = nil;
/** The parent node. */
Node parent = nil;
/**
* Simple constructor.
* @param key the key
* @param value the value
*/
Node(Object key, Object value, int color)
{
super(key, value);
this.color = color;
}
}
/**
* Instantiate a new TreeMap with no elements, using the keys' natural
* ordering to sort. All entries in the map must have a key which implements
* Comparable, and which are mutually comparable, otherwise map
* operations may throw a {@link ClassCastException}. Attempts to use
* a null key will throw a {@link NullPointerException}.
*
* @see Comparable
*/
public TreeMap()
{
this((Comparator) null);
}
/**
* Instantiate a new TreeMap with no elements, using the provided comparator
* to sort. All entries in the map must have keys which are mutually
* comparable by the Comparator, otherwise map operations may throw a
* {@link ClassCastException}.
*
* @param comparator the sort order for the keys of this map, or null
* for the natural order
*/
public TreeMap(Comparator c)
{
comparator = c;
fabricateTree(0);
}
/**
* 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. This algorithm runs in n*log(n) time. All entries
* in the map must have keys which implement Comparable and are mutually
* comparable, otherwise map operations may throw a
* {@link ClassCastException}.
*
* @param map a Map, whose entries will be put into this TreeMap
* @throws ClassCastException if the keys in the provided Map are not
* comparable
* @throws NullPointerException if map is null
* @see Comparable
*/
public TreeMap(Map map)
{
this((Comparator) null);
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
* comparator as in the provided SortedMap. This runs in linear time.
*
* @param sm a SortedMap, whose entries will be put into this TreeMap
* @throws NullPointerException if sm is null
*/
public TreeMap(SortedMap sm)
{
this(sm.comparator());
int pos = sm.size();
Iterator itr = sm.entrySet().iterator();
fabricateTree(pos);
Node node = firstNode();
while (--pos >= 0)
{
Map.Entry me = (Map.Entry) itr.next();
node.key = me.getKey();
node.value = me.getValue();
node = successor(node);
}
}
/**
* Clears the Map so it has no keys. This is O(1).
*/
public void clear()
{
if (size > 0)
{
modCount++;
root = nil;
size = 0;
}
}
/**
* Returns a shallow clone of this TreeMap. The Map itself is cloned,
* but its contents are not.
*
* @return the clone
*/
public Object clone()
{
TreeMap copy = null;
try
{
copy = (TreeMap) super.clone();
}
catch (CloneNotSupportedException x)
{
}
copy.entries = null;
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;
}
/**
* Return the comparator used to sort this map, or null if it is by
* natural order.
*
* @return the map's comparator
*/
public Comparator comparator()
{
return comparator;
}
/**
* Returns true if the map contains a mapping for the given key.
*
* @param key the key to look for
* @return true if the key has a mapping
* @throws ClassCastException if key is not comparable to map elements
* @throws NullPointerException if key is null and the comparator is not
* tolerant of nulls
*/
public boolean containsKey(Object key)
{
return getNode(key) != nil;
}
/**
* Returns true if the map contains at least one mapping to the given value.
* This requires linear time.
*
* @param value the value to look for
* @return true if the value appears in a mapping
*/
public boolean containsValue(Object value)
{
Node node = firstNode();
while (node != nil)
{
if (equals(value, node.value))
return true;
node = successor(node);
}
return false;
}
/**
* Returns a "set view" of this TreeMap's entries. The set is backed by
* the TreeMap, so changes in one show up in the other. The set supports
* element removal, but not element addition.
*
* Note that the iterators for all three views, from keySet(), entrySet(),
* and values(), traverse the TreeMap in sorted sequence.
*
* @return a set view of the entries
* @see #keySet()
* @see #values()
* @see Map.Entry
*/
public Set entrySet()
{
if (entries == null)
// Create an AbstractSet with custom implementations of those methods
// that can be overriden easily and efficiently.
entries = new AbstractSet()
{
public int size()
{
return size;
}
public Iterator iterator()
{
return new 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 && AbstractSet.equals(me.getValue(), 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 && AbstractSet.equals(me.getValue(), n.value))
{
removeNode(n);
return true;
}
return false;
}
};
return entries;
}
/**
* Returns the first (lowest) key in the map.
*
* @return the first key
* @throws NoSuchElementException if the map is empty
*/
public Object firstKey()
{
if (root == nil)
throw new NoSuchElementException();
return firstNode().key;
}
/**
* Return the value in this TreeMap associated with the supplied key,
* or null if the key maps to nothing. NOTE: Since the value
* could also be null, you must use containsKey to see if this key
* actually maps to something.
*
* @param key the key for which to fetch an associated value
* @return what the key maps to, if present
* @throws ClassCastException if key is not comparable to elements in the map
* @throws NullPointerException if key is null but the comparator does not
* tolerate nulls
* @see #put(Object, Object)
* @see #containsKey(Object)
*/
public Object get(Object key)
{
// Exploit fact that nil.value == null.
return getNode(key).value;
}
/**
* Returns a view of this Map including all entries with keys less than
* toKey. The returned map is backed by the original, so changes
* in one appear in the other. The submap will throw an
* {@link IllegalArgumentException} for any attempt to access or add an
* element beyond the specified cutoff. The returned map does not include
* the endpoint; if you want inclusion, pass the successor element.
*
* @param toKey the (exclusive) cutoff point
* @return a view of the map less than the cutoff
* @throws ClassCastException if toKey is not compatible with
* the comparator (or is not Comparable, for natural ordering)
* @throws NullPointerException if toKey is null, but the comparator does not
* tolerate null elements
*/
public SortedMap headMap(Object toKey)
{
return new SubMap(nil, toKey);
}
/**
* Returns a "set view" of this TreeMap's keys. The set is backed by the
* TreeMap, so changes in one show up in the other. The set supports
* element removal, but not element addition.
*
* @return a set view of the keys
* @see #values()
* @see #entrySet()
*/
public Set keySet()
{
if (keys == null)
// Create an AbstractSet with custom implementations of those methods
// that can be overriden easily and efficiently.
keys = new AbstractSet()
{
public int size()
{
return size;
}
public Iterator iterator()
{
return new TreeIterator(KEYS);
}
public void clear()
{
TreeMap.this.clear();
}
public boolean contains(Object o)
{
return containsKey(o);
}
public boolean remove(Object key)
{
Node n = getNode(key);
if (n == nil)
return false;
removeNode(n);
return true;
}
};
return keys;
}
/**
* Returns the last (highest) key in the map.
*
* @return the last key
* @throws NoSuchElementException if the map is empty
*/
public Object lastKey()
{
if (root == nil)
throw new NoSuchElementException("empty");
return lastNode().key;
}
/**
* Puts the supplied value into the Map, mapped by the supplied key.
* The value may be retrieved by any object which equals()
* this key. NOTE: Since the prior value could also be null, you must
* first use containsKey if you want to see if you are replacing the
* key's mapping.
*
* @param key the key used to locate the value
* @param value the value to be stored in the Map
* @return the prior mapping of the key, or null if there was none
* @throws ClassCastException if key is not comparable to current map keys
* @throws NullPointerException if key is null, but the comparator does
* not tolerate nulls
* @see #get(Object)
* @see Object#equals(Object)
*/
public Object put(Object key, Object value)
{
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.
return current.setValue(value);
}
// Set up new node.
Node n = new Node(key, value, RED);
n.parent = parent;
// Insert node in tree.
modCount++;
size++;
if (parent == nil)
{
// Special case inserting into an empty tree.
root = n;
return null;
}
if (comparison > 0)
parent.right = n;
else
parent.left = n;
// Rebalance after insert.
insertFixup(n);
return null;
}
/**
* Copies all elements of the given map into this TreeMap. If this map
* already has a mapping for a key, the new mapping replaces the current
* one.
*
* @param m the map to be added
* @throws ClassCastException if a key in m is not comparable with keys
* in the map
* @throws NullPointerException if a key in m is null, and the comparator
* does not tolerate nulls
*/
public void putAll(Map m)
{
Iterator itr = m.entrySet().iterator();
int pos = m.size();
while (--pos >= 0)
{
Map.Entry e = (Map.Entry) itr.next();
put(e.getKey(), e.getValue());
}
}
/**
* Removes from the TreeMap and returns the value which is mapped by the
* supplied key. If the key maps to nothing, then the TreeMap remains
* unchanged, and null is returned. NOTE: Since the value
* could also be null, you must use containsKey to see if you are
* actually removing a mapping.
*
* @param key the key used to locate the value to remove
* @return whatever the key mapped to, if present
* @throws ClassCastException if key is not comparable to current map keys
* @throws NullPointerException if key is null, but the comparator does
* not tolerate nulls
*/
public Object remove(Object key)
{
Node n = getNode(key);
if (n == nil)
return null;
// Note: removeNode can alter the contents of n, so save value now.
Object result = n.value;
removeNode(n);
return result;
}
/**
* Returns the number of key-value mappings currently in this Map.
*
* @return the size
*/
public int size()
{
return size;
}
/**
* Returns a view of this Map including all entries with keys greater or
* equal to fromKey and less than toKey (a
* half-open interval). The returned map is backed by the original, so
* changes in one appear in the other. The submap will throw an
* {@link IllegalArgumentException} for any attempt to access or add an
* element beyond the specified cutoffs. The returned map includes the low
* endpoint but not the high; if you want to reverse this behavior on
* either end, pass in the successor element.
*
* @param fromKey the (inclusive) low cutoff point
* @param toKey the (exclusive) high cutoff point
* @return a view of the map between the cutoffs
* @throws ClassCastException if either cutoff is not compatible with
* the comparator (or is not Comparable, for natural ordering)
* @throws NullPointerException if fromKey or toKey is null, but the
* comparator does not tolerate null elements
* @throws IllegalArgumentException if fromKey is greater than toKey
*/
public SortedMap subMap(Object fromKey, Object toKey)
{
return new SubMap(fromKey, toKey);
}
/**
* Returns a view of this Map including all entries with keys greater or
* equal to fromKey. The returned map is backed by the
* original, so changes in one appear in the other. The submap will throw an
* {@link IllegalArgumentException} for any attempt to access or add an
* element beyond the specified cutoff. The returned map includes the
* endpoint; if you want to exclude it, pass in the successor element.
*
* @param fromKey the (inclusive) low cutoff point
* @return a view of the map above the cutoff
* @throws ClassCastException if fromKey is not compatible with
* the comparator (or is not Comparable, for natural ordering)
* @throws NullPointerException if fromKey is null, but the comparator
* does not tolerate null elements
*/
public SortedMap tailMap(Object fromKey)
{
return new SubMap(fromKey, nil);
}
/**
* Returns a "collection view" (or "bag view") of this TreeMap's values.
* The collection is backed by the TreeMap, so changes in one show up
* in the other. The collection supports element removal, but not element
* addition.
*
* @return a bag view of the values
* @see #keySet()
* @see #entrySet()
*/
public Collection values()
{
if (values == null)
// We don't bother overriding many of the optional methods, as doing so
// wouldn't provide any significant performance advantage.
values = new AbstractCollection()
{
public int size()
{
return size;
}
public Iterator iterator()
{
return new TreeIterator(VALUES);
}
public void clear()
{
TreeMap.this.clear();
}
};
return values;
}
/**
* Compares two elements by the set comparator, or by natural ordering.
* Package visible for use by nested classes.
*
* @param o1 the first object
* @param o2 the second object
* @throws ClassCastException if o1 and o2 are not mutually comparable,
* or are not Comparable with natural ordering
* @throws NullPointerException if o1 or o2 is null with natural ordering
*/
final int compare(Object o1, Object o2)
{
return (comparator == null
? ((Comparable) o1).compareTo(o2)
: comparator.compare(o1, o2));
}
/**
* Maintain red-black balance after deleting a node.
*
* @param node the child of the node just deleted, possibly nil
* @param parent the parent of the node just deleted, never nil
*/
private void deleteFixup(Node node, Node parent)
{
// if (parent == nil)
// throw new InternalError();
// If a black node has been removed, 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 == parent.left)
{
// Rebalance left side.
Node sibling = parent.right;
// if (sibling == nil)
// throw new InternalError();
if (sibling.color == RED)
{
// Case 1: Sibling is red.
// Recolor sibling and parent, and rotate parent left.
sibling.color = BLACK;
parent.color = RED;
rotateLeft(parent);
sibling = parent.right;
}
if (sibling.left.color == BLACK && sibling.right.color == BLACK)
{
// Case 2: Sibling has no red children.
// Recolor sibling, and move to parent.
sibling.color = RED;
node = parent;
parent = parent.parent;
}
else
{
if (sibling.right.color == BLACK)
{
// Case 3: Sibling has red left child.
// Recolor sibling and left child, rotate sibling right.
sibling.left.color = BLACK;
sibling.color = RED;
rotateRight(sibling);
sibling = parent.right;
}
// Case 4: Sibling has red right child. Recolor sibling,
// right child, and parent, and rotate parent left.
sibling.color = parent.color;
parent.color = BLACK;
sibling.right.color = BLACK;
rotateLeft(parent);
node = root; // Finished.
}
}
else
{
// Symmetric "mirror" of left-side case.
Node sibling = parent.left;
// if (sibling == nil)
// throw new InternalError();
if (sibling.color == RED)
{
// Case 1: Sibling is red.
// Recolor sibling and parent, and rotate parent right.
sibling.color = BLACK;
parent.color = RED;
rotateRight(parent);
sibling = parent.left;
}
if (sibling.right.color == BLACK && sibling.left.color == BLACK)
{
// Case 2: Sibling has no red children.
// Recolor sibling, and move to parent.
sibling.color = RED;
node = parent;
parent = parent.parent;
}
else
{
if (sibling.left.color == BLACK)
{
// Case 3: Sibling has red right child.
// Recolor sibling and right child, rotate sibling left.
sibling.right.color = BLACK;
sibling.color = RED;
rotateLeft(sibling);
sibling = parent.left;
}
// Case 4: Sibling has red left child. Recolor sibling,
// left child, and parent, and rotate parent right.
sibling.color = parent.color;
parent.color = BLACK;
sibling.left.color = BLACK;
rotateRight(parent);
node = root; // Finished.
}
}
}
node.color = BLACK;
}
/**
* Construct a perfectly balanced tree consisting of n "blank" nodes. This
* permits a tree to be generated from pre-sorted input in linear time.
*
* @param count the number of blank nodes, non-negative
*/
private void fabricateTree(final int count)
{
if (count == 0)
{
root = nil;
size = 0;
return;
}
// We color every row of nodes black, except for the overflow nodes.
// I believe that this is the optimal arrangement. We construct the tree
// in place by temporarily linking each node to the next node in the row,
// then updating those links to the children when working on the next row.
// Make the root node.
root = new Node(null, null, BLACK);
size = count;
Node row = root;
int rowsize;
// Fill each row that is completely full of nodes.
for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)
{
Node parent = row;
Node last = null;
for (int i = 0; i < rowsize; i += 2)
{
Node left = new Node(null, null, BLACK);
Node right = new Node(null, null, BLACK);
left.parent = parent;
left.right = right;
right.parent = parent;
parent.left = left;
Node next = parent.right;
parent.right = right;
parent = next;
if (last != null)
last.right = left;
last = right;
}
row = row.left;
}
// Now do the partial final row in red.
int overflow = count - rowsize;
Node parent = row;
int i;
for (i = 0; i < overflow; i += 2)
{
Node left = new Node(null, null, RED);
Node right = new Node(null, null, RED);
left.parent = parent;
right.parent = parent;
parent.left = left;
Node next = parent.right;
parent.right = right;
parent = next;
}
// Add a lone left node if necessary.
if (i - overflow == 0)
{
Node left = new Node(null, null, RED);
left.parent = parent;
parent.left = left;
parent = parent.right;
left.parent.right = nil;
}
// Unlink the remaining nodes of the previous row.
while (parent != nil)
{
Node next = parent.right;
parent.right = nil;
parent = next;
}
}
/**
* Returns the first sorted node in the map, or nil if empty. Package
* visible for use by nested classes.
*
* @return the first node
*/
final Node firstNode()
{
// Exploit fact that nil.left == nil.
Node node = root;
while (node.left != nil)
node = node.left;
return node;
}
/**
* Return the TreeMap.Node associated with key, or the nil node if no such
* node exists in the tree. Package visible for use by nested classes.
*
* @param key the key to search for
* @return the node where the key is found, or nil
*/
final Node getNode(Object key)
{
Node current = root;
while (current != nil)
{
int comparison = compare(key, current.key);
if (comparison > 0)
current = current.right;
else if (comparison < 0)
current = current.left;
else
return current;
}
return current;
}
/**
* Find the "highest" node which is < key. If key is nil, return last
* node. Package visible for use by nested classes.
*
* @param key the upper bound, exclusive
* @return the previous node
*/
final 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);
}
return comparison <= 0 ? predecessor(last) : last;
}
/**
* Maintain red-black balance after inserting a new node.
*
* @param n the newly inserted 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). Remember
// that nil.color == BLACK.
while (n.parent.color == RED && n.parent.parent != nil)
{
if (n.parent == n.parent.parent.left)
{
Node uncle = n.parent.parent.right;
// Uncle may be nil, in which case it is BLACK.
if (uncle.color == RED)
{
// Case 1. Uncle is RED: Change colors of parent, uncle,
// and grandparent, and move n to grandparent.
n.parent.color = BLACK;
uncle.color = BLACK;
uncle.parent.color = RED;
n = uncle.parent;
}
else
{
if (n == n.parent.right)
{
// Case 2. Uncle is BLACK and x is right child.
// Move n to parent, and rotate n left.
n = n.parent;
rotateLeft(n);
}
// Case 3. Uncle is BLACK and x is left child.
// Recolor parent, grandparent, and rotate grandparent right.
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;
// Uncle may be nil, in which case it is BLACK.
if (uncle.color == RED)
{
// Case 1. Uncle is RED: Change colors of parent, uncle,
// and grandparent, and move n to grandparent.
n.parent.color = BLACK;
uncle.color = BLACK;
uncle.parent.color = RED;
n = uncle.parent;
}
else
{
if (n == n.parent.left)
{
// Case 2. Uncle is BLACK and x is left child.
// Move n to parent, and rotate n right.
n = n.parent;
rotateRight(n);
}
// Case 3. Uncle is BLACK and x is right child.
// Recolor parent, grandparent, and rotate grandparent left.
n.parent.color = BLACK;
n.parent.parent.color = RED;
rotateLeft(n.parent.parent);
}
}
}
root.color = BLACK;
}
/**
* Returns the last sorted node in the map, or nil if empty.
*
* @return the last node
*/
private Node lastNode()
{
// Exploit fact that nil.right == nil.
Node node = root;
while (node.right != nil)
node = node.right;
return node;
}
/**
* Find the "lowest" node which is >= key. If key is nil, return either
* nil or the first node, depending on the parameter first.
* Package visible for use by nested classes.
*
* @param key the lower bound, inclusive
* @param first true to return the first element instead of nil for nil key
* @return the next node
*/
final Node lowestGreaterThan(Object key, boolean first)
{
if (key == nil)
return first ? firstNode() : nil;
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;
}
return comparison > 0 ? successor(last) : last;
}
/**
* Return the node preceding the given one, or nil if there isn't one.
*
* @param node the current node, not nil
* @return the prior node in sorted order
*/
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;
// Exploit fact that nil.left == nil and node is non-nil.
while (node == parent.left)
{
node = parent;
parent = node.parent;
}
return parent;
}
/**
* Construct a tree from sorted keys in linear time. Package visible for
* use by TreeSet.
*
* @param s the stream to read from
* @param count the number of keys to read
* @param readValue true to read values, false to insert "" as the value
* @throws ClassNotFoundException if the underlying stream fails
* @throws IOException if the underlying stream fails
* @see #readObject(ObjectInputStream)
* @see TreeSet#readObject(ObjectInputStream)
*/
final void putFromObjStream(ObjectInputStream s, int count,
boolean readValues)
throws IOException, ClassNotFoundException
{
fabricateTree(count);
Node node = firstNode();
while (--count >= 0)
{
node.key = s.readObject();
node.value = readValues ? s.readObject() : "";
node = successor(node);
}
}
/**
* Construct a tree from sorted keys in linear time, with values of "".
* Package visible for use by TreeSet.
*
* @param keys the iterator over the sorted keys
* @param count the number of nodes to insert
* @see TreeSet#TreeSet(SortedSet)
*/
final void putKeysLinear(Iterator keys, int count)
{
fabricateTree(count);
Node node = firstNode();
while (--count >= 0)
{
node.key = keys.next();
node.value = "";
node = successor(node);
}
}
/**
* Deserializes this object from the given stream.
*
* @param s the stream to read from
* @throws ClassNotFoundException if the underlying stream fails
* @throws IOException if the underlying stream fails
* @serialData the size (int), followed by key (Object) and value
* (Object) pairs in sorted order
*/
private void readObject(ObjectInputStream s)
throws IOException, ClassNotFoundException
{
s.defaultReadObject();
int size = s.readInt();
putFromObjStream(s, size, true);
}
/**
* Remove node from tree. This will increment modCount and decrement size.
* Node must exist in the tree. Package visible for use by nested classes.
*
* @param node the node to remove
*/
final void removeNode(Node node)
{
Node splice;
Node child;
modCount++;
size--;
// Find splice, the node at the position to actually remove from the tree.
if (node.left == nil)
{
// Node to be deleted has 0 or 1 children.
splice = node;
child = node.right;
}
else if (node.right == nil)
{
// Node to be deleted has 1 child.
splice = node;
child = node.left;
}
else
{
// Node has 2 children. Splice is node's predecessor, and we swap
// its contents into node.
splice = node.left;
while (splice.right != nil)
splice = splice.right;
child = splice.left;
node.key = splice.key;
node.value = splice.value;
}
// Unlink splice from the tree.
Node parent = splice.parent;
if (child != nil)
child.parent = parent;
if (parent == nil)
{
// Special case for 0 or 1 node remaining.
root = child;
return;
}
if (splice == parent.left)
parent.left = child;
else
parent.right = child;
if (splice.color == BLACK)
deleteFixup(child, parent);
}
/**
* Rotate node n to the left.
*
* @param node the node to rotate
*/
private void rotateLeft(Node node)
{
Node child = node.right;
// if (node == nil || child == nil)
// throw new InternalError();
// 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;
node.parent = child;
}
/**
* Rotate node n to the right.
*
* @param node the node to rotate
*/
private void rotateRight(Node node)
{
Node child = node.left;
// if (node == nil || child == nil)
// throw new InternalError();
// 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;
node.parent = child;
}
/**
* Return the node following the given one, or nil if there isn't one.
* Package visible for use by nested classes.
*
* @param node the current node, not nil
* @return the next node in sorted order
*/
final Node successor(Node node)
{
if (node.right != nil)
{
node = node.right;
while (node.left != nil)
node = node.left;
return node;
}
Node parent = node.parent;
// Exploit fact that nil.right == nil and node is non-nil.
while (node == parent.right)
{
node = parent;
parent = parent.parent;
}
return parent;
}
/**
* Serializes this object to the given stream.
*
* @param s the stream to write to
* @throws IOException if the underlying stream fails
* @serialData the size (int), followed by key (Object) and value
* (Object) pairs in sorted order
*/
private void writeObject(ObjectOutputStream s) throws IOException
{
s.defaultWriteObject();
Node node = firstNode();
s.writeInt(size);
while (node != nil)
{
s.writeObject(node.key);
s.writeObject(node.value);
node = successor(node);
}
}
/**
* Iterate over TreeMap's entries. This implementation is parameterized
* to give a sequential view of keys, values, or entries.
*
* @author Eric Blake (ebb9@email.byu.edu)
*/
private final class TreeIterator implements Iterator
{
/**
* The type of this Iterator: {@link #KEYS}, {@link #VALUES},
* or {@link #ENTRIES}.
*/
private final int type;
/** The number of modifications to the backing Map that we know about. */
private int knownMod = modCount;
/** The last Entry returned by a next() call. */
private Node last;
/** The next entry that should be returned by next(). */
private Node next;
/**
* The last node visible to this iterator. This is used when iterating
* on a SubMap.
*/
private final Node max;
/**
* Construct a new TreeIterator with the supplied type.
* @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
*/
TreeIterator(int type)
{
// FIXME gcj cannot handle this. Bug java/4695
// this(type, firstNode(), nil);
this.type = type;
this.next = firstNode();
this.max = nil;
}
/**
* Construct a new TreeIterator with the supplied type. Iteration will
* be from "first" (inclusive) to "max" (exclusive).
*
* @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
* @param first where to start iteration, nil for empty iterator
* @param max the cutoff for iteration, nil for all remaining nodes
*/
TreeIterator(int type, Node first, Node max)
{
this.type = type;
this.next = first;
this.max = max;
}
/**
* Returns true if the Iterator has more elements.
* @return true if there are more elements
* @throws ConcurrentModificationException if the TreeMap was modified
*/
public boolean hasNext()
{
if (knownMod != modCount)
throw new ConcurrentModificationException();
return next != max;
}
/**
* Returns the next element in the Iterator's sequential view.
* @return the next element
* @throws ConcurrentModificationException if the TreeMap was modified
* @throws NoSuchElementException if there is none
*/
public Object next()
{
if (knownMod != modCount)
throw new ConcurrentModificationException();
if (next == max)
throw new NoSuchElementException();
last = next;
next = successor(last);
if (type == VALUES)
return last.value;
else if (type == KEYS)
return last.key;
return last;
}
/**
* Removes from the backing TreeMap the last element which was fetched
* with the next() method.
* @throws ConcurrentModificationException if the TreeMap was modified
* @throws IllegalStateException if called when there is no last element
*/
public void remove()
{
if (last == null)
throw new IllegalStateException();
if (knownMod != modCount)
throw new ConcurrentModificationException();
removeNode(last);
last = null;
knownMod++;
}
} // class TreeIterator
/**
* Implementation of {@link #subMap(Object, Object)} and other map
* ranges. This class provides a view of a portion of the original backing
* map, and throws {@link IllegalArgumentException} for attempts to
* access beyond that range.
*
* @author Eric Blake (ebb9@email.byu.edu)
*/
private final class SubMap extends AbstractMap implements SortedMap
{
/**
* The lower range of this view, inclusive, or nil for unbounded.
* Package visible for use by nested classes.
*/
final Object minKey;
/**
* The upper range of this view, exclusive, or nil for unbounded.
* Package visible for use by nested classes.
*/
final Object maxKey;
/**
* The cache for {@link #entrySet()}.
*/
private Set entries;
/**
* Create a SubMap representing the elements between minKey (inclusive)
* and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
* (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
*
* @param minKey the lower bound
* @param maxKey the upper bound
* @throws IllegalArgumentException if minKey > maxKey
*/
SubMap(Object minKey, Object maxKey)
{
if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
throw new IllegalArgumentException("fromKey > toKey");
this.minKey = minKey;
this.maxKey = maxKey;
}
/**
* 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. Package visible for use by nested classes.
*
* @param key the key to check
* @return true if the key is in range
*/
boolean keyInRange(Object key)
{
return ((minKey == nil || compare(key, minKey) >= 0)
&& (maxKey == nil || compare(key, maxKey) < 0));
}
public void clear()
{
Node next = lowestGreaterThan(minKey, true);
Node max = lowestGreaterThan(maxKey, false);
while (next != max)
{
Node current = next;
next = successor(current);
removeNode(current);
}
}
public Comparator comparator()
{
return comparator;
}
public boolean containsKey(Object key)
{
return keyInRange(key) && TreeMap.this.containsKey(key);
}
public boolean containsValue(Object value)
{
Node node = lowestGreaterThan(minKey, true);
Node max = lowestGreaterThan(maxKey, false);
while (node != max)
{
if (equals(value, node.getValue()))
return true;
node = successor(node);
}
return false;
}
public Set entrySet()
{
if (entries == null)
// Create an AbstractSet with custom implementations of those methods
// that can be overriden easily and efficiently.
entries = new AbstractSet()
{
public int size()
{
return SubMap.this.size();
}
public Iterator iterator()
{
Node first = lowestGreaterThan(minKey, true);
Node max = lowestGreaterThan(maxKey, false);
return new TreeIterator(ENTRIES, first, max);
}
public void clear()
{
SubMap.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 && AbstractSet.equals(me.getValue(), 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 && AbstractSet.equals(me.getValue(), n.value))
{
removeNode(n);
return true;
}
return false;
}
};
return entries;
}
public Object firstKey()
{
Node node = lowestGreaterThan(minKey, true);
if (node == nil || ! keyInRange(node.key))
throw new NoSuchElementException();
return node.key;
}
public Object get(Object key)
{
if (keyInRange(key))
return TreeMap.this.get(key);
return null;
}
public SortedMap headMap(Object toKey)
{
if (! keyInRange(toKey))
throw new IllegalArgumentException("key outside range");
return new SubMap(minKey, toKey);
}
public Set keySet()
{
if (this.keys == null)
// Create an AbstractSet with custom implementations of those methods
// that can be overriden easily and efficiently.
this.keys = new AbstractSet()
{
public int size()
{
return SubMap.this.size();
}
public Iterator iterator()
{
Node first = lowestGreaterThan(minKey, true);
Node max = lowestGreaterThan(maxKey, false);
return new TreeIterator(KEYS, first, max);
}
public void clear()
{
SubMap.this.clear();
}
public boolean contains(Object o)
{
if (! keyInRange(o))
return false;
return getNode(o) != nil;
}
public boolean remove(Object o)
{
if (! keyInRange(o))
return false;
Node n = getNode(o);
if (n != nil)
{
removeNode(n);
return true;
}
return false;
}
};
return this.keys;
}
public Object lastKey()
{
Node node = highestLessThan(maxKey);
if (node == nil || ! keyInRange(node.key))
throw new NoSuchElementException();
return node.key;
}
public Object put(Object key, Object value)
{
if (! keyInRange(key))
throw new IllegalArgumentException("Key outside range");
return TreeMap.this.put(key, value);
}
public Object remove(Object key)
{
if (keyInRange(key))
return TreeMap.this.remove(key);
return null;
}
public int size()
{
Node node = lowestGreaterThan(minKey, true);
Node max = lowestGreaterThan(maxKey, false);
int count = 0;
while (node != max)
{
count++;
node = successor(node);
}
return count;
}
public SortedMap subMap(Object fromKey, Object toKey)
{
if (! keyInRange(fromKey) || ! keyInRange(toKey))
throw new IllegalArgumentException("key outside range");
return new SubMap(fromKey, toKey);
}
public SortedMap tailMap(Object fromKey)
{
if (! keyInRange(fromKey))
throw new IllegalArgumentException("key outside range");
return new SubMap(fromKey, maxKey);
}
public Collection values()
{
if (this.values == null)
// Create an AbstractCollection with custom implementations of those
// methods that can be overriden easily and efficiently.
this.values = new AbstractCollection()
{
public int size()
{
return SubMap.this.size();
}
public Iterator iterator()
{
Node first = lowestGreaterThan(minKey, true);
Node max = lowestGreaterThan(maxKey, false);
return new TreeIterator(VALUES, first, max);
}
public void clear()
{
SubMap.this.clear();
}
};
return this.values;
}
} // class SubMap
} // class TreeMap