java.util
Class TreeMap<K,V>

java.lang.Object
  java.util.AbstractMap<K,V>
      java.util.TreeMap<K,V>

All Implemented Interfaces:

Serializable, Cloneable, Map<K,V>, SortedMap<K,V>

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable

TreeMap is an implementation of SortedMap. All optional operations are supported, adding and removing. The values can be any objects. The keys can be any objects which are comparable to each other either using their natural order or a specified Comparator.

Since:

1.2

See Also:

Serialized Form

Nested Class Summary

(package private) static class	TreeMap.Entry<K,V> Entry is an internal class which is used to hold the entries of a TreeMap.
(package private) static class	TreeMap.SubMap<K,V>
(package private) static class	TreeMap.SubMapEntrySet<K,V>
(package private) static class	TreeMap.SubMapKeySet<K,V>
(package private) static class	TreeMap.SubMapValuesCollection<K,V>
(package private) static class	TreeMap.UnboundedKeyIterator<K,V>
(package private) static class	TreeMap.UnboundedValueIterator<K,V>

Field Summary

(package private) Set<Map.Entry<K,V>>	entrySet
(package private) int	modCount
(package private) TreeMap.Entry<K,V>	root
(package private) int	size

Fields inherited from class java.util.AbstractMap

keySet, valuesCollection

Constructor Summary

TreeMap()
Constructs a new empty instance of TreeMap.

TreeMap(Comparator<? super K> comparator)
Constructs a new empty instance of TreeMap which uses the specified Comparator.

TreeMap(Map<? extends K,? extends V> map)
Constructs a new instance of TreeMap containing the mappings from the specified Map and using the natural ordering.

TreeMap(SortedMap<K,? extends V> map)
Constructs a new instance of TreeMap containing the mappings from the specified SortedMap and using the same Comparator.

Method Summary

(package private) void	balance(TreeMap.Entry<K,V> x)
void	clear() Removes all mappings from this TreeMap, leaving it empty.
Object	clone() Returns a new TreeMap with the same mappings, size and comparator as this TreeMap.
Comparator<? super K>	comparator() Returns the Comparator used to compare elements in this TreeMap.
boolean	containsKey(Object key) Searches this TreeMap for the specified key.
boolean	containsValue(Object value) Searches this TreeMap for the specified value.
Set<Map.Entry<K,V>>	entrySet() Returns a Set of the mappings contained in this TreeMap.
(package private) TreeMap.Entry<K,V>	findAfter(Object keyObj)
(package private) TreeMap.Entry<K,V>	findBefore(K key)
K	firstKey() Answer the first sorted key in this TreeMap.
V	get(Object key) Returns the value of the mapping with the specified key.
SortedMap<K,V>	headMap(K endKey) Returns a SortedMap of the specified portion of this TreeMap which contains keys less than the end key.
Set<K>	keySet() Returns a Set of the keys contained in this TreeMap.
K	lastKey() Answer the last sorted key in this TreeMap.
(package private) static <K,V> TreeMap.Entry<K,V>	maximum(TreeMap.Entry<K,V> x)
(package private) static <K,V> TreeMap.Entry<K,V>	minimum(TreeMap.Entry<K,V> x)
(package private) static <K,V> TreeMap.Entry<K,V>	predecessor(TreeMap.Entry<K,V> x)
V	put(K key, V value) Maps the specified key to the specified value.
void	putAll(Map<? extends K,? extends V> map) Copies every mapping in the specified Map to this TreeMap.
(package private) void	rbDelete(TreeMap.Entry<K,V> z)
V	remove(Object key) Removes a mapping with the specified key from this TreeMap.
int	size() Returns the number of mappings in this TreeMap.
SortedMap<K,V>	subMap(K startKey, K endKey) Returns a SortedMap of the specified portion of this TreeMap which contains keys greater or equal to the start key but less than the end key.
(package private) static <K,V> TreeMap.Entry<K,V>	successor(TreeMap.Entry<K,V> x)
SortedMap<K,V>	tailMap(K startKey) Returns a SortedMap of the specified portion of this TreeMap which contains keys greater or equal to the start key.
Collection<V>	values() Returns a Collection of the values contained in this TreeMap.

