| SortedSet.java |
1 /*
2 * %W% %E%
3 *
4 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
5 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6 */
7
8 package java.util;
9
10 /**
11 * A {@link Set} that further provides a <i>total ordering</i> on its elements.
12 * The elements are ordered using their {@linkplain Comparable natural
13 * ordering}, or by a {@link Comparator} typically provided at sorted
14 * set creation time. The set's iterator will traverse the set in
15 * ascending element order. Several additional operations are provided
16 * to take advantage of the ordering. (This interface is the set
17 * analogue of {@link SortedMap}.)
18 *
19 * <p>All elements inserted into a sorted set must implement the <tt>Comparable</tt>
20 * interface (or be accepted by the specified comparator). Furthermore, all
21 * such elements must be <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt>
22 * (or <tt>comparator.compare(e1, e2)</tt>) must not throw a
23 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</tt> in
24 * the sorted set. Attempts to violate this restriction will cause the
25 * offending method or constructor invocation to throw a
26 * <tt>ClassCastException</tt>.
27 *
28 * <p>Note that the ordering maintained by a sorted set (whether or not an
29 * explicit comparator is provided) must be <i>consistent with equals</i> if
30 * the sorted set is to correctly implement the <tt>Set</tt> interface. (See
31 * the <tt>Comparable</tt> interface or <tt>Comparator</tt> interface for a
32 * precise definition of <i>consistent with equals</i>.) This is so because
33 * the <tt>Set</tt> interface is defined in terms of the <tt>equals</tt>
34 * operation, but a sorted set performs all element comparisons using its
35 * <tt>compareTo</tt> (or <tt>compare</tt>) method, so two elements that are
36 * deemed equal by this method are, from the standpoint of the sorted set,
37 * equal. The behavior of a sorted set <i>is</i> well-defined even if its
38 * ordering is inconsistent with equals; it just fails to obey the general
39 * contract of the <tt>Set</tt> interface.
40 *
41 * <p>All general-purpose sorted set implementation classes should
42 * provide four "standard" constructors: 1) A void (no arguments)
43 * constructor, which creates an empty sorted set sorted according to
44 * the natural ordering of its elements. 2) A constructor with a
45 * single argument of type <tt>Comparator</tt>, which creates an empty
46 * sorted set sorted according to the specified comparator. 3) A
47 * constructor with a single argument of type <tt>Collection</tt>,
48 * which creates a new sorted set with the same elements as its
49 * argument, sorted according to the natural ordering of the elements.
50 * 4) A constructor with a single argument of type <tt>SortedSet</tt>,
51 * which creates a new sorted set with the same elements and the same
52 * ordering as the input sorted set. There is no way to enforce this
53 * recommendation, as interfaces cannot contain constructors.
54 *
55 * <p>Note: several methods return subsets with restricted ranges.
56 * Such ranges are <i>half-open</i>, that is, they include their low
57 * endpoint but not their high endpoint (where applicable).
58 * If you need a <i>closed range</i> (which includes both endpoints), and
59 * the element type allows for calculation of the successor of a given
60 * value, merely request the subrange from <tt>lowEndpoint</tt> to
61 * <tt>successor(highEndpoint)</tt>. For example, suppose that <tt>s</tt>
62 * is a sorted set of strings. The following idiom obtains a view
63 * containing all of the strings in <tt>s</tt> from <tt>low</tt> to
64 * <tt>high</tt>, inclusive:<pre>
65 * SortedSet<String> sub = s.subSet(low, high+"\0");</pre>
66 *
67 * A similar technique can be used to generate an <i>open range</i> (which
68 * contains neither endpoint). The following idiom obtains a view
69 * containing all of the Strings in <tt>s</tt> from <tt>low</tt> to
70 * <tt>high</tt>, exclusive:<pre>
71 * SortedSet<String> sub = s.subSet(low+"\0", high);</pre>
72 *
73 * <p>This interface is a member of the
74 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
75 * Java Collections Framework</a>.
76 *
77 * @param <E> the type of elements maintained by this set
78 *
79 * @author Josh Bloch
80 * @version %I%, %G%
81 * @see Set
82 * @see TreeSet
83 * @see SortedMap
84 * @see Collection
85 * @see Comparable
86 * @see Comparator
87 * @see ClassCastException
88 * @since 1.2
89 */
90
91 public interface SortedSet<E> extends Set<E> {
92 /**
93 * Returns the comparator used to order the elements in this set,
94 * or <tt>null</tt> if this set uses the {@linkplain Comparable
95 * natural ordering} of its elements.
96 *
97 * @return the comparator used to order the elements in this set,
98 * or <tt>null</tt> if this set uses the natural ordering
99 * of its elements
100 */
101 Comparator<? super E> comparator();
102
103 /**
104 * Returns a view of the portion of this set whose elements range
105 * from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
106 * exclusive. (If <tt>fromElement</tt> and <tt>toElement</tt> are
107 * equal, the returned set is empty.) The returned set is backed
108 * by this set, so changes in the returned set are reflected in
109 * this set, and vice-versa. The returned set supports all
110 * optional set operations that this set supports.
111 *
112 * <p>The returned set will throw an <tt>IllegalArgumentException</tt>
113 * on an attempt to insert an element outside its range.
114 *
115 * @param fromElement low endpoint (inclusive) of the returned set
116 * @param toElement high endpoint (exclusive) of the returned set
117 * @return a view of the portion of this set whose elements range from
118 * <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive
119 * @throws ClassCastException if <tt>fromElement</tt> and
120 * <tt>toElement</tt> cannot be compared to one another using this
121 * set's comparator (or, if the set has no comparator, using
122 * natural ordering). Implementations may, but are not required
123 * to, throw this exception if <tt>fromElement</tt> or
124 * <tt>toElement</tt> cannot be compared to elements currently in
125 * the set.
126 * @throws NullPointerException if <tt>fromElement</tt> or
127 * <tt>toElement</tt> is null and this set does not permit null
128 * elements
129 * @throws IllegalArgumentException if <tt>fromElement</tt> is
130 * greater than <tt>toElement</tt>; or if this set itself
131 * has a restricted range, and <tt>fromElement</tt> or
132 * <tt>toElement</tt> lies outside the bounds of the range
133 */
134 SortedSet<E> subSet(E fromElement, E toElement);
135
136 /**
137 * Returns a view of the portion of this set whose elements are
138 * strictly less than <tt>toElement</tt>. The returned set is
139 * backed by this set, so changes in the returned set are
140 * reflected in this set, and vice-versa. The returned set
141 * supports all optional set operations that this set supports.
142 *
143 * <p>The returned set will throw an <tt>IllegalArgumentException</tt>
144 * on an attempt to insert an element outside its range.
145 *
146 * @param toElement high endpoint (exclusive) of the returned set
147 * @return a view of the portion of this set whose elements are strictly
148 * less than <tt>toElement</tt>
149 * @throws ClassCastException if <tt>toElement</tt> is not compatible
150 * with this set's comparator (or, if the set has no comparator,
151 * if <tt>toElement</tt> does not implement {@link Comparable}).
152 * Implementations may, but are not required to, throw this
153 * exception if <tt>toElement</tt> cannot be compared to elements
154 * currently in the set.
155 * @throws NullPointerException if <tt>toElement</tt> is null and
156 * this set does not permit null elements
157 * @throws IllegalArgumentException if this set itself has a
158 * restricted range, and <tt>toElement</tt> lies outside the
159 * bounds of the range
160 */
161 SortedSet<E> headSet(E toElement);
162
163 /**
164 * Returns a view of the portion of this set whose elements are
165 * greater than or equal to <tt>fromElement</tt>. The returned
166 * set is backed by this set, so changes in the returned set are
167 * reflected in this set, and vice-versa. The returned set
168 * supports all optional set operations that this set supports.
169 *
170 * <p>The returned set will throw an <tt>IllegalArgumentException</tt>
171 * on an attempt to insert an element outside its range.
172 *
173 * @param fromElement low endpoint (inclusive) of the returned set
174 * @return a view of the portion of this set whose elements are greater
175 * than or equal to <tt>fromElement</tt>
176 * @throws ClassCastException if <tt>fromElement</tt> is not compatible
177 * with this set's comparator (or, if the set has no comparator,
178 * if <tt>fromElement</tt> does not implement {@link Comparable}).
179 * Implementations may, but are not required to, throw this
180 * exception if <tt>fromElement</tt> cannot be compared to elements
181 * currently in the set.
182 * @throws NullPointerException if <tt>fromElement</tt> is null
183 * and this set does not permit null elements
184 * @throws IllegalArgumentException if this set itself has a
185 * restricted range, and <tt>fromElement</tt> lies outside the
186 * bounds of the range
187 */
188 SortedSet<E> tailSet(E fromElement);
189
190 /**
191 * Returns the first (lowest) element currently in this set.
192 *
193 * @return the first (lowest) element currently in this set
194 * @throws NoSuchElementException if this set is empty
195 */
196 E first();
197
198 /**
199 * Returns the last (highest) element currently in this set.
200 *
201 * @return the last (highest) element currently in this set
202 * @throws NoSuchElementException if this set is empty
203 */
204 E last();
205 }
206