1 /*
2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3  *
4  * This code is free software; you can redistribute it and/or modify it
5  * under the terms of the GNU General Public License version 2 only, as
6  * published by the Free Software Foundation.  Oracle designates this
7  * particular file as subject to the "Classpath" exception as provided
8  * by Oracle in the LICENSE file that accompanied this code.
9  *
10  * This code is distributed in the hope that it will be useful, but WITHOUT
11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
13  * version 2 for more details (a copy is included in the LICENSE file that
14  * accompanied this code).
15  *
16  * You should have received a copy of the GNU General Public License version
17  * 2 along with this work; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19  *
20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21  * or visit www.oracle.com if you need additional information or have any
22  * questions.
23  */
24 
25 /*
26  * This file is available under and governed by the GNU General Public
27  * License version 2 only, as published by the Free Software Foundation.
28  * However, the following notice accompanied the original version of this
29  * file:
30  *
31  * Written by Doug Lea and Josh Bloch with assistance from members of JCP
32  * JSR-166 Expert Group and released to the public domain, as explained at
33  * http://creativecommons.org/publicdomain/zero/1.0/
34  */
35 
36 package java.util;
37 
38 // BEGIN android-note
39 // removed link to collections framework docs
40 // END android-note
41 
42 /**
43  * A {@link SortedMap} extended with navigation methods returning the
44  * closest matches for given search targets. Methods
45  * {@link #lowerEntry}, {@link #floorEntry}, {@link #ceilingEntry},
46  * and {@link #higherEntry} return {@code Map.Entry} objects
47  * associated with keys respectively less than, less than or equal,
48  * greater than or equal, and greater than a given key, returning
49  * {@code null} if there is no such key.  Similarly, methods
50  * {@link #lowerKey}, {@link #floorKey}, {@link #ceilingKey}, and
51  * {@link #higherKey} return only the associated keys. All of these
52  * methods are designed for locating, not traversing entries.
53  *
54  * <p>A {@code NavigableMap} may be accessed and traversed in either
55  * ascending or descending key order.  The {@link #descendingMap}
56  * method returns a view of the map with the senses of all relational
57  * and directional methods inverted. The performance of ascending
58  * operations and views is likely to be faster than that of descending
59  * ones.  Methods
60  * {@link #subMap(Object, boolean, Object, boolean) subMap(K, boolean, K, boolean)},
61  * {@link #headMap(Object, boolean) headMap(K, boolean)}, and
62  * {@link #tailMap(Object, boolean) tailMap(K, boolean)}
63  * differ from the like-named {@code SortedMap} methods in accepting
64  * additional arguments describing whether lower and upper bounds are
65  * inclusive versus exclusive.  Submaps of any {@code NavigableMap}
66  * must implement the {@code NavigableMap} interface.
67  *
68  * <p>This interface additionally defines methods {@link #firstEntry},
69  * {@link #pollFirstEntry}, {@link #lastEntry}, and
70  * {@link #pollLastEntry} that return and/or remove the least and
71  * greatest mappings, if any exist, else returning {@code null}.
72  *
73  * <p>Implementations of entry-returning methods are expected to
74  * return {@code Map.Entry} pairs representing snapshots of mappings
75  * at the time they were produced, and thus generally do <em>not</em>
76  * support the optional {@code Entry.setValue} method. Note however
77  * that it is possible to change mappings in the associated map using
78  * method {@code put}.
79  *
80  * <p>Methods
81  * {@link #subMap(Object, Object) subMap(K, K)},
82  * {@link #headMap(Object) headMap(K)}, and
83  * {@link #tailMap(Object) tailMap(K)}
84  * are specified to return {@code SortedMap} to allow existing
85  * implementations of {@code SortedMap} to be compatibly retrofitted to
86  * implement {@code NavigableMap}, but extensions and implementations
87  * of this interface are encouraged to override these methods to return
88  * {@code NavigableMap}.  Similarly,
89  * {@link #keySet()} can be overridden to return {@link NavigableSet}.
90  *
91  * @author Doug Lea
92  * @author Josh Bloch
93  * @param <K> the type of keys maintained by this map
94  * @param <V> the type of mapped values
95  * @since 1.6
96  */
97 public interface NavigableMap<K,V> extends SortedMap<K,V> {
98     /**
99      * Returns a key-value mapping associated with the greatest key
100      * strictly less than the given key, or {@code null} if there is
101      * no such key.
102      *
103      * @param key the key
104      * @return an entry with the greatest key less than {@code key},
105      *         or {@code null} if there is no such key
106      * @throws ClassCastException if the specified key cannot be compared
107      *         with the keys currently in the map
108      * @throws NullPointerException if the specified key is null
109      *         and this map does not permit null keys
110      */
lowerEntry(K key)111     Map.Entry<K,V> lowerEntry(K key);
112 
113     /**
114      * Returns the greatest key strictly less than the given key, or
115      * {@code null} if there is no such key.
116      *
117      * @param key the key
118      * @return the greatest key less than {@code key},
119      *         or {@code null} if there is no such key
120      * @throws ClassCastException if the specified key cannot be compared
121      *         with the keys currently in the map
122      * @throws NullPointerException if the specified key is null
123      *         and this map does not permit null keys
124      */
lowerKey(K key)125     K lowerKey(K key);
126 
127     /**
128      * Returns a key-value mapping associated with the greatest key
129      * less than or equal to the given key, or {@code null} if there
130      * is no such key.
131      *
132      * @param key the key
133      * @return an entry with the greatest key less than or equal to
134      *         {@code key}, or {@code null} if there is no such key
135      * @throws ClassCastException if the specified key cannot be compared
136      *         with the keys currently in the map
137      * @throws NullPointerException if the specified key is null
138      *         and this map does not permit null keys
139      */
floorEntry(K key)140     Map.Entry<K,V> floorEntry(K key);
141 
142     /**
143      * Returns the greatest key less than or equal to the given key,
144      * or {@code null} if there is no such key.
145      *
146      * @param key the key
147      * @return the greatest key less than or equal to {@code key},
148      *         or {@code null} if there is no such key
149      * @throws ClassCastException if the specified key cannot be compared
150      *         with the keys currently in the map
151      * @throws NullPointerException if the specified key is null
152      *         and this map does not permit null keys
153      */
floorKey(K key)154     K floorKey(K key);
155 
156     /**
157      * Returns a key-value mapping associated with the least key
158      * greater than or equal to the given key, or {@code null} if
159      * there is no such key.
160      *
161      * @param key the key
162      * @return an entry with the least key greater than or equal to
163      *         {@code key}, or {@code null} if there is no such key
164      * @throws ClassCastException if the specified key cannot be compared
165      *         with the keys currently in the map
166      * @throws NullPointerException if the specified key is null
167      *         and this map does not permit null keys
168      */
ceilingEntry(K key)169     Map.Entry<K,V> ceilingEntry(K key);
170 
171     /**
172      * Returns the least key greater than or equal to the given key,
173      * or {@code null} if there is no such key.
174      *
175      * @param key the key
176      * @return the least key greater than or equal to {@code key},
177      *         or {@code null} if there is no such key
178      * @throws ClassCastException if the specified key cannot be compared
179      *         with the keys currently in the map
180      * @throws NullPointerException if the specified key is null
181      *         and this map does not permit null keys
182      */
ceilingKey(K key)183     K ceilingKey(K key);
184 
185     /**
186      * Returns a key-value mapping associated with the least key
187      * strictly greater than the given key, or {@code null} if there
188      * is no such key.
189      *
190      * @param key the key
191      * @return an entry with the least key greater than {@code key},
192      *         or {@code null} if there is no such key
193      * @throws ClassCastException if the specified key cannot be compared
194      *         with the keys currently in the map
195      * @throws NullPointerException if the specified key is null
196      *         and this map does not permit null keys
197      */
higherEntry(K key)198     Map.Entry<K,V> higherEntry(K key);
199 
200     /**
201      * Returns the least key strictly greater than the given key, or
202      * {@code null} if there is no such key.
203      *
204      * @param key the key
205      * @return the least key greater than {@code key},
206      *         or {@code null} if there is no such key
207      * @throws ClassCastException if the specified key cannot be compared
208      *         with the keys currently in the map
209      * @throws NullPointerException if the specified key is null
210      *         and this map does not permit null keys
211      */
higherKey(K key)212     K higherKey(K key);
213 
214     /**
215      * Returns a key-value mapping associated with the least
216      * key in this map, or {@code null} if the map is empty.
217      *
218      * @return an entry with the least key,
219      *         or {@code null} if this map is empty
220      */
firstEntry()221     Map.Entry<K,V> firstEntry();
222 
223     /**
224      * Returns a key-value mapping associated with the greatest
225      * key in this map, or {@code null} if the map is empty.
226      *
227      * @return an entry with the greatest key,
228      *         or {@code null} if this map is empty
229      */
lastEntry()230     Map.Entry<K,V> lastEntry();
231 
232     /**
233      * Removes and returns a key-value mapping associated with
234      * the least key in this map, or {@code null} if the map is empty.
235      *
236      * @return the removed first entry of this map,
237      *         or {@code null} if this map is empty
238      */
pollFirstEntry()239     Map.Entry<K,V> pollFirstEntry();
240 
241     /**
242      * Removes and returns a key-value mapping associated with
243      * the greatest key in this map, or {@code null} if the map is empty.
244      *
245      * @return the removed last entry of this map,
246      *         or {@code null} if this map is empty
247      */
pollLastEntry()248     Map.Entry<K,V> pollLastEntry();
249 
250     /**
251      * Returns a reverse order view of the mappings contained in this map.
252      * The descending map is backed by this map, so changes to the map are
253      * reflected in the descending map, and vice-versa.  If either map is
254      * modified while an iteration over a collection view of either map
255      * is in progress (except through the iterator's own {@code remove}
256      * operation), the results of the iteration are undefined.
257      *
258      * <p>The returned map has an ordering equivalent to
259      * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}.
260      * The expression {@code m.descendingMap().descendingMap()} returns a
261      * view of {@code m} essentially equivalent to {@code m}.
262      *
263      * @return a reverse order view of this map
264      */
descendingMap()265     NavigableMap<K,V> descendingMap();
266 
267     /**
268      * Returns a {@link NavigableSet} view of the keys contained in this map.
269      * The set's iterator returns the keys in ascending order.
270      * The set is backed by the map, so changes to the map are reflected in
271      * the set, and vice-versa.  If the map is modified while an iteration
272      * over the set is in progress (except through the iterator's own {@code
273      * remove} operation), the results of the iteration are undefined.  The
274      * set supports element removal, which removes the corresponding mapping
275      * from the map, via the {@code Iterator.remove}, {@code Set.remove},
276      * {@code removeAll}, {@code retainAll}, and {@code clear} operations.
277      * It does not support the {@code add} or {@code addAll} operations.
278      *
279      * @return a navigable set view of the keys in this map
280      */
navigableKeySet()281     NavigableSet<K> navigableKeySet();
282 
283     /**
284      * Returns a reverse order {@link NavigableSet} view of the keys contained in this map.
285      * The set's iterator returns the keys in descending order.
286      * The set is backed by the map, so changes to the map are reflected in
287      * the set, and vice-versa.  If the map is modified while an iteration
288      * over the set is in progress (except through the iterator's own {@code
289      * remove} operation), the results of the iteration are undefined.  The
290      * set supports element removal, which removes the corresponding mapping
291      * from the map, via the {@code Iterator.remove}, {@code Set.remove},
292      * {@code removeAll}, {@code retainAll}, and {@code clear} operations.
293      * It does not support the {@code add} or {@code addAll} operations.
294      *
295      * @return a reverse order navigable set view of the keys in this map
296      */
descendingKeySet()297     NavigableSet<K> descendingKeySet();
298 
299     /**
300      * Returns a view of the portion of this map whose keys range from
301      * {@code fromKey} to {@code toKey}.  If {@code fromKey} and
302      * {@code toKey} are equal, the returned map is empty unless
303      * {@code fromInclusive} and {@code toInclusive} are both true.  The
304      * returned map is backed by this map, so changes in the returned map are
305      * reflected in this map, and vice-versa.  The returned map supports all
306      * optional map operations that this map supports.
307      *
308      * <p>The returned map will throw an {@code IllegalArgumentException}
309      * on an attempt to insert a key outside of its range, or to construct a
310      * submap either of whose endpoints lie outside its range.
311      *
312      * @param fromKey low endpoint of the keys in the returned map
313      * @param fromInclusive {@code true} if the low endpoint
314      *        is to be included in the returned view
315      * @param toKey high endpoint of the keys in the returned map
316      * @param toInclusive {@code true} if the high endpoint
317      *        is to be included in the returned view
318      * @return a view of the portion of this map whose keys range from
319      *         {@code fromKey} to {@code toKey}
320      * @throws ClassCastException if {@code fromKey} and {@code toKey}
321      *         cannot be compared to one another using this map's comparator
322      *         (or, if the map has no comparator, using natural ordering).
323      *         Implementations may, but are not required to, throw this
324      *         exception if {@code fromKey} or {@code toKey}
325      *         cannot be compared to keys currently in the map.
326      * @throws NullPointerException if {@code fromKey} or {@code toKey}
327      *         is null and this map does not permit null keys
328      * @throws IllegalArgumentException if {@code fromKey} is greater than
329      *         {@code toKey}; or if this map itself has a restricted
330      *         range, and {@code fromKey} or {@code toKey} lies
331      *         outside the bounds of the range
332      */
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)333     NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
334                              K toKey,   boolean toInclusive);
335 
336     /**
337      * Returns a view of the portion of this map whose keys are less than (or
338      * equal to, if {@code inclusive} is true) {@code toKey}.  The returned
339      * map is backed by this map, so changes in the returned map are reflected
340      * in this map, and vice-versa.  The returned map supports all optional
341      * map operations that this map supports.
342      *
343      * <p>The returned map will throw an {@code IllegalArgumentException}
344      * on an attempt to insert a key outside its range.
345      *
346      * @param toKey high endpoint of the keys in the returned map
347      * @param inclusive {@code true} if the high endpoint
348      *        is to be included in the returned view
349      * @return a view of the portion of this map whose keys are less than
350      *         (or equal to, if {@code inclusive} is true) {@code toKey}
351      * @throws ClassCastException if {@code toKey} is not compatible
352      *         with this map's comparator (or, if the map has no comparator,
353      *         if {@code toKey} does not implement {@link Comparable}).
354      *         Implementations may, but are not required to, throw this
355      *         exception if {@code toKey} cannot be compared to keys
356      *         currently in the map.
357      * @throws NullPointerException if {@code toKey} is null
358      *         and this map does not permit null keys
359      * @throws IllegalArgumentException if this map itself has a
360      *         restricted range, and {@code toKey} lies outside the
361      *         bounds of the range
362      */
headMap(K toKey, boolean inclusive)363     NavigableMap<K,V> headMap(K toKey, boolean inclusive);
364 
365     /**
366      * Returns a view of the portion of this map whose keys are greater than (or
367      * equal to, if {@code inclusive} is true) {@code fromKey}.  The returned
368      * map is backed by this map, so changes in the returned map are reflected
369      * in this map, and vice-versa.  The returned map supports all optional
370      * map operations that this map supports.
371      *
372      * <p>The returned map will throw an {@code IllegalArgumentException}
373      * on an attempt to insert a key outside its range.
374      *
375      * @param fromKey low endpoint of the keys in the returned map
376      * @param inclusive {@code true} if the low endpoint
377      *        is to be included in the returned view
378      * @return a view of the portion of this map whose keys are greater than
379      *         (or equal to, if {@code inclusive} is true) {@code fromKey}
380      * @throws ClassCastException if {@code fromKey} is not compatible
381      *         with this map's comparator (or, if the map has no comparator,
382      *         if {@code fromKey} does not implement {@link Comparable}).
383      *         Implementations may, but are not required to, throw this
384      *         exception if {@code fromKey} cannot be compared to keys
385      *         currently in the map.
386      * @throws NullPointerException if {@code fromKey} is null
387      *         and this map does not permit null keys
388      * @throws IllegalArgumentException if this map itself has a
389      *         restricted range, and {@code fromKey} lies outside the
390      *         bounds of the range
391      */
tailMap(K fromKey, boolean inclusive)392     NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
393 
394     /**
395      * {@inheritDoc}
396      *
397      * <p>Equivalent to {@code subMap(fromKey, true, toKey, false)}.
398      *
399      * @throws ClassCastException       {@inheritDoc}
400      * @throws NullPointerException     {@inheritDoc}
401      * @throws IllegalArgumentException {@inheritDoc}
402      */
subMap(K fromKey, K toKey)403     SortedMap<K,V> subMap(K fromKey, K toKey);
404 
405     /**
406      * {@inheritDoc}
407      *
408      * <p>Equivalent to {@code headMap(toKey, false)}.
409      *
410      * @throws ClassCastException       {@inheritDoc}
411      * @throws NullPointerException     {@inheritDoc}
412      * @throws IllegalArgumentException {@inheritDoc}
413      */
headMap(K toKey)414     SortedMap<K,V> headMap(K toKey);
415 
416     /**
417      * {@inheritDoc}
418      *
419      * <p>Equivalent to {@code tailMap(fromKey, true)}.
420      *
421      * @throws ClassCastException       {@inheritDoc}
422      * @throws NullPointerException     {@inheritDoc}
423      * @throws IllegalArgumentException {@inheritDoc}
424      */
tailMap(K fromKey)425     SortedMap<K,V> tailMap(K fromKey);
426 }
427