Methods inherited from class java.util.AbstractMap

equals, 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

size

transient int size

root

transient TreeMap.Entry<K,V> root

modCount

transient int modCount

entrySet

transient Set<Map.Entry<K,V>> entrySet

Constructor Detail

TreeMap

public TreeMap()

Constructs a new empty instance of TreeMap.

TreeMap

public TreeMap(Comparator<? super K> comparator)

Constructs a new empty instance of TreeMap which uses the specified Comparator.

Parameters:

comparator - the Comparator

TreeMap

public TreeMap(Map<? extends K,? extends V> map)

Constructs a new instance of TreeMap containing the mappings from the specified Map and using the natural ordering.

Parameters:

map - the mappings to add

Throws:

ClassCastException - when a key in the Map does not implement the Comparable interface, or they keys in the Map cannot be compared

TreeMap

public TreeMap(SortedMap<K,? extends V> map)

Constructs a new instance of TreeMap containing the mappings from the specified SortedMap and using the same Comparator.

Parameters:

map - the mappings to add

Method Detail

balance

void balance(TreeMap.Entry<K,V> x)

clear

public void clear()

Removes all mappings from this TreeMap, leaving it empty.

Specified by:

clear in interface Map<K,V>

Overrides:

clear in class AbstractMap<K,V>

See Also:

Map.isEmpty(), size

clone

public Object clone()

Returns a new TreeMap with the same mappings, size and comparator as this TreeMap.

Overrides:

clone in class AbstractMap<K,V>

Returns:

a shallow copy of this TreeMap

See Also:

Cloneable

comparator

public Comparator<? super K> comparator()

Returns the Comparator used to compare elements in this TreeMap.

Specified by:

comparator in interface SortedMap<K,V>

Returns:

a Comparator or null if the natural ordering is used

containsKey

public boolean containsKey(Object key)

Searches this TreeMap for the specified key.

Specified by:

containsKey in interface Map<K,V>

Overrides:

containsKey in class AbstractMap<K,V>

Parameters:

key - the object to search for

Returns:

true if key is a key of this TreeMap, false otherwise

Throws:

ClassCastException - when the key cannot be compared with the keys in this TreeMap

NullPointerException - when the key is null and the comparator cannot handle null

containsValue

public boolean containsValue(Object value)

Searches this TreeMap for the specified value.

Specified by:

containsValue in interface Map<K,V>

Overrides:

containsValue in class AbstractMap<K,V>

Parameters:

value - the object to search for

Returns:

true if value is a value of this TreeMap, false otherwise

entrySet

public Set<Map.Entry<K,V>> entrySet()

Returns a Set of the mappings contained in this TreeMap. Each element in the set is a Map.Entry. The set is backed by this TreeMap so changes to one are reflected by the other. The set does not support adding.

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in class AbstractMap<K,V>

Returns:

a Set of the mappings

findAfter

TreeMap.Entry<K,V> findAfter(Object keyObj)

findBefore

TreeMap.Entry<K,V> findBefore(K key)

firstKey

public K firstKey()

Answer the first sorted key in this TreeMap.

Specified by:

firstKey in interface SortedMap<K,V>

Returns:

the first sorted key

Throws:

NoSuchElementException - when this TreeMap is empty

get

public V get(Object key)

Returns the value of the mapping with the specified key.

Specified by:

get in interface Map<K,V>

Overrides:

get in class AbstractMap<K,V>

Parameters:

key - the key

Returns:

the value of the mapping with the specified key

Throws:

ClassCastException - when the key cannot be compared with the keys in this TreeMap

NullPointerException - when the key is null and the comparator cannot handle null

headMap

public SortedMap<K,V> headMap(K endKey)

Returns a SortedMap of the specified portion of this TreeMap which contains keys less than the end key. The returned SortedMap is backed by this TreeMap so changes to one are reflected by the other.

Specified by:

headMap in interface SortedMap<K,V>

Parameters:

endKey - the end key

Returns:

a sub-map where the keys are less than endKey

Throws:

ClassCastException - when the end key cannot be compared with the keys in this TreeMap

