public class

TreeMap

extends AbstractMap<K, V>
implements Serializable Cloneable NavigableMap<K, V> SortedMap<K, V>
java.lang.Object
   ↳ java.util.AbstractMap<K, V>
     ↳ java.util.TreeMap<K, V>

Class Overview

A map whose entries are sorted by their keys. All optional operations such as put(K, V) and remove(Object) are supported.

This map sorts keys using either a user-supplied comparator or the key's natural order:

  • User supplied comparators must be able to compare any pair of keys in this map. If a user-supplied comparator is in use, it will be returned by comparator().
  • If no user-supplied comparator is supplied, keys will be sorted by their natural order. Keys must be mutually comparable: they must implement Comparable and compareTo() must be able to compare each key with any other key in this map. In this case comparator() will return null.
With either a comparator or a natural ordering, comparisons should be consistent with equals. An ordering is consistent with equals if for every pair of keys 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 map = new TreeMap(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"));

Summary

Public Constructors
TreeMap()
Create a natural order, empty tree map whose keys must be mutually comparable and non-null.
TreeMap(Map<? extends K, ? extends V> copyFrom)
Create a natural order tree map populated with the key/value pairs of copyFrom.
TreeMap(Comparator<? super K> comparator)
Create a tree map ordered by comparator.
TreeMap(SortedMap<K, ? extends V> copyFrom)
Create a tree map with the ordering and key/value pairs of copyFrom.
Public Methods
Entry<K, V> ceilingEntry(K key)
Returns an entry related with the smallest key greater than or equal to the specified key, or null if no such key.
K ceilingKey(K key)
Returns the smallest key greater than or equal to the specified key, or null if no such key.
void clear()
Removes all elements from this Map, leaving it empty.

This implementation calls entrySet().clear().

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.

This implementation iterates its key set, looking for a key that key equals.

NavigableSet<K> descendingKeySet()
Returns a NavigableSet view of the keys in descending order.
NavigableMap<K, V> descendingMap()
Returns a reverse order view of the map.
Set<Entry<K, V>> entrySet()
Returns a Set containing all of the mappings in this Map.
Entry<K, V> firstEntry()
Returns the entry with the smallest key, or null if the map is empty.
K firstKey()
Returns the first key in this sorted map.
Entry<K, V> floorEntry(K key)
Returns an entry related with the biggest key less than or equal to the specified key, or null if no such key.
K floorKey(K key)
Returns the biggest key less than or equal to the specified key, or null if no such key.
V get(Object key)
Returns the value of the mapping with the specified key.

This implementation iterates its entry set, looking for an entry with a key that key equals.

NavigableMap<K, V> headMap(K to, boolean inclusive)
Returns a view of the head of the map whose keys are smaller than (or equal to, depends on inclusive argument) endKey.
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.
Entry<K, V> higherEntry(K key)
Returns an entry related with the smallest key greater than the specified key, or null if no such key.
K higherKey(K key)
Returns the smallest key greater than the specified key, or null if no such key.
boolean isEmpty()
Returns whether this map is empty.

This implementation compares size() to 0.

Set<K> keySet()
Returns a set of the keys contained in this Map.

This implementation returns a view that calls through this to map.

Entry<K, V> lastEntry()
Returns the entry with the biggest key, or null if the map is empty.
K lastKey()
Returns the last key in this sorted map.
Entry<K, V> lowerEntry(K key)
Returns an entry related with the biggest key less than the specified key, or null if no such key.
K lowerKey(K key)
Returns the biggest key less than the specified key, or null if no such key.
NavigableSet<K> navigableKeySet()
Returns a NavigableSet view of the keys in ascending order.
Entry<K, V> pollFirstEntry()
Deletes and returns the entry with the smallest key, or null if the map is empty.
Entry<K, V> pollLastEntry()
Deletes and returns the entry with the biggest key, or null if the map is empty.
V put(K key, V value)
Maps the specified key to the specified value.

This base implementation throws UnsupportedOperationException.

V remove(Object key)
Removes a mapping with the specified key from this Map.

This implementation iterates its entry set, removing the entry with a key that key equals.

int size()
Returns the number of mappings in this Map.

This implementation returns its entry set's size.

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.
NavigableMap<K, V> subMap(K from, boolean fromInclusive, K to, boolean toInclusive)
Returns a view of part of the map whose keys is from startKey to endKey.
NavigableMap<K, V> tailMap(K from, boolean inclusive)
Returns a view of the tail of the map whose keys are bigger than (or equal to, depends on inclusive argument) startKey.
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.
[Expand]
Inherited Methods
From class java.util.AbstractMap
From class java.lang.Object
From interface java.util.Map
From interface java.util.NavigableMap
From interface java.util.SortedMap

Public Constructors

public TreeMap ()

Since: API Level 1

Create a natural order, empty tree map whose keys must be mutually comparable and non-null.

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

Since: API Level 1

Create a natural order tree map populated with the key/value pairs of 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 customOrderedMap
       = new TreeMap(copyFrom.comparator());
   customOrderedMap.putAll(copyFrom);

public TreeMap (Comparator<? super K> comparator)

Since: API Level 1

Create a tree map ordered by comparator. This map's keys may only be null if comparator permits.

Parameters
comparator the comparator to order elements with, or null to use the natural ordering.

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

Since: API Level 1

Create a tree map with the ordering and key/value pairs of 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 ambigous, prefer to construct a map and populate it in two steps: 

   TreeMap customOrderedMap
       = new TreeMap(copyFrom.comparator());
   customOrderedMap.putAll(copyFrom);

Public Methods

public Entry<K, V> ceilingEntry (K key)

Since: API Level 9

Returns an entry related with the smallest key greater than or equal to the specified key, or null if no such key.

Parameters
key the key
Returns
  • the entry, or null if no such key

public K ceilingKey (K key)

Since: API Level 9

Returns the smallest key greater than or equal to the specified key, or null if no such key.

Parameters
key the key
Returns
  • the smallest key greater than or equal to key, or null if no such key

public void clear ()

Since: API Level 1

Removes all elements from this Map, leaving it empty.

This implementation calls entrySet().clear().

public Object clone ()

Since: API Level 1

Creates and returns a copy of this 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.

Returns
  • a copy of this object.

public Comparator<? super K> comparator ()

Since: API Level 1

Returns the comparator used to compare keys in this sorted map.

Returns
  • the comparator or null if the natural order is used.

public boolean containsKey (Object key)

Since: API Level 1

Returns whether this Map contains the specified key.

This implementation iterates its key set, looking for a key that key equals.

Parameters
key the key to search for.
Returns
  • true if this map contains the specified key, false otherwise.

public NavigableSet<K> descendingKeySet ()

Since: API Level 9

Returns a NavigableSet view of the keys in descending order.

Returns
  • the navigable set view

public NavigableMap<K, V> descendingMap ()

Since: API Level 9

Returns a reverse order view of the map.

Returns
  • the reverse order view of the map

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

Since: API Level 1

Returns a 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.

Returns
  • a set of the mappings

public Entry<K, V> firstEntry ()

Since: API Level 9

Returns the entry with the smallest key, or null if the map is empty.

Returns
  • the entry with the smallest key, or null if the map is empty

public K firstKey ()

Since: API Level 1

Returns the first key in this sorted map.

Returns
  • the first key in this sorted map.

public Entry<K, V> floorEntry (K key)

Since: API Level 9

Returns an entry related with the biggest key less than or equal to the specified key, or null if no such key.

Parameters
key the key
Returns
  • the entry, or null if no such key

public K floorKey (K key)

Since: API Level 9

Returns the biggest key less than or equal to the specified key, or null if no such key.

Parameters
key the key
Returns
  • the biggest key less than or equal to key, or null if no such key

public V get (Object key)

Since: API Level 1

Returns the value of the mapping with the specified key.

This implementation iterates its entry set, looking for an entry with a key that key equals.

Parameters
key the key.
Returns
  • the value of the mapping with the specified key, or null if no mapping for the specified key is found.

public NavigableMap<K, V> headMap (K to, boolean inclusive)

Since: API Level 9

Returns a view of the head of the map whose keys are smaller than (or equal to, depends on inclusive argument) endKey.

Parameters
to the end key
inclusive true if the end key is in the returned map
Returns
  • the head-map view

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

Since: API Level 1

Returns a sorted map over a range of this sorted map with all keys that are 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.

Parameters
toExclusive the high boundary of the range specified.
Returns
  • a sorted map where the keys are less than endKey.

public Entry<K, V> higherEntry (K key)

Since: API Level 9

Returns an entry related with the smallest key greater than the specified key, or null if no such key.

Parameters
key the key
Returns
  • the entry, or null if no such key

public K higherKey (K key)

Since: API Level 9

Returns the smallest key greater than the specified key, or null if no such key.

Parameters
key the key
Returns
  • the smallest key greater than key, or null if no such key

public boolean isEmpty ()

Since: API Level 1

Returns whether this map is empty.

This implementation compares size() to 0.

Returns
  • true if this map has no elements, false otherwise.

public Set<K> keySet ()

Since: API Level 1

Returns a set of the keys contained in this 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.

Returns
  • a set of the keys.

public Entry<K, V> lastEntry ()

Since: API Level 9

Returns the entry with the biggest key, or null if the map is empty.

Returns
  • the entry with the biggest key, or null if the map is empty

public K lastKey ()

Since: API Level 1

Returns the last key in this sorted map.

Returns
  • the last key in this sorted map.

public Entry<K, V> lowerEntry (K key)

Since: API Level 9

Returns an entry related with the biggest key less than the specified key, or null if no such key.

Parameters
key the key
Returns
  • the entry, or null if no such key

public K lowerKey (K key)

Since: API Level 9

Returns the biggest key less than the specified key, or null if no such key.

Parameters
key the key
Returns
  • the biggest key less than key, or null if no such key

public NavigableSet<K> navigableKeySet ()

Since: API Level 9

Returns a NavigableSet view of the keys in ascending order.

Returns
  • the navigable set view

public Entry<K, V> pollFirstEntry ()

Since: API Level 9

Deletes and returns the entry with the smallest key, or null if the map is empty.

Returns
  • the entry with the smallest key, or null if the map is empty

public Entry<K, V> pollLastEntry ()

Since: API Level 9

Deletes and returns the entry with the biggest key, or null if the map is empty.

Returns
  • the entry with the biggest key, or null if the map is empty

public V put (K key, V value)

Since: API Level 1

Maps the specified key to the specified value.

This base implementation throws UnsupportedOperationException.

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.

public V remove (Object key)

Since: API Level 1

Removes a mapping with the specified key from this Map.

This implementation iterates its entry set, removing the entry with a key that key equals.

Parameters
key the key of the mapping to remove.
Returns
  • the value of the removed mapping or null if no mapping for the specified key was found.

public int size ()

Since: API Level 1

Returns the number of mappings in this Map.

This implementation returns its entry set's size.

Returns
  • the number of mappings in this Map.

public SortedMap<K, V> subMap (K fromInclusive, K toExclusive)

Since: API Level 1

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

Parameters
fromInclusive the low boundary of the range (inclusive).
toExclusive the high boundary of the range (exclusive),
Returns
  • a sorted map with the key from the specified range.

public NavigableMap<K, V> subMap (K from, boolean fromInclusive, K to, boolean toInclusive)

Since: API Level 9

Returns a view of part of the map whose keys is from startKey to endKey.

Parameters
from the start key
fromInclusive true if the start key is in the returned map
to the end key
toInclusive true if the end key is in the returned map
Returns
  • the sub-map view

public NavigableMap<K, V> tailMap (K from, boolean inclusive)

Since: API Level 9

Returns a view of the tail of the map whose keys are bigger than (or equal to, depends on inclusive argument) startKey.

Parameters
from the start key
inclusive true if the start key is in the returned map
Returns
  • the tail-map view

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

Since: API Level 1

Returns a sorted map over a range of this sorted map with all keys that are greater than or equal to the specified 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.

Parameters
fromInclusive the low boundary of the range specified.
Returns
  • a sorted map where the keys are greater or equal to startKey.