public class TreeMap<K,V> extends AbstractMap<K,V> implements SortedMap<K,V>, NavigableMap<K,V>, Cloneable, Serializable
put(K, V)
and remove(java.lang.Object)
are supported.
This map sorts keys using either a user-supplied comparator or the key's natural order:
comparator
.
Comparable
and compareTo()
must be able to compare each key with any other key in
this map. In this case comparator
will return null.
a
and b
, a.equals(b)
if and only
if compare(a, b) == 0
.
When the ordering is not consistent with equals the behavior of this
class is well defined but does not honor the contract specified by Map
. Consider a tree map of case-insensitive strings, an ordering that is
not consistent with equals:
TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
map.put("a", "android");
// The Map API specifies that the next line should print "null" because
// "a".equals("A") is false and there is no mapping for upper case "A".
// But the case insensitive ordering says compare("a", "A") == 0. TreeMap
// uses only comparators/comparable on keys and so this prints "android".
System.out.println(map.get("A"));
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>
Constructor and Description |
---|
TreeMap()
Create a natural order, empty tree map whose keys must be mutually
comparable and non-null.
|
TreeMap(Comparator<? super K> comparator)
Create a tree map ordered by
comparator . |
TreeMap(Map<? extends K,? extends V> copyFrom)
Create a natural order tree map populated with the key/value pairs of
copyFrom . |
TreeMap(SortedMap<K,? extends V> copyFrom)
Create a tree map with the ordering and key/value pairs of
copyFrom . |
Modifier and Type | Method and Description |
---|---|
Map.Entry<K,V> |
ceilingEntry(K key)
Returns a key-value mapping associated with the least key
greater than or equal to the given key, or
null if
there is no such key. |
K |
ceilingKey(K key)
Returns the least key greater than or equal to the given key,
or
null if there is no such key. |
void |
clear()
Removes all elements from this
Map , leaving it empty. |
Object |
clone()
Creates and returns a copy of this
Object . |
Comparator<? super K> |
comparator()
Returns the comparator used to compare keys in this sorted map.
|
boolean |
containsKey(Object key)
Returns whether this
Map contains the specified key. |
NavigableSet<K> |
descendingKeySet()
Returns a reverse order
NavigableSet view of the keys contained in this map. |
NavigableMap<K,V> |
descendingMap()
Returns a reverse order view of the mappings contained in this map.
|
Set<Map.Entry<K,V>> |
entrySet()
Returns a
Set containing all of the mappings in this Map . |
Map.Entry<K,V> |
firstEntry()
Returns a key-value mapping associated with the least
key in this map, or
null if the map is empty. |
K |
firstKey()
Returns the first key in this sorted map.
|
Map.Entry<K,V> |
floorEntry(K key)
Returns a key-value mapping associated with the greatest key
less than or equal to the given key, or
null if there
is no such key. |
K |
floorKey(K key)
Returns the greatest key less than or equal to the given key,
or
null if there is no such key. |
V |
get(Object key)
Returns the value of the mapping with the specified key.
|
SortedMap<K,V> |
headMap(K toExclusive)
Returns a sorted map over a range of this sorted map with all keys that
are less than the specified
endKey . |
NavigableMap<K,V> |
headMap(K to,
boolean inclusive)
Returns a view of the portion of this map whose keys are less than (or
equal to, if
inclusive is true) toKey . |
Map.Entry<K,V> |
higherEntry(K key)
Returns a key-value mapping associated with the least key
strictly greater than the given key, or
null if there
is no such key. |
K |
higherKey(K key)
Returns the least key strictly greater than the given key, or
null if there is no such key. |
boolean |
isEmpty()
Returns whether this map is empty.
|
Set<K> |
keySet()
Returns a set of the keys contained in this
Map . |
Map.Entry<K,V> |
lastEntry()
Returns a key-value mapping associated with the greatest
key in this map, or
null if the map is empty. |
K |
lastKey()
Returns the last key in this sorted map.
|
Map.Entry<K,V> |
lowerEntry(K key)
Returns a key-value mapping associated with the greatest key
strictly less than the given key, or
null if there is
no such key. |
K |
lowerKey(K key)
Returns the greatest key strictly less than the given key, or
null if there is no such key. |
NavigableSet<K> |
navigableKeySet()
Returns a
NavigableSet view of the keys contained in this map. |
Map.Entry<K,V> |
pollFirstEntry()
Removes and returns a key-value mapping associated with
the least key in this map, or
null if the map is empty. |
Map.Entry<K,V> |
pollLastEntry()
Removes and returns a key-value mapping associated with
the greatest key in this map, or
null if the map is empty. |
V |
put(K key,
V value)
Maps the specified key to the specified value.
|
V |
remove(Object key)
Removes a mapping with the specified key from this
Map . |
int |
size()
Returns the number of mappings in this
Map . |
NavigableMap<K,V> |
subMap(K from,
boolean fromInclusive,
K to,
boolean toInclusive)
Returns a view of the portion of this map whose keys range from
fromKey to toKey . |
SortedMap<K,V> |
subMap(K fromInclusive,
K toExclusive)
Returns a sorted map over a range of this sorted map with all keys
greater than or equal to the specified
startKey and less than the
specified endKey . |
SortedMap<K,V> |
tailMap(K fromInclusive)
Returns a sorted map over a range of this sorted map with all keys that
are greater than or equal to the specified
startKey . |
NavigableMap<K,V> |
tailMap(K from,
boolean inclusive)
Returns a view of the portion of this map whose keys are greater than (or
equal to, if
inclusive is true) fromKey . |
containsValue, equals, hashCode, putAll, toString, values
public TreeMap()
public TreeMap(Map<? extends K,? extends V> copyFrom)
copyFrom
. This map's keys must be mutually comparable and
non-null.
Even if copyFrom
is a SortedMap
, the constructed map
will not use copyFrom
's ordering. This
constructor always creates a naturally-ordered map. Because the TreeMap
constructor overloads are ambiguous, prefer to construct a map
and populate it in two steps:
TreeMap<String, Integer> customOrderedMap
= new TreeMap<String, Integer>(copyFrom.comparator());
customOrderedMap.putAll(copyFrom);
public TreeMap(Comparator<? super K> comparator)
comparator
. This map's keys may only
be null if comparator
permits.comparator
- the comparator to order elements with, or null
to use the natural
ordering.public TreeMap(SortedMap<K,? extends V> copyFrom)
copyFrom
. This map's keys may only be null if the copyFrom
's
ordering permits.
The constructed map will always use copyFrom
's ordering. Because the TreeMap
constructor overloads
are ambiguous, prefer to construct a map and populate it in two steps:
TreeMap<String, Integer> customOrderedMap
= new TreeMap<String, Integer>(copyFrom.comparator());
customOrderedMap.putAll(copyFrom);
public Object clone()
Object
Object
. The default
implementation returns a so-called "shallow" copy: It creates a new
instance of the same class and then copies the field values (including
object references) from this instance to the new instance. A "deep" copy,
in contrast, would also recursively clone nested objects. A subclass that
needs to implement this kind of cloning should call super.clone()
to create the new instance and then create deep copies of the nested,
mutable objects.clone
in class AbstractMap<K,V>
public int size()
AbstractMap
Map
.
This implementation returns its entry set's size.
public boolean isEmpty()
AbstractMap
This implementation compares size()
to 0.
isEmpty
in interface Map<K,V>
isEmpty
in class AbstractMap<K,V>
true
if this map has no elements, false
otherwise.Map.size()
public V get(Object key)
AbstractMap
This implementation iterates its entry set, looking for an entry with
a key that key
equals.
public boolean containsKey(Object key)
AbstractMap
Map
contains the specified key.
This implementation iterates its key set, looking for a key that
key
equals.
containsKey
in interface Map<K,V>
containsKey
in class AbstractMap<K,V>
key
- the key to search for.true
if this map contains the specified key,
false
otherwise.public V put(K key, V value)
AbstractMap
This base implementation throws UnsupportedOperationException
.
public void clear()
AbstractMap
Map
, leaving it empty.
This implementation calls entrySet().clear()
.
clear
in interface Map<K,V>
clear
in class AbstractMap<K,V>
Map.isEmpty()
,
Map.size()
public V remove(Object key)
AbstractMap
Map
.
This implementation iterates its entry set, removing the entry with
a key that key
equals.
public Map.Entry<K,V> firstEntry()
NavigableMap
null
if the map is empty.firstEntry
in interface NavigableMap<K,V>
null
if this map is emptypublic Map.Entry<K,V> pollFirstEntry()
NavigableMap
null
if the map is empty.pollFirstEntry
in interface NavigableMap<K,V>
null
if this map is emptypublic K firstKey()
SortedMap
public Map.Entry<K,V> lastEntry()
NavigableMap
null
if the map is empty.lastEntry
in interface NavigableMap<K,V>
null
if this map is emptypublic Map.Entry<K,V> pollLastEntry()
NavigableMap
null
if the map is empty.pollLastEntry
in interface NavigableMap<K,V>
null
if this map is emptypublic K lastKey()
SortedMap
public Map.Entry<K,V> lowerEntry(K key)
NavigableMap
null
if there is
no such key.lowerEntry
in interface NavigableMap<K,V>
key
- the keykey
,
or null
if there is no such keypublic K lowerKey(K key)
NavigableMap
null
if there is no such key.lowerKey
in interface NavigableMap<K,V>
key
- the keykey
,
or null
if there is no such keypublic Map.Entry<K,V> floorEntry(K key)
NavigableMap
null
if there
is no such key.floorEntry
in interface NavigableMap<K,V>
key
- the keykey
, or null
if there is no such keypublic K floorKey(K key)
NavigableMap
null
if there is no such key.floorKey
in interface NavigableMap<K,V>
key
- the keykey
,
or null
if there is no such keypublic Map.Entry<K,V> ceilingEntry(K key)
NavigableMap
null
if
there is no such key.ceilingEntry
in interface NavigableMap<K,V>
key
- the keykey
, or null
if there is no such keypublic K ceilingKey(K key)
NavigableMap
null
if there is no such key.ceilingKey
in interface NavigableMap<K,V>
key
- the keykey
,
or null
if there is no such keypublic Map.Entry<K,V> higherEntry(K key)
NavigableMap
null
if there
is no such key.higherEntry
in interface NavigableMap<K,V>
key
- the keykey
,
or null
if there is no such keypublic K higherKey(K key)
NavigableMap
null
if there is no such key.higherKey
in interface NavigableMap<K,V>
key
- the keykey
,
or null
if there is no such keypublic Comparator<? super K> comparator()
SortedMap
comparator
in interface SortedMap<K,V>
null
if the natural order is used.public Set<Map.Entry<K,V>> entrySet()
Map
Set
containing all of the mappings in this Map
. Each mapping is
an instance of Map.Entry
. As the Set
is backed by this Map
,
changes in one will be reflected in the other.public Set<K> keySet()
AbstractMap
Map
. The Set
is backed by
this Map
so changes to one are reflected by the other. The Set
does not
support adding.
This implementation returns a view that calls through this to map. Its iterator transforms this map's entry set iterator to return keys.
public NavigableSet<K> navigableKeySet()
NavigableMap
NavigableSet
view of the keys contained in this map.
The set's iterator returns the keys in ascending order.
The set is backed by the map, so changes to the map are reflected in
the set, and vice-versa. If the map is modified while an iteration
over the set is in progress (except through the iterator's own remove
operation), the results of the iteration are undefined. The
set supports element removal, which removes the corresponding mapping
from the map, via the Iterator.remove
, Set.remove
,
removeAll
, retainAll
, and clear
operations.
It does not support the add
or addAll
operations.navigableKeySet
in interface NavigableMap<K,V>
public NavigableMap<K,V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive)
NavigableMap
fromKey
to toKey
. If fromKey
and
toKey
are equal, the returned map is empty unless
fromExclusive
and toExclusive
are both true. The
returned map is backed by this map, so changes in the returned map are
reflected in this map, and vice-versa. The returned map supports all
optional map operations that this map supports.
The returned map will throw an IllegalArgumentException
on an attempt to insert a key outside of its range, or to construct a
submap either of whose endpoints lie outside its range.
subMap
in interface NavigableMap<K,V>
from
- low endpoint of the keys in the returned mapfromInclusive
- true
if the low endpoint
is to be included in the returned viewto
- high endpoint of the keys in the returned maptoInclusive
- true
if the high endpoint
is to be included in the returned viewfromKey
to toKey
public SortedMap<K,V> subMap(K fromInclusive, K toExclusive)
SortedMap
startKey
and less than the
specified endKey
. Changes to the returned sorted map are
reflected in this sorted map and vice versa.
Note: The returned map will not allow an insertion of a key outside the specified range.
public NavigableMap<K,V> headMap(K to, boolean inclusive)
NavigableMap
inclusive
is true) toKey
. The returned
map is backed by this map, so changes in the returned map are reflected
in this map, and vice-versa. The returned map supports all optional
map operations that this map supports.
The returned map will throw an IllegalArgumentException
on an attempt to insert a key outside its range.
headMap
in interface NavigableMap<K,V>
to
- high endpoint of the keys in the returned mapinclusive
- true
if the high endpoint
is to be included in the returned viewinclusive
is true) toKey
public SortedMap<K,V> headMap(K toExclusive)
SortedMap
endKey
. Changes to the returned
sorted map are reflected in this sorted map and vice versa.
Note: The returned map will not allow an insertion of a key outside the specified range.
public NavigableMap<K,V> tailMap(K from, boolean inclusive)
NavigableMap
inclusive
is true) fromKey
. The returned
map is backed by this map, so changes in the returned map are reflected
in this map, and vice-versa. The returned map supports all optional
map operations that this map supports.
The returned map will throw an IllegalArgumentException
on an attempt to insert a key outside its range.
tailMap
in interface NavigableMap<K,V>
from
- low endpoint of the keys in the returned mapinclusive
- true
if the low endpoint
is to be included in the returned viewinclusive
is true) fromKey
public SortedMap<K,V> tailMap(K fromInclusive)
SortedMap
startKey
. Changes to
the returned sorted map are reflected in this sorted map and vice versa.
Note: The returned map will not allow an insertion of a key outside the specified range.
public NavigableMap<K,V> descendingMap()
NavigableMap
remove
operation), the results of the iteration are undefined.
The returned map has an ordering equivalent to
Collections.reverseOrder
(comparator()).
The expression m.descendingMap().descendingMap()
returns a
view of m
essentially equivalent to m
.
descendingMap
in interface NavigableMap<K,V>
public NavigableSet<K> descendingKeySet()
NavigableMap
NavigableSet
view of the keys contained in this map.
The set's iterator returns the keys in descending order.
The set is backed by the map, so changes to the map are reflected in
the set, and vice-versa. If the map is modified while an iteration
over the set is in progress (except through the iterator's own remove
operation), the results of the iteration are undefined. The
set supports element removal, which removes the corresponding mapping
from the map, via the Iterator.remove
, Set.remove
,
removeAll
, retainAll
, and clear
operations.
It does not support the add
or addAll
operations.descendingKeySet
in interface NavigableMap<K,V>