totalcross.util

Class TreeMap4D<K,V>

java.lang.Object

totalcross.util.AbstractMap4D<K,V>

totalcross.util.TreeMap4D<K,V>

All Implemented Interfaces:

java.lang.Cloneable, java.util.Map<K,V>, java.util.NavigableMap<K,V>, java.util.SortedMap<K,V>

public class TreeMap4D<K,V>
extends AbstractMap4D<K,V>
implements java.util.NavigableMap<K,V>, java.lang.Cloneable

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.

Since:

1.2

See Also:

Map, HashMap, Hashtable, LinkedHashMap, Comparable, Comparator, Collection, Collections.synchronizedSortedMap(SortedMap)

Nested Class Summary

Nested classes/interfaces inherited from class totalcross.util.AbstractMap4D

AbstractMap4D.SimpleEntry<K,V>, AbstractMap4D.SimpleImmutableEntry<K,V>

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

java.util.Map.Entry<K,V>

Constructor Summary

Constructors

Constructor and Description
TreeMap4D() Instantiate a new TreeMap with no elements, using the keys' natural ordering to sort.
TreeMap4D(java.util.Comparator<? super K> c) Instantiate a new TreeMap with no elements, using the provided comparator to sort.
TreeMap4D(java.util.Map<? extends K,? extends V> map) Instantiate a new TreeMap, initializing it with all of the elements in the provided Map.
TreeMap4D(java.util.SortedMap<K,? extends V> sm) Instantiate a new TreeMap, initializing it with all of the elements in the provided SortedMap.

Method Summary

Modifier and Type	Method and Description
java.util.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.
java.lang.Object	clone() Returns a shallow clone of this TreeMap.
java.util.Comparator<? super K>	comparator() Return the comparator used to sort this map, or null if it is by natural order.
boolean	containsKey(java.lang.Object key) Returns true if the map contains a mapping for the given key.
boolean	containsValue(java.lang.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.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Returns a "set view" of this TreeMap's entries.
java.util.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.
java.util.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(java.lang.Object key) Return the value in this TreeMap associated with the supplied key, or null if the key maps to nothing.
java.util.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.
java.util.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.
java.util.Set<K>	keySet() Returns a "set view" of this TreeMap's keys.
java.util.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.
java.util.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.
java.util.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.
java.util.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(java.util.Map<? extends K,? extends V> m) Copies all elements of the given map into this TreeMap.
V	remove(java.lang.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.
java.util.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).
java.util.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.
java.util.Collection<V>	values() Returns a "collection view" (or "bag view") of this TreeMap's values.

Methods inherited from class totalcross.util.AbstractMap4D

equals, equals, hashCode, hashCode, isEmpty, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, equals, forEach, getOrDefault, hashCode, isEmpty, merge, putIfAbsent, remove, replace, replace, replaceAll

Constructor Detail

TreeMap4D

public TreeMap4D()

Instantiate a new TreeMap with no elements, using the keys' natural ordering to sort. All entries in the map must have a key which implements Comparable, and which are mutually comparable, otherwise map operations may throw a ClassCastException. Attempts to use a null key will throw a NullPointerException.

See Also:

Comparable

TreeMap4D

public TreeMap4D(java.util.Comparator<? super K> c)

Instantiate a new TreeMap with no elements, using the provided comparator to sort. All entries in the map must have keys which are mutually comparable by the Comparator, otherwise map operations may throw a ClassCastException.

Parameters:

c - the sort order for the keys of this map, or null for the natural order

TreeMap4D

public TreeMap4D(java.util.Map<? extends K,? extends V> map)

Instantiate a new TreeMap, initializing it with all of the elements in the provided Map. The elements will be sorted using the natural ordering of the keys. This algorithm runs in n*log(n) time. All entries in the map must have keys which implement Comparable and are mutually comparable, otherwise map operations may throw a ClassCastException.

Parameters:

map - a Map, whose entries will be put into this TreeMap

Throws:

java.lang.ClassCastException - if the keys in the provided Map are not comparable

java.lang.NullPointerException - if map is null

See Also:

Comparable

TreeMap4D

public TreeMap4D(java.util.SortedMap<K,? extends V> sm)

Instantiate a new TreeMap, initializing it with all of the elements in the provided SortedMap. The elements will be sorted using the same comparator as in the provided SortedMap. This runs in linear time.

Parameters:

sm - a SortedMap, whose entries will be put into this TreeMap

Throws:

java.lang.NullPointerException - if sm is null

Method Detail

clear

public void clear()

Clears the Map so it has no keys. This is O(1).

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class AbstractMap4D<K,V>

See Also:

Set.clear()

clone

public java.lang.Object clone()

Returns a shallow clone of this TreeMap. The Map itself is cloned, but its contents are not.

Overrides:

clone in class AbstractMap4D<K,V>

Returns:

the clone

See Also:

Cloneable, Object.clone()

comparator

public java.util.Comparator<? super K> comparator()

Return the comparator used to sort this map, or null if it is by natural order.

Specified by:

comparator in interface java.util.SortedMap<K,V>

Returns:

the map's comparator

containsKey

public boolean containsKey(java.lang.Object key)

Returns true if the map contains a mapping for the given key.

Specified by:

containsKey in interface java.util.Map<K,V>

Overrides:

containsKey in class AbstractMap4D<K,V>

Parameters:

key - the key to look for

Returns:

true if the key has a mapping

Throws:

java.lang.ClassCastException - if key is not comparable to map elements

java.lang.NullPointerException - if key is null and the comparator is not tolerant of nulls

See Also:

AbstractMap4D.containsValue(Object)

containsValue

public boolean containsValue(java.lang.Object value)

Returns true if the map contains at least one mapping to the given value. This requires linear time.

Specified by:

containsValue in interface java.util.Map<K,V>

Overrides:

containsValue in class AbstractMap4D<K,V>

Parameters:

value - the value to look for

Returns:

true if the value appears in a mapping

See Also:

AbstractMap4D.containsKey(Object)

entrySet

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

Returns a "set view" of this TreeMap's entries. 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.

Note that the iterators for all three views, from keySet(), entrySet(), and values(), traverse the TreeMap in sorted sequence.

Specified by:

entrySet in interface java.util.Map<K,V>

Specified by:

entrySet in interface java.util.SortedMap<K,V>

Specified by:

entrySet in class AbstractMap4D<K,V>

Returns:

a set view of the entries

See Also:

keySet(), values(), Map.Entry

firstKey

public K firstKey()

Returns the first (lowest) key in the map.

Specified by:

firstKey in interface java.util.SortedMap<K,V>

Returns:

the first key

Throws:

java.util.NoSuchElementException - if the map is empty

get

public V get(java.lang.Object key)

Return the value in this TreeMap associated with the supplied key, or 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.

Specified by:

get in interface java.util.Map<K,V>

Overrides:

get in class AbstractMap4D<K,V>

Parameters:

key - the key for which to fetch an associated value

Returns:

what the key maps to, if present

Throws:

java.lang.ClassCastException - if key is not comparable to elements in the map

java.lang.NullPointerException - if key is null but the comparator does not tolerate nulls

See Also:

put(Object, Object), containsKey(Object)

headMap

public java.util.SortedMap<K,V> headMap(K toKey)

Returns a view of this Map including all entries with keys less than 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).

