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 */ 74 interface NavigableMap(K,V) : SortedMap!(K,V) { 75 /** 76 * Returns a key-value mapping associated with the greatest key 77 * strictly less than the given key, or {@code null} if there is 78 * no such key. 79 * 80 * @param key the key 81 * @return an entry with the greatest key less than {@code key}, 82 * or {@code null} if there is no such key 83 * @throws ClassCastException if the specified key cannot be compared 84 * with the keys currently in the map 85 * @throws NullPointerException if the specified key is null 86 * and this map does not permit null keys 87 */ 88 MapEntry!(K,V) lowerEntry(K key); 89 90 /** 91 * Returns the greatest key strictly less than the given key, or 92 * {@code null} if there is no such key. 93 * 94 * @param key the key 95 * @return the greatest key less than {@code key}, 96 * or {@code null} if there is no such key 97 * @throws ClassCastException if the specified key cannot be compared 98 * with the keys currently in the map 99 * @throws NullPointerException if the specified key is null 100 * and this map does not permit null keys 101 */ 102 K lowerKey(K key); 103 104 /** 105 * Returns a key-value mapping associated with the greatest key 106 * less than or equal to the given key, or {@code null} if there 107 * is no such key. 108 * 109 * @param key the key 110 * @return an entry with the greatest key less than or equal to 111 * {@code key}, 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 */ 117 MapEntry!(K,V) floorEntry(K key); 118 119 /** 120 * Returns the greatest key less than or equal to the given key, 121 * or {@code null} if there is no such key. 122 * 123 * @param key the key 124 * @return the greatest key less than or equal to {@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 */ 131 K floorKey(K key); 132 133 /** 134 * Returns a key-value mapping associated with the least key 135 * greater than or equal to the given key, or {@code null} if 136 * there is no such key. 137 * 138 * @param key the key 139 * @return an entry with the least key greater 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 */ 146 MapEntry!(K,V) ceilingEntry(K key); 147 148 /** 149 * Returns the least key greater 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 least key greater 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 */ 160 K ceilingKey(K key); 161 162 /** 163 * Returns a key-value mapping associated with the least key 164 * strictly greater than the given key, or {@code null} if there 165 * is no such key. 166 * 167 * @param key the key 168 * @return an entry with the least key greater than {@code key}, 169 * 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 */ 175 MapEntry!(K,V) higherEntry(K key); 176 177 /** 178 * Returns the least key strictly greater than the given key, or 179 * {@code null} if there is no such key. 180 * 181 * @param key the key 182 * @return the least key greater than {@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 */ 189 K higherKey(K key); 190 191 /** 192 * Returns a key-value mapping associated with the least 193 * key in this map, or {@code null} if the map is empty. 194 * 195 * @return an entry with the least key, 196 * or {@code null} if this map is empty 197 */ 198 MapEntry!(K,V) firstEntry(); 199 200 /** 201 * Returns a key-value mapping associated with the greatest 202 * key in this map, or {@code null} if the map is empty. 203 * 204 * @return an entry with the greatest key, 205 * or {@code null} if this map is empty 206 */ 207 MapEntry!(K,V) lastEntry(); 208 209 /** 210 * Removes and returns a key-value mapping associated with 211 * the least key in this map, or {@code null} if the map is empty. 212 * 213 * @return the removed first entry of this map, 214 * or {@code null} if this map is empty 215 */ 216 MapEntry!(K,V) pollFirstEntry(); 217 218 /** 219 * Removes and returns a key-value mapping associated with 220 * the greatest key in this map, or {@code null} if the map is empty. 221 * 222 * @return the removed last entry of this map, 223 * or {@code null} if this map is empty 224 */ 225 MapEntry!(K,V) pollLastEntry(); 226 227 /** 228 * Returns a reverse order view of the mappings contained in this map. 229 * The descending map is backed by this map, so changes to the map are 230 * reflected in the descending map, and vice-versa. If either map is 231 * modified while an iteration over a collection view of either map 232 * is in progress (except through the iterator's own {@code remove} 233 * operation), the results of the iteration are undefined. 234 * 235 * <p>The returned map has an ordering equivalent to 236 * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>. 237 * The expression {@code m.descendingMap().descendingMap()} returns a 238 * view of {@code m} essentially equivalent to {@code m}. 239 * 240 * @return a reverse order view of this map 241 */ 242 // NavigableMap!(K,V) descendingMap(); 243 244 /** 245 * Returns a {@link NavigableSet} view of the keys contained in this map. 246 * The set's iterator returns the keys in ascending order. 247 * The set is backed by the map, so changes to the map are reflected in 248 * the set, and vice-versa. If the map is modified while an iteration 249 * over the set is in progress (except through the iterator's own {@code 250 * remove} operation), the results of the iteration are undefined. The 251 * set supports element removal, which removes the corresponding mapping 252 * from the map, via the {@code Iterator.remove}, {@code Set.remove}, 253 * {@code removeAll}, {@code retainAll}, and {@code clear} operations. 254 * It does not support the {@code add} or {@code addAll} operations. 255 * 256 * @return a navigable set view of the keys in this map 257 */ 258 // NavigableSet!K navigableKeySet(); 259 260 /** 261 * Returns a reverse order {@link NavigableSet} view of the keys contained in this map. 262 * The set's iterator returns the keys in descending order. 263 * The set is backed by the map, so changes to the map are reflected in 264 * the set, and vice-versa. If the map is modified while an iteration 265 * over the set is in progress (except through the iterator's own {@code 266 * remove} operation), the results of the iteration are undefined. The 267 * set supports element removal, which removes the corresponding mapping 268 * from the map, via the {@code Iterator.remove}, {@code Set.remove}, 269 * {@code removeAll}, {@code retainAll}, and {@code clear} operations. 270 * It does not support the {@code add} or {@code addAll} operations. 271 * 272 * @return a reverse order navigable set view of the keys in this map 273 */ 274 // NavigableSet!K descendingKeySet(); 275 276 /** 277 * Returns a view of the portion of this map whose keys range from 278 * {@code fromKey} to {@code toKey}. If {@code fromKey} and 279 * {@code toKey} are equal, the returned map is empty unless 280 * {@code fromInclusive} and {@code toInclusive} are both true. The 281 * returned map is backed by this map, so changes in the returned map are 282 * reflected in this map, and vice-versa. The returned map supports all 283 * optional map operations that this map supports. 284 * 285 * <p>The returned map will throw an {@code IllegalArgumentException} 286 * on an attempt to insert a key outside of its range, or to construct a 287 * submap either of whose endpoints lie outside its range. 288 * 289 * @param fromKey low endpoint of the keys in the returned map 290 * @param fromInclusive {@code true} if the low endpoint 291 * is to be included in the returned view 292 * @param toKey high endpoint of the keys in the returned map 293 * @param toInclusive {@code true} if the high endpoint 294 * is to be included in the returned view 295 * @return a view of the portion of this map whose keys range from 296 * {@code fromKey} to {@code toKey} 297 * @throws ClassCastException if {@code fromKey} and {@code toKey} 298 * cannot be compared to one another using this map's comparator 299 * (or, if the map has no comparator, using natural ordering). 300 * Implementations may, but are not required to, throw this 301 * exception if {@code fromKey} or {@code toKey} 302 * cannot be compared to keys currently in the map. 303 * @throws NullPointerException if {@code fromKey} or {@code toKey} 304 * is null and this map does not permit null keys 305 * @throws IllegalArgumentException if {@code fromKey} is greater than 306 * {@code toKey}; or if this map itself has a restricted 307 * range, and {@code fromKey} or {@code toKey} lies 308 * outside the bounds of the range 309 */ 310 NavigableMap!(K,V) subMap(K fromKey, bool fromInclusive, 311 K toKey, bool toInclusive); 312 313 /** 314 * Returns a view of the portion of this map whose keys are less than (or 315 * equal to, if {@code inclusive} is true) {@code toKey}. The returned 316 * map is backed by this map, so changes in the returned map are reflected 317 * in this map, and vice-versa. The returned map supports all optional 318 * map operations that this map supports. 319 * 320 * <p>The returned map will throw an {@code IllegalArgumentException} 321 * on an attempt to insert a key outside its range. 322 * 323 * @param toKey high endpoint of the keys in the returned map 324 * @param inclusive {@code true} if the high endpoint 325 * is to be included in the returned view 326 * @return a view of the portion of this map whose keys are less than 327 * (or equal to, if {@code inclusive} is true) {@code toKey} 328 * @throws ClassCastException if {@code toKey} is not compatible 329 * with this map's comparator (or, if the map has no comparator, 330 * if {@code toKey} does not implement {@link Comparable}). 331 * Implementations may, but are not required to, throw this 332 * exception if {@code toKey} cannot be compared to keys 333 * currently in the map. 334 * @throws NullPointerException if {@code toKey} is null 335 * and this map does not permit null keys 336 * @throws IllegalArgumentException if this map itself has a 337 * restricted range, and {@code toKey} lies outside the 338 * bounds of the range 339 */ 340 NavigableMap!(K,V) headMap(K toKey, bool inclusive); 341 342 /** 343 * Returns a view of the portion of this map whose keys are greater than (or 344 * equal to, if {@code inclusive} is true) {@code fromKey}. 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 fromKey low endpoint of the keys in the returned map 353 * @param inclusive {@code true} if the low endpoint 354 * is to be included in the returned view 355 * @return a view of the portion of this map whose keys are greater than 356 * (or equal to, if {@code inclusive} is true) {@code fromKey} 357 * @throws ClassCastException if {@code fromKey} is not compatible 358 * with this map's comparator (or, if the map has no comparator, 359 * if {@code fromKey} does not implement {@link Comparable}). 360 * Implementations may, but are not required to, throw this 361 * exception if {@code fromKey} cannot be compared to keys 362 * currently in the map. 363 * @throws NullPointerException if {@code fromKey} 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 fromKey} lies outside the 367 * bounds of the range 368 */ 369 NavigableMap!(K,V) tailMap(K fromKey, bool inclusive); 370 371 /** 372 * {@inheritDoc} 373 * 374 * <p>Equivalent to {@code subMap(fromKey, true, toKey, false)}. 375 * 376 * @throws ClassCastException {@inheritDoc} 377 * @throws NullPointerException {@inheritDoc} 378 * @throws IllegalArgumentException {@inheritDoc} 379 */ 380 SortedMap!(K,V) subMap(K fromKey, K toKey); 381 382 /** 383 * {@inheritDoc} 384 * 385 * <p>Equivalent to {@code headMap(toKey, false)}. 386 * 387 * @throws ClassCastException {@inheritDoc} 388 * @throws NullPointerException {@inheritDoc} 389 * @throws IllegalArgumentException {@inheritDoc} 390 */ 391 SortedMap!(K,V) headMap(K toKey); 392 393 /** 394 * {@inheritDoc} 395 * 396 * <p>Equivalent to {@code tailMap(fromKey, true)}. 397 * 398 * @throws ClassCastException {@inheritDoc} 399 * @throws NullPointerException {@inheritDoc} 400 * @throws IllegalArgumentException {@inheritDoc} 401 */ 402 SortedMap!(K,V) tailMap(K fromKey); 403 }