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