/*
* Written by Doug Lea with assistance from members of JCP JSR-166
* Expert Group and released to the public domain, as explained at
* http://creativecommons.org/licenses/publicdomain
*/
package java.util;
/**
* A {@link SortedMap} extended with navigation methods returning the
* closest matches for given search targets. Methods
* lowerEntry, floorEntry, ceilingEntry,
* and higherEntry return Map.Entry objects
* associated with keys respectively less than, less than or equal,
* greater than or equal, and greater than a given key, returning
* null if there is no such key. Similarly, methods
* lowerKey, floorKey, ceilingKey, and
* higherKey return only the associated keys. All of these
* methods are designed for locating, not traversing entries.
*
* A NavigableMap may be viewed and traversed in either
* ascending or descending key order. The Map methods
* keySet and entrySet return ascending views, and
* the additional methods descendingKeySet and
* descendingEntrySet return descending views. The
* performance of ascending traversals is likely to be faster than
* descending traversals. Notice that it is possible to perform
* subrange traversals in either direction using navigableSubMap.
* Methods navigableSubMap, navigableHeadMap, and
* navigableTailMap differ from the similarly named
* SortedMap methods only in their declared return types.
* Submaps of any NavigableMap must implement the
* NavigableMap interface.
*
*
This interface additionally defines methods firstEntry,
* pollFirstEntry, lastEntry, and
* pollLastEntry that return and/or remove the least and
* greatest mappings, if any exist, else returning null.
*
*
Implementations of entry-returning methods are expected to
* return Map.Entry pairs representing snapshots of mappings
* at the time they were produced, and thus generally do not
* support the optional Entry.setValue method. Note however
* that it is possible to change mappings in the associated map using
* method put.
*
*
This interface is a member of the
*
* Java Collections Framework.
*
* @author Doug Lea
* @param the type of keys maintained by this map
* @param the type of mapped values
* @since 1.6
*/
public interface NavigableMap extends SortedMap {
/**
* Returns a key-value mapping associated with the greatest key
* strictly less than the given key, or null if there is
* no such key.
*
* @param key the key
* @return an entry with the greatest key less than key,
* or null if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
Map.Entry lowerEntry(K key);
/**
* Returns the greatest key strictly less than the given key, or
* null if there is no such key.
*
* @param key the key
* @return the greatest key less than key,
* or null if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
K lowerKey(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.
*
* @param key the key
* @return an entry with the greatest key less than or equal to
* key, or null if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
Map.Entry floorEntry(K key);
/**
* Returns the greatest key less than or equal to the given key,
* or null if there is no such key.
*
* @param key the key
* @return the greatest key less than or equal to key,
* or null if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
K floorKey(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.
*
* @param key the key
* @return an entry with the least key greater than or equal to
* key, or null if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
Map.Entry ceilingEntry(K key);
/**
* Returns the least key greater than or equal to the given key,
* or null if there is no such key.
*
* @param key the key
* @return the least key greater than or equal to key,
* or null if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
K ceilingKey(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.
*
* @param key the key
* @return an entry with the least key greater than key,
* or null if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
Map.Entry higherEntry(K key);
/**
* Returns the least key strictly greater than the given key, or
* null if there is no such key.
*
* @param key the key
* @return the least key greater than key,
* or null if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
K higherKey(K key);
/**
* Returns a key-value mapping associated with the least
* key in this map, or null if the map is empty.
*
* @return an entry with the least key,
* or null if this map is empty
*/
Map.Entry firstEntry();
/**
* Returns a key-value mapping associated with the greatest
* key in this map, or null if the map is empty.
*
* @return an entry with the greatest key,
* or null if this map is empty
*/
Map.Entry lastEntry();
/**
* Removes and returns a key-value mapping associated with
* the least key in this map, or null if the map is empty.
*
* @return the removed first entry of this map,
* or null if this map is empty
*/
Map.Entry pollFirstEntry();
/**
* Removes and returns a key-value mapping associated with
* the greatest key in this map, or null if the map is empty.
*
* @return the removed last entry of this map,
* or null if this map is empty
*/
Map.Entry pollLastEntry();
/**
* Returns a {@link Set} 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.
*
* @return a set view of the keys contained in this map, sorted in
* descending order
*/
Set descendingKeySet();
/**
* Returns a {@link Set} view of the mappings contained in this map.
* The set's iterator returns the entries in descending key 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, or through the
* setValue operation on a map entry returned by the
* iterator) 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.
*
* @return a set view of the mappings contained in this map,
* sorted in descending key order
*/
Set> descendingEntrySet();
/**
* Returns a view of the portion of this map whose keys range from
* fromKey, inclusive, to toKey, exclusive. (If
* fromKey and toKey are equal, the returned map
* is empty.) 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.
*
* @param fromKey low endpoint (inclusive) of the keys in the returned map
* @param toKey high endpoint (exclusive) of the keys in the returned map
* @return a view of the portion of this map whose keys range from
* fromKey, inclusive, to toKey, exclusive
* @throws ClassCastException if fromKey and toKey
* cannot be compared to one another using this map's comparator
* (or, if the map has no comparator, using natural ordering).
* Implementations may, but are not required to, throw this
* exception if fromKey or toKey
* cannot be compared to keys currently in the map.
* @throws NullPointerException if fromKey or toKey
* is null and this map does not permit null keys
* @throws IllegalArgumentException if fromKey is greater than
* toKey; or if this map itself has a restricted
* range, and fromKey or toKey lies
* outside the bounds of the range
*/
NavigableMap navigableSubMap(K fromKey, K toKey);
/**
* Returns a view of the portion of this map whose keys are
* strictly less than 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.
*
* @param toKey high endpoint (exclusive) of the keys in the returned map
* @return a view of the portion of this map whose keys are strictly
* less than toKey
* @throws ClassCastException if toKey is not compatible
* with this map's comparator (or, if the map has no comparator,
* if toKey does not implement {@link Comparable}).
* Implementations may, but are not required to, throw this
* exception if toKey cannot be compared to keys
* currently in the map.
* @throws NullPointerException if toKey is null
* and this map does not permit null keys
* @throws IllegalArgumentException if this map itself has a
* restricted range, and toKey lies outside the
* bounds of the range
*/
NavigableMap navigableHeadMap(K toKey);
/**
* Returns a view of the portion of this map whose keys are
* greater than or equal to 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.
*
* @param fromKey low endpoint (inclusive) of the keys in the returned map
* @return a view of the portion of this map whose keys are greater
* than or equal to fromKey
* @throws ClassCastException if fromKey is not compatible
* with this map's comparator (or, if the map has no comparator,
* if fromKey does not implement {@link Comparable}).
* Implementations may, but are not required to, throw this
* exception if fromKey cannot be compared to keys
* currently in the map.
* @throws NullPointerException if fromKey is null
* and this map does not permit null keys
* @throws IllegalArgumentException if this map itself has a
* restricted range, and fromKey lies outside the
* bounds of the range
*/
NavigableMap navigableTailMap(K fromKey);
}