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 keys
 * respectively less than, less than or equal, greater than or equal,
 * and greater than a given key, returning <tt>null</tt> if there is
 * no such key.  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
 * descending iterator. The performance of ascending traversals is
 * likely to be faster than descending traversals.  This interface
 * additionally defines methods <tt>pollFirst</tt> and
 * <t>pollLast</tt> that return and remove the lowest and highest key,
 * if one exists, else returning <tt>null</tt>.
 *
 * <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 <em>not</em> to permit insertion of
 * <tt>null</tt> elements. (Note that sorted sets of {@link
 * Comparable} elements intrinsically do not permit <tt>null</tt>.)
 *
 * @author Doug Lea
 * @param <E> the type of elements maintained by this set
 */
public interface NavigableSet<E> extends SortedSet<E> {
    /**
     * Returns an element greater than or equal to the given element, or
     * <tt>null</tt> if there is no such element.
     * 
     * @param o the value to match
     * @return an element greater than or equal to given element, or
     * <tt>null</tt> if there is no such element.
     * @throws ClassCastException if o cannot be compared with the elements
     *            currently in the set.
     * @throws NullPointerException if o is <tt>null</tt> 
     * and this set does not permit <tt>null</tt> elements
     */
    E ceiling(E o);

    /**
     * Returns an element strictly less than the given element, or
     * <tt>null</tt> if there is no such element.
     * 
     * @param o the value to match
     * @return the greatest element less than the given element, or
     * <tt>null</tt> if there is no such element.
     * @throws ClassCastException if o cannot be compared with the elements
     *            currently in the set.
     * @throws NullPointerException if o is <tt>null</tt>
     * and this set does not permit <tt>null</tt> elements
     */
    E lower(E o);

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

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

    /**
     * Retrieves and removes the first (lowest) element.
     *
     * @return the first element, or <tt>null</tt> if empty.
     */
    E pollFirst();

    /**
     * Retrieves and removes the last (highest) element.
     *
     * @return the last element, or <tt>null</tt> if empty.
     */
    E pollLast();

