1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.  Sun designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Sun in the LICENSE file that accompanied this code.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  21  * CA 95054 USA or visit www.sun.com if you need additional information or
  22  * have any questions.
  23  */
  24 
  25 /*
  26  * This file is available under and governed by the GNU General Public
  27  * License version 2 only, as published by the Free Software Foundation.
  28  * However, the following notice accompanied the original version of this
  29  * file:
  30  *
  31  * Written by Doug Lea and Josh Bloch with assistance from members of JCP
  32  * JSR-166 Expert Group and released to the public domain, as explained at
  33  * http://creativecommons.org/licenses/publicdomain
  34  */
  35 
  36 package java.util;
  37 
  38 /**
  39  * A {@link SortedMap} extended with navigation methods returning the
  40  * closest matches for given search targets. Methods
  41  * {@code lowerEntry}, {@code floorEntry}, {@code ceilingEntry},
  42  * and {@code higherEntry} return {@code Map.Entry} objects
  43  * associated with keys respectively less than, less than or equal,
  44  * greater than or equal, and greater than a given key, returning
  45  * {@code null} if there is no such key.  Similarly, methods
  46  * {@code lowerKey}, {@code floorKey}, {@code ceilingKey}, and
  47  * {@code higherKey} return only the associated keys. All of these
  48  * methods are designed for locating, not traversing entries.
  49  *
  50  * <p>A {@code NavigableMap} may be accessed and traversed in either
  51  * ascending or descending key order.  The {@code descendingMap}
  52  * method returns a view of the map with the senses of all relational
  53  * and directional methods inverted. The performance of ascending
  54  * operations and views is likely to be faster than that of descending
  55  * ones.  Methods {@code subMap}, {@code headMap},
  56  * and {@code tailMap} differ from the like-named {@code
  57  * SortedMap} methods in accepting additional arguments describing
  58  * whether lower and upper bounds are inclusive versus exclusive.
  59  * Submaps of any {@code NavigableMap} must implement the {@code
  60  * NavigableMap} interface.
  61  *
  62  * <p>This interface additionally defines methods {@code firstEntry},
  63  * {@code pollFirstEntry}, {@code lastEntry}, and
  64  * {@code pollLastEntry} that return and/or remove the least and
  65  * greatest mappings, if any exist, else returning {@code null}.
  66  *
  67  * <p>Implementations of entry-returning methods are expected to
  68  * return {@code Map.Entry} pairs representing snapshots of mappings
  69  * at the time they were produced, and thus generally do <em>not</em>
  70  * support the optional {@code Entry.setValue} method. Note however
  71  * that it is possible to change mappings in the associated map using
  72  * method {@code put}.
  73  *
  74  * <p>Methods
  75  * {@link #subMap(Object, Object) subMap(K, K)},
  76  * {@link #headMap(Object) headMap(K)}, and
  77  * {@link #tailMap(Object) tailMap(K)}
  78  * are specified to return {@code SortedMap} to allow existing
  79  * implementations of {@code SortedMap} to be compatibly retrofitted to
  80  * implement {@code NavigableMap}, but extensions and implementations
  81  * of this interface are encouraged to override these methods to return
  82  * {@code NavigableMap}.  Similarly,
  83  * {@link #keySet()} can be overriden to return {@code NavigableSet}.
  84  *
  85  * <p>This interface is a member of the
  86  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  87  * Java Collections Framework</a>.
  88  *
  89  * @author Doug Lea
  90  * @author Josh Bloch
  91  * @param <K> the type of keys maintained by this map
  92  * @param <V> the type of mapped values
  93  * @since 1.6
  94  */
  95 public interface NavigableMap<K,V> extends SortedMap<K,V> {
  96     /**
  97      * Returns a key-value mapping associated with the greatest key
  98      * strictly less than the given key, or {@code null} if there is
  99      * no such key.
 100      *
 101      * @param key the key
 102      * @return an entry with the greatest key less than {@code key},
 103      *         or {@code null} if there is no such key
 104      * @throws ClassCastException if the specified key cannot be compared
 105      *         with the keys currently in the map
 106      * @throws NullPointerException if the specified key is null
 107      *         and this map does not permit null keys
 108      */
 109     Map.Entry<K,V> lowerEntry(K key);
 110 
 111     /**
 112      * Returns the greatest key strictly less than the given key, or
 113      * {@code null} if there is no such key.
 114      *
 115      * @param key the key
 116      * @return the greatest key less than {@code key},
 117      *         or {@code null} if there is no such key
 118      * @throws ClassCastException if the specified key cannot be compared
 119      *         with the keys currently in the map
 120      * @throws NullPointerException if the specified key is null
 121      *         and this map does not permit null keys
 122      */
 123     K lowerKey(K key);
 124 
 125     /**
 126      * Returns a key-value mapping associated with the greatest key
 127      * less than or equal to the given key, or {@code null} if there
 128      * is no such key.
 129      *
 130      * @param key the key
 131      * @return an entry with the greatest key less than or equal to
 132      *         {@code key}, or {@code null} if there is no such key
 133      * @throws ClassCastException if the specified key cannot be compared
 134      *         with the keys currently in the map
 135      * @throws NullPointerException if the specified key is null
 136      *         and this map does not permit null keys
 137      */
 138     Map.Entry<K,V> floorEntry(K key);
 139 
 140     /**
 141      * Returns the greatest key less than or equal to the given key,
 142      * or {@code null} if there is no such key.
 143      *
 144      * @param key the key
 145      * @return the greatest key less than or equal to {@code key},
 146      *         or {@code null} if there is no such key
 147      * @throws ClassCastException if the specified key cannot be compared
 148      *         with the keys currently in the map
 149      * @throws NullPointerException if the specified key is null
 150      *         and this map does not permit null keys
 151      */
 152     K floorKey(K key);
 153 
 154     /**
 155      * Returns a key-value mapping associated with the least key
 156      * greater than or equal to the given key, or {@code null} if
 157      * there is no such key.
 158      *
 159      * @param key the key
 160      * @return an entry with the least key greater than or equal to
 161      *         {@code key}, or {@code null} if there is no such key
 162      * @throws ClassCastException if the specified key cannot be compared
 163      *         with the keys currently in the map
 164      * @throws NullPointerException if the specified key is null
 165      *         and this map does not permit null keys
 166      */
 167     Map.Entry<K,V> ceilingEntry(K key);
 168 
 169     /**
 170      * Returns the least key greater than or equal to the given key,
 171      * or {@code null} if there is no such key.
 172      *
 173      * @param key the key
 174      * @return the least key greater than or equal to {@code key},
 175      *         or {@code null} if there is no such key
 176      * @throws ClassCastException if the specified key cannot be compared
 177      *         with the keys currently in the map
 178      * @throws NullPointerException if the specified key is null
 179      *         and this map does not permit null keys
 180      */
 181     K ceilingKey(K key);
 182 
 183     /**
 184      * Returns a key-value mapping associated with the least key
 185      * strictly greater than the given key, or {@code null} if there
 186      * is no such key.
 187      *
 188      * @param key the key
 189      * @return an entry with the least key greater than {@code key},
 190      *         or {@code null} if there is no such key
 191      * @throws ClassCastException if the specified key cannot be compared
 192      *         with the keys currently in the map
 193      * @throws NullPointerException if the specified key is null
 194      *         and this map does not permit null keys
 195      */
 196     Map.Entry<K,V> higherEntry(K key);
 197 
 198     /**
 199      * Returns the least key strictly greater than the given key, or
 200      * {@code null} if there is no such key.
 201      *
 202      * @param key the key
 203      * @return the least key greater than {@code key},
 204      *         or {@code null} if there is no such key
 205      * @throws ClassCastException if the specified key cannot be compared
 206      *         with the keys currently in the map
 207      * @throws NullPointerException if the specified key is null
 208      *         and this map does not permit null keys
 209      */
 210     K higherKey(K key);
 211 
 212     /**
 213      * Returns a key-value mapping associated with the least
 214      * key in this map, or {@code null} if the map is empty.
 215      *
 216      * @return an entry with the least key,
 217      *         or {@code null} if this map is empty
 218      */
 219     Map.Entry<K,V> firstEntry();
 220 
 221     /**
 222      * Returns a key-value mapping associated with the greatest
 223      * key in this map, or {@code null} if the map is empty.
 224      *
 225      * @return an entry with the greatest key,
 226      *         or {@code null} if this map is empty
 227      */
 228     Map.Entry<K,V> lastEntry();
 229 
 230     /**
 231      * Removes and returns a key-value mapping associated with
 232      * the least key in this map, or {@code null} if the map is empty.
 233      *
 234      * @return the removed first entry of this map,
 235      *         or {@code null} if this map is empty
 236      */
 237     Map.Entry<K,V> pollFirstEntry();
 238 
 239     /**
 240      * Removes and returns a key-value mapping associated with
 241      * the greatest key in this map, or {@code null} if the map is empty.
 242      *
 243      * @return the removed last entry of this map,
 244      *         or {@code null} if this map is empty
 245      */
 246     Map.Entry<K,V> pollLastEntry();
 247 
 248     /**
 249      * Returns a reverse order view of the mappings contained in this map.
 250      * The descending map is backed by this map, so changes to the map are
 251      * reflected in the descending map, and vice-versa.  If either map is
 252      * modified while an iteration over a collection view of either map
 253      * is in progress (except through the iterator's own {@code remove}
 254      * operation), the results of the iteration are undefined.
 255      *
 256      * <p>The returned map has an ordering equivalent to
 257      * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
 258      * The expression {@code m.descendingMap().descendingMap()} returns a
 259      * view of {@code m} essentially equivalent to {@code m}.
 260      *
 261      * @return a reverse order view of this map
 262      */
 263     NavigableMap<K,V> descendingMap();
 264 
 265     /**
 266      * Returns a {@link NavigableSet} view of the keys contained in this map.
 267      * The set's iterator returns the keys in ascending order.
 268      * The set is backed by the map, so changes to the map are reflected in
 269      * the set, and vice-versa.  If the map is modified while an iteration
 270      * over the set is in progress (except through the iterator's own {@code
 271      * remove} operation), the results of the iteration are undefined.  The
 272      * set supports element removal, which removes the corresponding mapping
 273      * from the map, via the {@code Iterator.remove}, {@code Set.remove},
 274      * {@code removeAll}, {@code retainAll}, and {@code clear} operations.
 275      * It does not support the {@code add} or {@code addAll} operations.
 276      *
 277      * @return a navigable set view of the keys in this map
 278      */
 279     NavigableSet<K> navigableKeySet();
 280 
 281     /**
 282      * Returns a reverse order {@link NavigableSet} view of the keys contained in this map.
 283      * The set's iterator returns the keys in descending order.
 284      * The set is backed by the map, so changes to the map are reflected in
 285      * the set, and vice-versa.  If the map is modified while an iteration
 286      * over the set is in progress (except through the iterator's own {@code
 287      * remove} operation), the results of the iteration are undefined.  The
 288      * set supports element removal, which removes the corresponding mapping
 289      * from the map, via the {@code Iterator.remove}, {@code Set.remove},
 290      * {@code removeAll}, {@code retainAll}, and {@code clear} operations.
 291      * It does not support the {@code add} or {@code addAll} operations.
 292      *
 293      * @return a reverse order navigable set view of the keys in this map
 294      */
 295     NavigableSet<K> descendingKeySet();
 296 
 297     /**
 298      * Returns a view of the portion of this map whose keys range from
 299      * {@code fromKey} to {@code toKey}.  If {@code fromKey} and
 300      * {@code toKey} are equal, the returned map is empty unless
 301      * {@code fromInclusive} and {@code toInclusive} are both true.  The
 302      * returned map is backed by this map, so changes in the returned map are
 303      * reflected in this map, and vice-versa.  The returned map supports all
 304      * optional map operations that this map supports.
 305      *
 306      * <p>The returned map will throw an {@code IllegalArgumentException}
 307      * on an attempt to insert a key outside of its range, or to construct a
 308      * submap either of whose endpoints lie outside its range.
 309      *
 310      * @param fromKey low endpoint of the keys in the returned map
 311      * @param fromInclusive {@code true} if the low endpoint
 312      *        is to be included in the returned view
 313      * @param toKey high endpoint of the keys in the returned map
 314      * @param toInclusive {@code true} if the high endpoint
 315      *        is to be included in the returned view
 316      * @return a view of the portion of this map whose keys range from
 317      *         {@code fromKey} to {@code toKey}
 318      * @throws ClassCastException if {@code fromKey} and {@code toKey}
 319      *         cannot be compared to one another using this map's comparator
 320      *         (or, if the map has no comparator, using natural ordering).
 321      *         Implementations may, but are not required to, throw this
 322      *         exception if {@code fromKey} or {@code toKey}
 323      *         cannot be compared to keys currently in the map.
 324      * @throws NullPointerException if {@code fromKey} or {@code toKey}
 325      *         is null and this map does not permit null keys
 326      * @throws IllegalArgumentException if {@code fromKey} is greater than
 327      *         {@code toKey}; or if this map itself has a restricted
 328      *         range, and {@code fromKey} or {@code toKey} lies
 329      *         outside the bounds of the range
 330      */
 331     NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
 332                              K toKey,   boolean toInclusive);
 333 
 334     /**
 335      * Returns a view of the portion of this map whose keys are less than (or
 336      * equal to, if {@code inclusive} is true) {@code toKey}.  The returned
 337      * map is backed by this map, so changes in the returned map are reflected
 338      * in this map, and vice-versa.  The returned map supports all optional
 339      * map operations that this map supports.
 340      *
 341      * <p>The returned map will throw an {@code IllegalArgumentException}
 342      * on an attempt to insert a key outside its range.
 343      *
 344      * @param toKey high endpoint of the keys in the returned map
 345      * @param inclusive {@code true} if the high endpoint
 346      *        is to be included in the returned view
 347      * @return a view of the portion of this map whose keys are less than
 348      *         (or equal to, if {@code inclusive} is true) {@code toKey}
 349      * @throws ClassCastException if {@code toKey} is not compatible
 350      *         with this map's comparator (or, if the map has no comparator,
 351      *         if {@code toKey} does not implement {@link Comparable}).
 352      *         Implementations may, but are not required to, throw this
 353      *         exception if {@code toKey} cannot be compared to keys
 354      *         currently in the map.
 355      * @throws NullPointerException if {@code toKey} is null
 356      *         and this map does not permit null keys
 357      * @throws IllegalArgumentException if this map itself has a
 358      *         restricted range, and {@code toKey} lies outside the
 359      *         bounds of the range
 360      */
 361     NavigableMap<K,V> headMap(K toKey, boolean inclusive);
 362 
 363     /**
 364      * Returns a view of the portion of this map whose keys are greater than (or
 365      * equal to, if {@code inclusive} is true) {@code fromKey}.  The returned
 366      * map is backed by this map, so changes in the returned map are reflected
 367      * in this map, and vice-versa.  The returned map supports all optional
 368      * map operations that this map supports.
 369      *
 370      * <p>The returned map will throw an {@code IllegalArgumentException}
 371      * on an attempt to insert a key outside its range.
 372      *
 373      * @param fromKey low endpoint of the keys in the returned map
 374      * @param inclusive {@code true} if the low endpoint
 375      *        is to be included in the returned view
 376      * @return a view of the portion of this map whose keys are greater than
 377      *         (or equal to, if {@code inclusive} is true) {@code fromKey}
 378      * @throws ClassCastException if {@code fromKey} is not compatible
 379      *         with this map's comparator (or, if the map has no comparator,
 380      *         if {@code fromKey} does not implement {@link Comparable}).
 381      *         Implementations may, but are not required to, throw this
 382      *         exception if {@code fromKey} cannot be compared to keys
 383      *         currently in the map.
 384      * @throws NullPointerException if {@code fromKey} is null
 385      *         and this map does not permit null keys
 386      * @throws IllegalArgumentException if this map itself has a
 387      *         restricted range, and {@code fromKey} lies outside the
 388      *         bounds of the range
 389      */
 390     NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
 391 
 392     /**
 393      * {@inheritDoc}
 394      *
 395      * <p>Equivalent to {@code subMap(fromKey, true, toKey, false)}.
 396      *
 397      * @throws ClassCastException       {@inheritDoc}
 398      * @throws NullPointerException     {@inheritDoc}
 399      * @throws IllegalArgumentException {@inheritDoc}
 400      */
 401     SortedMap<K,V> subMap(K fromKey, K toKey);
 402 
 403     /**
 404      * {@inheritDoc}
 405      *
 406      * <p>Equivalent to {@code headMap(toKey, false)}.
 407      *
 408      * @throws ClassCastException       {@inheritDoc}
 409      * @throws NullPointerException     {@inheritDoc}
 410      * @throws IllegalArgumentException {@inheritDoc}
 411      */
 412     SortedMap<K,V> headMap(K toKey);
 413 
 414     /**
 415      * {@inheritDoc}
 416      *
 417      * <p>Equivalent to {@code tailMap(fromKey, true)}.
 418      *
 419      * @throws ClassCastException       {@inheritDoc}
 420      * @throws NullPointerException     {@inheritDoc}
 421      * @throws IllegalArgumentException {@inheritDoc}
 422      */
 423     SortedMap<K,V> tailMap(K fromKey);
 424 }