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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8