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. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * 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/publicdomain/zero/1.0/ 34 */ 35 36 package java.util; 37 38 // BEGIN android-note 39 // removed link to collections framework docs 40 // END android-note 41 42 /** 43 * A {@link SortedMap} extended with navigation methods returning the 44 * closest matches for given search targets. Methods 45 * {@link #lowerEntry}, {@link #floorEntry}, {@link #ceilingEntry}, 46 * and {@link #higherEntry} return {@code Map.Entry} objects 47 * associated with keys respectively less than, less than or equal, 48 * greater than or equal, and greater than a given key, returning 49 * {@code null} if there is no such key. Similarly, methods 50 * {@link #lowerKey}, {@link #floorKey}, {@link #ceilingKey}, and 51 * {@link #higherKey} return only the associated keys. All of these 52 * methods are designed for locating, not traversing entries. 53 * 54 * <p>A {@code NavigableMap} may be accessed and traversed in either 55 * ascending or descending key order. The {@link #descendingMap} 56 * method returns a view of the map with the senses of all relational 57 * and directional methods inverted. The performance of ascending 58 * operations and views is likely to be faster than that of descending 59 * ones. Methods 60 * {@link #subMap(Object, boolean, Object, boolean) subMap(K, boolean, K, boolean)}, 61 * {@link #headMap(Object, boolean) headMap(K, boolean)}, and 62 * {@link #tailMap(Object, boolean) tailMap(K, boolean)} 63 * differ from the like-named {@code SortedMap} methods in accepting 64 * additional arguments describing whether lower and upper bounds are 65 * inclusive versus exclusive. Submaps of any {@code NavigableMap} 66 * must implement the {@code NavigableMap} interface. 67 * 68 * <p>This interface additionally defines methods {@link #firstEntry}, 69 * {@link #pollFirstEntry}, {@link #lastEntry}, and 70 * {@link #pollLastEntry} that return and/or remove the least and 71 * greatest mappings, if any exist, else returning {@code null}. 72 * 73 * <p>The methods 74 * {@link #ceilingEntry}, 75 * {@link #firstEntry}, 76 * {@link #floorEntry}, 77 * {@link #higherEntry}, 78 * {@link #lastEntry}, 79 * {@link #lowerEntry}, 80 * {@link #pollFirstEntry}, and 81 * {@link #pollLastEntry} 82 * return {@link Map.Entry} instances that represent snapshots of mappings as 83 * of the time of the call. They do <em>not</em> support mutation of the 84 * underlying map via the optional {@link Map.Entry#setValue setValue} method. 85 * 86 * <p>Methods 87 * {@link #subMap(Object, Object) subMap(K, K)}, 88 * {@link #headMap(Object) headMap(K)}, and 89 * {@link #tailMap(Object) tailMap(K)} 90 * are specified to return {@code SortedMap} to allow existing 91 * implementations of {@code SortedMap} to be compatibly retrofitted to 92 * implement {@code NavigableMap}, but extensions and implementations 93 * of this interface are encouraged to override these methods to return 94 * {@code NavigableMap}. Similarly, 95 * {@link #keySet()} can be overridden to return {@link NavigableSet}. 96 * 97 * @author Doug Lea 98 * @author Josh Bloch 99 * @param <K> the type of keys maintained by this map 100 * @param <V> the type of mapped values 101 * @since 1.6 102 */ 103 public interface NavigableMap<K,V> extends SortedMap<K,V> { 104 /** 105 * Returns a key-value mapping associated with the greatest key 106 * strictly less than the given key, or {@code null} if there is 107 * no such key. 108 * 109 * @param key the key 110 * @return an entry with the greatest key less than {@code key}, 111 * or {@code null} if there is no such key 112 * @throws ClassCastException if the specified key cannot be compared 113 * with the keys currently in the map 114 * @throws NullPointerException if the specified key is null 115 * and this map does not permit null keys 116 */ lowerEntry(K key)117 Map.Entry<K,V> lowerEntry(K key); 118 119 /** 120 * Returns the greatest key strictly less than the given key, or 121 * {@code null} if there is no such key. 122 * 123 * @param key the key 124 * @return the greatest key less than {@code key}, 125 * or {@code null} if there is no such key 126 * @throws ClassCastException if the specified key cannot be compared 127 * with the keys currently in the map 128 * @throws NullPointerException if the specified key is null 129 * and this map does not permit null keys 130 */ lowerKey(K key)131 K lowerKey(K key); 132 133 /** 134 * Returns a key-value mapping associated with the greatest key 135 * less than or equal to the given key, or {@code null} if there 136 * is no such key. 137 * 138 * @param key the key 139 * @return an entry with the greatest key less than or equal to 140 * {@code key}, or {@code null} if there is no such key 141 * @throws ClassCastException if the specified key cannot be compared 142 * with the keys currently in the map 143 * @throws NullPointerException if the specified key is null 144 * and this map does not permit null keys 145 */ floorEntry(K key)146 Map.Entry<K,V> floorEntry(K key); 147 148 /** 149 * Returns the greatest key less than or equal to the given key, 150 * or {@code null} if there is no such key. 151 * 152 * @param key the key 153 * @return the greatest key less than or equal to {@code key}, 154 * or {@code null} if there is no such key 155 * @throws ClassCastException if the specified key cannot be compared 156 * with the keys currently in the map 157 * @throws NullPointerException if the specified key is null 158 * and this map does not permit null keys 159 */ floorKey(K key)160 K floorKey(K key); 161 162 /** 163 * Returns a key-value mapping associated with the least key 164 * greater than or equal to the given key, or {@code null} if 165 * there is no such key. 166 * 167 * @param key the key 168 * @return an entry with the least key greater than or equal to 169 * {@code key}, or {@code null} if there is no such key 170 * @throws ClassCastException if the specified key cannot be compared 171 * with the keys currently in the map 172 * @throws NullPointerException if the specified key is null 173 * and this map does not permit null keys 174 */ ceilingEntry(K key)175 Map.Entry<K,V> ceilingEntry(K key); 176 177 /** 178 * Returns the least key greater than or equal to the given key, 179 * or {@code null} if there is no such key. 180 * 181 * @param key the key 182 * @return the least key greater than or equal to {@code key}, 183 * or {@code null} if there is no such key 184 * @throws ClassCastException if the specified key cannot be compared 185 * with the keys currently in the map 186 * @throws NullPointerException if the specified key is null 187 * and this map does not permit null keys 188 */ ceilingKey(K key)189 K ceilingKey(K key); 190 191 /** 192 * Returns a key-value mapping associated with the least key 193 * strictly greater than the given key, or {@code null} if there 194 * is no such key. 195 * 196 * @param key the key 197 * @return an entry with the least key greater than {@code key}, 198 * or {@code null} if there is no such key 199 * @throws ClassCastException if the specified key cannot be compared 200 * with the keys currently in the map 201 * @throws NullPointerException if the specified key is null 202 * and this map does not permit null keys 203 */ higherEntry(K key)204 Map.Entry<K,V> higherEntry(K key); 205 206 /** 207 * Returns the least key strictly greater than the given key, or 208 * {@code null} if there is no such key. 209 * 210 * @param key the key 211 * @return the least key greater than {@code key}, 212 * or {@code null} if there is no such key 213 * @throws ClassCastException if the specified key cannot be compared 214 * with the keys currently in the map 215 * @throws NullPointerException if the specified key is null 216 * and this map does not permit null keys 217 */ higherKey(K key)218 K higherKey(K key); 219 220 /** 221 * Returns a key-value mapping associated with the least 222 * key in this map, or {@code null} if the map is empty. 223 * 224 * @return an entry with the least key, 225 * or {@code null} if this map is empty 226 */ firstEntry()227 Map.Entry<K,V> firstEntry(); 228 229 /** 230 * Returns a key-value mapping associated with the greatest 231 * key in this map, or {@code null} if the map is empty. 232 * 233 * @return an entry with the greatest key, 234 * or {@code null} if this map is empty 235 */ lastEntry()236 Map.Entry<K,V> lastEntry(); 237 238 /** 239 * Removes and returns a key-value mapping associated with 240 * the least key in this map, or {@code null} if the map is empty. 241 * 242 * @return the removed first entry of this map, 243 * or {@code null} if this map is empty 244 */ pollFirstEntry()245 Map.Entry<K,V> pollFirstEntry(); 246 247 /** 248 * Removes and returns a key-value mapping associated with 249 * the greatest key in this map, or {@code null} if the map is empty. 250 * 251 * @return the removed last entry of this map, 252 * or {@code null} if this map is empty 253 */ pollLastEntry()254 Map.Entry<K,V> pollLastEntry(); 255 256 /** 257 * Returns a reverse order view of the mappings contained in this map. 258 * The descending map is backed by this map, so changes to the map are 259 * reflected in the descending map, and vice-versa. If either map is 260 * modified while an iteration over a collection view of either map 261 * is in progress (except through the iterator's own {@code remove} 262 * operation), the results of the iteration are undefined. 263 * 264 * <p>The returned map has an ordering equivalent to 265 * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}. 266 * The expression {@code m.descendingMap().descendingMap()} returns a 267 * view of {@code m} essentially equivalent to {@code m}. 268 * 269 * @return a reverse order view of this map 270 */ descendingMap()271 NavigableMap<K,V> descendingMap(); 272 273 /** 274 * Returns a {@link NavigableSet} view of the keys contained in this map. 275 * The set's iterator returns the keys in ascending order. 276 * The set is backed by the map, so changes to the map are reflected in 277 * the set, and vice-versa. If the map is modified while an iteration 278 * over the set is in progress (except through the iterator's own {@code 279 * remove} operation), the results of the iteration are undefined. The 280 * set supports element removal, which removes the corresponding mapping 281 * from the map, via the {@code Iterator.remove}, {@code Set.remove}, 282 * {@code removeAll}, {@code retainAll}, and {@code clear} operations. 283 * It does not support the {@code add} or {@code addAll} operations. 284 * 285 * @return a navigable set view of the keys in this map 286 */ navigableKeySet()287 NavigableSet<K> navigableKeySet(); 288 289 /** 290 * Returns a reverse order {@link NavigableSet} view of the keys contained in this map. 291 * The set's iterator returns the keys in descending order. 292 * The set is backed by the map, so changes to the map are reflected in 293 * the set, and vice-versa. If the map is modified while an iteration 294 * over the set is in progress (except through the iterator's own {@code 295 * remove} operation), the results of the iteration are undefined. The 296 * set supports element removal, which removes the corresponding mapping 297 * from the map, via the {@code Iterator.remove}, {@code Set.remove}, 298 * {@code removeAll}, {@code retainAll}, and {@code clear} operations. 299 * It does not support the {@code add} or {@code addAll} operations. 300 * 301 * @return a reverse order navigable set view of the keys in this map 302 */ descendingKeySet()303 NavigableSet<K> descendingKeySet(); 304 305 /** 306 * Returns a view of the portion of this map whose keys range from 307 * {@code fromKey} to {@code toKey}. If {@code fromKey} and 308 * {@code toKey} are equal, the returned map is empty unless 309 * {@code fromInclusive} and {@code toInclusive} are both true. The 310 * returned map is backed by this map, so changes in the returned map are 311 * reflected in this map, and vice-versa. The returned map supports all 312 * optional map operations that this map supports. 313 * 314 * <p>The returned map will throw an {@code IllegalArgumentException} 315 * on an attempt to insert a key outside of its range, or to construct a 316 * submap either of whose endpoints lie outside its range. 317 * 318 * @param fromKey low endpoint of the keys in the returned map 319 * @param fromInclusive {@code true} if the low endpoint 320 * is to be included in the returned view 321 * @param toKey high endpoint of the keys in the returned map 322 * @param toInclusive {@code true} if the high endpoint 323 * is to be included in the returned view 324 * @return a view of the portion of this map whose keys range from 325 * {@code fromKey} to {@code toKey} 326 * @throws ClassCastException if {@code fromKey} and {@code toKey} 327 * cannot be compared to one another using this map's comparator 328 * (or, if the map has no comparator, using natural ordering). 329 * Implementations may, but are not required to, throw this 330 * exception if {@code fromKey} or {@code toKey} 331 * cannot be compared to keys currently in the map. 332 * @throws NullPointerException if {@code fromKey} or {@code toKey} 333 * is null and this map does not permit null keys 334 * @throws IllegalArgumentException if {@code fromKey} is greater than 335 * {@code toKey}; or if this map itself has a restricted 336 * range, and {@code fromKey} or {@code toKey} lies 337 * outside the bounds of the range 338 */ subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)339 NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, 340 K toKey, boolean toInclusive); 341 342 /** 343 * Returns a view of the portion of this map whose keys are less than (or 344 * equal to, if {@code inclusive} is true) {@code toKey}. The returned 345 * map is backed by this map, so changes in the returned map are reflected 346 * in this map, and vice-versa. The returned map supports all optional 347 * map operations that this map supports. 348 * 349 * <p>The returned map will throw an {@code IllegalArgumentException} 350 * on an attempt to insert a key outside its range. 351 * 352 * @param toKey high endpoint of the keys in the returned map 353 * @param inclusive {@code true} if the high endpoint 354 * is to be included in the returned view 355 * @return a view of the portion of this map whose keys are less than 356 * (or equal to, if {@code inclusive} is true) {@code toKey} 357 * @throws ClassCastException if {@code toKey} is not compatible 358 * with this map's comparator (or, if the map has no comparator, 359 * if {@code toKey} does not implement {@link Comparable}). 360 * Implementations may, but are not required to, throw this 361 * exception if {@code toKey} cannot be compared to keys 362 * currently in the map. 363 * @throws NullPointerException if {@code toKey} is null 364 * and this map does not permit null keys 365 * @throws IllegalArgumentException if this map itself has a 366 * restricted range, and {@code toKey} lies outside the 367 * bounds of the range 368 */ headMap(K toKey, boolean inclusive)369 NavigableMap<K,V> headMap(K toKey, boolean inclusive); 370 371 /** 372 * Returns a view of the portion of this map whose keys are greater than (or 373 * equal to, if {@code inclusive} is true) {@code fromKey}. The returned 374 * map is backed by this map, so changes in the returned map are reflected 375 * in this map, and vice-versa. The returned map supports all optional 376 * map operations that this map supports. 377 * 378 * <p>The returned map will throw an {@code IllegalArgumentException} 379 * on an attempt to insert a key outside its range. 380 * 381 * @param fromKey low endpoint of the keys in the returned map 382 * @param inclusive {@code true} if the low endpoint 383 * is to be included in the returned view 384 * @return a view of the portion of this map whose keys are greater than 385 * (or equal to, if {@code inclusive} is true) {@code fromKey} 386 * @throws ClassCastException if {@code fromKey} is not compatible 387 * with this map's comparator (or, if the map has no comparator, 388 * if {@code fromKey} does not implement {@link Comparable}). 389 * Implementations may, but are not required to, throw this 390 * exception if {@code fromKey} cannot be compared to keys 391 * currently in the map. 392 * @throws NullPointerException if {@code fromKey} is null 393 * and this map does not permit null keys 394 * @throws IllegalArgumentException if this map itself has a 395 * restricted range, and {@code fromKey} lies outside the 396 * bounds of the range 397 */ tailMap(K fromKey, boolean inclusive)398 NavigableMap<K,V> tailMap(K fromKey, boolean inclusive); 399 400 /** 401 * {@inheritDoc} 402 * 403 * <p>Equivalent to {@code subMap(fromKey, true, toKey, false)}. 404 * 405 * @throws ClassCastException {@inheritDoc} 406 * @throws NullPointerException {@inheritDoc} 407 * @throws IllegalArgumentException {@inheritDoc} 408 */ subMap(K fromKey, K toKey)409 SortedMap<K,V> subMap(K fromKey, K toKey); 410 411 /** 412 * {@inheritDoc} 413 * 414 * <p>Equivalent to {@code headMap(toKey, false)}. 415 * 416 * @throws ClassCastException {@inheritDoc} 417 * @throws NullPointerException {@inheritDoc} 418 * @throws IllegalArgumentException {@inheritDoc} 419 */ headMap(K toKey)420 SortedMap<K,V> headMap(K toKey); 421 422 /** 423 * {@inheritDoc} 424 * 425 * <p>Equivalent to {@code tailMap(fromKey, true)}. 426 * 427 * @throws ClassCastException {@inheritDoc} 428 * @throws NullPointerException {@inheritDoc} 429 * @throws IllegalArgumentException {@inheritDoc} 430 */ tailMap(K fromKey)431 SortedMap<K,V> tailMap(K fromKey); 432 433 /** 434 * {@inheritDoc} 435 * <p> 436 * This method is equivalent to {@link #descendingMap descendingMap}. 437 * 438 * @implSpec 439 * The implementation in this interface returns the result of calling the 440 * {@code descendingMap} method. 441 * 442 * @return a reverse-ordered view of this map, as a {@code NavigableMap} 443 * @since 21 444 */ reversed()445 default NavigableMap<K, V> reversed() { 446 return this.descendingMap(); 447 } 448 } 449