GNU Classpath (0.98) | |
Frames | No Frames |
1: /* 2: * Written by Doug Lea and Josh Bloch with assistance from members of JCP 3: * JSR-166 Expert Group and released to the public domain, as explained at 4: * http://creativecommons.org/licenses/publicdomain 5: */ 6: 7: package java.util; 8: 9: /** 10: * A {@link SortedMap} extended with navigation methods returning the 11: * closest matches for given search targets. Methods 12: * {@code lowerEntry}, {@code floorEntry}, {@code ceilingEntry}, 13: * and {@code higherEntry} return {@code Map.Entry} objects 14: * associated with keys respectively less than, less than or equal, 15: * greater than or equal, and greater than a given key, returning 16: * {@code null} if there is no such key. Similarly, methods 17: * {@code lowerKey}, {@code floorKey}, {@code ceilingKey}, and 18: * {@code higherKey} return only the associated keys. All of these 19: * methods are designed for locating, not traversing entries. 20: * 21: * <p>A {@code NavigableMap} may be accessed and traversed in either 22: * ascending or descending key order. The {@code descendingMap} 23: * method returns a view of the map with the senses of all relational 24: * and directional methods inverted. The performance of ascending 25: * operations and views is likely to be faster than that of descending 26: * ones. Methods {@code subMap}, {@code headMap}, 27: * and {@code tailMap} differ from the like-named {@code 28: * SortedMap} methods in accepting additional arguments describing 29: * whether lower and upper bounds are inclusive versus exclusive. 30: * Submaps of any {@code NavigableMap} must implement the {@code 31: * NavigableMap} interface. 32: * 33: * <p>This interface additionally defines methods {@code firstEntry}, 34: * {@code pollFirstEntry}, {@code lastEntry}, and 35: * {@code pollLastEntry} that return and/or remove the least and 36: * greatest mappings, if any exist, else returning {@code null}. 37: * 38: * <p>Implementations of entry-returning methods are expected to 39: * return {@code Map.Entry} pairs representing snapshots of mappings 40: * at the time they were produced, and thus generally do <em>not</em> 41: * support the optional {@code Entry.setValue} method. Note however 42: * that it is possible to change mappings in the associated map using 43: * method {@code put}. 44: * 45: * <p>Methods 46: * {@link #subMap(Object, Object) subMap(K, K)}, 47: * {@link #headMap(Object) headMap(K)}, and 48: * {@link #tailMap(Object) tailMap(K)} 49: * are specified to return {@code SortedMap} to allow existing 50: * implementations of {@code SortedMap} to be compatibly retrofitted to 51: * implement {@code NavigableMap}, but extensions and implementations 52: * of this interface are encouraged to override these methods to return 53: * {@code NavigableMap}. Similarly, 54: * {@link #keySet()} can be overriden to return {@code NavigableSet}. 55: * 56: * <p>This interface is a member of the 57: * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 58: * Java Collections Framework</a>. 59: * 60: * @author Doug Lea 61: * @author Josh Bloch 62: * @param <K> the type of keys maintained by this map 63: * @param <V> the type of mapped values 64: * @since 1.6 65: */ 66: public interface NavigableMap<K,V> extends SortedMap<K,V> { 67: /** 68: * Returns a key-value mapping associated with the greatest key 69: * strictly less than the given key, or {@code null} if there is 70: * no such key. 71: * 72: * @param key the key 73: * @return an entry with the greatest key less than {@code key}, 74: * or {@code null} if there is no such key 75: * @throws ClassCastException if the specified key cannot be compared 76: * with the keys currently in the map 77: * @throws NullPointerException if the specified key is null 78: * and this map does not permit null keys 79: */ 80: Map.Entry<K,V> lowerEntry(K key); 81: 82: /** 83: * Returns the greatest key strictly less than the given key, or 84: * {@code null} if there is no such key. 85: * 86: * @param key the key 87: * @return the greatest key less than {@code key}, 88: * or {@code null} if there is no such key 89: * @throws ClassCastException if the specified key cannot be compared 90: * with the keys currently in the map 91: * @throws NullPointerException if the specified key is null 92: * and this map does not permit null keys 93: */ 94: K lowerKey(K key); 95: 96: /** 97: * Returns a key-value mapping associated with the greatest key 98: * less than or equal to the given key, or {@code null} if there 99: * is no such key. 100: * 101: * @param key the key 102: * @return an entry with the greatest key less than or equal to 103: * {@code key}, 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> floorEntry(K key); 110: 111: /** 112: * Returns the greatest key less than or equal to the given key, 113: * or {@code null} if there is no such key. 114: * 115: * @param key the key 116: * @return the greatest key less than or equal to {@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 floorKey(K key); 124: 125: /** 126: * Returns a key-value mapping associated with the least key 127: * greater than or equal to the given key, or {@code null} if 128: * there is no such key. 129: * 130: * @param key the key 131: * @return an entry with the least key greater 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> ceilingEntry(K key); 139: 140: /** 141: * Returns the least key greater 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 least key greater 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 ceilingKey(K key); 153: 154: /** 155: * Returns a key-value mapping associated with the least key 156: * strictly greater than the given key, or {@code null} if there 157: * is no such key. 158: * 159: * @param key the key 160: * @return an entry with the least key greater than {@code key}, 161: * 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> higherEntry(K key); 168: 169: /** 170: * Returns the least key strictly greater than the given key, or 171: * {@code null} if there is no such key. 172: * 173: * @param key the key 174: * @return the least key greater than {@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 higherKey(K key); 182: 183: /** 184: * Returns a key-value mapping associated with the least 185: * key in this map, or {@code null} if the map is empty. 186: * 187: * @return an entry with the least key, 188: * or {@code null} if this map is empty 189: */ 190: Map.Entry<K,V> firstEntry(); 191: 192: /** 193: * Returns a key-value mapping associated with the greatest 194: * key in this map, or {@code null} if the map is empty. 195: * 196: * @return an entry with the greatest key, 197: * or {@code null} if this map is empty 198: */ 199: Map.Entry<K,V> lastEntry(); 200: 201: /** 202: * Removes and returns a key-value mapping associated with 203: * the least key in this map, or {@code null} if the map is empty. 204: * 205: * @return the removed first entry of this map, 206: * or {@code null} if this map is empty 207: */ 208: Map.Entry<K,V> pollFirstEntry(); 209: 210: /** 211: * Removes and returns a key-value mapping associated with 212: * the greatest key in this map, or {@code null} if the map is empty. 213: * 214: * @return the removed last entry of this map, 215: * or {@code null} if this map is empty 216: */ 217: Map.Entry<K,V> pollLastEntry(); 218: 219: /** 220: * Returns a reverse order view of the mappings contained in this map. 221: * The descending map is backed by this map, so changes to the map are 222: * reflected in the descending map, and vice-versa. If either map is 223: * modified while an iteration over a collection view of either map 224: * is in progress (except through the iterator's own {@code remove} 225: * operation), the results of the iteration are undefined. 226: * 227: * <p>The returned map has an ordering equivalent to 228: * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>. 229: * The expression {@code m.descendingMap().descendingMap()} returns a 230: * view of {@code m} essentially equivalent to {@code m}. 231: * 232: * @return a reverse order view of this map 233: */ 234: NavigableMap<K,V> descendingMap(); 235: 236: /** 237: * Returns a {@link NavigableSet} view of the keys contained in this map. 238: * The set's iterator returns the keys in ascending order. 239: * The set is backed by the map, so changes to the map are reflected in 240: * the set, and vice-versa. If the map is modified while an iteration 241: * over the set is in progress (except through the iterator's own {@code 242: * remove} operation), the results of the iteration are undefined. The 243: * set supports element removal, which removes the corresponding mapping 244: * from the map, via the {@code Iterator.remove}, {@code Set.remove}, 245: * {@code removeAll}, {@code retainAll}, and {@code clear} operations. 246: * It does not support the {@code add} or {@code addAll} operations. 247: * 248: * @return a navigable set view of the keys in this map 249: */ 250: NavigableSet<K> navigableKeySet(); 251: 252: /** 253: * Returns a reverse order {@link NavigableSet} view of the keys contained in this map. 254: * The set's iterator returns the keys in descending order. 255: * The set is backed by the map, so changes to the map are reflected in 256: * the set, and vice-versa. If the map is modified while an iteration 257: * over the set is in progress (except through the iterator's own {@code 258: * remove} operation), the results of the iteration are undefined. The 259: * set supports element removal, which removes the corresponding mapping 260: * from the map, via the {@code Iterator.remove}, {@code Set.remove}, 261: * {@code removeAll}, {@code retainAll}, and {@code clear} operations. 262: * It does not support the {@code add} or {@code addAll} operations. 263: * 264: * @return a reverse order navigable set view of the keys in this map 265: */ 266: NavigableSet<K> descendingKeySet(); 267: 268: /** 269: * Returns a view of the portion of this map whose keys range from 270: * {@code fromKey} to {@code toKey}. If {@code fromKey} and 271: * {@code toKey} are equal, the returned map is empty unless 272: * {@code fromExclusive} and {@code toExclusive} are both true. The 273: * returned map is backed by this map, so changes in the returned map are 274: * reflected in this map, and vice-versa. The returned map supports all 275: * optional map operations that this map supports. 276: * 277: * <p>The returned map will throw an {@code IllegalArgumentException} 278: * on an attempt to insert a key outside of its range, or to construct a 279: * submap either of whose endpoints lie outside its range. 280: * 281: * @param fromKey low endpoint of the keys in the returned map 282: * @param fromInclusive {@code true} if the low endpoint 283: * is to be included in the returned view 284: * @param toKey high endpoint of the keys in the returned map 285: * @param toInclusive {@code true} if the high endpoint 286: * is to be included in the returned view 287: * @return a view of the portion of this map whose keys range from 288: * {@code fromKey} to {@code toKey} 289: * @throws ClassCastException if {@code fromKey} and {@code toKey} 290: * cannot be compared to one another using this map's comparator 291: * (or, if the map has no comparator, using natural ordering). 292: * Implementations may, but are not required to, throw this 293: * exception if {@code fromKey} or {@code toKey} 294: * cannot be compared to keys currently in the map. 295: * @throws NullPointerException if {@code fromKey} or {@code toKey} 296: * is null and this map does not permit null keys 297: * @throws IllegalArgumentException if {@code fromKey} is greater than 298: * {@code toKey}; or if this map itself has a restricted 299: * range, and {@code fromKey} or {@code toKey} lies 300: * outside the bounds of the range 301: */ 302: NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, 303: K toKey, boolean toInclusive); 304: 305: /** 306: * Returns a view of the portion of this map whose keys are less than (or 307: * equal to, if {@code inclusive} is true) {@code toKey}. The returned 308: * map is backed by this map, so changes in the returned map are reflected 309: * in this map, and vice-versa. The returned map supports all optional 310: * map operations that this map supports. 311: * 312: * <p>The returned map will throw an {@code IllegalArgumentException} 313: * on an attempt to insert a key outside its range. 314: * 315: * @param toKey high endpoint of the keys in the returned map 316: * @param inclusive {@code true} if the high endpoint 317: * is to be included in the returned view 318: * @return a view of the portion of this map whose keys are less than 319: * (or equal to, if {@code inclusive} is true) {@code toKey} 320: * @throws ClassCastException if {@code toKey} is not compatible 321: * with this map's comparator (or, if the map has no comparator, 322: * if {@code toKey} does not implement {@link Comparable}). 323: * Implementations may, but are not required to, throw this 324: * exception if {@code toKey} cannot be compared to keys 325: * currently in the map. 326: * @throws NullPointerException if {@code toKey} is null 327: * and this map does not permit null keys 328: * @throws IllegalArgumentException if this map itself has a 329: * restricted range, and {@code toKey} lies outside the 330: * bounds of the range 331: */ 332: NavigableMap<K,V> headMap(K toKey, boolean inclusive); 333: 334: /** 335: * Returns a view of the portion of this map whose keys are greater than (or 336: * equal to, if {@code inclusive} is true) {@code fromKey}. 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 fromKey low endpoint of the keys in the returned map 345: * @param inclusive {@code true} if the low endpoint 346: * is to be included in the returned view 347: * @return a view of the portion of this map whose keys are greater than 348: * (or equal to, if {@code inclusive} is true) {@code fromKey} 349: * @throws ClassCastException if {@code fromKey} is not compatible 350: * with this map's comparator (or, if the map has no comparator, 351: * if {@code fromKey} does not implement {@link Comparable}). 352: * Implementations may, but are not required to, throw this 353: * exception if {@code fromKey} cannot be compared to keys 354: * currently in the map. 355: * @throws NullPointerException if {@code fromKey} 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 fromKey} lies outside the 359: * bounds of the range 360: */ 361: NavigableMap<K,V> tailMap(K fromKey, boolean inclusive); 362: 363: /** 364: * {@inheritDoc} 365: * 366: * <p>Equivalent to {@code subMap(fromKey, true, toKey, false)}. 367: * 368: * @throws ClassCastException {@inheritDoc} 369: * @throws NullPointerException {@inheritDoc} 370: * @throws IllegalArgumentException {@inheritDoc} 371: */ 372: SortedMap<K,V> subMap(K fromKey, K toKey); 373: 374: /** 375: * {@inheritDoc} 376: * 377: * <p>Equivalent to {@code headMap(toKey, false)}. 378: * 379: * @throws ClassCastException {@inheritDoc} 380: * @throws NullPointerException {@inheritDoc} 381: * @throws IllegalArgumentException {@inheritDoc} 382: */ 383: SortedMap<K,V> headMap(K toKey); 384: 385: /** 386: * {@inheritDoc} 387: * 388: * <p>Equivalent to {@code tailMap(fromKey, true)}. 389: * 390: * @throws ClassCastException {@inheritDoc} 391: * @throws NullPointerException {@inheritDoc} 392: * @throws IllegalArgumentException {@inheritDoc} 393: */ 394: SortedMap<K,V> tailMap(K fromKey); 395: }
GNU Classpath (0.98) |