--- jsr166/src/jsr166x/NavigableMap.java 2004/09/06 17:01:54 1.1 +++ jsr166/src/jsr166x/NavigableMap.java 2011/12/05 04:48:16 1.8 @@ -1,7 +1,7 @@ /* * 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 + * http://creativecommons.org/publicdomain/zero/1.0/ */ package jsr166x; @@ -9,39 +9,50 @@ package jsr166x; import java.util.*; /** - * A {@link SortedMap} extended with methods returning key-value pairs - * holding the closest matches for given search targets. Methods + * A {@link SortedMap} extended with navigation methods returning the + * closest matches for given search targets. Methods * lowerEntry, floorEntry, ceilingEntry, - * and higherEntry return {@link Map.Entry} objects + * 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. These methods are designed - * for locating, not traversing entries. To traverse, use view - * iterators and/or submap. 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. + * 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. * - *

Implementations of these 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. + *

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 + * subrannge traversals in either direction using SubMap. + * + *

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. * * @author Doug Lea * @param the type of keys maintained by this map - * @param the type of mapped values + * @param the type of mapped values */ public interface NavigableMap extends SortedMap { /** * 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 entry. - * + * greater than or equal to the given key, or null if there is + * no such entry. + * * @param key the key. - * @return an Entry associated with ceiling of given key, or null + * @return an Entry associated with ceiling of given key, or null * if there is no such Entry. * @throws ClassCastException if key cannot be compared with the keys * currently in the map. @@ -51,13 +62,27 @@ public interface NavigableMap exten public Map.Entry ceilingEntry(K key); /** + * Returns least key greater than or equal to the given key, or + * null if there is no such key. + * + * @param key the key. + * @return the ceiling key, or null + * if there is no such key. + * @throws ClassCastException if key cannot be compared with the keys + * currently in the map. + * @throws NullPointerException if key is null and this map + * does not support null keys. + */ + public K ceilingKey(K key); + + /** * Returns a key-value mapping associated with the greatest - * key strictly less than the given key, or null if there is no - * such entry. - * + * key strictly less than the given key, or null if there is no + * such entry. + * * @param key the key. * @return an Entry with greatest key less than the given - * key, or null if there is no such Entry. + * key, or null if there is no such Entry. * @throws ClassCastException if key cannot be compared with the keys * currently in the map. * @throws NullPointerException if key is null and this map @@ -66,12 +91,26 @@ public interface NavigableMap exten public Map.Entry lowerEntry(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 entry. - * + * Returns the greatest key strictly less than the given key, or + * null if there is no such key. + * * @param key the key. - * @return an Entry associated with floor of given key, or null + * @return the greatest key less than the given + * key, or null if there is no such key. + * @throws ClassCastException if key cannot be compared with the keys + * currently in the map. + * @throws NullPointerException if key is null and this map + * does not support null keys. + */ + public 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 entry. + * + * @param key the key. + * @return an Entry associated with floor of given key, or null * if there is no such Entry. * @throws ClassCastException if key cannot be compared with the keys * currently in the map. @@ -81,13 +120,28 @@ public interface NavigableMap exten public Map.Entry floorEntry(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 entry. - * + * 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 floor of given key, or null if there is no + * such key. + * @throws ClassCastException if key cannot be compared with the keys + * currently in the map. + * @throws NullPointerException if key is null and this map + * does not support null keys. + */ + public K floorKey(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 entry. + * * @param key the key. * @return an Entry with least key greater than the given key, or - * null if there is no such Entry. + * null if there is no such Entry. * @throws ClassCastException if key cannot be compared with the keys * currently in the map. * @throws NullPointerException if key is null and this map @@ -96,48 +150,99 @@ public interface NavigableMap exten public 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 the given key, or + * null if there is no such key. + * @throws ClassCastException if key cannot be compared with the keys + * currently in the map. + * @throws NullPointerException if key is null and this map + * does not support null keys. + */ + public 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 least key, or null + * key in this map, or null if the map is empty. + * + * @return an Entry with least key, or null * if the map is empty. */ public 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 greatest key, or null + * key in this map, or null if the map is empty. + * + * @return an Entry with greatest key, or null * if the map is empty. */ public 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 + * the least key in this map, or null if the map is empty. + * + * @return the removed first entry of this map, or null * if the map is empty. */ public 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 + * the greatest key in this map, or null if the map is empty. + * + * @return the removed last entry of this map, or null * if the map is empty. */ public Map.Entry pollLastEntry(); /** + * Returns a set view of the keys contained in this map, 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), + * 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. + */ + Set descendingKeySet(); + + /** + * Returns a set view of the mappings contained in this map, in + * descending key order. Each element in the returned set is a + * Map.Entry. 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. + */ + 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 sorted map * is empty.) The returned sorted map is backed by this map, so changes * in the returned sorted map are reflected in this map, and vice-versa. - + * * @param fromKey low endpoint (inclusive) of the subMap. * @param toKey high endpoint (exclusive) of the subMap. * @@ -160,7 +265,7 @@ public interface NavigableMap exten * Returns a view of the portion of this map whose keys are strictly less * than toKey. The returned sorted map is backed by this map, so * changes in the returned sorted map are reflected in this map, and - * vice-versa. + * vice-versa. * @param toKey high endpoint (exclusive) of the headMap. * @return a view of the portion of this map whose keys are strictly * less than toKey. @@ -187,5 +292,5 @@ public interface NavigableMap exten * @throws NullPointerException if fromKey is null * and this map does not support null keys. */ - public NavigableMap tailMap(K fromKey); + public NavigableMap tailMap(K fromKey); }