java/util/NavigableSet.java

/*
 * Written by Doug Lea and Josh Bloch with assistance from members of JCP
 * JSR-166 Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

package java.util;

/**
 * A {@link SortedSet} extended with navigation methods reporting
 * closest matches for given search targets. Methods {@code lower},
 * {@code floor}, {@code ceiling}, and {@code higher} return elements
 * respectively less than, less than or equal, greater than or equal,
 * and greater than a given element, returning {@code null} if there
 * is no such element.  A {@code NavigableSet} may be accessed and
 * traversed in either ascending or descending order.  The {@code
 * descendingSet} method returns a view of the set with the senses of
 * all relational and directional methods inverted. The performance of
 * ascending operations and views is likely to be faster than that of
 * descending ones.  This interface additionally defines methods
 * {@code pollFirst} and {@code pollLast} that return and remove the
 * lowest and highest element, if one exists, else returning {@code
 * null}.  Methods {@code subSet}, {@code headSet},
 * and {@code tailSet} differ from the like-named {@code
 * SortedSet} methods in accepting additional arguments describing
 * whether lower and upper bounds are inclusive versus exclusive.
 * Subsets of any {@code NavigableSet} must implement the {@code
 * NavigableSet} interface.
 *
 * <p> The return values of navigation methods may be ambiguous in
 * implementations that permit {@code null} elements. However, even
 * in this case the result can be disambiguated by checking
 * {@code contains(null)}. To avoid such issues, implementations of
 * this interface are encouraged to <em>not</em> permit insertion of
 * {@code null} elements. (Note that sorted sets of {@link
 * Comparable} elements intrinsically do not permit {@code null}.)
 *
 * <p>This interface is a member of the
 * <a href="{@docRoot}/../guide/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author Doug Lea
 * @author Josh Bloch
 * @param <E> the type of elements maintained by this set
 * @since 1.6
 */
public interface NavigableSet<E> extends SortedSet<E> {
    /**
     * Returns the greatest element in this set strictly less than the
     * given element, or {@code null} if there is no such element.
     *
     * @param e the value to match
     * @return the greatest element less than {@code e},
     *         or {@code null} if there is no such element
     * @throws ClassCastException if the specified element cannot be
     *         compared with the elements currently in the set
     * @throws NullPointerException if the specified element is null
     *         and this set does not permit null elements
     */
    E lower(E e);

    /**
     * Returns the greatest element in this set less than or equal to
     * the given element, or {@code null} if there is no such element.
     *
     * @param e the value to match
     * @return the greatest element less than or equal to {@code e},
     *         or {@code null} if there is no such element
     * @throws ClassCastException if the specified element cannot be
     *         compared with the elements currently in the set
     * @throws NullPointerException if the specified element is null
     *         and this set does not permit null elements
     */
    E floor(E e);

    /**
     * Returns the least element in this set greater than or equal to
     * the given element, or {@code null} if there is no such element.
     *
     * @param e the value to match
     * @return the least element greater than or equal to {@code e},
     *         or {@code null} if there is no such element
     * @throws ClassCastException if the specified element cannot be
     *         compared with the elements currently in the set
     * @throws NullPointerException if the specified element is null
     *         and this set does not permit null elements
     */
    E ceiling(E e);

    /**
     * Returns the least element in this set strictly greater than the
     * given element, or {@code null} if there is no such element.
     *
     * @param e the value to match
     * @return the least element greater than {@code e},
     *         or {@code null} if there is no such element
     * @throws ClassCastException if the specified element cannot be
     *         compared with the elements currently in the set
     * @throws NullPointerException if the specified element is null
     *         and this set does not permit null elements
     */
    E higher(E e);

    /**
     * Retrieves and removes the first (lowest) element,
     * or returns {@code null} if this set is empty.
     *
     * @return the first element, or {@code null} if this set is empty
     */
    E pollFirst();

    /**
     * Retrieves and removes the last (highest) element,
     * or returns {@code null} if this set is empty.
     *
     * @return the last element, or {@code null} if this set is empty
     */
    E pollLast();

    /**
     * Returns an iterator over the elements in this set, in ascending order.
     *
     * @return an iterator over the elements in this set, in ascending order
     */
    Iterator<E> iterator();

    /**
     * Returns a {@link NavigableSet} view of the elements contained in this
     * set in descending order.  The descending set is backed by this set, so
     * changes to the set are reflected in the descending set, and vice-versa.
     * If either set is modified while an iteration over the other set is in
     * progress (except through the iterator's own {@code remove} operation),
     * the results of the iteration are undefined.
     *
     * @return a navigable set view of the elements contained in this set,
     *         sorted in descending order
     */
    NavigableSet<E> descendingSet();

    /**
     * Returns an iterator over the elements in this set, in descending order.
     * Equivalent in effect to <tt>descendingSet().iterator()</tt>.
     *
     * @return an iterator over the elements in this set, in descending order
     */
    Iterator<E> descendingIterator();

