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