# Class TreeMap<K,V>

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

Type Parameters:
  `K` - type of key
  `V` - type of value

All Implemented Interfaces:
  `Map<K,V>, NavigableMap<K,V>, SortedMap<K,V>`

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>
TreeMap is an implementation of SortedMap. All optional operations (adding and removing) are supported. The values can be any objects. The keys can be any objects which are comparable to each other either using their natural

Since:
  1.2

- ## Nested Class Summary

  ### Nested classes/interfaces inherited from class AbstractMap

  `AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>`
  Modifier and Type
  Class
  Description
  `static class`
  `AbstractMap.SimpleEntry<K,V>`
  A key-value mapping.
  `static class`
  `AbstractMap.SimpleImmutableEntry<K,V>`
  An immutable key-value mapping.

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `TreeMap()`
  Constructs a new empty `TreeMap` instance.
  `TreeMap(Comparator<? super K> comparator)`
  Constructs a new empty `TreeMap` instance with the specified comparator.
  `TreeMap(Map<? extends K, ? extends V> map)`
  Constructs a new `TreeMap` instance containing the mappings from the specified map and using natural ordering.
  `TreeMap(SortedMap<K, ? extends V> map)`
  Constructs a new `TreeMap` instance containing the mappings from the specified SortedMap and using the same comparator.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `Map.Entry<K,V>`
  `ceilingEntry(K key)`
  Answers 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)`
  Answers the smallest key greater than or equal to the specified key, or null if no such key.
  `void`
  `clear()`
  Removes all mappings from this TreeMap, leaving it empty.
  `Comparator<? super K>`
  `comparator()`
  Returns the comparator used to compare elements in this map.
  `boolean`
  `containsKey(Object key)`
  Returns whether this map contains the specified key.
  `boolean`
  `containsValue(Object value)`
  Returns whether this map contains the specified value.
  `NavigableSet<K>`
  `descendingKeySet()`
  Answers a NavigableSet view of the keys in descending order.
  `NavigableMap<K,V>`
  `descendingMap()`
  Answers a reverse order view of the map.
  `Set<Map.Entry<K,V>>`
  `entrySet()`
  Returns a set containing all of the mappings in this map.
  `Map.Entry<K,V>`
  `firstEntry()`
  Answers the entry with the smallest key, or null if the map is empty.
  `K`
  `firstKey()`
  Returns the first key in this map.
  `Map.Entry<K,V>`
  `floorEntry(K key)`
  Answers 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)`
  Answers 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.
  `SortedMap<K,V>`
  `headMap(K endKey)`
  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 end, boolean inclusive)`
  Answers a view of the head of the map whose keys are smaller than (or equal to, depends on inclusive argument) endKey.
  `Map.Entry<K,V>`
  `higherEntry(K key)`
  Answers an entry related with the smallest key greater than the specified key, or null if no such key.
  `K`
  `higherKey(K key)`
  Answers the smallest key greater than the specified key, or null if no such key.
  `Set<K>`
  `keySet()`
  Returns a set of the keys contained in this map.
  `Map.Entry<K,V>`
  `lastEntry()`
  Answers the entry with the biggest key, or null if the map is empty.
  `K`
  `lastKey()`
  Returns the last key in this map.
  `Map.Entry<K,V>`
  `lowerEntry(K key)`
  Answers an entry related with the biggest key less than the specified key, or null if no such key.
  `K`
  `lowerKey(K key)`
  Answers the biggest key less than the specified key, or null if no such key.
  `NavigableSet<K>`
  `navigableKeySet()`
  Answers a NavigableSet view of the keys in ascending order.
  `Map.Entry<K,V>`
  `pollFirstEntry()`
  Deletes and answers the entry with the smallest key, or null if the map is empty.
  `Map.Entry<K,V>`
  `pollLastEntry()`
  Deletes and answers 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.
  `void`
  `putAll(Map<? extends K, ? extends V> map)`
  Copies all the mappings in the given map to this map.
  `V`
  `remove(Object key)`
  Removes the mapping with the specified key from this map.
  `int`
  `size()`
  Returns the number of mappings in this map.
  `NavigableMap<K,V>`
  `subMap(K start, boolean startInclusive, K end, boolean endInclusive)`
  Answers a view of part of the map whose keys is from startKey to endKey.
  `SortedMap<K,V>`
  `subMap(K startKey, K endKey)`
  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 startKey)`
  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 start, boolean inclusive)`
  Answers a view of the tail of the map whose keys are bigger than (or equal to, depends on inclusive argument) startKey.
  `Collection<V>`
  `values()`
  Returns a collection of the values contained in this map.

  ### Methods inherited from class AbstractMap

  `equals, hashCode, isEmpty, toString`
  Modifier and Type
  Method
  Description
  `boolean`
  `equals(Object object)`
  Compares the specified object to this instance, and returns `true` if the specified object is a map and both maps contain the same mappings.
  `int`
  `hashCode()`
  Returns the hash code for this object.
  `boolean`
  `isEmpty()`
  Returns whether this map is empty.
  `String`
  `toString()`
  Returns the string representation of this map.

  ### Methods inherited from class Object

  `clone, getClass, notify, notifyAll, wait, wait, wait`
  Modifier and Type
  Method
  Description
  `protected Object`
  `clone()`
  `final Class`
  `getClass()`
  Returns the runtime class of an object.
  `final void`
  `notify()`
  Wakes up a single thread that is waiting on this object's monitor.
  `final void`
  `notifyAll()`
  Wakes up all threads that are waiting on this object's monitor.
  `final void`
  `wait()`
  Causes current thread to wait until another thread invokes the method or the method for this object.
  `final void`
  `wait(long timeout)`
  Causes current thread to wait until either another thread invokes the method or the method for this object, or a specified amount of time has elapsed.
  `final void`
  `wait(long timeout, int nanos)`
  Causes current thread to wait until another thread invokes the method or the method for this object, or some other thread interrupts the current thread, or a certain amount of real time has elapsed.

- ## Constructor Details

  - ### TreeMap

    public TreeMap()
    Constructs a new empty `TreeMap` instance.

  - ### TreeMap

    public TreeMap(Comparator<? super K> comparator)
    Constructs a new empty `TreeMap` instance with the specified comparator.
    Parameters:
      `comparator` - the comparator to compare keys with.

  - ### TreeMap

    public TreeMap(Map<? extends K, ? extends V> map)
    Constructs a new `TreeMap` instance containing the mappings from the specified map and using natural ordering.
    Parameters:
      `map` - the mappings to add.
    Throws:
      `ClassCastException` - if a key in the specified map does not implement the Comparable interface, or if the keys in the map cannot be compared.

  - ### TreeMap

    public TreeMap(SortedMap<K, ? extends V> map)
    Constructs a new `TreeMap` instance containing the mappings from the specified SortedMap and using the same comparator.
    Parameters:
      `map` - the mappings to add.

- ## Method Details

  - ### 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()`

  - ### comparator

    public Comparator<? super K> comparator()
    Returns the comparator used to compare elements in this map.
    Specified by:
      `comparator` in interface `SortedMap<K,V>`
    Returns:
      the comparator or `null` if the natural ordering is used.

  - ### containsKey

    public boolean containsKey(Object key)
    Returns whether this map contains the specified key.
    Specified by:
      `containsKey` in interface `Map<K,V>`
    Overrides:
      `containsKey` in class `AbstractMap<K,V>`
    Parameters:
      `key` - the key to search for.
    Returns:
      `true` if this map contains the specified key, `false` otherwise.
    Throws:
      `ClassCastException` - if the specified key cannot be compared with the keys in this map.
      `NullPointerException` - if the specified key is `null` and the comparator cannot handle `null` keys.

  - ### containsValue

    public boolean containsValue(Object value)
    Returns whether this map contains the specified value.
    Specified by:
      `containsValue` in interface `Map<K,V>`
    Overrides:
      `containsValue` in class `AbstractMap<K,V>`
    Parameters:
      `value` - the value to search for.
    Returns:
      `true` if this map contains the specified value, `false` otherwise.

  - ### firstKey

    public K firstKey()
    Returns the first key in this map.
    Specified by:
      `firstKey` in interface `SortedMap<K,V>`
    Returns:
      the first key in this map.
    Throws:
      `NoSuchElementException` - if this map 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` - if the key cannot be compared with the keys in this map.
      `NullPointerException` - if the key is `null` and the comparator cannot handle `null`.

  - ### keySet

    public Set<K> keySet()
    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.
    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()
    Returns the last key in this map.
    Specified by:
      `lastKey` in interface `SortedMap<K,V>`
    Returns:
      the last key in this map.
    Throws:
      `NoSuchElementException` - if this map is empty.

  - ### 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` - if the specified key cannot be compared with the keys in this map.
      `NullPointerException` - if the specified key is `null` and the comparator cannot handle `null` keys.

  - ### putAll

    public void putAll(Map<? extends K, ? extends V> map)
    Copies all the mappings in the given map to this map. These mappings will replace all mappings that this map had for any of the keys currently in the given map.
    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` - if a key in the specified map cannot be compared with the keys in this map.
      `NullPointerException` - if a key in the specified map is `null` and the comparator cannot handle `null` keys.

  - ### remove

    public V remove(Object key)
    Removes the mapping with the specified key from this map.
    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 no mapping for the specified key was found.
    Throws:
      `ClassCastException` - if the specified key cannot be compared with the keys in this map.
      `NullPointerException` - if the specified key is `null` and the comparator cannot handle `null` keys.

  - ### size

    public int size()
    Returns the number of mappings in this map.
    Specified by:
      `size` in interface `Map<K,V>`
    Overrides:
      `size` in class `AbstractMap<K,V>`
    Returns:
      the number of mappings in this map.

  - ### values

    public Collection<V> values()
    Returns a collection of the values contained in this map. The collection is backed by this map so changes to one are reflected by the other. The collection supports remove, removeAll, retainAll and clear operations, and it does not support add or addAll operations.

    This method returns a collection which is the subclass of AbstractCollection. The iterator method of this subclass returns a "wrapper object" over the iterator of map's entrySet(). The `size` method wraps the map's size method and the `contains` method wraps the map's containsValue method.

    The collection is created when this method is called for the first time and returned in response to all subsequent calls. This method may return different collections when multiple concurrent calls occur, since no synchronization is performed.

    Specified by:
      `values` in interface `Map<K,V>`
    Overrides:
      `values` in class `AbstractMap<K,V>`
    Returns:
      a collection of the values contained in this map.

  - ### firstEntry

    public Map.Entry<K,V> firstEntry()
    Answers the entry with the smallest key, or null if the map is empty.
    Specified by:
      `firstEntry` in interface `NavigableMap<K,V>`
    Returns:
      the entry with the smallest key, or null if the map is empty
    Since:
      1.6
    See Also:
      - `NavigableMap.firstEntry()`

  - ### lastEntry

    public Map.Entry<K,V> lastEntry()
    Answers the entry with the biggest key, or null if the map is empty.
    Specified by:
      `lastEntry` in interface `NavigableMap<K,V>`
    Returns:
      the entry with the biggest key, or null if the map is empty
    Since:
      1.6
    See Also:
      - `NavigableMap.lastEntry()`

  - ### pollFirstEntry

    public Map.Entry<K,V> pollFirstEntry()
    Deletes and answers the entry with the smallest key, or null if the map is empty.
    Specified by:
      `pollFirstEntry` in interface `NavigableMap<K,V>`
    Returns:
      the entry with the smallest key, or null if the map is empty
    Since:
      1.6
    See Also:
      - `NavigableMap.pollFirstEntry()`

  - ### pollLastEntry

    public Map.Entry<K,V> pollLastEntry()
    Deletes and answers the entry with the biggest key, or null if the map is empty.
    Specified by:
      `pollLastEntry` in interface `NavigableMap<K,V>`
    Returns:
      the entry with the biggest key, or null if the map is empty
    Since:
      1.6
    See Also:
      - `NavigableMap.pollLastEntry()`

  - ### higherEntry

    public Map.Entry<K,V> higherEntry(K key)
    Answers an entry related with the smallest key greater than the specified key, or null if no such key.
    Specified by:
      `higherEntry` in interface `NavigableMap<K,V>`
    Parameters:
      `key` - the key
    Returns:
      the entry, or null if no such key
    Since:
      1.6
    See Also:
      - `NavigableMap.higherEntry(Object)`

  - ### higherKey

    public K higherKey(K key)
    Answers the smallest key greater than the specified key, or null if no such key.
    Specified by:
      `higherKey` in interface `NavigableMap<K,V>`
    Parameters:
      `key` - the key
    Returns:
      the smallest key greater than key, or null if no such key
    Since:
      1.6
    See Also:
      - `NavigableMap.higherKey(Object)`

  - ### lowerEntry

    public Map.Entry<K,V> lowerEntry(K key)
    Answers an entry related with the biggest key less than the specified key, or null if no such key.
    Specified by:
      `lowerEntry` in interface `NavigableMap<K,V>`
    Parameters:
      `key` - the key
    Returns:
      the entry, or null if no such key
    Since:
      1.6
    See Also:
      - `NavigableMap.lowerEntry(Object)`

  - ### lowerKey

    public K lowerKey(K key)
    Answers the biggest key less than the specified key, or null if no such key.
    Specified by:
      `lowerKey` in interface `NavigableMap<K,V>`
    Parameters:
      `key` - the key
    Returns:
      the biggest key less than key, or null if no such key
    Since:
      1.6
    See Also:
      - `NavigableMap.lowerKey(Object)`

  - ### ceilingEntry

    public Map.Entry<K,V> ceilingEntry(K key)
    Answers an entry related with the smallest key greater than or equal to the specified key, or null if no such key.
    Specified by:
      `ceilingEntry` in interface `NavigableMap<K,V>`
    Parameters:
      `key` - the key
    Returns:
      the entry, or null if no such key
    Since:
      1.6
    See Also:
      - `NavigableMap.ceilingEntry(java.lang.Object)`

  - ### ceilingKey

    public K ceilingKey(K key)
    Answers the smallest key greater than or equal to the specified key, or null if no such key.
    Specified by:
      `ceilingKey` in interface `NavigableMap<K,V>`
    Parameters:
      `key` - the key
    Returns:
      the smallest key greater than or equal to key, or null if no such key
    Since:
      1.6
    See Also:
      - `NavigableMap.ceilingKey(java.lang.Object)`

  - ### floorEntry

    public Map.Entry<K,V> floorEntry(K key)
    Answers an entry related with the biggest key less than or equal to the specified key, or null if no such key.
    Specified by:
      `floorEntry` in interface `NavigableMap<K,V>`
    Parameters:
      `key` - the key
    Returns:
      the entry, or null if no such key
    Since:
      1.6
    See Also:
      - `NavigableMap.floorEntry(Object)`

  - ### floorKey

    public K floorKey(K key)
    Answers the biggest key less than or equal to the specified key, or null if no such key.
    Specified by:
      `floorKey` in interface `NavigableMap<K,V>`
    Parameters:
      `key` - the key
    Returns:
      the biggest key less than or equal to key, or null if no such key
    Since:
      1.6
    See Also:
      - `NavigableMap.floorKey(Object)`

  - ### entrySet

    public Set<Map.Entry<K,V>> entrySet()
    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. It does not support adding operations.
    Specified by:
      `entrySet` in interface `Map<K,V>`
    Specified by:
      `entrySet` in class `AbstractMap<K,V>`
    Returns:
      a set of the mappings.

  - ### navigableKeySet

    public NavigableSet<K> navigableKeySet()
    Answers a NavigableSet view of the keys in ascending order.
    Specified by:
      `navigableKeySet` in interface `NavigableMap<K,V>`
    Returns:
      the navigable set view
    Since:
      1.6
    See Also:
      - `NavigableMap.navigableKeySet()`

  - ### descendingKeySet

    public NavigableSet<K> descendingKeySet()
    Answers a NavigableSet view of the keys in descending order.
    Specified by:
      `descendingKeySet` in interface `NavigableMap<K,V>`
    Returns:
      the navigable set view
    Since:
      1.6
    See Also:
      - `NavigableMap.descendingKeySet()`

  - ### descendingMap

    public NavigableMap<K,V> descendingMap()
    Answers a reverse order view of the map.
    Specified by:
      `descendingMap` in interface `NavigableMap<K,V>`
    Returns:
      the reverse order view of the map
    Since:
      1.6
    See Also:
      - `NavigableMap.descendingMap()`

  - ### subMap

    public NavigableMap<K,V> subMap(K start, boolean startInclusive, K end, boolean endInclusive)
    Answers a view of part of the map whose keys is from startKey to endKey.
    Specified by:
      `subMap` in interface `NavigableMap<K,V>`
    Parameters:
      `start` - the start key
      `startInclusive` - true if the start key is in the returned map
      `end` - the end key
      `endInclusive` - true if the end key is in the returned map
    Returns:
      the sub-map view
    Since:
      1.6
    See Also:
      - `NavigableMap.subMap(Object, boolean, Object, boolean)`

  - ### headMap

    public NavigableMap<K,V> headMap(K end, boolean inclusive)
    Answers a view of the head of the map whose keys are smaller than (or equal to, depends on inclusive argument) endKey.
    Specified by:
      `headMap` in interface `NavigableMap<K,V>`
    Parameters:
      `end` - the end key
      `inclusive` - true if the end key is in the returned map
    Returns:
      the head-map view
    Since:
      1.6
    See Also:
      - `NavigableMap.headMap(Object, boolean)`

  - ### tailMap

    public NavigableMap<K,V> tailMap(K start, boolean inclusive)
    Answers a view of the tail of the map whose keys are bigger than (or equal to, depends on inclusive argument) startKey.
    Specified by:
      `tailMap` in interface `NavigableMap<K,V>`
    Parameters:
      `start` - the start key
      `inclusive` - true if the start key is in the returned map
    Returns:
      the tail-map view
    Since:
      1.6
    See Also:
      - `NavigableMap.tailMap(Object, boolean)`

  - ### subMap

    public SortedMap<K,V> subMap(K startKey, K endKey)
    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.

    Specified by:
      `subMap` in interface `SortedMap<K,V>`
    Parameters:
      `startKey` - the low boundary of the range (inclusive).
      `endKey` - the high boundary of the range (exclusive),
    Returns:
      a sorted map with the key from the specified range.
    Throws:
      `ClassCastException` - if the start or end key cannot be compared with the keys in this map.
      `NullPointerException` - if the start or end key is `null` and the comparator cannot handle `null` keys.
      `IllegalArgumentException` - if the start key is greater than the end key, or if this map is itself a sorted map over a range of another sorted map and the specified range is outside of its range.

  - ### headMap

    public SortedMap<K,V> headMap(K endKey)
    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.

    Specified by:
      `headMap` in interface `SortedMap<K,V>`
    Parameters:
      `endKey` - the high boundary of the range specified.
    Returns:
      a sorted map where the keys are less than `endKey`.
    Throws:
      `ClassCastException` - if the specified key cannot be compared with the keys in this map.
      `NullPointerException` - if the specified key is `null` and the comparator cannot handle `null` keys.
      `IllegalArgumentException` - if this map is itself a sorted map over a range of another map and the specified key is outside of its range.

  - ### tailMap

    public SortedMap<K,V> tailMap(K startKey)
    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.

    Specified by:
      `tailMap` in interface `SortedMap<K,V>`
    Parameters:
      `startKey` - the low boundary of the range specified.
    Returns:
      a sorted map where the keys are greater or equal to `startKey`.
    Throws:
      `ClassCastException` - if the specified key cannot be compared with the keys in this map.
      `NullPointerException` - if the specified key is `null` and the comparator cannot handle `null` keys.
      `IllegalArgumentException` - if this map itself a sorted map over a range of another map and the specified key is outside of its range.