Specified by:

headMap in interface java.util.NavigableMap<K,V>

Specified by:

headMap in interface java.util.SortedMap<K,V>

Parameters:

toKey - the (exclusive) cutoff point

Returns:

a view of the map less than the cutoff

Throws:

java.lang.ClassCastException - if toKey is not compatible with the comparator (or is not Comparable, for natural ordering)

java.lang.NullPointerException - if toKey is null, but the comparator does not tolerate null elements

headMap

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

Specified by:

headMap in interface java.util.NavigableMap<K,V>

Parameters:

toKey - the cutoff point

inclusive - true if the cutoff point should be included.

Returns:

a view of the map less than (or equal to, if inclusive is true) the cutoff.

Throws:

java.lang.ClassCastException - if toKey is not compatible with the comparator (or is not Comparable, for natural ordering)

java.lang.NullPointerException - if toKey is null, but the comparator does not tolerate null elements

keySet

public java.util.Set<K> keySet()

Returns a "set view" of this TreeMap'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.

Specified by:

keySet in interface java.util.Map<K,V>

Specified by:

keySet in interface java.util.SortedMap<K,V>

Overrides:

keySet in class AbstractMap4D<K,V>

Returns:

a set view of the keys

See Also:

values(), entrySet()

lastKey

public K lastKey()

Returns the last (highest) key in the map.

Specified by:

lastKey in interface java.util.SortedMap<K,V>

Returns:

the last key

Throws:

java.util.NoSuchElementException - if the map is empty

put

public V put(K key,
             V value)

Puts the supplied value into the Map, mapped by the supplied key. The value may be retrieved by any object which 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.

Specified by:

put in interface java.util.Map<K,V>

Overrides:

put in class AbstractMap4D<K,V>

Parameters:

key - the key used to locate the value

