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