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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8