java/util/NavigableSet.java

/*
 * Written by Doug Lea 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;
import java.util.*; // for javadoc (till 6280605 is fixed)

/**
 * A {@link SortedSet} extended with navigation methods reporting
 * closest matches for given search targets. Methods <tt>lower</tt>,
 * <tt>floor</tt>, <tt>ceiling</tt>, and <tt>higher</tt> return elements
 * respectively less than, less than or equal, greater than or equal,
 * and greater than a given element, returning <tt>null</tt> if there is
 * no such element.  A <tt>NavigableSet</tt> may be viewed and traversed
 * in either ascending or descending order.  The <tt>Collection</tt>
 * <tt>iterator</tt> method returns an ascending <tt>Iterator</tt> and
 * the additional method <tt>descendingIterator</tt> returns a
 * descending iterator. The performance of ascending traversals is
 * likely to be faster than descending traversals.  This interface
 * additionally defines methods <tt>pollFirst</tt> and
 * <tt>pollLast</tt> that return and remove the lowest and highest
 * element, if one exists, else returning <tt>null</tt>.
 * Methods <tt>navigableSubSet</tt>, <tt>navigableHeadSet</tt>, and
 * <tt>navigableTailSet</tt> differ from the similarly named
 * <tt>SortedSet</tt> methods only in their declared return types.
 * Subsets of any <tt>NavigableSet</tt> must implement the
 * <tt>NavigableSet</tt> interface.
 *
 * <p> The return values of navigation methods may be ambiguous in
 * implementations that permit <tt>null</tt> elements. However, even
 * in this case the result can be disambiguated by checking
 * <tt>contains(null)</tt>. To avoid such issues, implementations of
 * this interface are encouraged to <em>not</em> permit insertion of
 * <tt>null</tt> elements. (Note that sorted sets of {@link
 * Comparable} elements intrinsically do not permit <tt>null</tt>.)
 *
 * <p>This interface is a member of the
 * <a href="{@docRoot}/../guide/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author Doug Lea
 * @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 <tt>null</tt> if there is no such element.
     *
     * @param e the value to match
     * @return the greatest element less than <tt>e</tt>,
     *         or <tt>null</tt> 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 <tt>null</tt> if there is no such element.
     *
     * @param e the value to match
     * @return the greatest element less than or equal to <tt>e</tt>,
     *         or <tt>null</tt> 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 <tt>null</tt> if there is no such element.
     *
     * @param e the value to match
     * @return the least element greater than or equal to <tt>e</tt>,
     *         or <tt>null</tt> 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 <tt>null</tt> if there is no such element.
     *
     * @param e the value to match
     * @return the least element greater than <tt>e</tt>,
     *         or <tt>null</tt> 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 <tt>null</tt> if this set is empty.
     *
     * @return the first element, or <tt>null</tt> if this set is empty
     */
    E pollFirst();

    /**
     * Retrieves and removes the last (highest) element,
     * or returns <tt>null</tt> if this set is empty.
     *
     * @return the last element, or <tt>null</tt> 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 an iterator over the elements in this set, in descending order.
     *
     * @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 <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
     * exclusive.  (If <tt>fromElement</tt> and <tt>toElement</tt> are
     * equal, the returned set is empty.)  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 <tt>IllegalArgumentException</tt>
     * on an attempt to insert an element outside its range.
     *
     * @param fromElement low endpoint (inclusive) of the returned set
     * @param toElement high endpoint (exclusive) of the returned set
     * @return a view of the portion of this set whose elements range from
     *         <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive
     * @throws ClassCastException if <tt>fromElement</tt> and
     *         <tt>toElement</tt> 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 <tt>fromElement</tt> or
     *         <tt>toElement</tt> cannot be compared to elements currently in
     *         the set.
     * @throws NullPointerException if <tt>fromElement</tt> or
     *         <tt>toElement</tt> is null and this set does
     *         not permit null elements
     * @throws IllegalArgumentException if <tt>fromElement</tt> is
     *         greater than <tt>toElement</tt>; or if this set itself
     *         has a restricted range, and <tt>fromElement</tt> or
     *         <tt>toElement</tt> lies outside the bounds of the range.
     */
    NavigableSet<E> navigableSubSet(E fromElement, E toElement);

    /**
     * Returns a view of the portion of this set whose elements are
     * strictly less than <tt>toElement</tt>.  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 <tt>IllegalArgumentException</tt>
     * on an attempt to insert an element outside its range.
     *
     * @param toElement high endpoint (exclusive) of the returned set
     * @return a view of the portion of this set whose elements are strictly
     *         less than <tt>toElement</tt>
     * @throws ClassCastException if <tt>toElement</tt> is not compatible
     *         with this set's comparator (or, if the set has no comparator,
     *         if <tt>toElement</tt> does not implement {@link Comparable}).
     *         Implementations may, but are not required to, throw this
     *         exception if <tt>toElement</tt> cannot be compared to elements
     *         currently in the set.
     * @throws NullPointerException if <tt>toElement</tt> is null and
     *         this set does not permit null elements
     * @throws IllegalArgumentException if this set itself has a
     *         restricted range, and <tt>toElement</tt> lies outside the
     *         bounds of the range
     */
    NavigableSet<E> navigableHeadSet(E toElement);

    /**
     * Returns a view of the portion of this set whose elements are
     * greater than or equal to <tt>fromElement</tt>.  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 <tt>IllegalArgumentException</tt>
     * on an attempt to insert an element outside its range.
     *
     * @param fromElement low endpoint (inclusive) of the returned set
     * @return a view of the portion of this set whose elements are greater
     *         than or equal to <tt>fromElement</tt>
     * @throws ClassCastException if <tt>fromElement</tt> is not compatible
     *         with this set's comparator (or, if the set has no comparator,
     *         if <tt>fromElement</tt> does not implement {@link Comparable}).
     *         Implementations may, but are not required to, throw this
     *         exception if <tt>fromElement</tt> cannot be compared to elements
     *         currently in the set.
     * @throws NullPointerException if <tt>fromElement</tt> is null
     *         and this set does not permit null elements
     * @throws IllegalArgumentException if this set itself has a
     *         restricted range, and <tt>fromElement</tt> lies outside the
     *         bounds of the range
     */
    NavigableSet<E> navigableTailSet(E fromElement);
}
Revision:	1.13
Committed:	Thu Aug 11 08:54:39 2005 UTC (18 years, 10 months ago) by jsr166
Branch:	MAIN
Changes since 1.12:	+4 -2 lines
Log Message:	doc fixes
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4			* http://creativecommons.org/licenses/publicdomain
5			*/
6
7			package java.util;
8	jsr166	1.12	import java.util.*; // for javadoc (till 6280605 is fixed)
9	dl	1.1
10			/**
11			* A {@link SortedSet} extended with navigation methods reporting
12			* closest matches for given search targets. Methods <tt>lower</tt>,
13	jsr166	1.9	* <tt>floor</tt>, <tt>ceiling</tt>, and <tt>higher</tt> return elements
14	dl	1.1	* respectively less than, less than or equal, greater than or equal,
15	jsr166	1.9	* and greater than a given element, returning <tt>null</tt> if there is
16			* no such element. A <tt>NavigableSet</tt> may be viewed and traversed
17	dl	1.1	* in either ascending or descending order. The <tt>Collection</tt>
18			* <tt>iterator</tt> method returns an ascending <tt>Iterator</tt> and
19	jsr166	1.9	* the additional method <tt>descendingIterator</tt> returns a
20	dl	1.1	* descending iterator. The performance of ascending traversals is
21			* likely to be faster than descending traversals. This interface
22			* additionally defines methods <tt>pollFirst</tt> and
23	jsr166	1.9	* <tt>pollLast</tt> that return and remove the lowest and highest
24			* element, if one exists, else returning <tt>null</tt>.
25	dl	1.4	* Methods <tt>navigableSubSet</tt>, <tt>navigableHeadSet</tt>, and
26			* <tt>navigableTailSet</tt> differ from the similarly named
27	dl	1.11	* <tt>SortedSet</tt> methods only in their declared return types.
28	jsr166	1.12	* Subsets of any <tt>NavigableSet</tt> must implement the
29			* <tt>NavigableSet</tt> interface.
30	dl	1.1	*
31			* <p> The return values of navigation methods may be ambiguous in
32			* implementations that permit <tt>null</tt> elements. However, even
33			* in this case the result can be disambiguated by checking
34			* <tt>contains(null)</tt>. To avoid such issues, implementations of
35	jsr166	1.9	* this interface are encouraged to <em>not</em> permit insertion of
36	dl	1.1	* <tt>null</tt> elements. (Note that sorted sets of {@link
37			* Comparable} elements intrinsically do not permit <tt>null</tt>.)
38			*
39	jsr166	1.8	* <p>This interface is a member of the
40			* <a href="{@docRoot}/../guide/collections/index.html">
41			* Java Collections Framework</a>.
42			*
43	dl	1.1	* @author Doug Lea
44			* @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			* given element, or <tt>null</tt> if there is no such element.
51	jsr166	1.6	*
52	jsr166	1.5	* @param e the value to match
53	jsr166	1.9	* @return the greatest element less than <tt>e</tt>,
54			* or <tt>null</tt> if there is no such element
55			* @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			* the given element, or <tt>null</tt> if there is no such element.
65	jsr166	1.6	*
66	jsr166	1.5	* @param e the value to match
67	jsr166	1.9	* @return the greatest element less than or equal to <tt>e</tt>,
68			* or <tt>null</tt> 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	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			* the given element, or <tt>null</tt> if there is no such element.
79	jsr166	1.6	*
80	jsr166	1.5	* @param e the value to match
81	jsr166	1.9	* @return the least element greater than or equal to <tt>e</tt>,
82			* or <tt>null</tt> 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	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			* given element, or <tt>null</tt> if there is no such element.
93	jsr166	1.6	*
94	jsr166	1.5	* @param e the value to match
95	jsr166	1.9	* @return the least element greater than <tt>e</tt>,
96			* or <tt>null</tt> 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	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			* or returns <tt>null</tt> if this set is empty.
107	dl	1.1	*
108	jsr166	1.9	* @return the first element, or <tt>null</tt> 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			* or returns <tt>null</tt> if this set is empty.
115	dl	1.1	*
116	jsr166	1.9	* @return the last element, or <tt>null</tt> 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			* Returns an iterator over the elements in this set, in descending order.
129			*
130			* @return an iterator over the elements in this set, in descending order
131	dl	1.1	*/
132			Iterator<E> descendingIterator();
133
134			/**
135	dl	1.3	* Returns a view of the portion of this set whose elements range
136			* from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
137			* exclusive. (If <tt>fromElement</tt> and <tt>toElement</tt> are
138	jsr166	1.9	* equal, the returned set is empty.) The returned set is backed
139			* by this set, so changes in the returned set are reflected in
140			* this set, and vice-versa. The returned set supports all
141			* optional set operations that this set supports.
142	dl	1.3	*
143	jsr166	1.9	* <p>The returned set will throw an <tt>IllegalArgumentException</tt>
144			* on an attempt to insert an element outside its range.
145			*
146			* @param fromElement low endpoint (inclusive) of the returned set
147			* @param toElement high endpoint (exclusive) of the returned set
148	dl	1.1	* @return a view of the portion of this set whose elements range from
149	jsr166	1.9	* <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive
150	dl	1.1	* @throws ClassCastException if <tt>fromElement</tt> and
151	jsr166	1.9	* <tt>toElement</tt> cannot be compared to one another using this
152			* set's comparator (or, if the set has no comparator, using
153			* natural ordering). Implementations may, but are not required
154			* to, throw this exception if <tt>fromElement</tt> or
155			* <tt>toElement</tt> cannot be compared to elements currently in
156			* the set.
157			* @throws NullPointerException if <tt>fromElement</tt> or
158			* <tt>toElement</tt> is null and this set does
159			* not permit null elements
160	dl	1.1	* @throws IllegalArgumentException if <tt>fromElement</tt> is
161	jsr166	1.9	* greater than <tt>toElement</tt>; or if this set itself
162			* has a restricted range, and <tt>fromElement</tt> or
163			* <tt>toElement</tt> lies outside the bounds of the range.
164	dl	1.1	*/
165	dl	1.3	NavigableSet<E> navigableSubSet(E fromElement, E toElement);
166	dl	1.1
167			/**
168	dl	1.3	* Returns a view of the portion of this set whose elements are
169	jsr166	1.9	* strictly less than <tt>toElement</tt>. The returned set is
170			* backed by this set, so changes in the returned set are
171			* reflected in this set, and vice-versa. The returned set
172			* supports all optional set operations that this set supports.
173			*
174			* <p>The returned set will throw an <tt>IllegalArgumentException</tt>
175			* on an attempt to insert an element outside its range.
176			*
177			* @param toElement high endpoint (exclusive) of the returned set
178	dl	1.1	* @return a view of the portion of this set whose elements are strictly
179	jsr166	1.9	* less than <tt>toElement</tt>
180	dl	1.1	* @throws ClassCastException if <tt>toElement</tt> is not compatible
181			* with this set's comparator (or, if the set has no comparator,
182	jsr166	1.9	* if <tt>toElement</tt> does not implement {@link Comparable}).
183			* Implementations may, but are not required to, throw this
184			* exception if <tt>toElement</tt> cannot be compared to elements
185			* currently in the set.
186			* @throws NullPointerException if <tt>toElement</tt> is null and
187			* this set does not permit null elements
188			* @throws IllegalArgumentException if this set itself has a
189			* restricted range, and <tt>toElement</tt> lies outside the
190			* bounds of the range
191	dl	1.1	*/
192	dl	1.3	NavigableSet<E> navigableHeadSet(E toElement);
193	dl	1.1
194			/**
195			* Returns a view of the portion of this set whose elements are
196			* greater than or equal to <tt>fromElement</tt>. The returned
197	jsr166	1.9	* set is backed by this set, so changes in the returned set are
198			* reflected in this set, and vice-versa. The returned set
199			* supports all optional set operations that this set supports.
200			*
201			* <p>The returned set will throw an <tt>IllegalArgumentException</tt>
202			* on an attempt to insert an element outside its range.
203			*
204			* @param fromElement low endpoint (inclusive) of the returned set
205			* @return a view of the portion of this set whose elements are greater
206			* than or equal to <tt>fromElement</tt>
207			* @throws ClassCastException if <tt>fromElement</tt> is not compatible
208			* with this set's comparator (or, if the set has no comparator,
209			* if <tt>fromElement</tt> does not implement {@link Comparable}).
210			* Implementations may, but are not required to, throw this
211			* exception if <tt>fromElement</tt> cannot be compared to elements
212			* currently in the set.
213			* @throws NullPointerException if <tt>fromElement</tt> is null
214			* and this set does not permit null elements
215			* @throws IllegalArgumentException if this set itself has a
216			* restricted range, and <tt>fromElement</tt> lies outside the
217			* bounds of the range
218	dl	1.1	*/
219	dl	1.3	NavigableSet<E> navigableTailSet(E fromElement);
220	dl	1.1	}