--- jsr166/src/jsr166x/NavigableMap.java 2004/09/07 11:37:57 1.2 +++ jsr166/src/jsr166x/NavigableMap.java 2011/03/15 19:47:02 1.6 @@ -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,37 +9,48 @@ package jsr166x; import java.util.*; /** - * A {@link SortedMap} extended with navigation methods returning - * key-value pairs holding 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. These - * methods are designed for locating, not traversing entries. To - * traverse, use view iterators and/or submap. This interface - * additionally defines methods firstEntry, + * 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 + * 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 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. + *

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. - * + * no such entry. + * * @param key the key. * @return an Entry associated with ceiling of given key, or null * if there is no such Entry. @@ -51,10 +62,24 @@ 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. - * + * 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. @@ -66,10 +91,24 @@ 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 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. @@ -81,10 +120,25 @@ 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. @@ -96,10 +150,24 @@ 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 + * + * @return an Entry with least key, or null * if the map is empty. */ public Map.Entry firstEntry(); @@ -107,7 +175,7 @@ public interface NavigableMap exten /** * 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 * if the map is empty. */ @@ -116,7 +184,7 @@ public interface NavigableMap exten /** * 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 the map is empty. */ @@ -125,13 +193,50 @@ public interface NavigableMap exten /** * 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 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 @@ -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.