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;

/**
 * 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 obey
 * the <tt>NavigableSet</tt> interface.
 * 
 * are guaranteed to obey 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.
     *
     * @return the first element, or <tt>null</tt> if this set is empty
     */
    E pollFirst();

    /**
     * Retrieves and removes the last (highest) element.
     *
     * @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.11
Committed:	Mon Jul 18 19:32:38 2005 UTC (18 years, 10 months ago) by dl
Branch:	MAIN
Changes since 1.10:	+4 -1 lines
Log Message:	Clarify submap specs
#	Content
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
9	/**
10	* A {@link SortedSet} extended with navigation methods reporting
11	* closest matches for given search targets. Methods <tt>lower</tt>,
12	* <tt>floor</tt>, <tt>ceiling</tt>, and <tt>higher</tt> return elements
13	* respectively less than, less than or equal, greater than or equal,
14	* and greater than a given element, returning <tt>null</tt> if there is
15	* no such element. A <tt>NavigableSet</tt> may be viewed and traversed
16	* in either ascending or descending order. The <tt>Collection</tt>
17	* <tt>iterator</tt> method returns an ascending <tt>Iterator</tt> and
18	* the additional method <tt>descendingIterator</tt> returns a
19	* descending iterator. The performance of ascending traversals is
20	* likely to be faster than descending traversals. This interface
21	* additionally defines methods <tt>pollFirst</tt> and
22	* <tt>pollLast</tt> that return and remove the lowest and highest
23	* element, if one exists, else returning <tt>null</tt>.
24	* Methods <tt>navigableSubSet</tt>, <tt>navigableHeadSet</tt>, and
25	* <tt>navigableTailSet</tt> differ from the similarly named
26	* <tt>SortedSet</tt> methods only in their declared return types.
27	* Subsets of any <tt>NavigableSet</tt> must obey
28	* the <tt>NavigableSet</tt> interface.
29	*
30	* are guaranteed to obey the <tt>NavigableSet</tt> interface.
31	*
32	* <p> The return values of navigation methods may be ambiguous in
33	* implementations that permit <tt>null</tt> elements. However, even
34	* in this case the result can be disambiguated by checking
35	* <tt>contains(null)</tt>. To avoid such issues, implementations of
36	* this interface are encouraged to <em>not</em> permit insertion of
37	* <tt>null</tt> elements. (Note that sorted sets of {@link
38	* Comparable} elements intrinsically do not permit <tt>null</tt>.)
39	*
40	* <p>This interface is a member of the
41	* <a href="{@docRoot}/../guide/collections/index.html">
42	* Java Collections Framework</a>.
43	*
44	* @author Doug Lea
45	* @param <E> the type of elements maintained by this set
46	* @since 1.6
47	*/
48	public interface NavigableSet<E> extends SortedSet<E> {
49	/**
50	* Returns the greatest element in this set strictly less than the
51	* given element, or <tt>null</tt> if there is no such element.
52	*
53	* @param e the value to match
54	* @return the greatest element less than <tt>e</tt>,
55	* or <tt>null</tt> if there is no such element
56	* @throws ClassCastException if the specified element cannot be
57	* compared with the elements currently in the set
58	* @throws NullPointerException if the specified element is null
59	* and this set does not permit null elements
60	*/
61	E lower(E e);
62
63	/**
64	* Returns the greatest element in this set less than or equal to
65	* the given element, or <tt>null</tt> if there is no such element.
66	*
67	* @param e the value to match
68	* @return the greatest element less than or equal to <tt>e</tt>,
69	* or <tt>null</tt> if there is no such element
70	* @throws ClassCastException if the specified element cannot be
71	* compared with the elements currently in the set
72	* @throws NullPointerException if the specified element is null
73	* and this set does not permit null elements
74	*/
75	E floor(E e);
76
77	/**
78	* Returns the least element in this set greater than or equal to
79	* the given element, or <tt>null</tt> if there is no such element.
80	*
81	* @param e the value to match
82	* @return the least element greater than or equal to <tt>e</tt>,
83	* or <tt>null</tt> if there is no such element
84	* @throws ClassCastException if the specified element cannot be
85	* compared with the elements currently in the set
86	* @throws NullPointerException if the specified element is null
87	* and this set does not permit null elements
88	*/
89	E ceiling(E e);
90
91	/**
92	* Returns the least element in this set strictly greater than the
93	* given element, or <tt>null</tt> if there is no such element.
94	*
95	* @param e the value to match
96	* @return the least element greater than <tt>e</tt>,
97	* or <tt>null</tt> if there is no such element
98	* @throws ClassCastException if the specified element cannot be
99	* compared with the elements currently in the set
100	* @throws NullPointerException if the specified element is null
101	* and this set does not permit null elements
102	*/
103	E higher(E e);
104
105	/**
106	* Retrieves and removes the first (lowest) element.
107	*
108	* @return the first element, or <tt>null</tt> if this set is empty
109	*/
110	E pollFirst();
111
112	/**
113	* Retrieves and removes the last (highest) element.
114	*
115	* @return the last element, or <tt>null</tt> if this set is empty
116	*/
117	E pollLast();
118
119	/**
120	* Returns an iterator over the elements in this set, in ascending order.
121	*
122	* @return an iterator over the elements in this set, in ascending order
123	*/
124	Iterator<E> iterator();
125
126	/**
127	* Returns an iterator over the elements in this set, in descending order.
128	*
129	* @return an iterator over the elements in this set, in descending order
130	*/
131	Iterator<E> descendingIterator();
132
133	/**
134	* Returns a view of the portion of this set whose elements range
135	* from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
136	* exclusive. (If <tt>fromElement</tt> and <tt>toElement</tt> are
137	* equal, the returned set is empty.) The returned set is backed
138	* by this set, so changes in the returned set are reflected in
139	* this set, and vice-versa. The returned set supports all
140	* optional set operations that this set supports.
141	*
142	* <p>The returned set will throw an <tt>IllegalArgumentException</tt>
143	* on an attempt to insert an element outside its range.
144	*
145	* @param fromElement low endpoint (inclusive) of the returned set
146	* @param toElement high endpoint (exclusive) of the returned set
147	* @return a view of the portion of this set whose elements range from
148	* <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive
149	* @throws ClassCastException if <tt>fromElement</tt> and
150	* <tt>toElement</tt> cannot be compared to one another using this
151	* set's comparator (or, if the set has no comparator, using
152	* natural ordering). Implementations may, but are not required
153	* to, throw this exception if <tt>fromElement</tt> or
154	* <tt>toElement</tt> cannot be compared to elements currently in
155	* the set.
156	* @throws NullPointerException if <tt>fromElement</tt> or
157	* <tt>toElement</tt> is null and this set does
158	* not permit null elements
159	* @throws IllegalArgumentException if <tt>fromElement</tt> is
160	* greater than <tt>toElement</tt>; or if this set itself
161	* has a restricted range, and <tt>fromElement</tt> or
162	* <tt>toElement</tt> lies outside the bounds of the range.
163	*/
164	NavigableSet<E> navigableSubSet(E fromElement, E toElement);
165
166	/**
167	* Returns a view of the portion of this set whose elements are
168	* strictly less than <tt>toElement</tt>. The returned set is
169	* backed by this set, so changes in the returned set are
170	* reflected in this set, and vice-versa. The returned set
171	* supports all optional set operations that this set supports.
172	*
173	* <p>The returned set will throw an <tt>IllegalArgumentException</tt>
174	* on an attempt to insert an element outside its range.
175	*
176	* @param toElement high endpoint (exclusive) of the returned set
177	* @return a view of the portion of this set whose elements are strictly
178	* less than <tt>toElement</tt>
179	* @throws ClassCastException if <tt>toElement</tt> is not compatible
180	* with this set's comparator (or, if the set has no comparator,
181	* if <tt>toElement</tt> does not implement {@link Comparable}).
182	* Implementations may, but are not required to, throw this
183	* exception if <tt>toElement</tt> cannot be compared to elements
184	* currently in the set.
185	* @throws NullPointerException if <tt>toElement</tt> is null and
186	* this set does not permit null elements
187	* @throws IllegalArgumentException if this set itself has a
188	* restricted range, and <tt>toElement</tt> lies outside the
189	* bounds of the range
190	*/
191	NavigableSet<E> navigableHeadSet(E toElement);
192
193	/**
194	* Returns a view of the portion of this set whose elements are
195	* greater than or equal to <tt>fromElement</tt>. The returned
196	* set is backed by this set, so changes in the returned set are
197	* reflected in this set, and vice-versa. The returned set
198	* supports all optional set operations that this set supports.
199	*
200	* <p>The returned set will throw an <tt>IllegalArgumentException</tt>
201	* on an attempt to insert an element outside its range.
202	*
203	* @param fromElement low endpoint (inclusive) of the returned set
204	* @return a view of the portion of this set whose elements are greater
205	* than or equal to <tt>fromElement</tt>
206	* @throws ClassCastException if <tt>fromElement</tt> is not compatible
207	* with this set's comparator (or, if the set has no comparator,
208	* if <tt>fromElement</tt> does not implement {@link Comparable}).
209	* Implementations may, but are not required to, throw this
210	* exception if <tt>fromElement</tt> cannot be compared to elements
211	* currently in the set.
212	* @throws NullPointerException if <tt>fromElement</tt> is null
213	* and this set does not permit null elements
214	* @throws IllegalArgumentException if this set itself has a
215	* restricted range, and <tt>fromElement</tt> lies outside the
216	* bounds of the range
217	*/
218	NavigableSet<E> navigableTailSet(E fromElement);
219	}