|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.AbstractMap<K,V>
java.util.TreeMap<K,V>
public class TreeMap<K,V>
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.
Map
,
HashMap
,
Hashtable
,
LinkedHashMap
,
Comparable
,
Comparator
,
Collection
,
Collections.synchronizedSortedMap(SortedMap)
,
Serialized FormNested Class Summary |
---|
Nested classes/interfaces inherited from class java.util.AbstractMap |
---|
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V> |
Nested classes/interfaces inherited from interface java.util.Map |
---|
Map.Entry<K,V> |
Constructor Summary | |
---|---|
TreeMap()
Instantiate a new TreeMap with no elements, using the keys' natural ordering to sort. |
|
TreeMap(Comparator<? super K> c)
Instantiate a new TreeMap with no elements, using the provided comparator to sort. |
|
TreeMap(Map<? extends K,? extends V> map)
Instantiate a new TreeMap, initializing it with all of the elements in the provided Map. |
|
TreeMap(SortedMap<K,? extends V> sm)
Instantiate a new TreeMap, initializing it with all of the elements in the provided SortedMap. |
Method Summary | |
---|---|
Map.Entry<K,V> |
ceilingEntry(K key)
Returns the entry associated with the least or lowest key that is greater than or equal to the specified key, or null if there is no such key. |
K |
ceilingKey(K key)
Returns the the least or lowest key that is greater than or equal to the specified key, or null if
there is no such key. |
void |
clear()
Clears the Map so it has no keys. |
Object |
clone()
Returns a shallow clone of this TreeMap. |
Comparator<? super K> |
comparator()
Return the comparator used to sort this map, or null if it is by natural order. |
boolean |
containsKey(Object key)
Returns true if the map contains a mapping for the given key. |
boolean |
containsValue(Object value)
Returns true if the map contains at least one mapping to the given value. |
java.util.NavigableSet<K> |
descendingKeySet()
Returns a reverse ordered NavigableSet view of this
map's keys. |
java.util.NavigableMap<K,V> |
descendingMap()
Returns a view of the map in reverse order. |
Set<Map.Entry<K,V>> |
entrySet()
Returns a "set view" of this TreeMap's entries. |
Map.Entry<K,V> |
firstEntry()
Returns the entry associated with the least or lowest key in the map, or null if the map is empty. |
K |
firstKey()
Returns the first (lowest) key in the map. |
Map.Entry<K,V> |
floorEntry(K key)
Returns the entry associated with the greatest or highest key that is less than or equal to the specified key, or null if there is no such key. |
K |
floorKey(K key)
Returns the the greatest or highest key that is less than or equal to the specified key, or null if
there is no such key. |
V |
get(Object key)
Return the value in this TreeMap associated with the supplied key, or null if the key maps to nothing. |
SortedMap<K,V> |
headMap(K toKey)
Returns a view of this Map including all entries with keys less than toKey . |
java.util.NavigableMap<K,V> |
headMap(K toKey,
boolean inclusive)
Returns a view of this Map including all entries with keys less than (or equal to, if inclusive is true) toKey . |
Map.Entry<K,V> |
higherEntry(K key)
Returns the entry associated with the least or lowest key that is strictly greater than the specified key, or null if there is no such key. |
K |
higherKey(K key)
Returns the the least or lowest key that is strictly greater than the specified key, or null if
there is no such key. |
Set<K> |
keySet()
Returns a "set view" of this TreeMap's keys. |
Map.Entry<K,V> |
lastEntry()
Returns the entry associated with the greatest or highest key in the map, or null if the map is empty. |
K |
lastKey()
Returns the last (highest) key in the map. |
Map.Entry<K,V> |
lowerEntry(K key)
Returns the entry associated with the greatest or highest key that is strictly less than the specified key, or null if there is no such key. |
K |
lowerKey(K key)
Returns the the greatest or highest key that is strictly less than the specified key, or null if
there is no such key. |
java.util.NavigableSet<K> |
navigableKeySet()
Returns a NavigableSet view of this map's keys. |
Map.Entry<K,V> |
pollFirstEntry()
Removes and returns the entry associated with the least or lowest key in the map, or null if the map
is empty. |
Map.Entry<K,V> |
pollLastEntry()
Removes and returns the entry associated with the greatest or highest key in the map, or null if the map
is empty. |
V |
put(K key,
V value)
Puts the supplied value into the Map, mapped by the supplied key. |
void |
putAll(Map<? extends K,? extends V> m)
Copies all elements of the given map into this TreeMap. |
V |
remove(Object key)
Removes from the TreeMap and returns the value which is mapped by the supplied key. |
int |
size()
Returns the number of key-value mappings currently in this Map. |
java.util.NavigableMap<K,V> |
subMap(K fromKey,
boolean fromInclusive,
K toKey,
boolean toInclusive)
Returns a view of this Map including all entries with keys greater (or equal to, if fromInclusive is true) fromKey and
less than (or equal to, if toInclusive is true)
toKey . |
SortedMap<K,V> |
subMap(K fromKey,
K 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). |
SortedMap<K,V> |
tailMap(K fromKey)
Returns a view of this Map including all entries with keys greater or equal to fromKey . |
java.util.NavigableMap<K,V> |
tailMap(K fromKey,
boolean inclusive)
Returns a view of this Map including all entries with keys greater or equal to fromKey . |
Collection<V> |
values()
Returns a "collection view" (or "bag view") of this TreeMap's values. |
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 |
Constructor Detail |
---|
public TreeMap()
ClassCastException
. Attempts to use
a null key will throw a NullPointerException
.
Comparable
public TreeMap(Comparator<? super K> c)
ClassCastException
.
c
- the sort order for the keys of this map, or null
for the natural orderpublic TreeMap(Map<? extends K,? extends V> map)
ClassCastException
.
map
- a Map, whose entries will be put into this TreeMap
ClassCastException
- if the keys in the provided Map are not
comparable
NullPointerException
- if map is nullComparable
public TreeMap(SortedMap<K,? extends V> sm)
sm
- a SortedMap, whose entries will be put into this TreeMap
NullPointerException
- if sm is nullMethod Detail |
---|
public void clear()
clear
in interface Map<K,V>
clear
in class AbstractMap<K,V>
Set.clear()
public Object clone()
clone
in class AbstractMap<K,V>
Cloneable
,
Object.clone()
public Comparator<? super K> comparator()
comparator
in interface SortedMap<K,V>
public boolean containsKey(Object key)
containsKey
in interface Map<K,V>
containsKey
in class AbstractMap<K,V>
key
- the key to look for
ClassCastException
- if key is not comparable to map elements
NullPointerException
- if key is null and the comparator is not
tolerant of nullsAbstractMap.containsValue(Object)
public boolean containsValue(Object value)
containsValue
in interface Map<K,V>
containsValue
in class AbstractMap<K,V>
value
- the value to look for
AbstractMap.containsKey(Object)
public Set<Map.Entry<K,V>> entrySet()
Note that the iterators for all three views, from keySet(), entrySet(), and values(), traverse the TreeMap in sorted sequence.
entrySet
in interface Map<K,V>
entrySet
in class AbstractMap<K,V>
keySet()
,
values()
,
Map.Entry
public K firstKey()
firstKey
in interface SortedMap<K,V>
NoSuchElementException
- if the map is emptypublic V get(Object key)
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.
get
in interface Map<K,V>
get
in class AbstractMap<K,V>
key
- the key for which to fetch an associated value
ClassCastException
- if key is not comparable to elements in the map
NullPointerException
- if key is null but the comparator does not
tolerate nullsput(Object, Object)
,
containsKey(Object)
public SortedMap<K,V> headMap(K toKey)
toKey
. The returned map is backed by the original, so changes
in one appear in the other. The submap will throw an
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
or call headMap(toKey, true)
. This is equivalent to
calling headMap(toKey, false)
.
headMap
in interface java.util.NavigableMap<K,V>
headMap
in interface SortedMap<K,V>
toKey
- the (exclusive) cutoff point
ClassCastException
- if toKey
is not compatible with
the comparator (or is not Comparable, for natural ordering)
NullPointerException
- if toKey is null, but the comparator does not
tolerate null elementspublic java.util.NavigableMap<K,V> headMap(K toKey, boolean inclusive)
inclusive
is true) toKey
.
The returned map is backed by the original, so changes in one appear
in the other. The submap will throw an IllegalArgumentException
for any attempt to access or add an element beyond the specified cutoff.
headMap
in interface java.util.NavigableMap<K,V>
toKey
- the cutoff pointinclusive
- true if the cutoff point should be included.
inclusive
is true) the cutoff.
ClassCastException
- if toKey
is not compatible with
the comparator (or is not Comparable, for natural ordering)
NullPointerException
- if toKey is null, but the comparator does not
tolerate null elementspublic Set<K> keySet()
keySet
in interface Map<K,V>
keySet
in class AbstractMap<K,V>
values()
,
entrySet()
public K lastKey()
lastKey
in interface SortedMap<K,V>
NoSuchElementException
- if the map is emptypublic V put(K key, V value)
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.
put
in interface Map<K,V>
put
in class AbstractMap<K,V>
key
- the key used to locate the valuevalue
- the value to be stored in the Map
ClassCastException
- if key is not comparable to current map keys
NullPointerException
- if key is null, but the comparator does
not tolerate nullsget(Object)
,
Object.equals(Object)
public void putAll(Map<? extends K,? extends V> m)
putAll
in interface Map<K,V>
putAll
in class AbstractMap<K,V>
m
- the map to be added
ClassCastException
- if a key in m is not comparable with keys
in the map
NullPointerException
- if a key in m is null, and the comparator
does not tolerate nullsAbstractMap.put(Object, Object)
public V remove(Object key)
null
is returned. NOTE: Since the value
could also be null, you must use containsKey to see if you are
actually removing a mapping.
remove
in interface Map<K,V>
remove
in class AbstractMap<K,V>
key
- the key used to locate the value to remove
ClassCastException
- if key is not comparable to current map keys
NullPointerException
- if key is null, but the comparator does
not tolerate nullsIterator.remove()
public int size()
size
in interface Map<K,V>
size
in class AbstractMap<K,V>
Set.size()
public SortedMap<K,V> subMap(K fromKey, K toKey)
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
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 or call
#subMap(K,boolean,K,boolean)
. This call is equivalent to
subMap(fromKey, true, toKey, false)
.
subMap
in interface java.util.NavigableMap<K,V>
subMap
in interface SortedMap<K,V>
fromKey
- the (inclusive) low cutoff pointtoKey
- the (exclusive) high cutoff point
ClassCastException
- if either cutoff is not compatible with
the comparator (or is not Comparable, for natural ordering)
NullPointerException
- if fromKey or toKey is null, but the
comparator does not tolerate null elements
IllegalArgumentException
- if fromKey is greater than toKeypublic java.util.NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
fromInclusive
is true) fromKey
and
less than (or equal to, if toInclusive
is true)
toKey
. The returned map is backed by the original, so
changes in one appear in the other. The submap will throw an
IllegalArgumentException
for any attempt to access or add an
element beyond the specified cutoffs.
subMap
in interface java.util.NavigableMap<K,V>
fromKey
- the low cutoff pointfromInclusive
- true if the low cutoff point should be included.toKey
- the high cutoff pointtoInclusive
- true if the high cutoff point should be included.
ClassCastException
- if either cutoff is not compatible with
the comparator (or is not Comparable, for natural ordering)
NullPointerException
- if fromKey or toKey is null, but the
comparator does not tolerate null elements
IllegalArgumentException
- if fromKey is greater than toKeypublic SortedMap<K,V> tailMap(K fromKey)
fromKey
. The returned map is backed by the
original, so changes in one appear in the other. The submap will throw an
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.
This is equivalent to calling tailMap(fromKey, true)
.
tailMap
in interface java.util.NavigableMap<K,V>
tailMap
in interface SortedMap<K,V>
fromKey
- the (inclusive) low cutoff point
ClassCastException
- if fromKey
is not compatible with
the comparator (or is not Comparable, for natural ordering)
NullPointerException
- if fromKey is null, but the comparator
does not tolerate null elementspublic java.util.NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
fromKey
. The returned map is backed by the
original, so changes in one appear in the other. The submap will throw an
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.
tailMap
in interface java.util.NavigableMap<K,V>
fromKey
- the low cutoff pointinclusive
- true if the cutoff point should be included.
ClassCastException
- if fromKey
is not compatible with
the comparator (or is not Comparable, for natural ordering)
NullPointerException
- if fromKey is null, but the comparator
does not tolerate null elementspublic Collection<V> values()
values
in interface Map<K,V>
values
in class AbstractMap<K,V>
keySet()
,
entrySet()
public Map.Entry<K,V> ceilingEntry(K key)
null
if there is no such key.
ceilingEntry
in interface java.util.NavigableMap<K,V>
key
- the key relative to the returned entry.
null
if there is
no such key.
ClassCastException
- if the specified key can not
be compared with those in the map.
NullPointerException
- if the key is null
and this map either uses natural
ordering or a comparator that does
not permit null keys.public K ceilingKey(K key)
null
if
there is no such key.
ceilingKey
in interface java.util.NavigableMap<K,V>
key
- the key relative to the returned entry.
null
if there is no such key.
ClassCastException
- if the specified key can not
be compared with those in the map.
NullPointerException
- if the key is null
and this map either uses natural
ordering or a comparator that does
not permit null keys.public java.util.NavigableSet<K> descendingKeySet()
NavigableSet
view of this
map'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.
descendingKeySet
in interface java.util.NavigableMap<K,V>
descendingMap()
public java.util.NavigableMap<K,V> descendingMap()
Iterator.remove()
operation)
result in undefined behaviour from the iteration. The ordering
of the descending map is the same as for a map with a
Comparator
given by Collections.reverseOrder()
,
and calling descendingMap()
on the descending map itself
results in a view equivalent to the original map.
descendingMap
in interface java.util.NavigableMap<K,V>
public Map.Entry<K,V> firstEntry()
null
if the map is empty.
firstEntry
in interface java.util.NavigableMap<K,V>
null
if the map
is empty.public Map.Entry<K,V> floorEntry(K key)
null
if there is no such key.
floorEntry
in interface java.util.NavigableMap<K,V>
key
- the key relative to the returned entry.
null
if there is
no such key.
ClassCastException
- if the specified key can not
be compared with those in the map.
NullPointerException
- if the key is null
and this map either uses natural
ordering or a comparator that does
not permit null keys.public K floorKey(K key)
null
if
there is no such key.
floorKey
in interface java.util.NavigableMap<K,V>
key
- the key relative to the returned entry.
null
if there is no such key.
ClassCastException
- if the specified key can not
be compared with those in the map.
NullPointerException
- if the key is null
and this map either uses natural
ordering or a comparator that does
not permit null keys.public Map.Entry<K,V> higherEntry(K key)
null
if there is no such key.
higherEntry
in interface java.util.NavigableMap<K,V>
key
- the key relative to the returned entry.
null
if there is
no such key.
ClassCastException
- if the specified key can not
be compared with those in the map.
NullPointerException
- if the key is null
and this map either uses natural
ordering or a comparator that does
not permit null keys.public K higherKey(K key)
null
if
there is no such key.
higherKey
in interface java.util.NavigableMap<K,V>
key
- the key relative to the returned entry.
null
if there is no such key.
ClassCastException
- if the specified key can not
be compared with those in the map.
NullPointerException
- if the key is null
and this map either uses natural
ordering or a comparator that does
not permit null keys.public Map.Entry<K,V> lastEntry()
null
if the map is empty.
lastEntry
in interface java.util.NavigableMap<K,V>
null
if the map
is empty.public Map.Entry<K,V> lowerEntry(K key)
null
if there is no such key.
lowerEntry
in interface java.util.NavigableMap<K,V>
key
- the key relative to the returned entry.
null
if there is
no such key.
ClassCastException
- if the specified key can not
be compared with those in the map.
NullPointerException
- if the key is null
and this map either uses natural
ordering or a comparator that does
not permit null keys.public K lowerKey(K key)
null
if
there is no such key.
lowerKey
in interface java.util.NavigableMap<K,V>
key
- the key relative to the returned entry.
null
if there is no such key.
ClassCastException
- if the specified key can not
be compared with those in the map.
NullPointerException
- if the key is null
and this map either uses natural
ordering or a comparator that does
not permit null keys.public java.util.NavigableSet<K> navigableKeySet()
NavigableSet
view of this map's keys. The set is
backed by the TreeMap
, so changes in one show up in the other.
Any changes occurring to either while an iteration is taking
place (with the exception of a Iterator.remove()
operation)
result in undefined behaviour from the iteration. The ordering
The set supports element removal, but not element addition.
navigableKeySet
in interface java.util.NavigableMap<K,V>
NavigableSet
view of the keys.public Map.Entry<K,V> pollFirstEntry()
null
if the map
is empty.
pollFirstEntry
in interface java.util.NavigableMap<K,V>
null
if the
map is empty.public Map.Entry<K,V> pollLastEntry()
null
if the map
is empty.
pollLastEntry
in interface java.util.NavigableMap<K,V>
null
if the
map is empty.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |