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