author | redestad |
Mon, 12 Sep 2016 17:45:55 +0200 | |
changeset 40812 | dc3755b63ade |
parent 32108 | aa5490a167ee |
child 44743 | f0bbd698c486 |
permissions | -rw-r--r-- |
2 | 1 |
/* |
16929 | 2 |
* Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved. |
2 | 3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 |
* |
|
5 |
* This code is free software; you can redistribute it and/or modify it |
|
6 |
* under the terms of the GNU General Public License version 2 only, as |
|
5506 | 7 |
* published by the Free Software Foundation. Oracle designates this |
2 | 8 |
* particular file as subject to the "Classpath" exception as provided |
5506 | 9 |
* by Oracle in the LICENSE file that accompanied this code. |
2 | 10 |
* |
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT |
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that |
|
15 |
* accompanied this code). |
|
16 |
* |
|
17 |
* You should have received a copy of the GNU General Public License version |
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation, |
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
20 |
* |
|
5506 | 21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
22 |
* or visit www.oracle.com if you need additional information or have any |
|
23 |
* questions. |
|
2 | 24 |
*/ |
25 |
||
26 |
package java.util; |
|
27 |
||
28 |
/** |
|
29 |
* A {@link Set} that further provides a <i>total ordering</i> on its elements. |
|
30 |
* The elements are ordered using their {@linkplain Comparable natural |
|
31 |
* ordering}, or by a {@link Comparator} typically provided at sorted |
|
32 |
* set creation time. The set's iterator will traverse the set in |
|
33 |
* ascending element order. Several additional operations are provided |
|
34 |
* to take advantage of the ordering. (This interface is the set |
|
35 |
* analogue of {@link SortedMap}.) |
|
36 |
* |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
37 |
* <p>All elements inserted into a sorted set must implement the {@code Comparable} |
2 | 38 |
* interface (or be accepted by the specified comparator). Furthermore, all |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
39 |
* such elements must be <i>mutually comparable</i>: {@code e1.compareTo(e2)} |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
40 |
* (or {@code comparator.compare(e1, e2)}) must not throw a |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
41 |
* {@code ClassCastException} for any elements {@code e1} and {@code e2} in |
2 | 42 |
* the sorted set. Attempts to violate this restriction will cause the |
43 |
* offending method or constructor invocation to throw a |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
44 |
* {@code ClassCastException}. |
2 | 45 |
* |
46 |
* <p>Note that the ordering maintained by a sorted set (whether or not an |
|
47 |
* explicit comparator is provided) must be <i>consistent with equals</i> if |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
48 |
* the sorted set is to correctly implement the {@code Set} interface. (See |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
49 |
* the {@code Comparable} interface or {@code Comparator} interface for a |
2 | 50 |
* precise definition of <i>consistent with equals</i>.) This is so because |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
51 |
* the {@code Set} interface is defined in terms of the {@code equals} |
2 | 52 |
* operation, but a sorted set performs all element comparisons using its |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
53 |
* {@code compareTo} (or {@code compare}) method, so two elements that are |
2 | 54 |
* deemed equal by this method are, from the standpoint of the sorted set, |
55 |
* equal. The behavior of a sorted set <i>is</i> well-defined even if its |
|
56 |
* ordering is inconsistent with equals; it just fails to obey the general |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
57 |
* contract of the {@code Set} interface. |
2 | 58 |
* |
59 |
* <p>All general-purpose sorted set implementation classes should |
|
60 |
* provide four "standard" constructors: 1) A void (no arguments) |
|
61 |
* constructor, which creates an empty sorted set sorted according to |
|
62 |
* the natural ordering of its elements. 2) A constructor with a |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
63 |
* single argument of type {@code Comparator}, which creates an empty |
2 | 64 |
* sorted set sorted according to the specified comparator. 3) A |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
65 |
* constructor with a single argument of type {@code Collection}, |
2 | 66 |
* which creates a new sorted set with the same elements as its |
67 |
* argument, sorted according to the natural ordering of the elements. |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
68 |
* 4) A constructor with a single argument of type {@code SortedSet}, |
2 | 69 |
* which creates a new sorted set with the same elements and the same |
70 |
* ordering as the input sorted set. There is no way to enforce this |
|
71 |
* recommendation, as interfaces cannot contain constructors. |
|
72 |
* |
|
73 |
* <p>Note: several methods return subsets with restricted ranges. |
|
74 |
* Such ranges are <i>half-open</i>, that is, they include their low |
|
75 |
* endpoint but not their high endpoint (where applicable). |
|
76 |
* If you need a <i>closed range</i> (which includes both endpoints), and |
|
77 |
* the element type allows for calculation of the successor of a given |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
78 |
* value, merely request the subrange from {@code lowEndpoint} to |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
79 |
* {@code successor(highEndpoint)}. For example, suppose that {@code s} |
2 | 80 |
* is a sorted set of strings. The following idiom obtains a view |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
81 |
* containing all of the strings in {@code s} from {@code low} to |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
82 |
* {@code high}, inclusive:<pre> |
2 | 83 |
* SortedSet<String> sub = s.subSet(low, high+"\0");</pre> |
84 |
* |
|
85 |
* A similar technique can be used to generate an <i>open range</i> (which |
|
86 |
* contains neither endpoint). The following idiom obtains a view |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
87 |
* containing all of the Strings in {@code s} from {@code low} to |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
88 |
* {@code high}, exclusive:<pre> |
2 | 89 |
* SortedSet<String> sub = s.subSet(low+"\0", high);</pre> |
90 |
* |
|
91 |
* <p>This interface is a member of the |
|
92 |
* <a href="{@docRoot}/../technotes/guides/collections/index.html"> |
|
93 |
* Java Collections Framework</a>. |
|
94 |
* |
|
95 |
* @param <E> the type of elements maintained by this set |
|
96 |
* |
|
97 |
* @author Josh Bloch |
|
98 |
* @see Set |
|
99 |
* @see TreeSet |
|
100 |
* @see SortedMap |
|
101 |
* @see Collection |
|
102 |
* @see Comparable |
|
103 |
* @see Comparator |
|
104 |
* @see ClassCastException |
|
105 |
* @since 1.2 |
|
106 |
*/ |
|
107 |
||
108 |
public interface SortedSet<E> extends Set<E> { |
|
109 |
/** |
|
110 |
* Returns the comparator used to order the elements in this set, |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
111 |
* or {@code null} if this set uses the {@linkplain Comparable |
2 | 112 |
* natural ordering} of its elements. |
113 |
* |
|
114 |
* @return the comparator used to order the elements in this set, |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
115 |
* or {@code null} if this set uses the natural ordering |
2 | 116 |
* of its elements |
117 |
*/ |
|
118 |
Comparator<? super E> comparator(); |
|
119 |
||
120 |
/** |
|
121 |
* Returns a view of the portion of this set whose elements range |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
122 |
* from {@code fromElement}, inclusive, to {@code toElement}, |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
123 |
* exclusive. (If {@code fromElement} and {@code toElement} are |
2 | 124 |
* equal, the returned set is empty.) The returned set is backed |
125 |
* by this set, so changes in the returned set are reflected in |
|
126 |
* this set, and vice-versa. The returned set supports all |
|
127 |
* optional set operations that this set supports. |
|
128 |
* |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
129 |
* <p>The returned set will throw an {@code IllegalArgumentException} |
2 | 130 |
* on an attempt to insert an element outside its range. |
131 |
* |
|
132 |
* @param fromElement low endpoint (inclusive) of the returned set |
|
133 |
* @param toElement high endpoint (exclusive) of the returned set |
|
134 |
* @return a view of the portion of this set whose elements range from |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
135 |
* {@code fromElement}, inclusive, to {@code toElement}, exclusive |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
136 |
* @throws ClassCastException if {@code fromElement} and |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
137 |
* {@code toElement} cannot be compared to one another using this |
2 | 138 |
* set's comparator (or, if the set has no comparator, using |
139 |
* natural ordering). Implementations may, but are not required |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
140 |
* to, throw this exception if {@code fromElement} or |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
141 |
* {@code toElement} cannot be compared to elements currently in |
2 | 142 |
* the set. |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
143 |
* @throws NullPointerException if {@code fromElement} or |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
144 |
* {@code toElement} is null and this set does not permit null |
2 | 145 |
* elements |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
146 |
* @throws IllegalArgumentException if {@code fromElement} is |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
147 |
* greater than {@code toElement}; or if this set itself |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
148 |
* has a restricted range, and {@code fromElement} or |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
149 |
* {@code toElement} lies outside the bounds of the range |
2 | 150 |
*/ |
151 |
SortedSet<E> subSet(E fromElement, E toElement); |
|
152 |
||
153 |
/** |
|
154 |
* Returns a view of the portion of this set whose elements are |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
155 |
* strictly less than {@code toElement}. The returned set is |
2 | 156 |
* backed by this set, so changes in the returned set are |
157 |
* reflected in this set, and vice-versa. The returned set |
|
158 |
* supports all optional set operations that this set supports. |
|
159 |
* |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
160 |
* <p>The returned set will throw an {@code IllegalArgumentException} |
2 | 161 |
* on an attempt to insert an element outside its range. |
162 |
* |
|
163 |
* @param toElement high endpoint (exclusive) of the returned set |
|
164 |
* @return a view of the portion of this set whose elements are strictly |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
165 |
* less than {@code toElement} |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
166 |
* @throws ClassCastException if {@code toElement} is not compatible |
2 | 167 |
* with this set's comparator (or, if the set has no comparator, |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
168 |
* if {@code toElement} does not implement {@link Comparable}). |
2 | 169 |
* Implementations may, but are not required to, throw this |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
170 |
* exception if {@code toElement} cannot be compared to elements |
2 | 171 |
* currently in the set. |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
172 |
* @throws NullPointerException if {@code toElement} is null and |
2 | 173 |
* this set does not permit null elements |
174 |
* @throws IllegalArgumentException if this set itself has a |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
175 |
* restricted range, and {@code toElement} lies outside the |
2 | 176 |
* bounds of the range |
177 |
*/ |
|
178 |
SortedSet<E> headSet(E toElement); |
|
179 |
||
180 |
/** |
|
181 |
* Returns a view of the portion of this set whose elements are |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
182 |
* greater than or equal to {@code fromElement}. The returned |
2 | 183 |
* set is backed by this set, so changes in the returned set are |
184 |
* reflected in this set, and vice-versa. The returned set |
|
185 |
* supports all optional set operations that this set supports. |
|
186 |
* |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
187 |
* <p>The returned set will throw an {@code IllegalArgumentException} |
2 | 188 |
* on an attempt to insert an element outside its range. |
189 |
* |
|
190 |
* @param fromElement low endpoint (inclusive) of the returned set |
|
191 |
* @return a view of the portion of this set whose elements are greater |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
192 |
* than or equal to {@code fromElement} |
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
193 |
* @throws ClassCastException if {@code fromElement} is not compatible |
2 | 194 |
* with this set's comparator (or, if the set has no comparator, |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
195 |
* if {@code fromElement} does not implement {@link Comparable}). |
2 | 196 |
* Implementations may, but are not required to, throw this |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
197 |
* exception if {@code fromElement} cannot be compared to elements |
2 | 198 |
* currently in the set. |
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
199 |
* @throws NullPointerException if {@code fromElement} is null |
2 | 200 |
* and this set does not permit null elements |
201 |
* @throws IllegalArgumentException if this set itself has a |
|
32108
aa5490a167ee
8133188: docs: replace <tt> tags (obsolete in html5) for java.util
avstepan
parents:
25859
diff
changeset
|
202 |
* restricted range, and {@code fromElement} lies outside the |
2 | 203 |
* bounds of the range |
204 |
*/ |
|
205 |
SortedSet<E> tailSet(E fromElement); |
|
206 |
||
207 |
/** |
|
208 |
* Returns the first (lowest) element currently in this set. |
|
209 |
* |
|
210 |
* @return the first (lowest) element currently in this set |
|
211 |
* @throws NoSuchElementException if this set is empty |
|
212 |
*/ |
|
213 |
E first(); |
|
214 |
||
215 |
/** |
|
216 |
* Returns the last (highest) element currently in this set. |
|
217 |
* |
|
218 |
* @return the last (highest) element currently in this set |
|
219 |
* @throws NoSuchElementException if this set is empty |
|
220 |
*/ |
|
221 |
E last(); |
|
16929 | 222 |
|
223 |
/** |
|
224 |
* Creates a {@code Spliterator} over the elements in this sorted set. |
|
225 |
* |
|
20489
cce02e4a6cbe
8024408: Specifications for Collection/List/Set/SortedSet.spliterator() need to document if all the (subclass) instances are required to return SIZED spliterators
psandoz
parents:
19435
diff
changeset
|
226 |
* <p>The {@code Spliterator} reports {@link Spliterator#DISTINCT}, |
cce02e4a6cbe
8024408: Specifications for Collection/List/Set/SortedSet.spliterator() need to document if all the (subclass) instances are required to return SIZED spliterators
psandoz
parents:
19435
diff
changeset
|
227 |
* {@link Spliterator#SORTED} and {@link Spliterator#ORDERED}. |
cce02e4a6cbe
8024408: Specifications for Collection/List/Set/SortedSet.spliterator() need to document if all the (subclass) instances are required to return SIZED spliterators
psandoz
parents:
19435
diff
changeset
|
228 |
* Implementations should document the reporting of additional |
cce02e4a6cbe
8024408: Specifications for Collection/List/Set/SortedSet.spliterator() need to document if all the (subclass) instances are required to return SIZED spliterators
psandoz
parents:
19435
diff
changeset
|
229 |
* characteristic values. |
16929 | 230 |
* |
231 |
* <p>The spliterator's comparator (see |
|
232 |
* {@link java.util.Spliterator#getComparator()}) must be {@code null} if |
|
233 |
* the sorted set's comparator (see {@link #comparator()}) is {@code null}. |
|
234 |
* Otherwise, the spliterator's comparator must be the same as or impose the |
|
235 |
* same total ordering as the sorted set's comparator. |
|
236 |
* |
|
237 |
* @implSpec |
|
238 |
* The default implementation creates a |
|
239 |
* <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator |
|
240 |
* from the sorted set's {@code Iterator}. The spliterator inherits the |
|
19435
9d7530ff42cb
8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents:
16929
diff
changeset
|
241 |
* <em>fail-fast</em> properties of the set's iterator. The |
16929 | 242 |
* spliterator's comparator is the same as the sorted set's comparator. |
20489
cce02e4a6cbe
8024408: Specifications for Collection/List/Set/SortedSet.spliterator() need to document if all the (subclass) instances are required to return SIZED spliterators
psandoz
parents:
19435
diff
changeset
|
243 |
* <p> |
cce02e4a6cbe
8024408: Specifications for Collection/List/Set/SortedSet.spliterator() need to document if all the (subclass) instances are required to return SIZED spliterators
psandoz
parents:
19435
diff
changeset
|
244 |
* The created {@code Spliterator} additionally reports |
cce02e4a6cbe
8024408: Specifications for Collection/List/Set/SortedSet.spliterator() need to document if all the (subclass) instances are required to return SIZED spliterators
psandoz
parents:
19435
diff
changeset
|
245 |
* {@link Spliterator#SIZED}. |
16929 | 246 |
* |
247 |
* @implNote |
|
248 |
* The created {@code Spliterator} additionally reports |
|
249 |
* {@link Spliterator#SUBSIZED}. |
|
250 |
* |
|
251 |
* @return a {@code Spliterator} over the elements in this sorted set |
|
252 |
* @since 1.8 |
|
253 |
*/ |
|
254 |
@Override |
|
255 |
default Spliterator<E> spliterator() { |
|
256 |
return new Spliterators.IteratorSpliterator<E>( |
|
257 |
this, Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED) { |
|
258 |
@Override |
|
259 |
public Comparator<? super E> getComparator() { |
|
260 |
return SortedSet.this.comparator(); |
|
261 |
} |
|
262 |
}; |
|
263 |
} |
|
2 | 264 |
} |