ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/NavigableMap.java
Revision: 1.7
Committed: Tue May 3 02:52:07 2005 UTC (19 years ago) by jsr166
Branch: MAIN
Changes since 1.6: +4 -0 lines
Log Message: 
Update collections framework pointer

File Contents

# User Rev Content
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 jsr166 1.7 * <p>This interface is a member of the
47     * <a href="{@docRoot}/../guide/collections/index.html">
48     * Java Collections Framework</a>.
49     *
50 dl 1.1 * @author Doug Lea
51     * @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     * Returns a key-value mapping associated with the least key
58     * greater than or equal to the given key, or <tt>null</tt> if there is
59 jsr166 1.5 * no such entry.
60     *
61 dl 1.1 * @param key the key.
62     * @return an Entry associated with ceiling of given key, or <tt>null</tt>
63     * if there is no such Entry.
64     * @throws ClassCastException if key cannot be compared with the keys
65     * currently in the map.
66     * @throws NullPointerException if key is <tt>null</tt> and this map
67     * does not support <tt>null</tt> keys.
68     */
69 dl 1.3 Map.Entry<K,V> ceilingEntry(K key);
70 dl 1.1
71     /**
72     * Returns least key greater than or equal to the given key, or
73     * <tt>null</tt> if there is no such key.
74 jsr166 1.5 *
75 dl 1.1 * @param key the key.
76     * @return the ceiling key, or <tt>null</tt>
77     * if there is no such key.
78     * @throws ClassCastException if key cannot be compared with the keys
79     * currently in the map.
80     * @throws NullPointerException if key is <tt>null</tt> and this map
81     * does not support <tt>null</tt> keys.
82     */
83 dl 1.3 K ceilingKey(K key);
84 dl 1.1
85     /**
86     * Returns a key-value mapping associated with the greatest
87     * key strictly less than the given key, or <tt>null</tt> if there is no
88 jsr166 1.5 * such entry.
89     *
90 dl 1.1 * @param key the key.
91     * @return an Entry with greatest key less than the given
92     * key, or <tt>null</tt> if there is no such Entry.
93     * @throws ClassCastException if key cannot be compared with the keys
94     * currently in the map.
95     * @throws NullPointerException if key is <tt>null</tt> and this map
96     * does not support <tt>null</tt> keys.
97     */
98 dl 1.3 Map.Entry<K,V> lowerEntry(K key);
99 dl 1.1
100     /**
101     * Returns the greatest key strictly less than the given key, or
102     * <tt>null</tt> if there is no such key.
103 jsr166 1.5 *
104 dl 1.1 * @param key the key.
105     * @return the greatest key less than the given
106     * key, or <tt>null</tt> if there is no such key.
107     * @throws ClassCastException if key cannot be compared with the keys
108     * currently in the map.
109     * @throws NullPointerException if key is <tt>null</tt> and this map
110     * does not support <tt>null</tt> keys.
111     */
112 dl 1.3 K lowerKey(K key);
113 dl 1.1
114     /**
115     * Returns a key-value mapping associated with the greatest key
116     * less than or equal to the given key, or <tt>null</tt> if there
117     * is no such entry.
118 jsr166 1.5 *
119 dl 1.1 * @param key the key.
120     * @return an Entry associated with floor of given key, or <tt>null</tt>
121     * if there is no such Entry.
122     * @throws ClassCastException if key cannot be compared with the keys
123     * currently in the map.
124     * @throws NullPointerException if key is <tt>null</tt> and this map
125     * does not support <tt>null</tt> keys.
126     */
127 dl 1.3 Map.Entry<K,V> floorEntry(K key);
128 dl 1.1
129     /**
130     * Returns the greatest key
131     * less than or equal to the given key, or <tt>null</tt> if there
132     * is no such key.
133 jsr166 1.5 *
134 dl 1.1 * @param key the key.
135     * @return the floor of given key, or <tt>null</tt> if there is no
136     * such key.
137     * @throws ClassCastException if key cannot be compared with the keys
138     * currently in the map.
139     * @throws NullPointerException if key is <tt>null</tt> and this map
140     * does not support <tt>null</tt> keys.
141     */
142 dl 1.3 K floorKey(K key);
143 dl 1.1
144     /**
145     * Returns a key-value mapping associated with the least key
146     * strictly greater than the given key, or <tt>null</tt> if there
147     * is no such entry.
148 jsr166 1.5 *
149 dl 1.1 * @param key the key.
150     * @return an Entry with least key greater than the given key, or
151     * <tt>null</tt> if there is no such Entry.
152     * @throws ClassCastException if key cannot be compared with the keys
153     * currently in the map.
154     * @throws NullPointerException if key is <tt>null</tt> and this map
155     * does not support <tt>null</tt> keys.
156     */
157 dl 1.3 Map.Entry<K,V> higherEntry(K key);
158 dl 1.1
159     /**
160     * Returns the least key strictly greater than the given key, or
161     * <tt>null</tt> if there is no such key.
162 jsr166 1.5 *
163 dl 1.1 * @param key the key.
164     * @return the least key greater than the given key, or
165     * <tt>null</tt> if there is no such key.
166     * @throws ClassCastException if key cannot be compared with the keys
167     * currently in the map.
168     * @throws NullPointerException if key is <tt>null</tt> and this map
169     * does not support <tt>null</tt> keys.
170     */
171 dl 1.3 K higherKey(K key);
172 dl 1.1
173     /**
174     * Returns a key-value mapping associated with the least
175     * key in this map, or <tt>null</tt> if the map is empty.
176 jsr166 1.5 *
177     * @return an Entry with least key, or <tt>null</tt>
178 dl 1.1 * if the map is empty.
179     */
180 dl 1.3 Map.Entry<K,V> firstEntry();
181 dl 1.1
182     /**
183     * Returns a key-value mapping associated with the greatest
184     * key in this map, or <tt>null</tt> if the map is empty.
185 jsr166 1.5 *
186 dl 1.1 * @return an Entry with greatest key, or <tt>null</tt>
187     * if the map is empty.
188     */
189 dl 1.3 Map.Entry<K,V> lastEntry();
190 dl 1.1
191     /**
192     * Removes and returns a key-value mapping associated with
193     * the least key in this map, or <tt>null</tt> if the map is empty.
194 jsr166 1.5 *
195 dl 1.1 * @return the removed first entry of this map, or <tt>null</tt>
196     * if the map is empty.
197     */
198 dl 1.3 Map.Entry<K,V> pollFirstEntry();
199 dl 1.1
200     /**
201     * Removes and returns a key-value mapping associated with
202     * the greatest key in this map, or <tt>null</tt> if the map is empty.
203 jsr166 1.5 *
204 dl 1.1 * @return the removed last entry of this map, or <tt>null</tt>
205     * if the map is empty.
206     */
207 dl 1.3 Map.Entry<K,V> pollLastEntry();
208 dl 1.1
209     /**
210     * Returns a set view of the keys contained in this map, in
211     * descending key order. The set is backed by the map, so changes
212     * to the map are reflected in the set, and vice-versa. If the
213     * map is modified while an iteration over the set is in progress
214     * (except through the iterator's own <tt>remove</tt> operation),
215     * the results of the iteration are undefined. The set supports
216     * element removal, which removes the corresponding mapping from
217     * the map, via the <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
218     * <tt>removeAll</tt> <tt>retainAll</tt>, and <tt>clear</tt>
219     * operations. It does not support the add or <tt>addAll</tt>
220     * operations.
221     *
222     * @return a set view of the keys contained in this map.
223     */
224     Set<K> descendingKeySet();
225    
226     /**
227     * Returns a set view of the mappings contained in this map, in
228     * descending key order. Each element in the returned set is a
229     * <tt>Map.Entry</tt>. The set is backed by the map, so changes to
230     * the map are reflected in the set, and vice-versa. If the map
231     * is modified while an iteration over the set is in progress
232     * (except through the iterator's own <tt>remove</tt> operation,
233     * or through the <tt>setValue</tt> operation on a map entry
234     * returned by the iterator) the results of the iteration are
235     * undefined. The set supports element removal, which removes the
236     * corresponding mapping from the map, via the
237     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
238     * <tt>removeAll</tt>, <tt>retainAll</tt> and <tt>clear</tt>
239     * operations. It does not support the <tt>add</tt> or
240     * <tt>addAll</tt> operations.
241     *
242     * @return a set view of the mappings contained in this map.
243     */
244     Set<Map.Entry<K, V>> descendingEntrySet();
245    
246     /**
247     * Returns a view of the portion of this map whose keys range from
248     * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. (If
249 dl 1.3 * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned
250     * navigable map is empty.) The returned navigable map is backed
251     * by this map, so changes in the returned navigable map are
252 jsr166 1.5 * reflected in this map, and vice-versa.
253 dl 1.3 *
254 dl 1.1 * @param fromKey low endpoint (inclusive) of the subMap.
255     * @param toKey high endpoint (exclusive) of the subMap.
256     *
257     * @return a view of the portion of this map whose keys range from
258     * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
259     *
260     * @throws ClassCastException if <tt>fromKey</tt> and
261     * <tt>toKey</tt> cannot be compared to one another using this
262     * map's comparator (or, if the map has no comparator, using
263     * natural ordering).
264     * @throws IllegalArgumentException if <tt>fromKey</tt> is greater
265     * than <tt>toKey</tt>.
266     * @throws NullPointerException if <tt>fromKey</tt> or
267     * <tt>toKey</tt> is <tt>null</tt> and this map does not support
268     * <tt>null</tt> keys.
269     */
270 dl 1.3 NavigableMap<K,V> navigableSubMap(K fromKey, K toKey);
271 dl 1.1
272     /**
273     * Returns a view of the portion of this map whose keys are strictly less
274 dl 1.3 * than <tt>toKey</tt>. The returned navigable map is backed by this map, so
275     * changes in the returned navigable map are reflected in this map, and
276 jsr166 1.5 * vice-versa.
277 dl 1.1 * @param toKey high endpoint (exclusive) of the headMap.
278     * @return a view of the portion of this map whose keys are strictly
279     * less than <tt>toKey</tt>.
280     *
281     * @throws ClassCastException if <tt>toKey</tt> is not compatible
282     * with this map's comparator (or, if the map has no comparator,
283     * if <tt>toKey</tt> does not implement <tt>Comparable</tt>).
284     * @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt>
285     * and this map does not support <tt>null</tt> keys.
286     */
287 dl 1.3 NavigableMap<K,V> navigableHeadMap(K toKey);
288 dl 1.1
289     /**
290     * Returns a view of the portion of this map whose keys are
291 dl 1.3 * greater than or equal to <tt>fromKey</tt>. The returned navigable
292     * map is backed by this map, so changes in the returned navigable
293 dl 1.1 * map are reflected in this map, and vice-versa.
294     * @param fromKey low endpoint (inclusive) of the tailMap.
295     * @return a view of the portion of this map whose keys are greater
296     * than or equal to <tt>fromKey</tt>.
297     * @throws ClassCastException if <tt>fromKey</tt> is not compatible
298     * with this map's comparator (or, if the map has no comparator,
299     * if <tt>fromKey</tt> does not implement <tt>Comparable</tt>).
300     * @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt>
301     * and this map does not support <tt>null</tt> keys.
302     */
303 dl 1.3 NavigableMap<K,V> navigableTailMap(K fromKey);
304 dl 1.1 }