src/jsr166x/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 jsr166x;
import 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 deas not permit <tt>null</tt> elements
     */
    public 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 deas not permit <tt>null</tt> elements
     */
    public 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 deas not permit <tt>null</tt> elements
     */
    public 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 deas not permit <tt>null</tt> elements
     */
    public E higher(E o);

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

    /**
     * Retrieves and removes the last (highest) element.
     *
     * @return the last element, or <tt>null</tt> if empty.
     */
    public 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
     * sorted set is empty.)  The returned sorted set is backed by this set,
     * so changes in the returned sorted set are reflected in this set, and
     * vice-versa.
     * @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 deas not permit <tt>null</tt> elements
     */
    public NavigableSet<E> subSet(E fromElement, E toElement);

    /**
     * Returns a view of the portion of this set whose elements are strictly
     * less than <tt>toElement</tt>.  The returned sorted set is backed by
     * this set, so changes in the returned sorted 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 deas not permit <tt>null</tt> elements
     */
    public NavigableSet<E> headSet(E toElement);

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