1 /* 2 * Copyright (c) 1998, 2013, 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 <tt>Comparable</tt> 38 * interface (or be accepted by the specified comparator). Furthermore, all 39 * such elements must be <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt> 40 * (or <tt>comparator.compare(e1, e2)</tt>) must not throw a 41 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</tt> in 42 * the sorted set. Attempts to violate this restriction will cause the 43 * offending method or constructor invocation to throw a 44 * <tt>ClassCastException</tt>. 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 <tt>Set</tt> interface. (See 49 * the <tt>Comparable</tt> interface or <tt>Comparator</tt> interface for a 50 * precise definition of <i>consistent with equals</i>.) This is so because 51 * the <tt>Set</tt> interface is defined in terms of the <tt>equals</tt> 52 * operation, but a sorted set performs all element comparisons using its 53 * <tt>compareTo</tt> (or <tt>compare</tt>) 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 <tt>Set</tt> 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 <tt>Comparator</tt>, which creates an empty 64 * sorted set sorted according to the specified comparator. 3) A 65 * constructor with a single argument of type <tt>Collection</tt>, 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 <tt>SortedSet</tt>, 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 <tt>lowEndpoint</tt> to 79 * <tt>successor(highEndpoint)</tt>. For example, suppose that <tt>s</tt> 80 * is a sorted set of strings. The following idiom obtains a view 81 * containing all of the strings in <tt>s</tt> from <tt>low</tt> to 82 * <tt>high</tt>, 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 <tt>s</tt> from <tt>low</tt> to 88 * <tt>high</tt>, 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}/../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, 111 * or <tt>null</tt> 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 <tt>null</tt> 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 <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, 123 * exclusive. (If <tt>fromElement</tt> and <tt>toElement</tt> 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 <tt>IllegalArgumentException</tt> 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 * <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive 136 * @throws ClassCastException if <tt>fromElement</tt> and 137 * <tt>toElement</tt> 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 <tt>fromElement</tt> or 141 * <tt>toElement</tt> cannot be compared to elements currently in 142 * the set. 143 * @throws NullPointerException if <tt>fromElement</tt> or 144 * <tt>toElement</tt> is null and this set does not permit null 145 * elements 146 * @throws IllegalArgumentException if <tt>fromElement</tt> is 147 * greater than <tt>toElement</tt>; or if this set itself 148 * has a restricted range, and <tt>fromElement</tt> or 149 * <tt>toElement</tt> 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 <tt>toElement</tt>. 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 <tt>IllegalArgumentException</tt> 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 <tt>toElement</tt> 166 * @throws ClassCastException if <tt>toElement</tt> is not compatible 167 * with this set's comparator (or, if the set has no comparator, 168 * if <tt>toElement</tt> does not implement {@link Comparable}). 169 * Implementations may, but are not required to, throw this 170 * exception if <tt>toElement</tt> cannot be compared to elements 171 * currently in the set. 172 * @throws NullPointerException if <tt>toElement</tt> is null and 173 * this set does not permit null elements 174 * @throws IllegalArgumentException if this set itself has a 175 * restricted range, and <tt>toElement</tt> 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 <tt>fromElement</tt>. 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 <tt>IllegalArgumentException</tt> 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 <tt>fromElement</tt> 193 * @throws ClassCastException if <tt>fromElement</tt> is not compatible 194 * with this set's comparator (or, if the set has no comparator, 195 * if <tt>fromElement</tt> does not implement {@link Comparable}). 196 * Implementations may, but are not required to, throw this 197 * exception if <tt>fromElement</tt> cannot be compared to elements 198 * currently in the set. 199 * @throws NullPointerException if <tt>fromElement</tt> is null 200 * and this set does not permit null elements 201 * @throws IllegalArgumentException if this set itself has a 202 * restricted range, and <tt>fromElement</tt> 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