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 /**
39 * A {@link SortedSet} extended with navigation methods reporting
40 * closest matches for given search targets. Methods {@link #lower},
41 * {@link #floor}, {@link #ceiling}, and {@link #higher} return elements
42 * respectively less than, less than or equal, greater than or equal,
43 * and greater than a given element, returning {@code null} if there
44 * is no such element.
45 *
46 * <p>A {@code NavigableSet} may be accessed and traversed in either
47 * ascending or descending order. The {@link #descendingSet} method
48 * returns a view of the set with the senses of all relational and
49 * directional methods inverted. The performance of ascending
50 * operations and views is likely to be faster than that of descending
51 * ones. This interface additionally defines methods {@link
52 * #pollFirst} and {@link #pollLast} that return and remove the lowest
53 * and highest element, if one exists, else returning {@code null}.
54 * Methods
55 * {@link #subSet(Object, boolean, Object, boolean) subSet(E, boolean, E, boolean)},
56 * {@link #headSet(Object, boolean) headSet(E, boolean)}, and
57 * {@link #tailSet(Object, boolean) tailSet(E, boolean)}
58 * differ from the like-named {@code SortedSet} methods in accepting
59 * additional arguments describing whether lower and upper bounds are
60 * inclusive versus exclusive. Subsets of any {@code NavigableSet}
61 * must implement the {@code NavigableSet} interface.
62 *
63 * <p>The return values of navigation methods may be ambiguous in
64 * implementations that permit {@code null} elements. However, even
65 * in this case the result can be disambiguated by checking
66 * {@code contains(null)}. To avoid such issues, implementations of
67 * this interface are encouraged to <em>not</em> permit insertion of
68 * {@code null} elements. (Note that sorted sets of {@link
69 * Comparable} elements intrinsically do not permit {@code null}.)
70 *
71 * <p>Methods
72 * {@link #subSet(Object, Object) subSet(E, E)},
73 * {@link #headSet(Object) headSet(E)}, and
74 * {@link #tailSet(Object) tailSet(E)}
75 * are specified to return {@code SortedSet} to allow existing
76 * implementations of {@code SortedSet} to be compatibly retrofitted to
77 * implement {@code NavigableSet}, but extensions and implementations
78 * of this interface are encouraged to override these methods to return
79 * {@code NavigableSet}.
80 *
81 * <p>This interface is a member of the
82 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
83 * Java Collections Framework</a>.
84 *
85 * @author Doug Lea
86 * @author Josh Bloch
87 * @param <E> the type of elements maintained by this set
88 * @since 1.6
89 */
90 public interface NavigableSet<E> extends SortedSet<E> {
91 /**
92 * Returns the greatest element in this set strictly less than the
93 * given element, or {@code null} if there is no such element.
94 *
95 * @param e the value to match
96 * @return the greatest element less than {@code e},
97 * or {@code null} if there is no such element
98 * @throws ClassCastException if the specified element cannot be
99 * compared with the elements currently in the set
100 * @throws NullPointerException if the specified element is null
101 * and this set does not permit null elements
102 */
103 E lower(E e);
104
105 /**
106 * Returns the greatest element in this set less than or equal to
107 * the given element, or {@code null} if there is no such element.
108 *
109 * @param e the value to match
110 * @return the greatest element less than or equal to {@code e},
111 * or {@code null} if there is no such element
112 * @throws ClassCastException if the specified element cannot be
113 * compared with the elements currently in the set
114 * @throws NullPointerException if the specified element is null
115 * and this set does not permit null elements
116 */
117 E floor(E e);
118
119 /**
120 * Returns the least element in this set greater than or equal to
121 * the given element, or {@code null} if there is no such element.
122 *
123 * @param e the value to match
124 * @return the least element greater than or equal to {@code e},
125 * or {@code null} if there is no such element
126 * @throws ClassCastException if the specified element cannot be
127 * compared with the elements currently in the set
128 * @throws NullPointerException if the specified element is null
129 * and this set does not permit null elements
130 */
131 E ceiling(E e);
132
133 /**
134 * Returns the least element in this set strictly greater than the
135 * given element, or {@code null} if there is no such element.
136 *
137 * @param e the value to match
138 * @return the least element greater than {@code e},
139 * or {@code null} if there is no such element
140 * @throws ClassCastException if the specified element cannot be
141 * compared with the elements currently in the set
142 * @throws NullPointerException if the specified element is null
143 * and this set does not permit null elements
144 */
145 E higher(E e);
146
147 /**
148 * Retrieves and removes the first (lowest) element,
149 * or returns {@code null} if this set is empty.
150 *
151 * @return the first element, or {@code null} if this set is empty
152 */
153 E pollFirst();
154
155 /**
156 * Retrieves and removes the last (highest) element,
157 * or returns {@code null} if this set is empty.
158 *
159 * @return the last element, or {@code null} if this set is empty
160 */
161 E pollLast();
162
163 /**
164 * Returns an iterator over the elements in this set, in ascending order.
165 *
166 * @return an iterator over the elements in this set, in ascending order
167 */
168 Iterator<E> iterator();
169
170 /**
171 * Returns a reverse order view of the elements contained in this set.
172 * The descending set is backed by this set, so changes to the set are
173 * reflected in the descending set, and vice-versa. If either set is
174 * modified while an iteration over either set is in progress (except
175 * through the iterator's own {@code remove} operation), the results of
176 * the iteration are undefined.
177 *
178 * <p>The returned set has an ordering equivalent to
179 * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}.
180 * The expression {@code s.descendingSet().descendingSet()} returns a
181 * view of {@code s} essentially equivalent to {@code s}.
182 *
183 * @return a reverse order view of this set
184 */
185 NavigableSet<E> descendingSet();
186
187 /**
188 * Returns an iterator over the elements in this set, in descending order.
189 * Equivalent in effect to {@code descendingSet().iterator()}.
190 *
191 * @return an iterator over the elements in this set, in descending order
192 */
193 Iterator<E> descendingIterator();
194
195 /**
196 * Returns a view of the portion of this set whose elements range from
197 * {@code fromElement} to {@code toElement}. If {@code fromElement} and
198 * {@code toElement} are equal, the returned set is empty unless {@code
199 * fromInclusive} and {@code toInclusive} are both true. The returned set
200 * is backed by this set, so changes in the returned set are reflected in
201 * this set, and vice-versa. The returned set supports all optional set
202 * operations that this set supports.
203 *
204 * <p>The returned set will throw an {@code IllegalArgumentException}
205 * on an attempt to insert an element outside its range.
206 *
207 * @param fromElement low endpoint of the returned set
208 * @param fromInclusive {@code true} if the low endpoint
209 * is to be included in the returned view
210 * @param toElement high endpoint of the returned set
211 * @param toInclusive {@code true} if the high endpoint
212 * is to be included in the returned view
213 * @return a view of the portion of this set whose elements range from
214 * {@code fromElement}, inclusive, to {@code toElement}, exclusive
215 * @throws ClassCastException if {@code fromElement} and
216 * {@code toElement} cannot be compared to one another using this
217 * set's comparator (or, if the set has no comparator, using
218 * natural ordering). Implementations may, but are not required
219 * to, throw this exception if {@code fromElement} or
220 * {@code toElement} cannot be compared to elements currently in
221 * the set.
222 * @throws NullPointerException if {@code fromElement} or
223 * {@code toElement} is null and this set does
224 * not permit null elements
225 * @throws IllegalArgumentException if {@code fromElement} is
226 * greater than {@code toElement}; or if this set itself
227 * has a restricted range, and {@code fromElement} or
228 * {@code toElement} lies outside the bounds of the range.
229 */
230 NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
231 E toElement, boolean toInclusive);
232
233 /**
234 * Returns a view of the portion of this set whose elements are less than
235 * (or equal to, if {@code inclusive} is true) {@code toElement}. The
236 * returned set is backed by this set, so changes in the returned set are
237 * reflected in this set, and vice-versa. The returned set supports all
238 * optional set operations that this set supports.
239 *
240 * <p>The returned set will throw an {@code IllegalArgumentException}
241 * on an attempt to insert an element outside its range.
242 *
243 * @param toElement high endpoint of the returned set
244 * @param inclusive {@code true} if the high endpoint
245 * is to be included in the returned view
246 * @return a view of the portion of this set whose elements are less than
247 * (or equal to, if {@code inclusive} is true) {@code toElement}
248 * @throws ClassCastException if {@code toElement} is not compatible
249 * with this set's comparator (or, if the set has no comparator,
250 * if {@code toElement} does not implement {@link Comparable}).
251 * Implementations may, but are not required to, throw this
252 * exception if {@code toElement} cannot be compared to elements
253 * currently in the set.
254 * @throws NullPointerException if {@code toElement} is null and
255 * this set does not permit null elements
256 * @throws IllegalArgumentException if this set itself has a
257 * restricted range, and {@code toElement} lies outside the
258 * bounds of the range
259 */
260 NavigableSet<E> headSet(E toElement, boolean inclusive);
261
262 /**
263 * Returns a view of the portion of this set whose elements are greater
264 * than (or equal to, if {@code inclusive} is true) {@code fromElement}.
265 * The returned set is backed by this set, so changes in the returned set
266 * are reflected in this set, and vice-versa. The returned set supports
267 * all optional set operations that this set supports.
268 *
269 * <p>The returned set will throw an {@code IllegalArgumentException}
270 * on an attempt to insert an element outside its range.
271 *
272 * @param fromElement low endpoint of the returned set
273 * @param inclusive {@code true} if the low endpoint
274 * is to be included in the returned view
275 * @return a view of the portion of this set whose elements are greater
276 * than or equal to {@code fromElement}
277 * @throws ClassCastException if {@code fromElement} is not compatible
278 * with this set's comparator (or, if the set has no comparator,
279 * if {@code fromElement} does not implement {@link Comparable}).
280 * Implementations may, but are not required to, throw this
281 * exception if {@code fromElement} cannot be compared to elements
282 * currently in the set.
283 * @throws NullPointerException if {@code fromElement} is null
284 * and this set does not permit null elements
285 * @throws IllegalArgumentException if this set itself has a
286 * restricted range, and {@code fromElement} lies outside the
287 * bounds of the range
288 */
289 NavigableSet<E> tailSet(E fromElement, boolean inclusive);
290
291 /**
292 * {@inheritDoc}
293 *
294 * <p>Equivalent to {@code subSet(fromElement, true, toElement, false)}.
295 *
296 * @throws ClassCastException {@inheritDoc}
297 * @throws NullPointerException {@inheritDoc}
298 * @throws IllegalArgumentException {@inheritDoc}
299 */
300 SortedSet<E> subSet(E fromElement, E toElement);
301
302 /**
303 * {@inheritDoc}
304 *
305 * <p>Equivalent to {@code headSet(toElement, false)}.
306 *
307 * @throws ClassCastException {@inheritDoc}
308 * @throws NullPointerException {@inheritDoc}
309 * @throws IllegalArgumentException {@inheritDoc}
310 */
311 SortedSet<E> headSet(E toElement);
312
313 /**
314 * {@inheritDoc}
315 *
316 * <p>Equivalent to {@code tailSet(fromElement, true)}.
317 *
318 * @throws ClassCastException {@inheritDoc}
319 * @throws NullPointerException {@inheritDoc}
320 * @throws IllegalArgumentException {@inheritDoc}
321 */
322 SortedSet<E> tailSet(E fromElement);
323 }