001 /*
002 * Copyright 1998-2006 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 package java.util;
027
028 /**
029 * A {@link Set} that further provides a <i>total ordering</i> on its elements.
030 * The elements are ordered using their {@linkplain Comparable natural
031 * ordering}, or by a {@link Comparator} typically provided at sorted
032 * set creation time. The set's iterator will traverse the set in
033 * ascending element order. Several additional operations are provided
034 * to take advantage of the ordering. (This interface is the set
035 * analogue of {@link SortedMap}.)
036 *
037 * <p>All elements inserted into a sorted set must implement the <tt>Comparable</tt>
038 * interface (or be accepted by the specified comparator). Furthermore, all
039 * such elements must be <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt>
040 * (or <tt>comparator.compare(e1, e2)</tt>) must not throw a
041 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and <tt>e2</tt> in
042 * the sorted set. Attempts to violate this restriction will cause the
043 * offending method or constructor invocation to throw a
044 * <tt>ClassCastException</tt>.
045 *
046 * <p>Note that the ordering maintained by a sorted set (whether or not an
047 * explicit comparator is provided) must be <i>consistent with equals</i> if
048 * the sorted set is to correctly implement the <tt>Set</tt> interface. (See
049 * the <tt>Comparable</tt> interface or <tt>Comparator</tt> interface for a
050 * precise definition of <i>consistent with equals</i>.) This is so because
051 * the <tt>Set</tt> interface is defined in terms of the <tt>equals</tt>
052 * operation, but a sorted set performs all element comparisons using its
053 * <tt>compareTo</tt> (or <tt>compare</tt>) method, so two elements that are
054 * deemed equal by this method are, from the standpoint of the sorted set,
055 * equal. The behavior of a sorted set <i>is</i> well-defined even if its
056 * ordering is inconsistent with equals; it just fails to obey the general
057 * contract of the <tt>Set</tt> interface.
058 *
059 * <p>All general-purpose sorted set implementation classes should
060 * provide four "standard" constructors: 1) A void (no arguments)
061 * constructor, which creates an empty sorted set sorted according to
062 * the natural ordering of its elements. 2) A constructor with a
063 * single argument of type <tt>Comparator</tt>, which creates an empty
064 * sorted set sorted according to the specified comparator. 3) A
065 * constructor with a single argument of type <tt>Collection</tt>,
066 * which creates a new sorted set with the same elements as its
067 * argument, sorted according to the natural ordering of the elements.
068 * 4) A constructor with a single argument of type <tt>SortedSet</tt>,
069 * which creates a new sorted set with the same elements and the same
070 * ordering as the input sorted set. There is no way to enforce this
071 * recommendation, as interfaces cannot contain constructors.
072 *
073 * <p>Note: several methods return subsets with restricted ranges.
074 * Such ranges are <i>half-open</i>, that is, they include their low
075 * endpoint but not their high endpoint (where applicable).
076 * If you need a <i>closed range</i> (which includes both endpoints), and
077 * the element type allows for calculation of the successor of a given
078 * value, merely request the subrange from <tt>lowEndpoint</tt> to
079 * <tt>successor(highEndpoint)</tt>. For example, suppose that <tt>s</tt>
080 * is a sorted set of strings. The following idiom obtains a view
081 * containing all of the strings in <tt>s</tt> from <tt>low</tt> to
082 * <tt>high</tt>, inclusive:<pre>
083 * SortedSet<String> sub = s.subSet(low, high+"\0");</pre>
084 *
085 * A similar technique can be used to generate an <i>open range</i> (which
086 * contains neither endpoint). The following idiom obtains a view
087 * containing all of the Strings in <tt>s</tt> from <tt>low</tt> to
088 * <tt>high</tt>, exclusive:<pre>
089 * SortedSet<String> sub = s.subSet(low+"\0", high);</pre>
090 *
091 * <p>This interface is a member of the
092 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
093 * Java Collections Framework</a>.
094 *
095 * @param <E> the type of elements maintained by this set
096 *
097 * @author Josh Bloch
098 * @version 1.38, 05/05/07
099 * @see Set
100 * @see TreeSet
101 * @see SortedMap
102 * @see Collection
103 * @see Comparable
104 * @see Comparator
105 * @see ClassCastException
106 * @since 1.2
107 */
108
109 public interface SortedSet<E> extends Set<E> {
110 /**
111 * Returns the comparator used to order the elements in this set,
112 * or <tt>null</tt> if this set uses the {@linkplain Comparable
113 * natural ordering} of its elements.
114 *
115 * @return the comparator used to order the elements in this set,
116 * or <tt>null</tt> if this set uses the natural ordering
117 * of its elements
118 */
119 Comparator<? super E> comparator();
120
121 /**
122 * Returns a view of the portion of this set whose elements range
123 * from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
124 * exclusive. (If <tt>fromElement</tt> and <tt>toElement</tt> are
125 * equal, the returned set is empty.) The returned set is backed
126 * by this set, so changes in the returned set are reflected in
127 * this set, and vice-versa. The returned set supports all
128 * optional set operations that this set supports.
129 *
130 * <p>The returned set will throw an <tt>IllegalArgumentException</tt>
131 * on an attempt to insert an element outside its range.
132 *
133 * @param fromElement low endpoint (inclusive) of the returned set
134 * @param toElement high endpoint (exclusive) of the returned set
135 * @return a view of the portion of this set whose elements range from
136 * <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive
137 * @throws ClassCastException if <tt>fromElement</tt> and
138 * <tt>toElement</tt> cannot be compared to one another using this
139 * set's comparator (or, if the set has no comparator, using
140 * natural ordering). Implementations may, but are not required
141 * to, throw this exception if <tt>fromElement</tt> or
142 * <tt>toElement</tt> cannot be compared to elements currently in
143 * the set.
144 * @throws NullPointerException if <tt>fromElement</tt> or
145 * <tt>toElement</tt> is null and this set does not permit null
146 * elements
147 * @throws IllegalArgumentException if <tt>fromElement</tt> is
148 * greater than <tt>toElement</tt>; or if this set itself
149 * has a restricted range, and <tt>fromElement</tt> or
150 * <tt>toElement</tt> lies outside the bounds of the range
151 */
152 SortedSet<E> subSet(E fromElement, E toElement);
153
154 /**
155 * Returns a view of the portion of this set whose elements are
156 * strictly less than <tt>toElement</tt>. The returned set is
157 * backed by this set, so changes in the returned set are
158 * reflected in this set, and vice-versa. The returned set
159 * supports all optional set operations that this set supports.
160 *
161 * <p>The returned set will throw an <tt>IllegalArgumentException</tt>
162 * on an attempt to insert an element outside its range.
163 *
164 * @param toElement high endpoint (exclusive) of the returned set
165 * @return a view of the portion of this set whose elements are strictly
166 * less than <tt>toElement</tt>
167 * @throws ClassCastException if <tt>toElement</tt> is not compatible
168 * with this set's comparator (or, if the set has no comparator,
169 * if <tt>toElement</tt> does not implement {@link Comparable}).
170 * Implementations may, but are not required to, throw this
171 * exception if <tt>toElement</tt> cannot be compared to elements
172 * currently in the set.
173 * @throws NullPointerException if <tt>toElement</tt> is null and
174 * this set does not permit null elements
175 * @throws IllegalArgumentException if this set itself has a
176 * restricted range, and <tt>toElement</tt> lies outside the
177 * bounds of the range
178 */
179 SortedSet<E> headSet(E toElement);
180
181 /**
182 * Returns a view of the portion of this set whose elements are
183 * greater than or equal to <tt>fromElement</tt>. The returned
184 * set is backed by this set, so changes in the returned set are
185 * reflected in this set, and vice-versa. The returned set
186 * supports all optional set operations that this set supports.
187 *
188 * <p>The returned set will throw an <tt>IllegalArgumentException</tt>
189 * on an attempt to insert an element outside its range.
190 *
191 * @param fromElement low endpoint (inclusive) of the returned set
192 * @return a view of the portion of this set whose elements are greater
193 * than or equal to <tt>fromElement</tt>
194 * @throws ClassCastException if <tt>fromElement</tt> is not compatible
195 * with this set's comparator (or, if the set has no comparator,
196 * if <tt>fromElement</tt> does not implement {@link Comparable}).
197 * Implementations may, but are not required to, throw this
198 * exception if <tt>fromElement</tt> cannot be compared to elements
199 * currently in the set.
200 * @throws NullPointerException if <tt>fromElement</tt> is null
201 * and this set does not permit null elements
202 * @throws IllegalArgumentException if this set itself has a
203 * restricted range, and <tt>fromElement</tt> lies outside the
204 * bounds of the range
205 */
206 SortedSet<E> tailSet(E fromElement);
207
208 /**
209 * Returns the first (lowest) element currently in this set.
210 *
211 * @return the first (lowest) element currently in this set
212 * @throws NoSuchElementException if this set is empty
213 */
214 E first();
215
216 /**
217 * Returns the last (highest) element currently in this set.
218 *
219 * @return the last (highest) element currently in this set
220 * @throws NoSuchElementException if this set is empty
221 */
222 E last();
223 }
|