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/publicdomain/zero/1.0/
 */

package java.util;

/**
 * A {@link SortedSet} extended with navigation methods reporting
 * closest matches for given search targets. Methods {@link #lower},
 * {@link #floor}, {@link #ceiling}, and {@link #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.
 *
 * <p>A {@code NavigableSet} may be accessed and traversed in either
 * ascending or descending order.  The {@link #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 {@link
 * #pollFirst} and {@link #pollLast} that return and remove the lowest
 * and highest element, if one exists, else returning {@code null}.
 * Methods
 * {@link #subSet(Object, boolean, Object, boolean) subSet(E, boolean, E, boolean)},
 * {@link #headSet(Object, boolean) headSet(E, boolean)}, and
 * {@link #tailSet(Object, boolean) tailSet(E, boolean)}
 * 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>Methods
 * {@link #subSet(Object, Object) subSet(E, E)},
 * {@link #headSet(Object) headSet(E)}, and
 * {@link #tailSet(Object) tailSet(E)}
 * are specified to return {@code SortedSet} to allow existing
 * implementations of {@code SortedSet} to be compatibly retrofitted to
 * implement {@code NavigableSet}, but extensions and implementations
 * of this interface are encouraged to override these methods to return
 * {@code NavigableSet}.
 *
 * <p>This interface is a member of the
 * <a href="{@docRoot}/../technotes/guides/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 reverse order view of the elements contained in this set.
     * 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 either set is in progress (except
     * through the iterator's own {@code remove} operation), the results of
     * the iteration are undefined.
     *
     * <p>The returned set has an ordering equivalent to
     * {@link Collections#reverseOrder(Comparator) Collections.reverseOrder}{@code (comparator())}.
     * The expression {@code s.descendingSet().descendingSet()} returns a
     * view of {@code s} essentially equivalent to {@code s}.
     *
     * @return a reverse order view of this set
     */
    NavigableSet<E> descendingSet();

    /**
     * Returns an iterator over the elements in this set, in descending order.
     * Equivalent in effect to {@code descendingSet().iterator()}.
     *
     * @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
     * fromInclusive} and {@code toInclusive} 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);

    /**
     * {@inheritDoc}
     *
     * <p>Equivalent to {@code subSet(fromElement, true, toElement, false)}.
     *
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    SortedSet<E> subSet(E fromElement, E toElement);

    /**
     * {@inheritDoc}
     *
     * <p>Equivalent to {@code headSet(toElement, false)}.
     *
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    SortedSet<E> headSet(E toElement);

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