NullPointerException - when the end key is null and the comparator cannot handle null

keySet

public Set<K> keySet()

Returns a Set of the keys contained in this TreeMap. The set is backed by this TreeMap so changes to one are reflected by the other. The set does not support adding.

Specified by:

keySet in interface Map<K,V>

Overrides:

keySet in class AbstractMap<K,V>

Returns:

a Set of the keys

lastKey

public K lastKey()

Answer the last sorted key in this TreeMap.

Specified by:

lastKey in interface SortedMap<K,V>

Returns:

the last sorted key

Throws:

NoSuchElementException - when this TreeMap is empty

maximum

static <K,V> TreeMap.Entry<K,V> maximum(TreeMap.Entry<K,V> x)

minimum

static <K,V> TreeMap.Entry<K,V> minimum(TreeMap.Entry<K,V> x)

predecessor

static <K,V> TreeMap.Entry<K,V> predecessor(TreeMap.Entry<K,V> x)

put

public V put(K key,
             V value)

Maps the specified key to the specified value.

Specified by:

put in interface Map<K,V>

Overrides:

put in class AbstractMap<K,V>

Parameters:

key - the key

value - the value

Returns:

the value of any previous mapping with the specified key or null if there was no mapping

Throws:

ClassCastException - when the key cannot be compared with the keys in this TreeMap

NullPointerException - when the key is null and the comparator cannot handle null

putAll

public void putAll(Map<? extends K,? extends V> map)

Copies every mapping in the specified Map to this TreeMap.

Specified by:

putAll in interface Map<K,V>

Overrides:

putAll in class AbstractMap<K,V>

Parameters:

map - the Map to copy mappings from

Throws:

ClassCastException - when a key in the Map cannot be compared with the keys in this TreeMap

NullPointerException - when a key in the Map is null and the comparator cannot handle null

rbDelete

void rbDelete(TreeMap.Entry<K,V> z)

remove

public V remove(Object key)

Removes a mapping with the specified key from this TreeMap.

Specified by:

remove in interface Map<K,V>

Overrides:

remove in class AbstractMap<K,V>

Parameters:

key - the key of the mapping to remove

Returns:

the value of the removed mapping or null if key is not a key in this TreeMap

Throws:

ClassCastException - when the key cannot be compared with the keys in this TreeMap

NullPointerException - when the key is null and the comparator cannot handle null

size

public int size()

Returns the number of mappings in this TreeMap.

Specified by:

size in interface Map<K,V>

Overrides:

size in class AbstractMap<K,V>

Returns:

the number of mappings in this TreeMap

subMap

public SortedMap<K,V> subMap(K startKey,
                             K endKey)

Returns a SortedMap of the specified portion of this TreeMap which contains keys greater or equal to the start key but less than the end key. The returned SortedMap is backed by this TreeMap so changes to one are reflected by the other.

Specified by:

subMap in interface SortedMap<K,V>

Parameters:

startKey - the start key

endKey - the end key

Returns:

a sub-map where the keys are greater or equal to startKey and less than endKey

Throws:

ClassCastException - when the start or end key cannot be compared with the keys in this TreeMap

NullPointerException - when the start or end key is null and the comparator cannot handle null

successor

static <K,V> TreeMap.Entry<K,V> successor(TreeMap.Entry<K,V> x)

tailMap

public SortedMap<K,V> tailMap(K startKey)

Returns a SortedMap of the specified portion of this TreeMap which contains keys greater or equal to the start key. The returned SortedMap is backed by this TreeMap so changes to one are reflected by the other.

Specified by:

tailMap in interface SortedMap<K,V>

Parameters:

startKey - the start key

Returns:

a sub-map where the keys are greater or equal to startKey

Throws:

ClassCastException - when the start key cannot be compared with the keys in this TreeMap

NullPointerException - when the start key is null and the comparator cannot handle null

values

public Collection<V> values()

Returns a Collection of the values contained in this TreeMap. The collection is backed by this TreeMap so changes to one are reflected by the other. The collection does not support adding.

Specified by:

values in interface Map<K,V>

Overrides:

values in class AbstractMap<K,V>

Returns:

a Collection of the values