001 /*
002 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
003 *
004 * This code is free software; you can redistribute it and/or modify it
005 * under the terms of the GNU General Public License version 2 only, as
006 * published by the Free Software Foundation. Sun designates this
007 * particular file as subject to the "Classpath" exception as provided
008 * by Sun in the LICENSE file that accompanied this code.
009 *
010 * This code is distributed in the hope that it will be useful, but WITHOUT
011 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
012 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
013 * version 2 for more details (a copy is included in the LICENSE file that
014 * accompanied this code).
015 *
016 * You should have received a copy of the GNU General Public License version
017 * 2 along with this work; if not, write to the Free Software Foundation,
018 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
019 *
020 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
021 * CA 95054 USA or visit www.sun.com if you need additional information or
022 * have any questions.
023 */
024
025 /*
026 * This file is available under and governed by the GNU General Public
027 * License version 2 only, as published by the Free Software Foundation.
028 * However, the following notice accompanied the original version of this
029 * file:
030 *
031 * Written by Doug Lea and Josh Bloch with assistance from members of JCP
032 * JSR-166 Expert Group and released to the public domain, as explained at
033 * http://creativecommons.org/licenses/publicdomain
034 */
035
036 package java.util;
037
038 /**
039 * A {@link SortedSet} extended with navigation methods reporting
040 * closest matches for given search targets. Methods {@code lower},
041 * {@code floor}, {@code ceiling}, and {@code higher} return elements
042 * respectively less than, less than or equal, greater than or equal,
043 * and greater than a given element, returning {@code null} if there
044 * is no such element. A {@code NavigableSet} may be accessed and
045 * traversed in either ascending or descending order. The {@code
046 * descendingSet} method returns a view of the set with the senses of
047 * all relational and directional methods inverted. The performance of
048 * ascending operations and views is likely to be faster than that of
049 * descending ones. This interface additionally defines methods
050 * {@code pollFirst} and {@code pollLast} that return and remove the
051 * lowest and highest element, if one exists, else returning {@code
052 * null}. Methods {@code subSet}, {@code headSet},
053 * and {@code tailSet} differ from the like-named {@code
054 * SortedSet} methods in accepting additional arguments describing
055 * whether lower and upper bounds are inclusive versus exclusive.
056 * Subsets of any {@code NavigableSet} must implement the {@code
057 * NavigableSet} interface.
058 *
059 * <p> The return values of navigation methods may be ambiguous in
060 * implementations that permit {@code null} elements. However, even
061 * in this case the result can be disambiguated by checking
062 * {@code contains(null)}. To avoid such issues, implementations of
063 * this interface are encouraged to <em>not</em> permit insertion of
064 * {@code null} elements. (Note that sorted sets of {@link
065 * Comparable} elements intrinsically do not permit {@code null}.)
066 *
067 * <p>Methods
068 * {@link #subSet(Object, Object) subSet(E, E)},
069 * {@link #headSet(Object) headSet(E)}, and
070 * {@link #tailSet(Object) tailSet(E)}
071 * are specified to return {@code SortedSet} to allow existing
072 * implementations of {@code SortedSet} to be compatibly retrofitted to
073 * implement {@code NavigableSet}, but extensions and implementations
074 * of this interface are encouraged to override these methods to return
075 * {@code NavigableSet}.
076 *
077 * <p>This interface is a member of the
078 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
079 * Java Collections Framework</a>.
080 *
081 * @author Doug Lea
082 * @author Josh Bloch
083 * @param <E> the type of elements maintained by this set
084 * @since 1.6
085 */
086 public interface NavigableSet<E> extends SortedSet<E> {
087 /**
088 * Returns the greatest element in this set strictly less than the
089 * given element, or {@code null} if there is no such element.
090 *
091 * @param e the value to match
092 * @return the greatest element less than {@code e},
093 * or {@code null} if there is no such element
094 * @throws ClassCastException if the specified element cannot be
095 * compared with the elements currently in the set
096 * @throws NullPointerException if the specified element is null
097 * and this set does not permit null elements
098 */
099 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 * fromExclusive} and {@code toExclusive} 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 na */
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 }
|