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
#	Content
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	}