[cvs] / jsr166 / src / main / java / util / NavigableMap.java Repository:
ViewVC logotype

Annotation of /jsr166/src/main/java/util/NavigableMap.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.31 - (view) (download)

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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8