1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/emul/compact/src/main/java/java/util/NavigableMap.java Sat Sep 07 13:51:24 2013 +0200
1.3 @@ -0,0 +1,424 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.6 + *
1.7 + * This code is free software; you can redistribute it and/or modify it
1.8 + * under the terms of the GNU General Public License version 2 only, as
1.9 + * published by the Free Software Foundation. Oracle designates this
1.10 + * particular file as subject to the "Classpath" exception as provided
1.11 + * by Oracle in the LICENSE file that accompanied this code.
1.12 + *
1.13 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.14 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.15 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.16 + * version 2 for more details (a copy is included in the LICENSE file that
1.17 + * accompanied this code).
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License version
1.20 + * 2 along with this work; if not, write to the Free Software Foundation,
1.21 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.22 + *
1.23 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.24 + * or visit www.oracle.com if you need additional information or have any
1.25 + * questions.
1.26 + */
1.27 +
1.28 +/*
1.29 + * This file is available under and governed by the GNU General Public
1.30 + * License version 2 only, as published by the Free Software Foundation.
1.31 + * However, the following notice accompanied the original version of this
1.32 + * file:
1.33 + *
1.34 + * Written by Doug Lea and Josh Bloch with assistance from members of JCP
1.35 + * JSR-166 Expert Group and released to the public domain, as explained at
1.36 + * http://creativecommons.org/publicdomain/zero/1.0/
1.37 + */
1.38 +
1.39 +package java.util;
1.40 +
1.41 +/**
1.42 + * A {@link SortedMap} extended with navigation methods returning the
1.43 + * closest matches for given search targets. Methods
1.44 + * {@code lowerEntry}, {@code floorEntry}, {@code ceilingEntry},
1.45 + * and {@code higherEntry} return {@code Map.Entry} objects
1.46 + * associated with keys respectively less than, less than or equal,
1.47 + * greater than or equal, and greater than a given key, returning
1.48 + * {@code null} if there is no such key. Similarly, methods
1.49 + * {@code lowerKey}, {@code floorKey}, {@code ceilingKey}, and
1.50 + * {@code higherKey} return only the associated keys. All of these
1.51 + * methods are designed for locating, not traversing entries.
1.52 + *
1.53 + * <p>A {@code NavigableMap} may be accessed and traversed in either
1.54 + * ascending or descending key order. The {@code descendingMap}
1.55 + * method returns a view of the map with the senses of all relational
1.56 + * and directional methods inverted. The performance of ascending
1.57 + * operations and views is likely to be faster than that of descending
1.58 + * ones. Methods {@code subMap}, {@code headMap},
1.59 + * and {@code tailMap} differ from the like-named {@code
1.60 + * SortedMap} methods in accepting additional arguments describing
1.61 + * whether lower and upper bounds are inclusive versus exclusive.
1.62 + * Submaps of any {@code NavigableMap} must implement the {@code
1.63 + * NavigableMap} interface.
1.64 + *
1.65 + * <p>This interface additionally defines methods {@code firstEntry},
1.66 + * {@code pollFirstEntry}, {@code lastEntry}, and
1.67 + * {@code pollLastEntry} that return and/or remove the least and
1.68 + * greatest mappings, if any exist, else returning {@code null}.
1.69 + *
1.70 + * <p>Implementations of entry-returning methods are expected to
1.71 + * return {@code Map.Entry} pairs representing snapshots of mappings
1.72 + * at the time they were produced, and thus generally do <em>not</em>
1.73 + * support the optional {@code Entry.setValue} method. Note however
1.74 + * that it is possible to change mappings in the associated map using
1.75 + * method {@code put}.
1.76 + *
1.77 + * <p>Methods
1.78 + * {@link #subMap(Object, Object) subMap(K, K)},
1.79 + * {@link #headMap(Object) headMap(K)}, and
1.80 + * {@link #tailMap(Object) tailMap(K)}
1.81 + * are specified to return {@code SortedMap} to allow existing
1.82 + * implementations of {@code SortedMap} to be compatibly retrofitted to
1.83 + * implement {@code NavigableMap}, but extensions and implementations
1.84 + * of this interface are encouraged to override these methods to return
1.85 + * {@code NavigableMap}. Similarly,
1.86 + * {@link #keySet()} can be overriden to return {@code NavigableSet}.
1.87 + *
1.88 + * <p>This interface is a member of the
1.89 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.90 + * Java Collections Framework</a>.
1.91 + *
1.92 + * @author Doug Lea
1.93 + * @author Josh Bloch
1.94 + * @param <K> the type of keys maintained by this map
1.95 + * @param <V> the type of mapped values
1.96 + * @since 1.6
1.97 + */
1.98 +public interface NavigableMap<K,V> extends SortedMap<K,V> {
1.99 + /**
1.100 + * Returns a key-value mapping associated with the greatest key
1.101 + * strictly less than the given key, or {@code null} if there is
1.102 + * no such key.
1.103 + *
1.104 + * @param key the key
1.105 + * @return an entry with the greatest key less than {@code key},
1.106 + * or {@code null} if there is no such key
1.107 + * @throws ClassCastException if the specified key cannot be compared
1.108 + * with the keys currently in the map
1.109 + * @throws NullPointerException if the specified key is null
1.110 + * and this map does not permit null keys
1.111 + */
1.112 + Map.Entry<K,V> lowerEntry(K key);
1.113 +
1.114 + /**
1.115 + * Returns the greatest key strictly less than the given key, or
1.116 + * {@code null} if there is no such key.
1.117 + *
1.118 + * @param key the key
1.119 + * @return the greatest key less than {@code key},
1.120 + * or {@code null} if there is no such key
1.121 + * @throws ClassCastException if the specified key cannot be compared
1.122 + * with the keys currently in the map
1.123 + * @throws NullPointerException if the specified key is null
1.124 + * and this map does not permit null keys
1.125 + */
1.126 + K lowerKey(K key);
1.127 +
1.128 + /**
1.129 + * Returns a key-value mapping associated with the greatest key
1.130 + * less than or equal to the given key, or {@code null} if there
1.131 + * is no such key.
1.132 + *
1.133 + * @param key the key
1.134 + * @return an entry with the greatest key less than or equal to
1.135 + * {@code key}, or {@code null} if there is no such key
1.136 + * @throws ClassCastException if the specified key cannot be compared
1.137 + * with the keys currently in the map
1.138 + * @throws NullPointerException if the specified key is null
1.139 + * and this map does not permit null keys
1.140 + */
1.141 + Map.Entry<K,V> floorEntry(K key);
1.142 +
1.143 + /**
1.144 + * Returns the greatest key less than or equal to the given key,
1.145 + * or {@code null} if there is no such key.
1.146 + *
1.147 + * @param key the key
1.148 + * @return the greatest key less than or equal to {@code key},
1.149 + * or {@code null} if there is no such key
1.150 + * @throws ClassCastException if the specified key cannot be compared
1.151 + * with the keys currently in the map
1.152 + * @throws NullPointerException if the specified key is null
1.153 + * and this map does not permit null keys
1.154 + */
1.155 + K floorKey(K key);
1.156 +
1.157 + /**
1.158 + * Returns a key-value mapping associated with the least key
1.159 + * greater than or equal to the given key, or {@code null} if
1.160 + * there is no such key.
1.161 + *
1.162 + * @param key the key
1.163 + * @return an entry with the least key greater than or equal to
1.164 + * {@code key}, or {@code null} if there is no such key
1.165 + * @throws ClassCastException if the specified key cannot be compared
1.166 + * with the keys currently in the map
1.167 + * @throws NullPointerException if the specified key is null
1.168 + * and this map does not permit null keys
1.169 + */
1.170 + Map.Entry<K,V> ceilingEntry(K key);
1.171 +
1.172 + /**
1.173 + * Returns the least key greater than or equal to the given key,
1.174 + * or {@code null} if there is no such key.
1.175 + *
1.176 + * @param key the key
1.177 + * @return the least key greater than or equal to {@code key},
1.178 + * or {@code null} if there is no such key
1.179 + * @throws ClassCastException if the specified key cannot be compared
1.180 + * with the keys currently in the map
1.181 + * @throws NullPointerException if the specified key is null
1.182 + * and this map does not permit null keys
1.183 + */
1.184 + K ceilingKey(K key);
1.185 +
1.186 + /**
1.187 + * Returns a key-value mapping associated with the least key
1.188 + * strictly greater than the given key, or {@code null} if there
1.189 + * is no such key.
1.190 + *
1.191 + * @param key the key
1.192 + * @return an entry with the least key greater than {@code key},
1.193 + * or {@code null} if there is no such key
1.194 + * @throws ClassCastException if the specified key cannot be compared
1.195 + * with the keys currently in the map
1.196 + * @throws NullPointerException if the specified key is null
1.197 + * and this map does not permit null keys
1.198 + */
1.199 + Map.Entry<K,V> higherEntry(K key);
1.200 +
1.201 + /**
1.202 + * Returns the least key strictly greater than the given key, or
1.203 + * {@code null} if there is no such key.
1.204 + *
1.205 + * @param key the key
1.206 + * @return the least key greater than {@code key},
1.207 + * or {@code null} if there is no such key
1.208 + * @throws ClassCastException if the specified key cannot be compared
1.209 + * with the keys currently in the map
1.210 + * @throws NullPointerException if the specified key is null
1.211 + * and this map does not permit null keys
1.212 + */
1.213 + K higherKey(K key);
1.214 +
1.215 + /**
1.216 + * Returns a key-value mapping associated with the least
1.217 + * key in this map, or {@code null} if the map is empty.
1.218 + *
1.219 + * @return an entry with the least key,
1.220 + * or {@code null} if this map is empty
1.221 + */
1.222 + Map.Entry<K,V> firstEntry();
1.223 +
1.224 + /**
1.225 + * Returns a key-value mapping associated with the greatest
1.226 + * key in this map, or {@code null} if the map is empty.
1.227 + *
1.228 + * @return an entry with the greatest key,
1.229 + * or {@code null} if this map is empty
1.230 + */
1.231 + Map.Entry<K,V> lastEntry();
1.232 +
1.233 + /**
1.234 + * Removes and returns a key-value mapping associated with
1.235 + * the least key in this map, or {@code null} if the map is empty.
1.236 + *
1.237 + * @return the removed first entry of this map,
1.238 + * or {@code null} if this map is empty
1.239 + */
1.240 + Map.Entry<K,V> pollFirstEntry();
1.241 +
1.242 + /**
1.243 + * Removes and returns a key-value mapping associated with
1.244 + * the greatest key in this map, or {@code null} if the map is empty.
1.245 + *
1.246 + * @return the removed last entry of this map,
1.247 + * or {@code null} if this map is empty
1.248 + */
1.249 + Map.Entry<K,V> pollLastEntry();
1.250 +
1.251 + /**
1.252 + * Returns a reverse order view of the mappings contained in this map.
1.253 + * The descending map is backed by this map, so changes to the map are
1.254 + * reflected in the descending map, and vice-versa. If either map is
1.255 + * modified while an iteration over a collection view of either map
1.256 + * is in progress (except through the iterator's own {@code remove}
1.257 + * operation), the results of the iteration are undefined.
1.258 + *
1.259 + * <p>The returned map has an ordering equivalent to
1.260 + * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
1.261 + * The expression {@code m.descendingMap().descendingMap()} returns a
1.262 + * view of {@code m} essentially equivalent to {@code m}.
1.263 + *
1.264 + * @return a reverse order view of this map
1.265 + */
1.266 + NavigableMap<K,V> descendingMap();
1.267 +
1.268 + /**
1.269 + * Returns a {@link NavigableSet} view of the keys contained in this map.
1.270 + * The set's iterator returns the keys in ascending order.
1.271 + * The set is backed by the map, so changes to the map are reflected in
1.272 + * the set, and vice-versa. If the map is modified while an iteration
1.273 + * over the set is in progress (except through the iterator's own {@code
1.274 + * remove} operation), the results of the iteration are undefined. The
1.275 + * set supports element removal, which removes the corresponding mapping
1.276 + * from the map, via the {@code Iterator.remove}, {@code Set.remove},
1.277 + * {@code removeAll}, {@code retainAll}, and {@code clear} operations.
1.278 + * It does not support the {@code add} or {@code addAll} operations.
1.279 + *
1.280 + * @return a navigable set view of the keys in this map
1.281 + */
1.282 + NavigableSet<K> navigableKeySet();
1.283 +
1.284 + /**
1.285 + * Returns a reverse order {@link NavigableSet} view of the keys contained in this map.
1.286 + * The set's iterator returns the keys in descending order.
1.287 + * The set is backed by the map, so changes to the map are reflected in
1.288 + * the set, and vice-versa. If the map is modified while an iteration
1.289 + * over the set is in progress (except through the iterator's own {@code
1.290 + * remove} operation), the results of the iteration are undefined. The
1.291 + * set supports element removal, which removes the corresponding mapping
1.292 + * from the map, via the {@code Iterator.remove}, {@code Set.remove},
1.293 + * {@code removeAll}, {@code retainAll}, and {@code clear} operations.
1.294 + * It does not support the {@code add} or {@code addAll} operations.
1.295 + *
1.296 + * @return a reverse order navigable set view of the keys in this map
1.297 + */
1.298 + NavigableSet<K> descendingKeySet();
1.299 +
1.300 + /**
1.301 + * Returns a view of the portion of this map whose keys range from
1.302 + * {@code fromKey} to {@code toKey}. If {@code fromKey} and
1.303 + * {@code toKey} are equal, the returned map is empty unless
1.304 + * {@code fromInclusive} and {@code toInclusive} are both true. The
1.305 + * returned map is backed by this map, so changes in the returned map are
1.306 + * reflected in this map, and vice-versa. The returned map supports all
1.307 + * optional map operations that this map supports.
1.308 + *
1.309 + * <p>The returned map will throw an {@code IllegalArgumentException}
1.310 + * on an attempt to insert a key outside of its range, or to construct a
1.311 + * submap either of whose endpoints lie outside its range.
1.312 + *
1.313 + * @param fromKey low endpoint of the keys in the returned map
1.314 + * @param fromInclusive {@code true} if the low endpoint
1.315 + * is to be included in the returned view
1.316 + * @param toKey high endpoint of the keys in the returned map
1.317 + * @param toInclusive {@code true} if the high endpoint
1.318 + * is to be included in the returned view
1.319 + * @return a view of the portion of this map whose keys range from
1.320 + * {@code fromKey} to {@code toKey}
1.321 + * @throws ClassCastException if {@code fromKey} and {@code toKey}
1.322 + * cannot be compared to one another using this map's comparator
1.323 + * (or, if the map has no comparator, using natural ordering).
1.324 + * Implementations may, but are not required to, throw this
1.325 + * exception if {@code fromKey} or {@code toKey}
1.326 + * cannot be compared to keys currently in the map.
1.327 + * @throws NullPointerException if {@code fromKey} or {@code toKey}
1.328 + * is null and this map does not permit null keys
1.329 + * @throws IllegalArgumentException if {@code fromKey} is greater than
1.330 + * {@code toKey}; or if this map itself has a restricted
1.331 + * range, and {@code fromKey} or {@code toKey} lies
1.332 + * outside the bounds of the range
1.333 + */
1.334 + NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1.335 + K toKey, boolean toInclusive);
1.336 +
1.337 + /**
1.338 + * Returns a view of the portion of this map whose keys are less than (or
1.339 + * equal to, if {@code inclusive} is true) {@code toKey}. The returned
1.340 + * map is backed by this map, so changes in the returned map are reflected
1.341 + * in this map, and vice-versa. The returned map supports all optional
1.342 + * map operations that this map supports.
1.343 + *
1.344 + * <p>The returned map will throw an {@code IllegalArgumentException}
1.345 + * on an attempt to insert a key outside its range.
1.346 + *
1.347 + * @param toKey high endpoint of the keys in the returned map
1.348 + * @param inclusive {@code true} if the high endpoint
1.349 + * is to be included in the returned view
1.350 + * @return a view of the portion of this map whose keys are less than
1.351 + * (or equal to, if {@code inclusive} is true) {@code toKey}
1.352 + * @throws ClassCastException if {@code toKey} is not compatible
1.353 + * with this map's comparator (or, if the map has no comparator,
1.354 + * if {@code toKey} does not implement {@link Comparable}).
1.355 + * Implementations may, but are not required to, throw this
1.356 + * exception if {@code toKey} cannot be compared to keys
1.357 + * currently in the map.
1.358 + * @throws NullPointerException if {@code toKey} is null
1.359 + * and this map does not permit null keys
1.360 + * @throws IllegalArgumentException if this map itself has a
1.361 + * restricted range, and {@code toKey} lies outside the
1.362 + * bounds of the range
1.363 + */
1.364 + NavigableMap<K,V> headMap(K toKey, boolean inclusive);
1.365 +
1.366 + /**
1.367 + * Returns a view of the portion of this map whose keys are greater than (or
1.368 + * equal to, if {@code inclusive} is true) {@code fromKey}. The returned
1.369 + * map is backed by this map, so changes in the returned map are reflected
1.370 + * in this map, and vice-versa. The returned map supports all optional
1.371 + * map operations that this map supports.
1.372 + *
1.373 + * <p>The returned map will throw an {@code IllegalArgumentException}
1.374 + * on an attempt to insert a key outside its range.
1.375 + *
1.376 + * @param fromKey low endpoint of the keys in the returned map
1.377 + * @param inclusive {@code true} if the low endpoint
1.378 + * is to be included in the returned view
1.379 + * @return a view of the portion of this map whose keys are greater than
1.380 + * (or equal to, if {@code inclusive} is true) {@code fromKey}
1.381 + * @throws ClassCastException if {@code fromKey} is not compatible
1.382 + * with this map's comparator (or, if the map has no comparator,
1.383 + * if {@code fromKey} does not implement {@link Comparable}).
1.384 + * Implementations may, but are not required to, throw this
1.385 + * exception if {@code fromKey} cannot be compared to keys
1.386 + * currently in the map.
1.387 + * @throws NullPointerException if {@code fromKey} is null
1.388 + * and this map does not permit null keys
1.389 + * @throws IllegalArgumentException if this map itself has a
1.390 + * restricted range, and {@code fromKey} lies outside the
1.391 + * bounds of the range
1.392 + */
1.393 + NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
1.394 +
1.395 + /**
1.396 + * {@inheritDoc}
1.397 + *
1.398 + * <p>Equivalent to {@code subMap(fromKey, true, toKey, false)}.
1.399 + *
1.400 + * @throws ClassCastException {@inheritDoc}
1.401 + * @throws NullPointerException {@inheritDoc}
1.402 + * @throws IllegalArgumentException {@inheritDoc}
1.403 + */
1.404 + SortedMap<K,V> subMap(K fromKey, K toKey);
1.405 +
1.406 + /**
1.407 + * {@inheritDoc}
1.408 + *
1.409 + * <p>Equivalent to {@code headMap(toKey, false)}.
1.410 + *
1.411 + * @throws ClassCastException {@inheritDoc}
1.412 + * @throws NullPointerException {@inheritDoc}
1.413 + * @throws IllegalArgumentException {@inheritDoc}
1.414 + */
1.415 + SortedMap<K,V> headMap(K toKey);
1.416 +
1.417 + /**
1.418 + * {@inheritDoc}
1.419 + *
1.420 + * <p>Equivalent to {@code tailMap(fromKey, true)}.
1.421 + *
1.422 + * @throws ClassCastException {@inheritDoc}
1.423 + * @throws NullPointerException {@inheritDoc}
1.424 + * @throws IllegalArgumentException {@inheritDoc}
1.425 + */
1.426 + SortedMap<K,V> tailMap(K fromKey);
1.427 +}