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

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8