value - the value to be stored in the Map

Returns:

the prior mapping of the key, or null if there was none

Throws:

java.lang.ClassCastException - if key is not comparable to current map keys

java.lang.NullPointerException - if key is null, but the comparator does not tolerate nulls

See Also:

get(Object), Object.equals(Object)

putAll

public void putAll(java.util.Map<? extends K,? extends V> m)

Copies all elements of the given map into this TreeMap. If this map already has a mapping for a key, the new mapping replaces the current one.

Specified by:

putAll in interface java.util.Map<K,V>

Overrides:

putAll in class AbstractMap4D<K,V>

Parameters:

m - the map to be added

Throws:

java.lang.ClassCastException - if a key in m is not comparable with keys in the map

java.lang.NullPointerException - if a key in m is null, and the comparator does not tolerate nulls

See Also:

AbstractMap4D.put(Object, Object)

remove

public V remove(java.lang.Object key)

Removes from the TreeMap and returns the value which is mapped by the supplied key. If the key maps to nothing, then the TreeMap remains unchanged, and null is returned. NOTE: Since the value could also be null, you must use containsKey to see if you are actually removing a mapping.

Specified by:

remove in interface java.util.Map<K,V>

Overrides:

remove in class AbstractMap4D<K,V>

Parameters:

key - the key used to locate the value to remove

Returns:

whatever the key mapped to, if present

Throws:

java.lang.ClassCastException - if key is not comparable to current map keys

java.lang.NullPointerException - if key is null, but the comparator does not tolerate nulls

See Also:

Iterator.remove()

size

public int size()

Returns the number of key-value mappings currently in this Map.

Specified by:

size in interface java.util.Map<K,V>

Overrides:

size in class AbstractMap4D<K,V>

Returns:

the size

See Also:

Set.size()

subMap

public java.util.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). 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).

Specified by:

subMap in interface java.util.NavigableMap<K,V>

Specified by:

subMap in interface java.util.SortedMap<K,V>

Parameters:

fromKey - the (inclusive) low cutoff point

toKey - the (exclusive) high cutoff point

Returns:

a view of the map between the cutoffs

Throws:

java.lang.ClassCastException - if either cutoff is not compatible with the comparator (or is not Comparable, for natural ordering)

java.lang.NullPointerException - if fromKey or toKey is null, but the comparator does not tolerate null elements

java.lang.IllegalArgumentException - if fromKey is greater than toKey

subMap

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

Specified by:

subMap in interface java.util.NavigableMap<K,V>

Parameters:

fromKey - the low cutoff point

fromInclusive - true if the low cutoff point should be included.

toKey - the high cutoff point

toInclusive - true if the high cutoff point should be included.

Returns:

a view of the map for the specified range.

Throws:

java.lang.ClassCastException - if either cutoff is not compatible with the comparator (or is not Comparable, for natural ordering)

java.lang.NullPointerException - if fromKey or toKey is null, but the comparator does not tolerate null elements

java.lang.IllegalArgumentException - if fromKey is greater than toKey

tailMap

public java.util.SortedMap<K,V> tailMap(K fromKey)

Returns a view of this Map including all entries with keys greater or equal to 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).

Specified by:

tailMap in interface java.util.NavigableMap<K,V>

Specified by:

tailMap in interface java.util.SortedMap<K,V>

Parameters:

fromKey - the (inclusive) low cutoff point

Returns:

a view of the map above the cutoff

Throws:

java.lang.ClassCastException - if fromKey is not compatible with the comparator (or is not Comparable, for natural ordering)

java.lang.NullPointerException - if fromKey is null, but the comparator does not tolerate null elements

tailMap

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

Specified by:

tailMap in interface java.util.NavigableMap<K,V>

Parameters:

fromKey - the low cutoff point

inclusive - true if the cutoff point should be included.

Returns:

a view of the map above the cutoff

Throws:

java.lang.ClassCastException - if fromKey is not compatible with the comparator (or is not Comparable, for natural ordering)

java.lang.NullPointerException - if fromKey is null, but the comparator does not tolerate null elements

values

public java.util.Collection<V> values()

Returns a "collection view" (or "bag view") of this TreeMap's values. The collection is backed by the TreeMap, so changes in one show up in the other. The collection supports element removal, but not element addition.

Specified by:

values in interface java.util.Map<K,V>

Specified by:

values in interface java.util.SortedMap<K,V>

Overrides:

values in class AbstractMap4D<K,V>

Returns:

a bag view of the values

See Also:

keySet(), entrySet()

ceilingEntry

public java.util.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.

Specified by:

