NavigableMap


1   /*
2    * @(#)NavigableMap.java    1.6 06/05/10
3    *
4    * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   package java.util;
9   
10  /**
11   * A {@link SortedMap} extended with navigation methods returning the
12   * closest matches for given search targets. Methods
13   * {@code lowerEntry}, {@code floorEntry}, {@code ceilingEntry},
14   * and {@code higherEntry} return {@code Map.Entry} 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   * {@code null} if there is no such key.  Similarly, methods
18   * {@code lowerKey}, {@code floorKey}, {@code ceilingKey}, and
19   * {@code higherKey} return only the associated keys. All of these
20   * methods are designed for locating, not traversing entries.
21   *
22   * <p>A {@code NavigableMap} may be accessed and traversed in either
23   * ascending or descending key order.  The {@code descendingMap}
24   * method returns a view of the map with the senses of all relational
25   * and directional methods inverted. The performance of ascending
26   * operations and views is likely to be faster than that of descending
27   * ones.  Methods {@code subMap}, {@code headMap},
28   * and {@code tailMap} differ from the like-named {@code
29   * SortedMap} methods in accepting additional arguments describing
30   * whether lower and upper bounds are inclusive versus exclusive.
31   * Submaps of any {@code NavigableMap} must implement the {@code
32   * NavigableMap} interface.
33   *
34   * <p>This interface additionally defines methods {@code firstEntry},
35   * {@code pollFirstEntry}, {@code lastEntry}, and
36   * {@code pollLastEntry} that return and/or remove the least and
37   * greatest mappings, if any exist, else returning {@code null}.
38   *
39   * <p>Implementations of entry-returning methods are expected to
40   * return {@code Map.Entry} pairs representing snapshots of mappings
41   * at the time they were produced, and thus generally do <em>not</em>
42   * support the optional {@code Entry.setValue} method. Note however
43   * that it is possible to change mappings in the associated map using
44   * method {@code put}.
45   *
46   * <p>Methods
47   * {@link #subMap(Object, Object) subMap(K, K)},
48   * {@link #headMap(Object) headMap(K)}, and
49   * {@link #tailMap(Object) tailMap(K)}
50   * are specified to return {@code SortedMap} to allow existing
51   * implementations of {@code SortedMap} to be compatibly retrofitted to
52   * implement {@code NavigableMap}, but extensions and implementations
53   * of this interface are encouraged to override these methods to return
54   * {@code NavigableMap}.  Similarly,
55   * {@link #keySet()} can be overriden to return {@code NavigableSet}.
56   *
57   * <p>This interface is a member of the
58   * <a HREF="{@docRoot}/../technotes/guides/collections/index.html">
59   * Java Collections Framework</a>.
60   *
61   * @author Doug Lea
62   * @author Josh Bloch
63   * @param <K> the type of keys maintained by this map
64   * @param <V> the type of mapped values
65   * @since 1.6
66   */
67  public interface NavigableMap<K,V> extends SortedMap  <K,V> {
68      /**
69       * Returns a key-value mapping associated with the greatest key
70       * strictly less than the given key, or {@code null} if there is
71       * no such key.
72       *
73       * @param key the key
74       * @return an entry with the greatest key less than {@code key},
75       *         or {@code null} if there is no such key
76       * @throws ClassCastException if the specified key cannot be compared
77       *         with the keys currently in the map
78       * @throws NullPointerException if the specified key is null
79       *         and this map does not permit null keys
80       */
81      Map.Entry  <K,V> lowerEntry(K key);
82  
83      /**
84       * Returns the greatest key strictly less than the given key, or
85       * {@code null} if there is no such key.
86       *
87       * @param key the key
88       * @return the greatest key less than {@code key},
89       *         or {@code null} if there is no such key
90       * @throws ClassCastException if the specified key cannot be compared
91       *         with the keys currently in the map
92       * @throws NullPointerException if the specified key is null
93       *         and this map does not permit null keys
94       */
95      K lowerKey(K key);
96  
97      /**
98       * Returns a key-value mapping associated with the greatest key
99       * less than or equal to the given key, or {@code null} if there
100      * is no such key.
101      *
102      * @param key the key
103      * @return an entry with the greatest key less than or equal to
104      *         {@code key}, or {@code null} if there is no such key
105      * @throws ClassCastException if the specified key cannot be compared
106      *         with the keys currently in the map
107      * @throws NullPointerException if the specified key is null
108      *         and this map does not permit null keys
109      */
110     Map.Entry  <K,V> floorEntry(K key);
111 
112     /**
113      * Returns the greatest key less than or equal to the given key,
114      * or {@code null} if there is no such key.
115      *
116      * @param key the key
117      * @return the greatest key less than or equal to {@code key},
118      *         or {@code null} if there is no such key
119      * @throws ClassCastException if the specified key cannot be compared
120      *         with the keys currently in the map
121      * @throws NullPointerException if the specified key is null
122      *         and this map does not permit null keys
123      */
124     K floorKey(K key);
125 
126     /**
127      * Returns a key-value mapping associated with the least key
128      * greater than or equal to the given key, or {@code null} if
129      * there is no such key.
130      *
131      * @param key the key
132      * @return an entry with the least key greater than or equal to
133      *         {@code key}, or {@code null} if there is no such key
134      * @throws ClassCastException if the specified key cannot be compared
135      *         with the keys currently in the map
136      * @throws NullPointerException if the specified key is null
137      *         and this map does not permit null keys
138      */
139     Map.Entry  <K,V> ceilingEntry(K key);
140 
141     /**
142      * Returns the least key greater than or equal to the given key,
143      * or {@code null} if there is no such key.
144      *
145      * @param key the key
146      * @return the least key greater than or equal to {@code key},
147      *         or {@code null} if there is no such key
148      * @throws ClassCastException if the specified key cannot be compared
149      *         with the keys currently in the map
150      * @throws NullPointerException if the specified key is null
151      *         and this map does not permit null keys
152      */
153     K ceilingKey(K key);
154 
155     /**
156      * Returns a key-value mapping associated with the least key
157      * strictly greater than the given key, or {@code null} if there
158      * is no such key.
159      *
160      * @param key the key
161      * @return an entry with the least key greater than {@code key},
162      *         or {@code null} if there is no such key
163      * @throws ClassCastException if the specified key cannot be compared
164      *         with the keys currently in the map
165      * @throws NullPointerException if the specified key is null
166      *         and this map does not permit null keys
167      */
168     Map.Entry  <K,V> higherEntry(K key);
169 
170     /**
171      * Returns the least key strictly greater than the given key, or
172      * {@code null} if there is no such key.
173      *
174      * @param key the key
175      * @return the least key greater than {@code key},
176      *         or {@code null} if there is no such key
177      * @throws ClassCastException if the specified key cannot be compared
178      *         with the keys currently in the map
179      * @throws NullPointerException if the specified key is null
180      *         and this map does not permit null keys
181      */
182     K higherKey(K key);
183 
184     /**
185      * Returns a key-value mapping associated with the least
186      * key in this map, or {@code null} if the map is empty.
187      *
188      * @return an entry with the least key,
189      *         or {@code null} if this map is empty
190      */
191     Map.Entry  <K,V> firstEntry();
192 
193     /**
194      * Returns a key-value mapping associated with the greatest
195      * key in this map, or {@code null} if the map is empty.
196      *
197      * @return an entry with the greatest key,
198      *         or {@code null} if this map is empty
199      */
200     Map.Entry  <K,V> lastEntry();
201 
202     /**
203      * Removes and returns a key-value mapping associated with
204      * the least key in this map, or {@code null} if the map is empty.
205      *
206      * @return the removed first entry of this map,
207      *         or {@code null} if this map is empty
208      */
209     Map.Entry  <K,V> pollFirstEntry();
210 
211     /**
212      * Removes and returns a key-value mapping associated with
213      * the greatest key in this map, or {@code null} if the map is empty.
214      *
215      * @return the removed last entry of this map,
216      *         or {@code null} if this map is empty
217      */
218     Map.Entry  <K,V> pollLastEntry();
219 
220     /**
221      * Returns a reverse order view of the mappings contained in this map.
222      * The descending map is backed by this map, so changes to the map are
223      * reflected in the descending map, and vice-versa.  If either map is
224      * modified while an iteration over a collection view of either map
225      * is in progress (except through the iterator's own {@code remove}
226      * operation), the results of the iteration are undefined.
227      *
228      * <p>The returned map has an ordering equivalent to
229      * <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
230      * The expression {@code m.descendingMap().descendingMap()} returns a
231      * view of {@code m} essentially equivalent to {@code m}.
232      *
233      * @return a reverse order view of this map
234      */
235     NavigableMap  <K,V> descendingMap();
236 
237     /**
238      * Returns a {@link NavigableSet} view of the keys contained in this map.
239      * The set's iterator returns the keys in ascending order.
240      * The set is backed by the map, so changes to the map are reflected in
241      * the set, and vice-versa.  If the map is modified while an iteration
242      * over the set is in progress (except through the iterator's own {@code
243      * remove} operation), the results of the iteration are undefined.  The
244      * set supports element removal, which removes the corresponding mapping
245      * from the map, via the {@code Iterator.remove}, {@code Set.remove},
246      * {@code removeAll}, {@code retainAll}, and {@code clear} operations.
247      * It does not support the {@code add} or {@code addAll} operations.
248      *
249      * @return a navigable set view of the keys in this map
250      */
251     NavigableSet  <K> navigableKeySet();
252 
253     /**
254      * Returns a reverse order {@link NavigableSet} view of the keys contained in this map.
255      * The set's iterator returns the keys in descending order.
256      * The set is backed by the map, so changes to the map are reflected in
257      * the set, and vice-versa.  If the map is modified while an iteration
258      * over the set is in progress (except through the iterator's own {@code
259      * remove} operation), the results of the iteration are undefined.  The
260      * set supports element removal, which removes the corresponding mapping
261      * from the map, via the {@code Iterator.remove}, {@code Set.remove},
262      * {@code removeAll}, {@code retainAll}, and {@code clear} operations.
263      * It does not support the {@code add} or {@code addAll} operations.
264      *
265      * @return a reverse order navigable set view of the keys in this map
266      */
267     NavigableSet  <K> descendingKeySet();
268 
269     /**
270      * Returns a view of the portion of this map whose keys range from
271      * {@code fromKey} to {@code toKey}.  If {@code fromKey} and
272      * {@code toKey} are equal, the returned map is empty unless
273      * {@code fromExclusive} and {@code toExclusive} are both true.  The
274      * returned map is backed by this map, so changes in the returned map are
275      * reflected in this map, and vice-versa.  The returned map supports all
276      * optional map operations that this map supports.
277      *
278      * <p>The returned map will throw an {@code IllegalArgumentException}
279      * on an attempt to insert a key outside of its range, or to construct a
280      * submap either of whose endpoints lie outside its range.
281      *
282      * @param fromKey low endpoint of the keys in the returned map
283      * @param fromInclusive {@code true} if the low endpoint
284      *        is to be included in the returned view
285      * @param toKey high endpoint of the keys in the returned map
286      * @param toInclusive {@code true} if the high endpoint
287      *        is to be included in the returned view
288      * @return a view of the portion of this map whose keys range from
289      *         {@code fromKey} to {@code toKey}
290      * @throws ClassCastException if {@code fromKey} and {@code toKey}
291      *         cannot be compared to one another using this map's comparator
292      *         (or, if the map has no comparator, using natural ordering).
293      *         Implementations may, but are not required to, throw this
294      *         exception if {@code fromKey} or {@code toKey}
295      *         cannot be compared to keys currently in the map.
296      * @throws NullPointerException if {@code fromKey} or {@code toKey}
297      *         is null and this map does not permit null keys
298      * @throws IllegalArgumentException if {@code fromKey} is greater than
299      *         {@code toKey}; or if this map itself has a restricted
300      *         range, and {@code fromKey} or {@code toKey} lies
301      *         outside the bounds of the range
302      */
303     NavigableMap  <K,V> subMap(K fromKey, boolean fromInclusive,
304                              K toKey,   boolean toInclusive);
305 
306     /**
307      * Returns a view of the portion of this map whose keys are less than (or
308      * equal to, if {@code inclusive} is true) {@code toKey}.  The returned
309      * map is backed by this map, so changes in the returned map are reflected
310      * in this map, and vice-versa.  The returned map supports all optional
311      * map operations that this map supports.
312      *
313      * <p>The returned map will throw an {@code IllegalArgumentException}
314      * on an attempt to insert a key outside its range.
315      *
316      * @param toKey high endpoint of the keys in the returned map
317      * @param inclusive {@code true} if the high endpoint
318      *        is to be included in the returned view
319      * @return a view of the portion of this map whose keys are less than
320      *         (or equal to, if {@code inclusive} is true) {@code toKey}
321      * @throws ClassCastException if {@code toKey} is not compatible
322      *         with this map's comparator (or, if the map has no comparator,
323      *         if {@code toKey} does not implement {@link Comparable}).
324      *         Implementations may, but are not required to, throw this
325      *         exception if {@code toKey} cannot be compared to keys
326      *         currently in the map.
327      * @throws NullPointerException if {@code toKey} is null
328      *         and this map does not permit null keys
329      * @throws IllegalArgumentException if this map itself has a
330      *         restricted range, and {@code toKey} lies outside the
331      *         bounds of the range
332      */
333     NavigableMap  <K,V> headMap(K toKey, boolean inclusive);
334 
335     /**
336      * Returns a view of the portion of this map whose keys are greater than (or
337      * equal to, if {@code inclusive} is true) {@code fromKey}.  The returned
338      * map is backed by this map, so changes in the returned map are reflected
339      * in this map, and vice-versa.  The returned map supports all optional
340      * map operations that this map supports.
341      *
342      * <p>The returned map will throw an {@code IllegalArgumentException}
343      * on an attempt to insert a key outside its range.
344      *
345      * @param fromKey low endpoint of the keys in the returned map
346      * @param inclusive {@code true} if the low endpoint
347      *        is to be included in the returned view
348      * @return a view of the portion of this map whose keys are greater than
349      *         (or equal to, if {@code inclusive} is true) {@code fromKey}
350      * @throws ClassCastException if {@code fromKey} is not compatible
351      *         with this map's comparator (or, if the map has no comparator,
352      *         if {@code fromKey} does not implement {@link Comparable}).
353      *         Implementations may, but are not required to, throw this
354      *         exception if {@code fromKey} cannot be compared to keys
355      *         currently in the map.
356      * @throws NullPointerException if {@code fromKey} is null
357      *         and this map does not permit null keys
358      * @throws IllegalArgumentException if this map itself has a
359      *         restricted range, and {@code fromKey} lies outside the
360      *         bounds of the range
361      */
362     NavigableMap  <K,V> tailMap(K fromKey, boolean inclusive);
363 
364     /**
365      * {@inheritDoc}
366      *
367      * <p>Equivalent to {@code subMap(fromKey, true, toKey, false)}.
368      *
369      * @throws ClassCastException       {@inheritDoc}
370      * @throws NullPointerException     {@inheritDoc}
371      * @throws IllegalArgumentException {@inheritDoc}
372      */
373     SortedMap  <K,V> subMap(K fromKey, K toKey);
374 
375     /**
376      * {@inheritDoc}
377      *
378      * <p>Equivalent to {@code headMap(toKey, false)}.
379      *
380      * @throws ClassCastException       {@inheritDoc}
381      * @throws NullPointerException     {@inheritDoc}
382      * @throws IllegalArgumentException {@inheritDoc}
383      */
384     SortedMap  <K,V> headMap(K toKey);
385 
386     /**
387      * {@inheritDoc}
388      *
389      * <p>Equivalent to {@code tailMap(fromKey, true)}.
390      *
391      * @throws ClassCastException       {@inheritDoc}
392      * @throws NullPointerException     {@inheritDoc}
393      * @throws IllegalArgumentException {@inheritDoc}
394      */
395     SortedMap  <K,V> tailMap(K fromKey);
396 }
397
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags