/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 * This file is available under and governed by the GNU General Public
 * License version 2 only, as published by the Free Software Foundation.
 * However, the following notice accompanied the original version of this
 * file:
 *
 * Written by Doug Lea and Josh Bloch with assistance from members of JCP
 * JSR-166 Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util;

A 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 accessed and traversed in either ascending or descending key order. The descendingMap method returns a view of the map with the senses of all relational and directional methods inverted. The performance of ascending operations and views is likely to be faster than that of descending ones. Methods subMap(K, boolean, K, boolean), headMap(K, boolean), and tailMap(K, boolean) differ from the like-named SortedMap methods in accepting additional arguments describing whether lower and upper bounds are inclusive versus exclusive. 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.

Methods subMap(K, K), headMap(K), and tailMap(K) are specified to return SortedMap to allow existing implementations of SortedMap to be compatibly retrofitted to implement NavigableMap, but extensions and implementations of this interface are encouraged to override these methods to return NavigableMap. Similarly, SortedMap.keySet() can be overridden to return NavigableSet.

This interface is a member of the Java Collections Framework.

Author:Doug Lea, Josh Bloch
Type parameters:
  • <K> – the type of keys maintained by this map
  • <V> – the type of mapped values
Since:1.6
/** * A {@link SortedMap} extended with navigation methods returning the * closest matches for given search targets. Methods * {@link #lowerEntry}, {@link #floorEntry}, {@link #ceilingEntry}, * and {@link #higherEntry} return {@code Map.Entry} objects * associated with keys respectively less than, less than or equal, * greater than or equal, and greater than a given key, returning * {@code null} if there is no such key. Similarly, methods * {@link #lowerKey}, {@link #floorKey}, {@link #ceilingKey}, and * {@link #higherKey} return only the associated keys. All of these * methods are designed for locating, not traversing entries. * * <p>A {@code NavigableMap} may be accessed and traversed in either * ascending or descending key order. The {@link #descendingMap} * method returns a view of the map with the senses of all relational * and directional methods inverted. The performance of ascending * operations and views is likely to be faster than that of descending * ones. Methods * {@link #subMap(Object, boolean, Object, boolean) subMap(K, boolean, K, boolean)}, * {@link #headMap(Object, boolean) headMap(K, boolean)}, and * {@link #tailMap(Object, boolean) tailMap(K, boolean)} * differ from the like-named {@code SortedMap} methods in accepting * additional arguments describing whether lower and upper bounds are * inclusive versus exclusive. Submaps of any {@code NavigableMap} * must implement the {@code NavigableMap} interface. * * <p>This interface additionally defines methods {@link #firstEntry}, * {@link #pollFirstEntry}, {@link #lastEntry}, and * {@link #pollLastEntry} that return and/or remove the least and * greatest mappings, if any exist, else returning {@code null}. * * <p>Implementations of entry-returning methods are expected to * return {@code Map.Entry} pairs representing snapshots of mappings * at the time they were produced, and thus generally do <em>not</em> * support the optional {@code Entry.setValue} method. Note however * that it is possible to change mappings in the associated map using * method {@code put}. * * <p>Methods * {@link #subMap(Object, Object) subMap(K, K)}, * {@link #headMap(Object) headMap(K)}, and * {@link #tailMap(Object) tailMap(K)} * are specified to return {@code SortedMap} to allow existing * implementations of {@code SortedMap} to be compatibly retrofitted to * implement {@code NavigableMap}, but extensions and implementations * of this interface are encouraged to override these methods to return * {@code NavigableMap}. Similarly, * {@link #keySet()} can be overridden to return {@link NavigableSet}. * * <p>This interface is a member of the * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> * Java Collections Framework</a>. * * @author Doug Lea * @author Josh Bloch * @param <K> the type of keys maintained by this map * @param <V> the type of mapped values * @since 1.6 */
public interface NavigableMap<K,V> extends SortedMap<K,V> {
Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
Params:
  • key – the key
Throws:
Returns:an entry with the greatest key less than key, or null if there is no such key
/** * Returns a key-value mapping associated with the greatest key * strictly less than the given key, or {@code null} if there is * no such key. * * @param key the key * @return an entry with the greatest key less than {@code key}, * or {@code 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<K,V> lowerEntry(K key);
Returns the greatest key strictly less than the given key, or null if there is no such key.
Params:
  • key – the key
Throws:
Returns:the greatest key less than key, or null if there is no such key
/** * Returns the greatest key strictly less than the given key, or * {@code null} if there is no such key. * * @param key the key * @return the greatest key less than {@code key}, * or {@code 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.
Params:
  • key – the key
Throws:
Returns:an entry with the greatest key less than or equal to key, or null if there is no such key
/** * Returns a key-value mapping associated with the greatest key * less than or equal to the given key, or {@code null} if there * is no such key. * * @param key the key * @return an entry with the greatest key less than or equal to * {@code key}, or {@code 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<K,V> floorEntry(K key);
Returns the greatest key less than or equal to the given key, or null if there is no such key.
Params:
  • key – the key
Throws:
Returns:the greatest key less than or equal to key, or null if there is no such key
/** * Returns the greatest key less than or equal to the given key, * or {@code null} if there is no such key. * * @param key the key * @return the greatest key less than or equal to {@code key}, * or {@code 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.
Params:
  • key – the key
Throws:
Returns:an entry with the least key greater than or equal to key, or null if there is no such key
/** * Returns a key-value mapping associated with the least key * greater than or equal to the given key, or {@code null} if * there is no such key. * * @param key the key * @return an entry with the least key greater than or equal to * {@code key}, or {@code 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<K,V> ceilingEntry(K key);
Returns the least key greater than or equal to the given key, or null if there is no such key.
Params:
  • key – the key
Throws:
Returns:the least key greater than or equal to key, or null if there is no such key
/** * Returns the least key greater than or equal to the given key, * or {@code null} if there is no such key. * * @param key the key * @return the least key greater than or equal to {@code key}, * or {@code 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.
Params:
  • key – the key
Throws:
Returns:an entry with the least key greater than key, or null if there is no such key
/** * Returns a key-value mapping associated with the least key * strictly greater than the given key, or {@code null} if there * is no such key. * * @param key the key * @return an entry with the least key greater than {@code key}, * or {@code 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<K,V> higherEntry(K key);
Returns the least key strictly greater than the given key, or null if there is no such key.
Params:
  • key – the key
Throws:
Returns:the least key greater than key, or null if there is no such key
/** * Returns the least key strictly greater than the given key, or * {@code null} if there is no such key. * * @param key the key * @return the least key greater than {@code key}, * or {@code 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.
Returns:an entry with the least key, or null if this map is empty
/** * Returns a key-value mapping associated with the least * key in this map, or {@code null} if the map is empty. * * @return an entry with the least key, * or {@code null} if this map is empty */
Map.Entry<K,V> firstEntry();
Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
Returns:an entry with the greatest key, or null if this map is empty
/** * Returns a key-value mapping associated with the greatest * key in this map, or {@code null} if the map is empty. * * @return an entry with the greatest key, * or {@code null} if this map is empty */
Map.Entry<K,V> lastEntry();
Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.
Returns:the removed first entry of this map, or null if this map is empty
/** * Removes and returns a key-value mapping associated with * the least key in this map, or {@code null} if the map is empty. * * @return the removed first entry of this map, * or {@code null} if this map is empty */
Map.Entry<K,V> pollFirstEntry();
Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
Returns:the removed last entry of this map, or null if this map is empty
/** * Removes and returns a key-value mapping associated with * the greatest key in this map, or {@code null} if the map is empty. * * @return the removed last entry of this map, * or {@code null} if this map is empty */
Map.Entry<K,V> pollLastEntry();
Returns a reverse order view of the mappings contained in this map. The descending map is backed by this map, so changes to the map are reflected in the descending map, and vice-versa. If either map is modified while an iteration over a collection view of either map is in progress (except through the iterator's own 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.

Returns:a reverse order view of this map
/** * Returns a reverse order view of the mappings contained in this map. * The descending map is backed by this map, so changes to the map are * reflected in the descending map, and vice-versa. If either map is * modified while an iteration over a collection view of either map * is in progress (except through the iterator's own {@code remove} * operation), the results of the iteration are undefined. * * <p>The returned map has an ordering equivalent to * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}. * The expression {@code m.descendingMap().descendingMap()} returns a * view of {@code m} essentially equivalent to {@code m}. * * @return a reverse order view of this map */
NavigableMap<K,V> descendingMap();
Returns a 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.
Returns:a navigable set view of the keys in this map
/** * Returns a {@link 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 {@code * remove} operation), the results of the iteration are undefined. The * set supports element removal, which removes the corresponding mapping * from the map, via the {@code Iterator.remove}, {@code Set.remove}, * {@code removeAll}, {@code retainAll}, and {@code clear} operations. * It does not support the {@code add} or {@code addAll} operations. * * @return a navigable set view of the keys in this map */
NavigableSet<K> navigableKeySet();
Returns a reverse order 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.
Returns:a reverse order navigable set view of the keys in this map
/** * Returns a reverse order {@link 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 {@code * remove} operation), the results of the iteration are undefined. The * set supports element removal, which removes the corresponding mapping * from the map, via the {@code Iterator.remove}, {@code Set.remove}, * {@code removeAll}, {@code retainAll}, and {@code clear} operations. * It does not support the {@code add} or {@code addAll} operations. * * @return a reverse order navigable set view of the keys in this map */
NavigableSet<K> descendingKeySet();
Returns a view of the portion of this map whose keys range from fromKey to toKey. If fromKey and toKey are equal, the returned map is empty unless fromInclusive and toInclusive 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.

Params:
  • fromKey – low endpoint of the keys in the returned map
  • fromInclusive – true if the low endpoint is to be included in the returned view
  • toKey – high endpoint of the keys in the returned map
  • toInclusive – true if the high endpoint is to be included in the returned view
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.
  • NullPointerException – if fromKey or toKey is null and this map does not permit null keys
  • 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
Returns:a view of the portion of this map whose keys range from fromKey to toKey
/** * Returns a view of the portion of this map whose keys range from * {@code fromKey} to {@code toKey}. If {@code fromKey} and * {@code toKey} are equal, the returned map is empty unless * {@code fromInclusive} and {@code toInclusive} 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. * * <p>The returned map will throw an {@code 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. * * @param fromKey low endpoint of the keys in the returned map * @param fromInclusive {@code true} if the low endpoint * is to be included in the returned view * @param toKey high endpoint of the keys in the returned map * @param toInclusive {@code true} if the high endpoint * is to be included in the returned view * @return a view of the portion of this map whose keys range from * {@code fromKey} to {@code toKey} * @throws ClassCastException if {@code fromKey} and {@code 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 {@code fromKey} or {@code toKey} * cannot be compared to keys currently in the map. * @throws NullPointerException if {@code fromKey} or {@code toKey} * is null and this map does not permit null keys * @throws IllegalArgumentException if {@code fromKey} is greater than * {@code toKey}; or if this map itself has a restricted * range, and {@code fromKey} or {@code toKey} lies * outside the bounds of the range */
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive);
Returns a view of the portion of this map whose keys are less than (or equal to, if 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.

Params:
  • toKey – high endpoint of the keys in the returned map
  • inclusive – true if the high endpoint is to be included in the returned view
Throws:
  • ClassCastException – if toKey is not compatible with this map's comparator (or, if the map has no comparator, if toKey does not implement Comparable). Implementations may, but are not required to, throw this exception if toKey cannot be compared to keys currently in the map.
  • NullPointerException – if toKey is null and this map does not permit null keys
  • IllegalArgumentException – if this map itself has a restricted range, and toKey lies outside the bounds of the range
Returns:a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey
/** * Returns a view of the portion of this map whose keys are less than (or * equal to, if {@code inclusive} is true) {@code 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. * * <p>The returned map will throw an {@code IllegalArgumentException} * on an attempt to insert a key outside its range. * * @param toKey high endpoint of the keys in the returned map * @param inclusive {@code true} if the high endpoint * is to be included in the returned view * @return a view of the portion of this map whose keys are less than * (or equal to, if {@code inclusive} is true) {@code toKey} * @throws ClassCastException if {@code toKey} is not compatible * with this map's comparator (or, if the map has no comparator, * if {@code toKey} does not implement {@link Comparable}). * Implementations may, but are not required to, throw this * exception if {@code toKey} cannot be compared to keys * currently in the map. * @throws NullPointerException if {@code toKey} is null * and this map does not permit null keys * @throws IllegalArgumentException if this map itself has a * restricted range, and {@code toKey} lies outside the * bounds of the range */
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
Returns a view of the portion of this map whose keys are greater than (or equal to, if 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.

Params:
  • fromKey – low endpoint of the keys in the returned map
  • inclusive – true if the low endpoint is to be included in the returned view
Throws:
  • ClassCastException – if fromKey is not compatible with this map's comparator (or, if the map has no comparator, if fromKey does not implement Comparable). Implementations may, but are not required to, throw this exception if fromKey cannot be compared to keys currently in the map.
  • NullPointerException – if fromKey is null and this map does not permit null keys
  • IllegalArgumentException – if this map itself has a restricted range, and fromKey lies outside the bounds of the range
Returns:a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey
/** * Returns a view of the portion of this map whose keys are greater than (or * equal to, if {@code inclusive} is true) {@code 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. * * <p>The returned map will throw an {@code IllegalArgumentException} * on an attempt to insert a key outside its range. * * @param fromKey low endpoint of the keys in the returned map * @param inclusive {@code true} if the low endpoint * is to be included in the returned view * @return a view of the portion of this map whose keys are greater than * (or equal to, if {@code inclusive} is true) {@code fromKey} * @throws ClassCastException if {@code fromKey} is not compatible * with this map's comparator (or, if the map has no comparator, * if {@code fromKey} does not implement {@link Comparable}). * Implementations may, but are not required to, throw this * exception if {@code fromKey} cannot be compared to keys * currently in the map. * @throws NullPointerException if {@code fromKey} is null * and this map does not permit null keys * @throws IllegalArgumentException if this map itself has a * restricted range, and {@code fromKey} lies outside the * bounds of the range */
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
{@inheritDoc}

Equivalent to subMap(fromKey, true, toKey, false).

Throws:
/** * {@inheritDoc} * * <p>Equivalent to {@code subMap(fromKey, true, toKey, false)}. * * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */
SortedMap<K,V> subMap(K fromKey, K toKey);
{@inheritDoc}

Equivalent to headMap(toKey, false).

Throws:
/** * {@inheritDoc} * * <p>Equivalent to {@code headMap(toKey, false)}. * * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */
SortedMap<K,V> headMap(K toKey);
{@inheritDoc}

Equivalent to tailMap(fromKey, true).

Throws:
/** * {@inheritDoc} * * <p>Equivalent to {@code tailMap(fromKey, true)}. * * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */
SortedMap<K,V> tailMap(K fromKey); }