[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.11 - (view) (download)

1 : dl 1.1 /*
2 :     * Written by Doug Lea with assistance from members of JCP JSR-166
3 :     * Expert Group and released to the public domain, as explained at
4 :     * http://creativecommons.org/licenses/publicdomain
5 :     */
6 :    
7 :     package java.util;
8 : jsr166 1.11 import java.util.*; // for javadoc (till 6280605 is fixed)
9 : dl 1.1
10 :     /**
11 :     * A {@link SortedMap} extended with navigation methods returning the
12 :     * closest matches for given search targets. Methods
13 :     * <tt>lowerEntry</tt>, <tt>floorEntry</tt>, <tt>ceilingEntry</tt>,
14 :     * and <tt>higherEntry</tt> return <tt>Map.Entry</tt> 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 :     * <tt>null</tt> if there is no such key. Similarly, methods
18 :     * <tt>lowerKey</tt>, <tt>floorKey</tt>, <tt>ceilingKey</tt>, and
19 :     * <tt>higherKey</tt> return only the associated keys. All of these
20 :     * methods are designed for locating, not traversing entries.
21 :     *
22 :     * <p>A <tt>NavigableMap</tt> may be viewed and traversed in either
23 :     * ascending or descending key order. The <tt>Map</tt> methods
24 :     * <tt>keySet</tt> and <tt>entrySet</tt> return ascending views, and
25 :     * the additional methods <tt>descendingKeySet</tt> and
26 :     * <tt>descendingEntrySet</tt> return descending views. The
27 :     * performance of ascending traversals is likely to be faster than
28 :     * descending traversals. Notice that it is possible to perform
29 : dl 1.4 * subrange traversals in either direction using <tt>navigableSubMap</tt>.
30 :     * Methods <tt>navigableSubMap</tt>, <tt>navigableHeadMap</tt>, and
31 :     * <tt>navigableTailMap</tt> differ from the similarly named
32 : dl 1.10 * <tt>SortedMap</tt> methods only in their declared return types.
33 : jsr166 1.11 * Submaps of any <tt>NavigableMap<tt> must implement the
34 :     * <tt>NavigableMap</tt> interface.
35 : jsr166 1.5 *
36 : dl 1.1 * <p>This interface additionally defines methods <tt>firstEntry</tt>,
37 :     * <tt>pollFirstEntry</tt>, <tt>lastEntry</tt>, and
38 :     * <tt>pollLastEntry</tt> that return and/or remove the least and
39 :     * greatest mappings, if any exist, else returning <tt>null</tt>.
40 :     *
41 :     * <p> Implementations of entry-returning methods are expected to
42 :     * return <tt>Map.Entry</tt> pairs representing snapshots of mappings
43 :     * at the time they were produced, and thus generally do <em>not</em>
44 :     * support the optional <tt>Entry.setValue</tt> method. Note however
45 :     * that it is possible to change mappings in the associated map using
46 :     * method <tt>put</tt>.
47 :     *
48 : jsr166 1.7 * <p>This interface is a member of the
49 :     * <a href="{@docRoot}/../guide/collections/index.html">
50 :     * Java Collections Framework</a>.
51 :     *
52 : dl 1.1 * @author Doug Lea
53 :     * @param <K> the type of keys maintained by this map
54 : jsr166 1.5 * @param <V> the type of mapped values
55 : jsr166 1.6 * @since 1.6
56 : dl 1.1 */
57 :     public interface NavigableMap<K,V> extends SortedMap<K,V> {
58 :     /**
59 : jsr166 1.8 * Returns a key-value mapping associated with the greatest key
60 :     * strictly less than the given key, or <tt>null</tt> if there is
61 :     * no such key.
62 : jsr166 1.5 *
63 : jsr166 1.8 * @param key the key
64 :     * @return an entry with the greatest key less than <tt>key</tt>,
65 :     * or <tt>null</tt> if there is no such key
66 :     * @throws ClassCastException if the specified key cannot be compared
67 :     * with the keys currently in the map
68 :     * @throws NullPointerException if the specified key is null
69 :     * and this map does not permit null keys
70 : dl 1.1 */
71 : jsr166 1.8 Map.Entry<K,V> lowerEntry(K key);
72 : dl 1.1
73 :     /**
74 : jsr166 1.8 * Returns the greatest key strictly less than the given key, or
75 : dl 1.1 * <tt>null</tt> if there is no such key.
76 : jsr166 1.5 *
77 : jsr166 1.8 * @param key the key
78 :     * @return the greatest key less than <tt>key</tt>,
79 :     * or <tt>null</tt> if there is no such key
80 :     * @throws ClassCastException if the specified key cannot be compared
81 :     * with the keys currently in the map
82 :     * @throws NullPointerException if the specified key is null
83 :     * and this map does not permit null keys
84 : dl 1.1 */
85 : jsr166 1.8 K lowerKey(K key);
86 : dl 1.1
87 :     /**
88 : jsr166 1.8 * Returns a key-value mapping associated with the greatest key
89 :     * less than or equal to the given key, or <tt>null</tt> if there
90 :     * is no such key.
91 : jsr166 1.5 *
92 : jsr166 1.8 * @param key the key
93 :     * @return an entry with the greatest key less than or equal to
94 :     * <tt>key</tt>, or <tt>null</tt> if there is no such key
95 :     * @throws ClassCastException if the specified key cannot be compared
96 :     * with the keys currently in the map
97 :     * @throws NullPointerException if the specified key is null
98 :     * and this map does not permit null keys
99 : dl 1.1 */
100 : jsr166 1.8 Map.Entry<K,V> floorEntry(K key);
101 : dl 1.1
102 :     /**
103 : jsr166 1.8 * Returns the greatest key less than or equal to the given key,
104 :     * or <tt>null</tt> if there is no such key.
105 : jsr166 1.5 *
106 : jsr166 1.8 * @param key the key
107 :     * @return the greatest key less than or equal to <tt>key</tt>,
108 :     * or <tt>null</tt> if there is no such key
109 :     * @throws ClassCastException if the specified key cannot be compared
110 :     * with the keys currently in the map
111 :     * @throws NullPointerException if the specified key is null
112 :     * and this map does not permit null keys
113 : dl 1.1 */
114 : jsr166 1.8 K floorKey(K key);
115 : dl 1.1
116 :     /**
117 : jsr166 1.8 * Returns a key-value mapping associated with the least key
118 :     * greater than or equal to the given key, or <tt>null</tt> if
119 :     * there is no such key.
120 : jsr166 1.5 *
121 : jsr166 1.8 * @param key the key
122 :     * @return an entry with the least key greater than or equal to
123 :     * <tt>key</tt>, or <tt>null</tt> if there is no such key
124 :     * @throws ClassCastException if the specified key cannot be compared
125 :     * with the keys currently in the map
126 :     * @throws NullPointerException if the specified key is null
127 :     * and this map does not permit null keys
128 : dl 1.1 */
129 : jsr166 1.8 Map.Entry<K,V> ceilingEntry(K key);
130 : dl 1.1
131 :     /**
132 : jsr166 1.8 * Returns the least key greater than or equal to the given key,
133 :     * or <tt>null</tt> if there is no such key.
134 : jsr166 1.5 *
135 : jsr166 1.8 * @param key the key
136 :     * @return the least key greater than or equal to <tt>key</tt>,
137 :     * or <tt>null</tt> if there is no such key
138 :     * @throws ClassCastException if the specified key cannot be compared
139 :     * with the keys currently in the map
140 :     * @throws NullPointerException if the specified key is null
141 :     * and this map does not permit null keys
142 : dl 1.1 */
143 : jsr166 1.8 K ceilingKey(K key);
144 : dl 1.1
145 :     /**
146 :     * Returns a key-value mapping associated with the least key
147 :     * strictly greater than the given key, or <tt>null</tt> if there
148 : jsr166 1.8 * is no such key.
149 : jsr166 1.5 *
150 : jsr166 1.8 * @param key the key
151 :     * @return an entry with the least key greater than <tt>key</tt>,
152 :     * or <tt>null</tt> if there is no such key
153 :     * @throws ClassCastException if the specified key cannot be compared
154 :     * with the keys currently in the map
155 :     * @throws NullPointerException if the specified key is null
156 :     * and this map does not permit null keys
157 : dl 1.1 */
158 : dl 1.3 Map.Entry<K,V> higherEntry(K key);
159 : dl 1.1
160 :     /**
161 :     * Returns the least key strictly greater than the given key, or
162 :     * <tt>null</tt> if there is no such key.
163 : jsr166 1.5 *
164 : jsr166 1.8 * @param key the key
165 :     * @return the least key greater than <tt>key</tt>,
166 :     * or <tt>null</tt> if there is no such key
167 :     * @throws ClassCastException if the specified key cannot be compared
168 :     * with the keys currently in the map
169 :     * @throws NullPointerException if the specified key is null
170 :     * and this map does not permit null keys
171 : dl 1.1 */
172 : dl 1.3 K higherKey(K key);
173 : dl 1.1
174 :     /**
175 :     * Returns a key-value mapping associated with the least
176 :     * key in this map, or <tt>null</tt> if the map is empty.
177 : jsr166 1.5 *
178 : jsr166 1.8 * @return an entry with the least key,
179 :     * or <tt>null</tt> if this map is empty
180 : dl 1.1 */
181 : dl 1.3 Map.Entry<K,V> firstEntry();
182 : dl 1.1
183 :     /**
184 :     * Returns a key-value mapping associated with the greatest
185 :     * key in this map, or <tt>null</tt> if the map is empty.
186 : jsr166 1.5 *
187 : jsr166 1.8 * @return an entry with the greatest key,
188 :     * or <tt>null</tt> if this map is empty
189 : dl 1.1 */
190 : dl 1.3 Map.Entry<K,V> lastEntry();
191 : dl 1.1
192 :     /**
193 :     * Removes and returns a key-value mapping associated with
194 :     * the least key in this map, or <tt>null</tt> if the map is empty.
195 : jsr166 1.5 *
196 : jsr166 1.8 * @return the removed first entry of this map,
197 :     * or <tt>null</tt> if this map is empty
198 : dl 1.1 */
199 : dl 1.3 Map.Entry<K,V> pollFirstEntry();
200 : dl 1.1
201 :     /**
202 :     * Removes and returns a key-value mapping associated with
203 :     * the greatest key in this map, or <tt>null</tt> if the map is empty.
204 : jsr166 1.5 *
205 : jsr166 1.8 * @return the removed last entry of this map,
206 :     * or <tt>null</tt> if this map is empty
207 : dl 1.1 */
208 : dl 1.3 Map.Entry<K,V> pollLastEntry();
209 : dl 1.1
210 :     /**
211 : jsr166 1.8 * Returns a {@link Set} view of the keys contained in this map.
212 :     * The set's iterator returns the keys in descending order.
213 :     * The set is backed by the map, so changes to the map are
214 :     * reflected in the set, and vice-versa. If the map is modified
215 :     * while an iteration over the set is in progress (except through
216 :     * the iterator's own <tt>remove</tt> operation), the results of
217 :     * the iteration are undefined. The set supports element removal,
218 :     * which removes the corresponding mapping from the map, via the
219 :     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
220 : jsr166 1.9 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
221 :     * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
222 : dl 1.1 * operations.
223 :     *
224 : jsr166 1.8 * @return a set view of the keys contained in this map, sorted in
225 :     * descending order
226 : dl 1.1 */
227 :     Set<K> descendingKeySet();
228 :    
229 :     /**
230 : jsr166 1.8 * Returns a {@link Set} view of the mappings contained in this map.
231 :     * The set's iterator returns the entries in descending key order.
232 :     * The set is backed by the map, so changes to the map are
233 :     * reflected in the set, and vice-versa. If the map is modified
234 :     * while an iteration over the set is in progress (except through
235 :     * the iterator's own <tt>remove</tt> operation, or through the
236 :     * <tt>setValue</tt> operation on a map entry returned by the
237 :     * iterator) the results of the iteration are undefined. The set
238 :     * supports element removal, which removes the corresponding
239 :     * mapping from the map, via the <tt>Iterator.remove</tt>,
240 :     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
241 :     * <tt>clear</tt> operations. It does not support the
242 :     * <tt>add</tt> or <tt>addAll</tt> operations.
243 : dl 1.1 *
244 : jsr166 1.8 * @return a set view of the mappings contained in this map,
245 :     * sorted in descending key order
246 : dl 1.1 */
247 :     Set<Map.Entry<K, V>> descendingEntrySet();
248 :    
249 :     /**
250 :     * Returns a view of the portion of this map whose keys range from
251 :     * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. (If
252 : jsr166 1.8 * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned map
253 :     * is empty.) The returned map is backed by this map, so changes
254 :     * in the returned map are reflected in this map, and vice-versa.
255 :     * The returned map supports all optional map operations that this
256 :     * map supports.
257 : dl 1.3 *
258 : jsr166 1.8 * <p>The returned map will throw an <tt>IllegalArgumentException</tt>
259 :     * on an attempt to insert a key outside its range.
260 : dl 1.1 *
261 : jsr166 1.8 * @param fromKey low endpoint (inclusive) of the keys in the returned map
262 :     * @param toKey high endpoint (exclusive) of the keys in the returned map
263 : dl 1.1 * @return a view of the portion of this map whose keys range from
264 : jsr166 1.8 * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive
265 :     * @throws ClassCastException if <tt>fromKey</tt> and <tt>toKey</tt>
266 :     * cannot be compared to one another using this map's comparator
267 :     * (or, if the map has no comparator, using natural ordering).
268 :     * Implementations may, but are not required to, throw this
269 :     * exception if <tt>fromKey</tt> or <tt>toKey</tt>
270 :     * cannot be compared to keys currently in the map.
271 :     * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt>
272 :     * is null and this map does not permit null keys
273 :     * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
274 :     * <tt>toKey</tt>; or if this map itself has a restricted
275 :     * range, and <tt>fromKey</tt> or <tt>toKey</tt> lies
276 :     * outside the bounds of the range
277 : dl 1.1 */
278 : dl 1.3 NavigableMap<K,V> navigableSubMap(K fromKey, K toKey);
279 : dl 1.1
280 :     /**
281 : jsr166 1.8 * Returns a view of the portion of this map whose keys are
282 :     * strictly less than <tt>toKey</tt>. The returned map is backed
283 :     * by this map, so changes in the returned map are reflected in
284 :     * this map, and vice-versa. The returned map supports all
285 :     * optional map operations that this map supports.
286 :     *
287 :     * <p>The returned map will throw an <tt>IllegalArgumentException</tt>
288 :     * on an attempt to insert a key outside its range.
289 :     *
290 :     * @param toKey high endpoint (exclusive) of the keys in the returned map
291 : dl 1.1 * @return a view of the portion of this map whose keys are strictly
292 : jsr166 1.8 * less than <tt>toKey</tt>
293 : dl 1.1 * @throws ClassCastException if <tt>toKey</tt> is not compatible
294 :     * with this map's comparator (or, if the map has no comparator,
295 : jsr166 1.8 * if <tt>toKey</tt> does not implement {@link Comparable}).
296 :     * Implementations may, but are not required to, throw this
297 :     * exception if <tt>toKey</tt> cannot be compared to keys
298 :     * currently in the map.
299 :     * @throws NullPointerException if <tt>toKey</tt> is null
300 :     * and this map does not permit null keys
301 :     * @throws IllegalArgumentException if this map itself has a
302 :     * restricted range, and <tt>toKey</tt> lies outside the
303 :     * bounds of the range
304 : dl 1.1 */
305 : dl 1.3 NavigableMap<K,V> navigableHeadMap(K toKey);
306 : dl 1.1
307 :     /**
308 :     * Returns a view of the portion of this map whose keys are
309 : jsr166 1.8 * greater than or equal to <tt>fromKey</tt>. The returned map is
310 :     * backed by this map, so changes in the returned map are
311 :     * reflected in this map, and vice-versa. The returned map
312 :     * supports all optional map operations that this map supports.
313 :     *
314 :     * <p>The returned map will throw an <tt>IllegalArgumentException</tt>
315 :     * on an attempt to insert a key outside its range.
316 :     *
317 :     * @param fromKey low endpoint (inclusive) of the keys in the returned map
318 : dl 1.1 * @return a view of the portion of this map whose keys are greater
319 : jsr166 1.8 * than or equal to <tt>fromKey</tt>
320 : dl 1.1 * @throws ClassCastException if <tt>fromKey</tt> is not compatible
321 :     * with this map's comparator (or, if the map has no comparator,
322 : jsr166 1.8 * if <tt>fromKey</tt> does not implement {@link Comparable}).
323 :     * Implementations may, but are not required to, throw this
324 :     * exception if <tt>fromKey</tt> cannot be compared to keys
325 :     * currently in the map.
326 :     * @throws NullPointerException if <tt>fromKey</tt> is null
327 :     * and this map does not permit null keys
328 :     * @throws IllegalArgumentException if this map itself has a
329 :     * restricted range, and <tt>fromKey</tt> lies outside the
330 :     * bounds of the range
331 : dl 1.1 */
332 : jsr166 1.8 NavigableMap<K,V> navigableTailMap(K fromKey);
333 : dl 1.1 }

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8