1 /* 2 * Copyright (c) 1998, 2023, Oracle and/or its affiliates. All rights reserved. 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 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 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 * 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. 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 * 37 * <p>All elements inserted into a sorted set must implement the {@code Comparable} 38 * interface (or be accepted by the specified comparator). Furthermore, all 39 * such elements must be <i>mutually comparable</i>: {@code e1.compareTo(e2)} 40 * (or {@code comparator.compare(e1, e2)}) must not throw a 41 * {@code ClassCastException} for any elements {@code e1} and {@code e2} in 42 * the sorted set. Attempts to violate this restriction will cause the 43 * offending method or constructor invocation to throw a 44 * {@code ClassCastException}. 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 48 * the sorted set is to correctly implement the {@code Set} interface. (See 49 * the {@code Comparable} interface or {@code Comparator} interface for a 50 * precise definition of <i>consistent with equals</i>.) This is so because 51 * the {@code Set} interface is defined in terms of the {@code equals} 52 * operation, but a sorted set performs all element comparisons using its 53 * {@code compareTo} (or {@code compare}) method, so two elements that are 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 57 * contract of the {@code Set} interface. 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 63 * single argument of type {@code Comparator}, which creates an empty 64 * sorted set sorted according to the specified comparator. 3) A 65 * constructor with a single argument of type {@code Collection}, 66 * which creates a new sorted set with the same elements as its 67 * argument, sorted according to the natural ordering of the elements. 68 * 4) A constructor with a single argument of type {@code SortedSet}, 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 78 * value, merely request the subrange from {@code lowEndpoint} to 79 * {@code successor(highEndpoint)}. For example, suppose that {@code s} 80 * is a sorted set of strings. The following idiom obtains a view 81 * containing all of the strings in {@code s} from {@code low} to 82 * {@code high}, inclusive:<pre> 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 87 * containing all of the Strings in {@code s} from {@code low} to 88 * {@code high}, exclusive:<pre> 89 * SortedSet<String> sub = s.subSet(low+"\0", high);</pre> 90 * 91 * <p>This interface is a member of the 92 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 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>, SequencedSet<E> { 109 /** 110 * Returns the comparator used to order the elements in this set, 111 * or {@code null} if this set uses the {@linkplain Comparable 112 * natural ordering} of its elements. 113 * 114 * @return the comparator used to order the elements in this set, 115 * or {@code null} if this set uses the natural ordering 116 * of its elements 117 */ comparator()118 Comparator<? super E> comparator(); 119 120 /** 121 * Returns a view of the portion of this set whose elements range 122 * from {@code fromElement}, inclusive, to {@code toElement}, 123 * exclusive. (If {@code fromElement} and {@code toElement} are 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 * 129 * <p>The returned set will throw an {@code IllegalArgumentException} 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 135 * {@code fromElement}, inclusive, to {@code toElement}, exclusive 136 * @throws ClassCastException if {@code fromElement} and 137 * {@code toElement} cannot be compared to one another using this 138 * set's comparator (or, if the set has no comparator, using 139 * natural ordering). Implementations may, but are not required 140 * to, throw this exception if {@code fromElement} or 141 * {@code toElement} cannot be compared to elements currently in 142 * the set. 143 * @throws NullPointerException if {@code fromElement} or 144 * {@code toElement} is null and this set does not permit null 145 * elements 146 * @throws IllegalArgumentException if {@code fromElement} is 147 * greater than {@code toElement}; or if this set itself 148 * has a restricted range, and {@code fromElement} or 149 * {@code toElement} lies outside the bounds of the range 150 */ subSet(E fromElement, E toElement)151 SortedSet<E> subSet(E fromElement, E toElement); 152 153 /** 154 * Returns a view of the portion of this set whose elements are 155 * strictly less than {@code toElement}. The returned set is 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 * 160 * <p>The returned set will throw an {@code IllegalArgumentException} 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 165 * less than {@code toElement} 166 * @throws ClassCastException if {@code toElement} is not compatible 167 * with this set's comparator (or, if the set has no comparator, 168 * if {@code toElement} does not implement {@link Comparable}). 169 * Implementations may, but are not required to, throw this 170 * exception if {@code toElement} cannot be compared to elements 171 * currently in the set. 172 * @throws NullPointerException if {@code toElement} is null and 173 * this set does not permit null elements 174 * @throws IllegalArgumentException if this set itself has a 175 * restricted range, and {@code toElement} lies outside the 176 * bounds of the range 177 */ headSet(E toElement)178 SortedSet<E> headSet(E toElement); 179 180 /** 181 * Returns a view of the portion of this set whose elements are 182 * greater than or equal to {@code fromElement}. The returned 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 * 187 * <p>The returned set will throw an {@code IllegalArgumentException} 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 192 * than or equal to {@code fromElement} 193 * @throws ClassCastException if {@code fromElement} is not compatible 194 * with this set's comparator (or, if the set has no comparator, 195 * if {@code fromElement} does not implement {@link Comparable}). 196 * Implementations may, but are not required to, throw this 197 * exception if {@code fromElement} cannot be compared to elements 198 * currently in the set. 199 * @throws NullPointerException if {@code fromElement} is null 200 * and this set does not permit null elements 201 * @throws IllegalArgumentException if this set itself has a 202 * restricted range, and {@code fromElement} lies outside the 203 * bounds of the range 204 */ tailSet(E fromElement)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 */ first()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 */ last()221 E last(); 222 223 /** 224 * Creates a {@code Spliterator} over the elements in this sorted set. 225 * 226 * <p>The {@code Spliterator} reports {@link Spliterator#DISTINCT}, 227 * {@link Spliterator#SORTED} and {@link Spliterator#ORDERED}. 228 * Implementations should document the reporting of additional 229 * characteristic values. 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 241 * <em>fail-fast</em> properties of the set's iterator. The 242 * spliterator's comparator is the same as the sorted set's comparator. 243 * <p> 244 * The created {@code Spliterator} additionally reports 245 * {@link Spliterator#SIZED}. 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 spliterator()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 } 264 265 // ========== SequencedCollection ========== 266 267 /** 268 * Throws {@code UnsupportedOperationException}. The encounter order induced by this 269 * set's comparison method determines the position of elements, so explicit positioning 270 * is not supported. 271 * 272 * @implSpec 273 * The implementation in this interface always throws {@code UnsupportedOperationException}. 274 * 275 * @throws UnsupportedOperationException always 276 * @since 21 277 */ 278 default void addFirst(E e) { 279 throw new UnsupportedOperationException(); 280 } 281 282 /** 283 * Throws {@code UnsupportedOperationException}. The encounter order induced by this 284 * set's comparison method determines the position of elements, so explicit positioning 285 * is not supported. 286 * 287 * @implSpec 288 * The implementation in this interface always throws {@code UnsupportedOperationException}. 289 * 290 * @throws UnsupportedOperationException always 291 * @since 21 292 */ 293 default void addLast(E e) { 294 throw new UnsupportedOperationException(); 295 } 296 297 /** 298 * {@inheritDoc} 299 * 300 * @implSpec 301 * The implementation in this interface returns the result of calling the {@code first} method. 302 * 303 * @throws NoSuchElementException {@inheritDoc} 304 * @since 21 305 */ 306 default E getFirst() { 307 return this.first(); 308 } 309 310 /** 311 * {@inheritDoc} 312 * 313 * @implSpec 314 * The implementation in this interface returns the result of calling the {@code last} method. 315 * 316 * @throws NoSuchElementException {@inheritDoc} 317 * @since 21 318 */ 319 default E getLast() { 320 return this.last(); 321 } 322 323 /** 324 * {@inheritDoc} 325 * 326 * @implSpec 327 * The implementation in this interface calls the {@code first} method to obtain the first 328 * element, then it calls {@code remove(element)} to remove the element, and then it returns 329 * the element. 330 * 331 * @throws NoSuchElementException {@inheritDoc} 332 * @throws UnsupportedOperationException {@inheritDoc} 333 * @since 21 334 */ 335 default E removeFirst() { 336 E e = this.first(); 337 this.remove(e); 338 return e; 339 } 340 341 /** 342 * {@inheritDoc} 343 * 344 * @implSpec 345 * The implementation in this interface calls the {@code last} method to obtain the last 346 * element, then it calls {@code remove(element)} to remove the element, and then it returns 347 * the element. 348 * 349 * @throws NoSuchElementException {@inheritDoc} 350 * @throws UnsupportedOperationException {@inheritDoc} 351 * @since 21 352 */ 353 default E removeLast() { 354 E e = this.last(); 355 this.remove(e); 356 return e; 357 } 358 359 /** 360 * {@inheritDoc} 361 * 362 * @implSpec 363 * The implementation in this interface returns a reverse-ordered SortedSet 364 * view. The {@code reversed()} method of the view returns a reference 365 * to this SortedSet. Other operations on the view are implemented via calls to 366 * public methods on this SortedSet. The exact relationship between calls on the 367 * view and calls on this SortedSet is unspecified. However, order-sensitive 368 * operations generally delegate to the appropriate method with the opposite 369 * orientation. For example, calling {@code getFirst} on the view results in 370 * a call to {@code getLast} on this SortedSet. 371 * 372 * @return a reverse-ordered view of this collection, as a {@code SortedSet} 373 * @since 21 374 */ 375 default SortedSet<E> reversed() { 376 return ReverseOrderSortedSetView.of(this); 377 } 378 } 379