java.util

Class TreeMap<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

java.util.TreeMap<K,V>

Type Parameters:

K - key type

V - value type

All Implemented Interfaces:

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

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

Implements a TreeMap using a red-black tree. This guarantees O(log n) performance on lookups, inserts, and deletes while maintaining linear in-order traversal time. Null keys and values are fully supported if the comparator supports them (the default comparator does not).

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K,V>

Constructor Summary

Constructors

Constructor and Description
TreeMap()
TreeMap(Comparator<? super K> c)
TreeMap(Map<? extends K,? extends V> map)
TreeMap(SortedMap<K,? extends V> map)

Method Summary

Modifier and Type	Method and Description
void	clear()
Comparator<? super K>	comparator()
boolean	containsKey(Object key)
Set<Map.Entry<K,V>>	entrySet()
K	firstKey()
V	get(Object k)
protected java.util.TreeMap.Node<K,V>	getNodeAtOrAfter(K key) Returns the first node which compares equal to or greater than the given key.
protected java.util.TreeMap.Node<K,V>	getNodeBefore(K key) Returns the last node which is strictly less than the given key.
SortedMap<K,V>	headMap(K toKey)
K	lastKey()
V	put(K key, V value)
V	remove(Object keyObj)
int	size()
SortedMap<K,V>	subMap(K fromKey, K toKey)
SortedMap<K,V>	tailMap(K fromKey)

Methods inherited from class java.util.AbstractMap

containsValue, equals, hashCode, isEmpty, keySet, putAll, toString, values

Methods inherited from class java.lang.Object

finalize, getClass

Methods inherited from interface java.util.Map

containsValue, equals, hashCode, isEmpty, keySet, putAll, values

Constructor Detail

TreeMap

public TreeMap()

TreeMap

public TreeMap(Comparator<? super K> c)

TreeMap

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

TreeMap

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

Method Detail

clear

public void clear()

Specified by:

clear in interface Map<K,V>

Overrides:

clear in class AbstractMap<K,V>

comparator

public Comparator<? super K> comparator()

Specified by:

comparator in interface SortedMap<K,V>

containsKey

public boolean containsKey(Object key)

Specified by:

containsKey in interface Map<K,V>

Overrides:

containsKey in class AbstractMap<K,V>

entrySet

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

Specified by:

entrySet in interface Map<K,V>

Specified by:

entrySet in class AbstractMap<K,V>

firstKey

public K firstKey()

Specified by:

firstKey in interface SortedMap<K,V>

get

public V get(Object k)

Specified by:

get in interface Map<K,V>

Overrides:

get in class AbstractMap<K,V>

headMap

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

Specified by:

headMap in interface SortedMap<K,V>

lastKey

public K lastKey()

Specified by:

lastKey in interface SortedMap<K,V>

put

public V put(K key,
             V value)

Specified by:

put in interface Map<K,V>

Overrides:

put in class AbstractMap<K,V>

remove

public V remove(Object keyObj)

Specified by:

remove in interface Map<K,V>

Overrides:

remove in class AbstractMap<K,V>

size

public int size()

Specified by:

size in interface Map<K,V>

Overrides:

size in class AbstractMap<K,V>

subMap

public SortedMap<K,V> subMap(K fromKey,
                             K toKey)

Specified by:

subMap in interface SortedMap<K,V>

tailMap

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

Specified by:

tailMap in interface SortedMap<K,V>

getNodeAtOrAfter

protected java.util.TreeMap.Node<K,V> getNodeAtOrAfter(K key)

Returns the first node which compares equal to or greater than the given key.

Parameters:

key - the key to search for

Returns:

the next node, or null if there is none

getNodeBefore

protected java.util.TreeMap.Node<K,V> getNodeBefore(K key)

Returns the last node which is strictly less than the given key.

Parameters:

key - the key to search for

Returns:

the previous node, or null if there is none