    /**
     * Returns an iterator over the elements in this collection, in
     * descending order.  
     * 
     * @return an <tt>Iterator</tt> over the elements in this collection
     */
    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 navigable set is empty.)  The returned
     * navigable set is backed by this set, so changes in the returned
     * navigable set are reflected in this set, and vice-versa. Note:
     * This method differs from <tt>SortedSet.subSet</tt> only in that
     * the returned set is guaranteed to support the
     * <tt>NavigableSet</tt> interface.
     *
     * @param fromElement low endpoint (inclusive) of the subSet.
     * @param toElement high endpoint (exclusive) of the subSet.
     * @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).
     * @throws IllegalArgumentException if <tt>fromElement</tt> is
     * greater than <tt>toElement</tt>.
     * @throws NullPointerException if <tt>fromElement</tt> or
     *         <tt>toElement</tt> is <tt>null</tt> 
     * and this set does not permit <tt>null</tt> elements
     */
    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 navigable
     * set is backed by this set, so changes in the returned navigable
     * set are reflected in this set, and vice-versa.
     * @param toElement high endpoint (exclusive) of the headSet.
     * @return a view of the portion of this set whose elements are strictly
     *         less than toElement.
     * @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 <tt>Comparable</tt>).
     * @throws NullPointerException if <tt>toElement</tt> is <tt>null</tt>
     * and this set does not permit <tt>null</tt> elements
     */
    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
     * navigable set is backed by this set, so changes in the returned
     * navigable set are reflected in this set, and vice-versa.
     * @param fromElement low endpoint (inclusive) of the tailSet.
     * @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
     * <tt>Comparable</tt>).
     * @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>
     * and this set does not permit <tt>null</tt> elements
     */
    NavigableSet<E> navigableTailSet(E fromElement);
}
Revision:	1.3
Committed:	Tue Mar 22 01:30:10 2005 UTC (19 years, 2 months ago) by dl
Branch:	MAIN
Changes since 1.2:	+25 -21 lines
Log Message:	NavigableMap.subMap -> NavigableMap.navigableSubMap, and associated changes
#	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
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 keys
13			* respectively less than, less than or equal, greater than or equal,
14			* and greater than a given key, returning <tt>null</tt> if there is
15			* no such key. 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
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			* <t>pollLast</tt> that return and remove the lowest and highest key,
23			* if one exists, else returning <tt>null</tt>.
24			*
25			* <p> The return values of navigation methods may be ambiguous in
26			* implementations that permit <tt>null</tt> elements. However, even
27			* in this case the result can be disambiguated by checking
28			* <tt>contains(null)</tt>. To avoid such issues, implementations of
29			* this interface are encouraged <em>not</em> to permit insertion of
30			* <tt>null</tt> elements. (Note that sorted sets of {@link
31			* Comparable} elements intrinsically do not permit <tt>null</tt>.)
32			*
33			* @author Doug Lea
34			* @param <E> the type of elements maintained by this set
35			*/
36			public interface NavigableSet<E> extends SortedSet<E> {
37			/**
38			* Returns an element greater than or equal to the given element, or
39			* <tt>null</tt> if there is no such element.
40			*
41			* @param o the value to match
42			* @return an element greater than or equal to given element, or
43			* <tt>null</tt> if there is no such element.
44			* @throws ClassCastException if o cannot be compared with the elements
45			* currently in the set.
46			* @throws NullPointerException if o is <tt>null</tt>
47	dl	1.2	* and this set does not permit <tt>null</tt> elements
48	dl	1.1	*/
49	dl	1.3	E ceiling(E o);
50	dl	1.1
51			/**
52			* Returns an element strictly less than the given element, or
53			* <tt>null</tt> if there is no such element.
54			*
55			* @param o the value to match
56			* @return the greatest element less than the given element, or
57			* <tt>null</tt> if there is no such element.
58			* @throws ClassCastException if o cannot be compared with the elements
59			* currently in the set.
60			* @throws NullPointerException if o is <tt>null</tt>
61	dl	1.2	* and this set does not permit <tt>null</tt> elements
62	dl	1.1	*/
63	dl	1.3	E lower(E o);
64	dl	1.1
65			/**
66			* Returns an element less than or equal to the given element, or
67			* <tt>null</tt> if there is no such element.
68			*
69			* @param o the value to match
70			* @return the greatest element less than or equal to given
71			* element, or <tt>null</tt> if there is no such element.
72			* @throws ClassCastException if o cannot be compared with the elements
73			* currently in the set.
74			* @throws NullPointerException if o is <tt>null</tt>.
75	dl	1.2	* and this set does not permit <tt>null</tt> elements
76	dl	1.1	*/
77	dl	1.3	E floor(E o);
78	dl	1.1
79			/**
80			* Returns an element strictly greater than the given element, or
81			* <tt>null</tt> if there is no such element.
82			*
83			* @param o the value to match
84			* @return the least element greater than the given element, or
85			* <tt>null</tt> if there is no such element.
86			* @throws ClassCastException if o cannot be compared with the elements
87			* currently in the set.
88			* @throws NullPointerException if o is <tt>null</tt>
89	dl	1.2	* and this set does not permit <tt>null</tt> elements
90	dl	1.1	*/
91	dl	1.3	E higher(E o);
92	dl	1.1
93			/**
94			* Retrieves and removes the first (lowest) element.
95			*
96			* @return the first element, or <tt>null</tt> if empty.
97			*/
98	dl	1.3	E pollFirst();
99	dl	1.1
100			/**
101			* Retrieves and removes the last (highest) element.
102			*
103			* @return the last element, or <tt>null</tt> if empty.
104			*/
105	dl	1.3	E pollLast();
106	dl	1.1
107			/**
108			* Returns an iterator over the elements in this collection, in
109			* descending order.
110			*
111			* @return an <tt>Iterator</tt> over the elements in this collection
112			*/
113			Iterator<E> descendingIterator();
114
115			/**
116	dl	1.3	* Returns a view of the portion of this set whose elements range
117			* from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
118			* exclusive. (If <tt>fromElement</tt> and <tt>toElement</tt> are
119			* equal, the returned navigable set is empty.) The returned
120			* navigable set is backed by this set, so changes in the returned
121			* navigable set are reflected in this set, and vice-versa. Note:
122			* This method differs from <tt>SortedSet.subSet</tt> only in that
123			* the returned set is guaranteed to support the
124			* <tt>NavigableSet</tt> interface.
125			*
126	dl	1.1	* @param fromElement low endpoint (inclusive) of the subSet.
127			* @param toElement high endpoint (exclusive) of the subSet.
128			* @return a view of the portion of this set whose elements range from
129			* <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
130			* exclusive.
131			* @throws ClassCastException if <tt>fromElement</tt> and
132			* <tt>toElement</tt> cannot be compared to one another using
133			* this set's comparator (or, if the set has no comparator,
134			* using natural ordering).
135			* @throws IllegalArgumentException if <tt>fromElement</tt> is
136			* greater than <tt>toElement</tt>.
137			* @throws NullPointerException if <tt>fromElement</tt> or
138			* <tt>toElement</tt> is <tt>null</tt>
139	dl	1.2	* and this set does not permit <tt>null</tt> elements
140	dl	1.1	*/
141	dl	1.3	NavigableSet<E> navigableSubSet(E fromElement, E toElement);
142	dl	1.1
143			/**
144	dl	1.3	* Returns a view of the portion of this set whose elements are
145			* strictly less than <tt>toElement</tt>. The returned navigable
146			* set is backed by this set, so changes in the returned navigable
147			* set are reflected in this set, and vice-versa.
148	dl	1.1	* @param toElement high endpoint (exclusive) of the headSet.
149			* @return a view of the portion of this set whose elements are strictly
150			* less than toElement.
151			* @throws ClassCastException if <tt>toElement</tt> is not compatible
152			* with this set's comparator (or, if the set has no comparator,
153			* if <tt>toElement</tt> does not implement <tt>Comparable</tt>).
154			* @throws NullPointerException if <tt>toElement</tt> is <tt>null</tt>
155	dl	1.2	* and this set does not permit <tt>null</tt> elements
156	dl	1.1	*/
157	dl	1.3	NavigableSet<E> navigableHeadSet(E toElement);
158	dl	1.1
159			/**
160			* Returns a view of the portion of this set whose elements are
161			* greater than or equal to <tt>fromElement</tt>. The returned
162	dl	1.3	* navigable set is backed by this set, so changes in the returned
163			* navigable set are reflected in this set, and vice-versa.
164	dl	1.1	* @param fromElement low endpoint (inclusive) of the tailSet.
165			* @return a view of the portion of this set whose elements are
166			* greater than or equal to <tt>fromElement</tt>.
167			* @throws ClassCastException if <tt>fromElement</tt> is not
168			* compatible with this set's comparator (or, if the set has no
169			* comparator, if <tt>fromElement</tt> does not implement
170			* <tt>Comparable</tt>).
171			* @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>
172	dl	1.2	* and this set does not permit <tt>null</tt> elements
173	dl	1.1	*/
174	dl	1.3	NavigableSet<E> navigableTailSet(E fromElement);
175	dl	1.1	}