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