    /**
     * Returns a view of the portion of this set whose elements range from
     * {@code fromElement} to {@code toElement}.  If {@code fromElement} and
     * {@code toElement} are equal, the returned set is empty unless {@code
     * fromExclusive} and {@code toExclusive} are both true.  The returned set
     * is backed by this set, so changes in the returned set are reflected in
     * this set, and vice-versa.  The returned set supports all optional set
     * operations that this set supports.
     *
     * <p>The returned set will throw an {@code IllegalArgumentException}
     * on an attempt to insert an element outside its range.
     *
     * @param fromElement low endpoint of the returned set
     * @param fromInclusive {@code true} if the low endpoint
     *        is to be included in the returned view
     * @param toElement high endpoint of the returned set
     * @param toInclusive {@code true} if the high endpoint
     *        is to be included in the returned view
     * @return a view of the portion of this set whose elements range from
     *         {@code fromElement}, inclusive, to {@code toElement}, exclusive
     * @throws ClassCastException if {@code fromElement} and
     *         {@code toElement} cannot be compared to one another using this
     *         set's comparator (or, if the set has no comparator, using
     *         natural ordering).  Implementations may, but are not required
     *         to, throw this exception if {@code fromElement} or
     *         {@code toElement} cannot be compared to elements currently in
     *         the set.
     * @throws NullPointerException if {@code fromElement} or
     *         {@code toElement} is null and this set does
     *         not permit null elements
     * @throws IllegalArgumentException if {@code fromElement} is
     *         greater than {@code toElement}; or if this set itself
     *         has a restricted range, and {@code fromElement} or
     *         {@code toElement} lies outside the bounds of the range.
     */
    NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);

    /**
     * Returns a view of the portion of this set whose elements are less than
     * (or equal to, if {@code inclusive} is true) {@code toElement}.  The
     * returned set is backed by this set, so changes in the returned set are
     * reflected in this set, and vice-versa.  The returned set supports all
     * optional set operations that this set supports.
     *
     * <p>The returned set will throw an {@code IllegalArgumentException}
     * on an attempt to insert an element outside its range.
     *
     * @param toElement high endpoint of the returned set
     * @param inclusive {@code true} if the high endpoint
     *        is to be included in the returned view
     * @return a view of the portion of this set whose elements are less than
     *         (or equal to, if {@code inclusive} is true) {@code toElement}
     * @throws ClassCastException if {@code toElement} is not compatible
     *         with this set's comparator (or, if the set has no comparator,
     *         if {@code toElement} does not implement {@link Comparable}).
     *         Implementations may, but are not required to, throw this
     *         exception if {@code toElement} cannot be compared to elements
     *         currently in the set.
     * @throws NullPointerException if {@code toElement} is null and
     *         this set does not permit null elements
     * @throws IllegalArgumentException if this set itself has a
     *         restricted range, and {@code toElement} lies outside the
     *         bounds of the range
     */
    NavigableSet<E> headSet(E toElement, boolean inclusive);

    /**
     * Returns a view of the portion of this set whose elements are greater
     * than (or equal to, if {@code inclusive} is true) {@code fromElement}.
     * The returned set is backed by this set, so changes in the returned set
     * are reflected in this set, and vice-versa.  The returned set supports
     * all optional set operations that this set supports.
     *
     * <p>The returned set will throw an {@code IllegalArgumentException}
     * on an attempt to insert an element outside its range.
     *
     * @param fromElement low endpoint of the returned set
     * @param inclusive {@code true} if the low endpoint
     *        is to be included in the returned view
     * @return a view of the portion of this set whose elements are greater
     *         than or equal to {@code fromElement}
     * @throws ClassCastException if {@code fromElement} is not compatible
     *         with this set's comparator (or, if the set has no comparator,
     *         if {@code fromElement} does not implement {@link Comparable}).
     *         Implementations may, but are not required to, throw this
     *         exception if {@code fromElement} cannot be compared to elements
     *         currently in the set.
     * @throws NullPointerException if {@code fromElement} is null
     *         and this set does not permit null elements
     * @throws IllegalArgumentException if this set itself has a
     *         restricted range, and {@code fromElement} lies outside the
     *         bounds of the range
     */
    NavigableSet<E> tailSet(E fromElement, boolean inclusive);

    /**
     * Equivalent to {@code subSet(fromElement, true, toElement, false)}
     * but with a return type conforming to the {@code SortedSet} interface.
     *
     * <p>{@inheritDoc}
     *
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    SortedSet<E> subSet(E fromElement, E toElement);

    /**
     * Equivalent to {@code headSet(toElement, false)}
     * but with a return type conforming to the {@code SortedSet} interface.
     *
     * <p>{@inheritDoc}
     *
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    SortedSet<E> headSet(E toElement);

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