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 jsr166x; |
8 |
|
|
|
9 |
|
|
import java.util.*; |
10 |
|
|
|
11 |
|
|
/** |
12 |
|
|
* A {@link SortedMap} extended with methods returning key-value pairs |
13 |
|
|
* holding the closest matches for given search targets. Methods |
14 |
|
|
* <tt>lowerEntry</tt>, <tt>floorEntry</tt>, <tt>ceilingEntry</tt>, |
15 |
|
|
* and <tt>higherEntry</tt> return {@link Map.Entry} objects |
16 |
|
|
* associated with keys respectively less than, less than or equal, |
17 |
|
|
* greater than or equal, and greater than a given key, returning |
18 |
|
|
* <tt>null</tt> if there is no such key. These methods are designed |
19 |
|
|
* for locating, not traversing entries. To traverse, use view |
20 |
|
|
* iterators and/or <tt>submap</tt>. This interface additionally |
21 |
|
|
* defines methods <tt>firstEntry</tt>, <tt>pollFirstEntry</tt> |
22 |
|
|
* <tt>lastEntry</tt>, and <tt>pollLastEntry</tt> that return and/or |
23 |
|
|
* remove the least and greatest mappings, if any exist, else |
24 |
|
|
* returning <tt>null</tt>. |
25 |
|
|
* |
26 |
|
|
* <p> Implementations of these methods are expected to return |
27 |
|
|
* <tt>Map.Entry</tt> pairs representing snapshots of mappings at the |
28 |
|
|
* time they were produced, and thus generally do <em>not</em> support |
29 |
|
|
* the optional <tt>Entry.setValue</tt> method. Note however that it |
30 |
|
|
* is possible to change mappings in the associated map using method |
31 |
|
|
* <tt>put</tt>. |
32 |
|
|
* |
33 |
|
|
* @author Doug Lea |
34 |
|
|
* @param <K> the type of keys maintained by this map |
35 |
|
|
* @param <V> the type of mapped values |
36 |
|
|
*/ |
37 |
|
|
public interface NavigableMap<K,V> extends SortedMap<K,V> { |
38 |
|
|
/** |
39 |
|
|
* Returns a key-value mapping associated with the least key |
40 |
|
|
* greater than or equal to the given key, or null if there is |
41 |
|
|
* no such entry. |
42 |
|
|
* |
43 |
|
|
* @param key the key. |
44 |
|
|
* @return an Entry associated with ceiling of given key, or null |
45 |
|
|
* if there is no such Entry. |
46 |
|
|
* @throws ClassCastException if key cannot be compared with the keys |
47 |
|
|
* currently in the map. |
48 |
|
|
* @throws NullPointerException if key is <tt>null</tt> and this map |
49 |
|
|
* does not support <tt>null</tt> keys. |
50 |
|
|
*/ |
51 |
|
|
public Map.Entry<K,V> ceilingEntry(K key); |
52 |
|
|
|
53 |
|
|
/** |
54 |
|
|
* Returns a key-value mapping associated with the greatest |
55 |
|
|
* key strictly less than the given key, or null if there is no |
56 |
|
|
* such entry. |
57 |
|
|
* |
58 |
|
|
* @param key the key. |
59 |
|
|
* @return an Entry with greatest key less than the given |
60 |
|
|
* key, or null if there is no such Entry. |
61 |
|
|
* @throws ClassCastException if key cannot be compared with the keys |
62 |
|
|
* currently in the map. |
63 |
|
|
* @throws NullPointerException if key is <tt>null</tt> and this map |
64 |
|
|
* does not support <tt>null</tt> keys. |
65 |
|
|
*/ |
66 |
|
|
public Map.Entry<K,V> lowerEntry(K key); |
67 |
|
|
|
68 |
|
|
/** |
69 |
|
|
* Returns a key-value mapping associated with the greatest |
70 |
|
|
* key less than or equal to the given key, or null if there is no |
71 |
|
|
* such entry. |
72 |
|
|
* |
73 |
|
|
* @param key the key. |
74 |
|
|
* @return an Entry associated with floor of given key, or null |
75 |
|
|
* if there is no such Entry. |
76 |
|
|
* @throws ClassCastException if key cannot be compared with the keys |
77 |
|
|
* currently in the map. |
78 |
|
|
* @throws NullPointerException if key is <tt>null</tt> and this map |
79 |
|
|
* does not support <tt>null</tt> keys. |
80 |
|
|
*/ |
81 |
|
|
public Map.Entry<K,V> floorEntry(K key); |
82 |
|
|
|
83 |
|
|
/** |
84 |
|
|
* Returns a key-value mapping associated with the least |
85 |
|
|
* key strictly greater than the given key, or null if there is no |
86 |
|
|
* such entry. |
87 |
|
|
* |
88 |
|
|
* @param key the key. |
89 |
|
|
* @return an Entry with least key greater than the given key, or |
90 |
|
|
* null if there is no such Entry. |
91 |
|
|
* @throws ClassCastException if key cannot be compared with the keys |
92 |
|
|
* currently in the map. |
93 |
|
|
* @throws NullPointerException if key is <tt>null</tt> and this map |
94 |
|
|
* does not support <tt>null</tt> keys. |
95 |
|
|
*/ |
96 |
|
|
public Map.Entry<K,V> higherEntry(K key); |
97 |
|
|
|
98 |
|
|
/** |
99 |
|
|
* Returns a key-value mapping associated with the least |
100 |
|
|
* key in this map, or null if the map is empty. |
101 |
|
|
* |
102 |
|
|
* @return an Entry with least key, or null |
103 |
|
|
* if the map is empty. |
104 |
|
|
*/ |
105 |
|
|
public Map.Entry<K,V> firstEntry(); |
106 |
|
|
|
107 |
|
|
/** |
108 |
|
|
* Returns a key-value mapping associated with the greatest |
109 |
|
|
* key in this map, or null if the map is empty. |
110 |
|
|
* |
111 |
|
|
* @return an Entry with greatest key, or null |
112 |
|
|
* if the map is empty. |
113 |
|
|
*/ |
114 |
|
|
public Map.Entry<K,V> lastEntry(); |
115 |
|
|
|
116 |
|
|
/** |
117 |
|
|
* Removes and returns a key-value mapping associated with |
118 |
|
|
* the least key in this map, or null if the map is empty. |
119 |
|
|
* |
120 |
|
|
* @return the removed first entry of this map, or null |
121 |
|
|
* if the map is empty. |
122 |
|
|
*/ |
123 |
|
|
public Map.Entry<K,V> pollFirstEntry(); |
124 |
|
|
|
125 |
|
|
/** |
126 |
|
|
* Removes and returns a key-value mapping associated with |
127 |
|
|
* the greatest key in this map, or null if the map is empty. |
128 |
|
|
* |
129 |
|
|
* @return the removed last entry of this map, or null |
130 |
|
|
* if the map is empty. |
131 |
|
|
*/ |
132 |
|
|
public Map.Entry<K,V> pollLastEntry(); |
133 |
|
|
|
134 |
|
|
/** |
135 |
|
|
* Returns a view of the portion of this map whose keys range from |
136 |
|
|
* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. (If |
137 |
|
|
* <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map |
138 |
|
|
* is empty.) The returned sorted map is backed by this map, so changes |
139 |
|
|
* in the returned sorted map are reflected in this map, and vice-versa. |
140 |
|
|
|
141 |
|
|
* @param fromKey low endpoint (inclusive) of the subMap. |
142 |
|
|
* @param toKey high endpoint (exclusive) of the subMap. |
143 |
|
|
* |
144 |
|
|
* @return a view of the portion of this map whose keys range from |
145 |
|
|
* <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive. |
146 |
|
|
* |
147 |
|
|
* @throws ClassCastException if <tt>fromKey</tt> and |
148 |
|
|
* <tt>toKey</tt> cannot be compared to one another using this |
149 |
|
|
* map's comparator (or, if the map has no comparator, using |
150 |
|
|
* natural ordering). |
151 |
|
|
* @throws IllegalArgumentException if <tt>fromKey</tt> is greater |
152 |
|
|
* than <tt>toKey</tt>. |
153 |
|
|
* @throws NullPointerException if <tt>fromKey</tt> or |
154 |
|
|
* <tt>toKey</tt> is <tt>null</tt> and this map does not support |
155 |
|
|
* <tt>null</tt> keys. |
156 |
|
|
*/ |
157 |
|
|
public NavigableMap<K,V> subMap(K fromKey, K toKey); |
158 |
|
|
|
159 |
|
|
/** |
160 |
|
|
* Returns a view of the portion of this map whose keys are strictly less |
161 |
|
|
* than <tt>toKey</tt>. The returned sorted map is backed by this map, so |
162 |
|
|
* changes in the returned sorted map are reflected in this map, and |
163 |
|
|
* vice-versa. |
164 |
|
|
* @param toKey high endpoint (exclusive) of the headMap. |
165 |
|
|
* @return a view of the portion of this map whose keys are strictly |
166 |
|
|
* less than <tt>toKey</tt>. |
167 |
|
|
* |
168 |
|
|
* @throws ClassCastException if <tt>toKey</tt> is not compatible |
169 |
|
|
* with this map's comparator (or, if the map has no comparator, |
170 |
|
|
* if <tt>toKey</tt> does not implement <tt>Comparable</tt>). |
171 |
|
|
* @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> |
172 |
|
|
* and this map does not support <tt>null</tt> keys. |
173 |
|
|
*/ |
174 |
|
|
public NavigableMap<K,V> headMap(K toKey); |
175 |
|
|
|
176 |
|
|
/** |
177 |
|
|
* Returns a view of the portion of this map whose keys are |
178 |
|
|
* greater than or equal to <tt>fromKey</tt>. The returned sorted |
179 |
|
|
* map is backed by this map, so changes in the returned sorted |
180 |
|
|
* map are reflected in this map, and vice-versa. |
181 |
|
|
* @param fromKey low endpoint (inclusive) of the tailMap. |
182 |
|
|
* @return a view of the portion of this map whose keys are greater |
183 |
|
|
* than or equal to <tt>fromKey</tt>. |
184 |
|
|
* @throws ClassCastException if <tt>fromKey</tt> is not compatible |
185 |
|
|
* with this map's comparator (or, if the map has no comparator, |
186 |
|
|
* if <tt>fromKey</tt> does not implement <tt>Comparable</tt>). |
187 |
|
|
* @throws NullPointerException if <tt>fromKey</tt> is <tt>null</tt> |
188 |
|
|
* and this map does not support <tt>null</tt> keys. |
189 |
|
|
*/ |
190 |
|
|
public NavigableMap<K,V> tailMap(K fromKey); |
191 |
|
|
} |