ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/NavigableMap.java
Revision: 1.16
Committed: Thu Apr 20 21:55:42 2006 UTC (18 years ago) by jsr166
Branch: MAIN
Changes since 1.15: +4 -4 lines
Log Message: 
the the

File Contents

# User Rev Content
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     * changes to the map are reflected in the descending set, and vice-versa.
212     * 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     * sorted in descending order
218     */
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     * {@code Set.remove}, {@code removeAll} {@code retainAll}, and
230     * {@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     * the iterator's own <tt>remove</tt> operation), the results of
244     * the iteration are undefined. The set supports element removal,
245     * which removes the corresponding mapping from the map, via the
246     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
247 jsr166 1.9 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
248     * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
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     * @param fromInclusive true if the low endpoint ({@code fromKey}) is
271 jsr166 1.16 * to be included in the returned view
272 dl 1.14 * @param toKey high endpoint of the keys in the returned map
273     * @param toInclusive true if the high endpoint ({@code toKey}) is
274 jsr166 1.16 * 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     * @param inclusive true if the high endpoint ({@code toKey}) is
305 jsr166 1.16 * 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     * @param inclusive true if the low endpoint ({@code fromKey}) is
334 jsr166 1.16 * 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 dl 1.1 }