ceilingEntry in interface java.util.NavigableMap<K,V>

Parameters:

key - the key relative to the returned entry.

Returns:

the entry with the least key greater than or equal to the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if the specified key can not be compared with those in the map.

java.lang.NullPointerException - if the key is null and this map either uses natural ordering or a comparator that does not permit null keys.

Since:

1.6

ceilingKey

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

Specified by:

ceilingKey in interface java.util.NavigableMap<K,V>

Parameters:

key - the key relative to the returned entry.

Returns:

the least key greater than or equal to the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if the specified key can not be compared with those in the map.

java.lang.NullPointerException - if the key is null and this map either uses natural ordering or a comparator that does not permit null keys.

Since:

1.6

descendingKeySet

public java.util.NavigableSet<K> descendingKeySet()

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

Specified by:

descendingKeySet in interface java.util.NavigableMap<K,V>

Returns:

a reverse ordered set view of the keys.

Since:

1.6

See Also:

descendingMap()

descendingMap

public java.util.NavigableMap<K,V> descendingMap()

Returns a view of the map in reverse order. The descending map is backed by the original map, so that changes affect both maps. Any changes occurring to either map while an iteration is taking place (with the exception of a 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.

Specified by:

descendingMap in interface java.util.NavigableMap<K,V>

Returns:

a reverse order view of the map.

Since:

1.6

firstEntry

public java.util.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.

Specified by:

firstEntry in interface java.util.NavigableMap<K,V>

Returns:

the lowest entry, or null if the map is empty.

Since:

1.6

floorEntry

public java.util.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.

Specified by:

floorEntry in interface java.util.NavigableMap<K,V>

Parameters:

key - the key relative to the returned entry.

Returns:

the entry with the greatest key less than or equal to the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if the specified key can not be compared with those in the map.

java.lang.NullPointerException - if the key is null and this map either uses natural ordering or a comparator that does not permit null keys.

Since:

1.6

floorKey

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

Specified by:

floorKey in interface java.util.NavigableMap<K,V>

Parameters:

key - the key relative to the returned entry.

Returns:

the greatest key less than or equal to the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if the specified key can not be compared with those in the map.

java.lang.NullPointerException - if the key is null and this map either uses natural ordering or a comparator that does not permit null keys.

Since:

1.6

higherEntry

public java.util.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.

Specified by:

higherEntry in interface java.util.NavigableMap<K,V>

Parameters:

key - the key relative to the returned entry.

Returns:

the entry with the least key greater than the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if the specified key can not be compared with those in the map.

java.lang.NullPointerException - if the key is null and this map either uses natural ordering or a comparator that does not permit null keys.

Since:

1.6

higherKey

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

Specified by:

higherKey in interface java.util.NavigableMap<K,V>

Parameters:

key - the key relative to the returned entry.

Returns:

the least key greater than the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if the specified key can not be compared with those in the map.

java.lang.NullPointerException - if the key is null and this map either uses natural ordering or a comparator that does not permit null keys.

Since:

1.6

lastEntry

public java.util.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.

Specified by:

lastEntry in interface java.util.NavigableMap<K,V>

Returns:

the highest entry, or null if the map is empty.

Since:

1.6

lowerEntry

public java.util.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.

Specified by:

lowerEntry in interface java.util.NavigableMap<K,V>

Parameters:

key - the key relative to the returned entry.

Returns:

the entry with the greatest key less than the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if the specified key can not be compared with those in the map.

java.lang.NullPointerException - if the key is null and this map either uses natural ordering or a comparator that does not permit null keys.

Since:

1.6

lowerKey

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

Specified by:

lowerKey in interface java.util.NavigableMap<K,V>

Parameters:

key - the key relative to the returned entry.

Returns:

the greatest key less than the given key, or null if there is no such key.

Throws:

java.lang.ClassCastException - if the specified key can not be compared with those in the map.

java.lang.NullPointerException - if the key is null and this map either uses natural ordering or a comparator that does not permit null keys.

Since:

1.6

navigableKeySet

public java.util.NavigableSet<K> navigableKeySet()

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

Specified by:

navigableKeySet in interface java.util.NavigableMap<K,V>

Returns:

a NavigableSet view of the keys.

Since:

1.6

pollFirstEntry

public java.util.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.

Specified by:

pollFirstEntry in interface java.util.NavigableMap<K,V>

Returns:

the removed first entry, or null if the map is empty.

Since:

1.6

pollLastEntry

public java.util.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.

Specified by:

pollLastEntry in interface java.util.NavigableMap<K,V>

Returns:

the removed last entry, or null if the map is empty.

Since:

1.6