Overview  Package   Class  Use  Deprecated  Index
Home >> All >> java >> [ util overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---

java.util
Class TreeMap  

java.lang.Object
  java.util.AbstractMap
      java.util.TreeMap

All Implemented Interfaces:

java.lang.Cloneable, Map, java.io.Serializable, SortedMap

---

public class TreeMap

extends AbstractMap

implements SortedMap, java.lang.Cloneable, java.io.Serializable

This class provides a red-black tree implementation of the SortedMap interface. Elements in the Map will be sorted by either a user-provided Comparator object, or by the natural ordering of the keys. The algorithms are adopted from Corman, Leiserson, and Rivest's Introduction to Algorithms. 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. If something is already sorted, you may want to just use a LinkedHashMap to maintain the order while providing O(1) access. 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; natural ordering cannot cope with null. Null values are always allowed. Note that the ordering must be consistent with equals to correctly implement the Map interface. If this condition is violated, the map is still well-behaved, but you may have suprising results when comparing it to other maps.

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.

Since:

1.2

---

Nested Class Summary
private static class	TreeMap.Node           Class to represent an entry in the tree.
private  class	TreeMap.SubMap           Implementation of TreeMap.SubMap.subMap(Object, Object) 55 and other map ranges.
private  class	TreeMap.TreeIterator           Iterate over TreeMap's entries.

 

Nested classes inherited from class java.util.AbstractMap

AbstractMap.BasicMapEntry

 

Nested classes inherited from class java.util.Map

Map.Entry

 

Field Summary
(package private) static int	BLACK           Color status of a node.
(package private)  Comparator	comparator           This TreeMap's comparator, or null for natural ordering.
private  Set	entries           The cache for entrySet() 55 .
(package private)  int	modCount           Counts the number of modifications this TreeMap has undergone, used by Iterators to know when to throw ConcurrentModificationExceptions.
(package private) static TreeMap.Node	nil           Sentinal node, used to avoid null checks for corner cases and make the delete rebalance code simpler.
(package private) static int	RED           Color status of a node.
private  TreeMap.Node	root           The root node of this TreeMap.
private static long	serialVersionUID           Compatible with JDK 1.2.
(package private)  int	size           The size of this TreeMap.

 

Fields inherited from class java.util.AbstractMap

ENTRIES, keys, KEYS, values, VALUES

 

Constructor Summary

TreeMap()           Instantiate a new TreeMap with no elements, using the keys' natural ordering to sort.

TreeMap(Comparator c)           Instantiate a new TreeMap with no elements, using the provided comparator to sort.

TreeMap(Map map)           Instantiate a new TreeMap, initializing it with all of the elements in the provided Map.

TreeMap(SortedMap sm)           Instantiate a new TreeMap, initializing it with all of the elements in the provided SortedMap.

 

Method Summary
void	clear()           Clears the Map so it has no keys.
java.lang.Object	clone()           Returns a shallow clone of this TreeMap.
Comparator	comparator()           Return the comparator used to sort this map, or null if it is by natural order.
(package private)  int	compare(java.lang.Object o1, java.lang.Object o2)           Compares two elements by the set comparator, or by natural ordering.
boolean	containsKey(java.lang.Object key)           Returns true if the map contains a mapping for the given key.
boolean	containsValue(java.lang.Object value)           Returns true if the map contains at least one mapping to the given value.
private  void	deleteFixup(TreeMap.Node node, TreeMap.Node parent)           Maintain red-black balance after deleting a node.
Set	entrySet()           Returns a "set view" of this TreeMap's entries.
private  void	fabricateTree(int count)           Construct a perfectly balanced tree consisting of n "blank" nodes.
java.lang.Object	firstKey()           Returns the first (lowest) key in the map.
(package private)  TreeMap.Node	firstNode()           Returns the first sorted node in the map, or nil if empty.
java.lang.Object	get(java.lang.Object key)           Return the value in this TreeMap associated with the supplied key, or null if the key maps to nothing.
(package private)  TreeMap.Node	getNode(java.lang.Object key)           Return the TreeMap.Node associated with key, or the nil node if no such node exists in the tree.
SortedMap	headMap(java.lang.Object toKey)           Returns a view of this Map including all entries with keys less than toKey.
(package private)  TreeMap.Node	highestLessThan(java.lang.Object key)           Find the "highest" node which is < key.
private  void	insertFixup(TreeMap.Node n)           Maintain red-black balance after inserting a new node.
Set	keySet()           Returns a "set view" of this TreeMap's keys.
java.lang.Object	lastKey()           Returns the last (highest) key in the map.
private  TreeMap.Node	lastNode()           Returns the last sorted node in the map, or nil if empty.
(package private)  TreeMap.Node	lowestGreaterThan(java.lang.Object key, boolean first)           Find the "lowest" node which is >= key.
private  TreeMap.Node	predecessor(TreeMap.Node node)           Return the node preceding the given one, or nil if there isn't one.
java.lang.Object	put(java.lang.Object key, java.lang.Object value)           Puts the supplied value into the Map, mapped by the supplied key.
void	putAll(Map m)           Copies all elements of the given map into this TreeMap.
(package private)  void	putFromObjStream(java.io.ObjectInputStream s, int count, boolean readValues)           Construct a tree from sorted keys in linear time.
(package private)  void	putKeysLinear(Iterator keys, int count)           Construct a tree from sorted keys in linear time, with values of "".
private  void	readObject(java.io.ObjectInputStream s)           Deserializes this object from the given stream.
java.lang.Object	remove(java.lang.Object key)           Removes from the TreeMap and returns the value which is mapped by the supplied key.
(package private)  void	removeNode(TreeMap.Node node)           Remove node from tree.
private  void	rotateLeft(TreeMap.Node node)           Rotate node n to the left.
private  void	rotateRight(TreeMap.Node node)           Rotate node n to the right.
int	size()           Returns the number of key-value mappings currently in this Map.
SortedMap	subMap(java.lang.Object fromKey, java.lang.Object toKey)           Returns a view of this Map including all entries with keys greater or equal to fromKey and less than toKey (a half-open interval).
(package private)  TreeMap.Node	successor(TreeMap.Node node)           Return the node following the given one, or nil if there isn't one.
SortedMap	tailMap(java.lang.Object fromKey)           Returns a view of this Map including all entries with keys greater or equal to fromKey.
Collection	values()           Returns a "collection view" (or "bag view") of this TreeMap's values.
private  void	writeObject(java.io.ObjectOutputStream s)           Serializes this object to the given stream.

 

Methods inherited from class java.util.AbstractMap

equals, equals, hashCode, hashCode, isEmpty, toString

 

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

 

Methods inherited from interface java.util.Map

equals, hashCode, isEmpty

 

Field Detail

serialVersionUID

private static final long serialVersionUID

Compatible with JDK 1.2.

See Also:

Constant Field Values

---

RED

static final int RED

Color status of a node. Package visible for use by nested classes.

See Also:

Constant Field Values

---

BLACK

static final int BLACK

Color status of a node. Package visible for use by nested classes.

See Also:

Constant Field Values

---

nil

static final TreeMap.Node nil

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.

---

root

private transient TreeMap.Node root

The root node of this TreeMap.

---

size

transient int size

The size of this TreeMap. Package visible for use by nested classes.

---

entries

private transient Set entries

The cache for entrySet() 55 .

---

modCount

transient int modCount

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.

---

comparator

final Comparator comparator

This TreeMap's comparator, or null for natural ordering. Package visible for use by nested classes.

Constructor Detail

TreeMap

public TreeMap()

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 java.lang.ClassCastException. Attempts to use a null key will throw a java.lang.NullPointerException.

---

TreeMap

public TreeMap(Comparator c)

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 java.lang.ClassCastException.

---

TreeMap

public TreeMap(Map map)

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 java.lang.ClassCastException.

---

TreeMap

public TreeMap(SortedMap sm)

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.

Method Detail

clear

public void clear()

Clears the Map so it has no keys. This is O(1).

Specified by:

clear in interface Map

Overrides:

clear in class AbstractMap

---

clone

public java.lang.Object clone()

Returns a shallow clone of this TreeMap. The Map itself is cloned, but its contents are not.

Overrides:

clone in class AbstractMap

---

comparator

public Comparator comparator()

Return the comparator used to sort this map, or null if it is by natural order.

Specified by:

comparator in interface SortedMap

---

containsKey

public boolean containsKey(java.lang.Object key)

Returns true if the map contains a mapping for the given key.

Specified by:

containsKey in interface Map

Overrides:

containsKey in class AbstractMap

---

containsValue

public boolean containsValue(java.lang.Object value)

Returns true if the map contains at least one mapping to the given value. This requires linear time.

Specified by:

containsValue in interface Map

Overrides:

containsValue in class AbstractMap

---

entrySet

public Set entrySet()

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.

Specified by:

entrySet in interface Map

Specified by:

entrySet in class AbstractMap

---

firstKey

public java.lang.Object firstKey()

Returns the first (lowest) key in the map.

Specified by:

firstKey in interface SortedMap

---

get

public java.lang.Object get(java.lang.Object 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.

Specified by:

get in interface Map

Overrides:

get in class AbstractMap

---

headMap

public SortedMap headMap(java.lang.Object toKey)

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 java.lang.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.

Specified by:

headMap in interface SortedMap

---

keySet

public Set keySet()

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.

Specified by:

keySet in interface Map

Overrides:

keySet in class AbstractMap

---

lastKey

public java.lang.Object lastKey()

Returns the last (highest) key in the map.

Specified by:

lastKey in interface SortedMap

---

put

public java.lang.Object put(java.lang.Object key,
                            java.lang.Object value)

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.

Specified by:

put in interface Map

Overrides:

put in class AbstractMap

---

putAll

public void putAll(Map m)

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.

Specified by:

putAll in interface Map

Overrides:

putAll in class AbstractMap

---

remove

public java.lang.Object remove(java.lang.Object key)

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.

Specified by:

remove in interface Map

Overrides:

remove in class AbstractMap

---

size

public int size()

Returns the number of key-value mappings currently in this Map.

Specified by:

size in interface Map

Overrides:

size in class AbstractMap

---

subMap

public SortedMap subMap(java.lang.Object fromKey,
                        java.lang.Object toKey)

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 java.lang.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.

Specified by:

subMap in interface SortedMap

---

tailMap

public SortedMap tailMap(java.lang.Object fromKey)

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 java.lang.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.

Specified by:

tailMap in interface SortedMap

---

values

public Collection values()

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.

Specified by:

values in interface Map

Overrides:

values in class AbstractMap

---

compare

final int compare(java.lang.Object o1,
                  java.lang.Object o2)

Compares two elements by the set comparator, or by natural ordering. Package visible for use by nested classes.

---

deleteFixup

private void deleteFixup(TreeMap.Node node,
                         TreeMap.Node parent)

Maintain red-black balance after deleting a node.

---

fabricateTree

private void fabricateTree(int count)

Construct a perfectly balanced tree consisting of n "blank" nodes. This permits a tree to be generated from pre-sorted input in linear time.

---

firstNode

final TreeMap.Node firstNode()

Returns the first sorted node in the map, or nil if empty. Package visible for use by nested classes.

---

getNode

final TreeMap.Node getNode(java.lang.Object key)

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.

---

highestLessThan

final TreeMap.Node highestLessThan(java.lang.Object key)

Find the "highest" node which is < key. If key is nil, return last node. Package visible for use by nested classes.

---

insertFixup

private void insertFixup(TreeMap.Node n)

Maintain red-black balance after inserting a new node.

---

lastNode

private TreeMap.Node lastNode()

Returns the last sorted node in the map, or nil if empty.

---

lowestGreaterThan

final TreeMap.Node lowestGreaterThan(java.lang.Object key,
                                     boolean first)

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.

---

predecessor

private TreeMap.Node predecessor(TreeMap.Node node)

Return the node preceding the given one, or nil if there isn't one.

---

putFromObjStream

final void putFromObjStream(java.io.ObjectInputStream s,
                            int count,
                            boolean readValues)
                     throws java.io.IOException,
                            java.lang.ClassNotFoundException

Construct a tree from sorted keys in linear time. Package visible for use by TreeSet.

---

putKeysLinear

final void putKeysLinear(Iterator keys,
                         int count)

Construct a tree from sorted keys in linear time, with values of "". Package visible for use by TreeSet.

---

readObject

private void readObject(java.io.ObjectInputStream s)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException

Deserializes this object from the given stream.

---

removeNode

final void removeNode(TreeMap.Node node)

Remove node from tree. This will increment modCount and decrement size. Node must exist in the tree. Package visible for use by nested classes.

---

rotateLeft

private void rotateLeft(TreeMap.Node node)

Rotate node n to the left.

---

rotateRight

private void rotateRight(TreeMap.Node node)

Rotate node n to the right.

---

successor

final TreeMap.Node successor(TreeMap.Node node)

Return the node following the given one, or nil if there isn't one. Package visible for use by nested classes.

---

writeObject

private void writeObject(java.io.ObjectOutputStream s)
                  throws java.io.IOException

Serializes this object to the given stream.

---

Overview  Package   Class  Use  Deprecated  Index
Home >> All >> java >> [ util overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---