ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/TreeSet.java

Comparing jsr166/src/main/java/util/TreeSet.java (file contents):
Revision 1.9 by jsr166, Mon May 2 21:44:01 2005 UTC vs.
Revision 1.25 by jsr166, Sun Jan 7 07:38:27 2007 UTC

#	Line 1 | Line 1
1		/*
2		* %W% %E%
3		*
4	<	* Copyright 2005 Sun Microsystems, Inc. All rights reserved.
4	>	* Copyright 2007 Sun Microsystems, Inc. All rights reserved.
5		* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6		*/
7
8		package java.util;
9
10		/**
11	<	* This class implements the <tt>Set</tt> interface, backed by a
12	<	* <tt>TreeMap</tt> instance.  This class guarantees that the sorted set will
13	<	* be in ascending element order, sorted according to the <i>natural order</i>
14	<	* of the elements (see <tt>Comparable</tt>), or by the comparator provided at
15	<	* set creation time, depending on which constructor is used.<p>
11	>	* A {@link NavigableSet} implementation based on a {@link TreeMap}.
12	>	* The elements are ordered using their {@linkplain Comparable natural
13	>	* ordering}, or by a {@link Comparator} provided at set creation
14	>	* time, depending on which constructor is used.
15		*
16	<	* This implementation provides guaranteed log(n) time cost for the basic
17	<	* operations (<tt>add</tt>, <tt>remove</tt> and <tt>contains</tt>).<p>
16	>	* <p>This implementation provides guaranteed log(n) time cost for the basic
17	>	* operations ({@code add}, {@code remove} and {@code contains}).
18		*
19	<	* Note that the ordering maintained by a set (whether or not an explicit
19	>	* <p>Note that the ordering maintained by a set (whether or not an explicit
20		* comparator is provided) must be <i>consistent with equals</i> if it is to
21	<	* correctly implement the <tt>Set</tt> interface.  (See <tt>Comparable</tt>
22	<	* or <tt>Comparator</tt> for a precise definition of <i>consistent with
23	<	* equals</i>.)  This is so because the <tt>Set</tt> interface is defined in
24	<	* terms of the <tt>equals</tt> operation, but a <tt>TreeSet</tt> instance
25	<	* performs all key comparisons using its <tt>compareTo</tt> (or
26	<	* <tt>compare</tt>) method, so two keys that are deemed equal by this method
21	>	* correctly implement the {@code Set} interface.  (See {@code Comparable}
22	>	* or {@code Comparator} for a precise definition of <i>consistent with
23	>	* equals</i>.)  This is so because the {@code Set} interface is defined in
24	>	* terms of the {@code equals} operation, but a {@code TreeSet} instance
25	>	* performs all element comparisons using its {@code compareTo} (or
26	>	* {@code compare}) method, so two elements that are deemed equal by this method
27		* are, from the standpoint of the set, equal.  The behavior of a set
28		* <i>is</i> well-defined even if its ordering is inconsistent with equals; it
29	<	* just fails to obey the general contract of the <tt>Set</tt> interface.<p>
29	>	* just fails to obey the general contract of the {@code Set} interface.
30		*
31	<	* <b>Note that this implementation is not synchronized.</b> If multiple
32	<	* threads access a set concurrently, and at least one of the threads modifies
33	<	* the set, it <i>must</i> be synchronized externally.  This is typically
34	<	* accomplished by synchronizing on some object that naturally encapsulates
35	<	* the set.  If no such object exists, the set should be "wrapped" using the
36	<	* <tt>Collections.synchronizedSet</tt> method.  This is best done at creation
37	<	* time, to prevent accidental unsynchronized access to the set: <pre>
38	<	*     SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
39	<	* </pre><p>
31	>	* <p><strong>Note that this implementation is not synchronized.</strong>
32	>	* If multiple threads access a tree set concurrently, and at least one
33	>	* of the threads modifies the set, it <i>must</i> be synchronized
34	>	* externally.  This is typically accomplished by synchronizing on some
35	>	* object that naturally encapsulates the set.
36	>	* If no such object exists, the set should be "wrapped" using the
37	>	* {@link Collections#synchronizedSortedSet Collections.synchronizedSortedSet}
38	>	* method.  This is best done at creation time, to prevent accidental
39	>	* unsynchronized access to the set: <pre>
40	>	*   SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));</pre>
41		*
42	<	* The Iterators returned by this class's <tt>iterator</tt> method are
42	>	* <p>The iterators returned by this class's {@code iterator} method are
43		* <i>fail-fast</i>: if the set is modified at any time after the iterator is
44	<	* created, in any way except through the iterator's own <tt>remove</tt>
45	<	* method, the iterator will throw a <tt>ConcurrentModificationException</tt>.
44	>	* created, in any way except through the iterator's own {@code remove}
45	>	* method, the iterator will throw a {@link ConcurrentModificationException}.
46		* Thus, in the face of concurrent modification, the iterator fails quickly
47		* and cleanly, rather than risking arbitrary, non-deterministic behavior at
48		* an undetermined time in the future.
#	Line 50 | Line 50 | package java.util;
50		* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
51		* as it is, generally speaking, impossible to make any hard guarantees in the
52		* presence of unsynchronized concurrent modification.  Fail-fast iterators
53	<	* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
53	>	* throw {@code ConcurrentModificationException} on a best-effort basis.
54		* Therefore, it would be wrong to write a program that depended on this
55		* exception for its correctness:   <i>the fail-fast behavior of iterators
56	<	* should be used only to detect bugs.</i><p>
56	>	* should be used only to detect bugs.</i>
57		*
58	<	* This class is a member of the
59	<	* <a href="{@docRoot}/../guide/collections/index.html">
58	>	* <p>This class is a member of the
59	>	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
60		* Java Collections Framework</a>.
61		*
62	+	* @param <E> the type of elements maintained by this set
63	+	*
64		* @author  Josh Bloch
65		* @version %I%, %G%
66		* @see     Collection
#	Line 66 | Line 68 | package java.util;
68		* @see     HashSet
69		* @see     Comparable
70		* @see     Comparator
69	–	* @see     Collections#synchronizedSortedSet(SortedSet)
71		* @see     TreeMap
72		* @since   1.2
73		*/
74
75	<	public class TreeSet<E>
75	<	extends AbstractSet<E>
75	>	public class TreeSet<E> extends AbstractSet<E>
76		implements NavigableSet<E>, Cloneable, java.io.Serializable
77		{
78	<	private transient NavigableMap<E,Object> m; // The backing Map
78	>	/**
79	>	* The backing map.
80	>	*/
81	>	private transient NavigableMap<E,Object> m;
82
83		// Dummy value to associate with an Object in the backing Map
84		private static final Object PRESENT = new Object();
85
86		/**
87	<	* Constructs a set backed by the specified sorted map.
87	>	* Constructs a set backed by the specified navigable map.
88		*/
89	<	private TreeSet(NavigableMap<E,Object> m) {
89	>	TreeSet(NavigableMap<E,Object> m) {
90		this.m = m;
91		}
92
93		/**
94	<	* Constructs a new, empty set, sorted according to the elements' natural
95	<	* order.  All elements inserted into the set must implement the
96	<	* <tt>Comparable</tt> interface.  Furthermore, all such elements must be
97	<	* <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt> must not throw a
98	<	* <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
99	<	* <tt>e2</tt> in the set.  If the user attempts to add an element to the
100	<	* set that violates this constraint (for example, the user attempts to
101	<	* add a string element to a set whose elements are integers), the
102	<	* <tt>add(Object)</tt> call will throw a <tt>ClassCastException</tt>.
103	<	*
104	<	* @see Comparable
94	>	* Constructs a new, empty tree set, sorted according to the
95	>	* natural ordering of its elements.  All elements inserted into
96	>	* the set must implement the {@link Comparable} interface.
97	>	* Furthermore, all such elements must be <i>mutually
98	>	* comparable</i>: {@code e1.compareTo(e2)} must not throw a
99	>	* {@code ClassCastException} for any elements {@code e1} and
100	>	* {@code e2} in the set.  If the user attempts to add an element
101	>	* to the set that violates this constraint (for example, the user
102	>	* attempts to add a string element to a set whose elements are
103	>	* integers), the {@code add} call will throw a
104	>	* {@code ClassCastException}.
105		*/
106		public TreeSet() {
107		this(new TreeMap<E,Object>());
108		}
109
110		/**
111	<	* Constructs a new, empty set, sorted according to the specified
111	>	* Constructs a new, empty tree set, sorted according to the specified
112		* comparator.  All elements inserted into the set must be <i>mutually
113	<	* comparable</i> by the specified comparator: <tt>comparator.compare(e1,
114	<	* e2)</tt> must not throw a <tt>ClassCastException</tt> for any elements
115	<	* <tt>e1</tt> and <tt>e2</tt> in the set.  If the user attempts to add
113	>	* comparable</i> by the specified comparator: {@code comparator.compare(e1,
114	>	* e2)} must not throw a {@code ClassCastException} for any elements
115	>	* {@code e1} and {@code e2} in the set.  If the user attempts to add
116		* an element to the set that violates this constraint, the
117	<	* <tt>add(Object)</tt> call will throw a <tt>ClassCastException</tt>.
117	>	* {@code add} call will throw a {@code ClassCastException}.
118		*
119	<	* @param c the comparator that will be used to sort this set.  A
120	<	*        <tt>null</tt> value indicates that the elements' <i>natural
121	<	*        ordering</i> should be used.
119	>	* @param comparator the comparator that will be used to order this set.
120	>	*        If {@code null}, the {@linkplain Comparable natural
121	>	*        ordering} of the elements will be used.
122		*/
123	<	public TreeSet(Comparator<? super E> c) {
124	<	this(new TreeMap<E,Object>(c));
123	>	public TreeSet(Comparator<? super E> comparator) {
124	>	this(new TreeMap<E,Object>(comparator));
125		}
126
127		/**
128	<	* Constructs a new set containing the elements in the specified
129	<	* collection, sorted according to the elements' <i>natural order</i>.
130	<	* All keys inserted into the set must implement the <tt>Comparable</tt>
131	<	* interface.  Furthermore, all such keys must be <i>mutually
132	<	* comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
133	<	* <tt>ClassCastException</tt> for any elements <tt>k1</tt> and
134	<	* <tt>k2</tt> in the set.
128	>	* Constructs a new tree set containing the elements in the specified
129	>	* collection, sorted according to the <i>natural ordering</i> of its
130	>	* elements.  All elements inserted into the set must implement the
131	>	* {@link Comparable} interface.  Furthermore, all such elements must be
132	>	* <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a
133	>	* {@code ClassCastException} for any elements {@code e1} and
134	>	* {@code e2} in the set.
135		*
136	<	* @param c The elements that will comprise the new set.
137	<	*
138	<	* @throws ClassCastException if the keys in the specified collection are
139	<	*         not comparable, or are not mutually comparable.
137	<	* @throws NullPointerException if the specified collection is null.
136	>	* @param c collection whose elements will comprise the new set
137	>	* @throws ClassCastException if the elements in {@code c} are
138	>	*         not {@link Comparable}, or are not mutually comparable
139	>	* @throws NullPointerException if the specified collection is null
140		*/
141		public TreeSet(Collection<? extends E> c) {
142		this();
#	Line 142 | Line 144 | public class TreeSet<E>
144		}
145
146		/**
147	<	* Constructs a new set containing the same elements as the specified
148	<	* sorted set, sorted according to the same ordering.
147	>	* Constructs a new tree set containing the same elements and
148	>	* using the same ordering as the specified sorted set.
149		*
150	<	* @param s sorted set whose elements will comprise the new set.
151	<	* @throws NullPointerException if the specified sorted set is null.
150	>	* @param s sorted set whose elements will comprise the new set
151	>	* @throws NullPointerException if the specified sorted set is null
152		*/
153		public TreeSet(SortedSet<E> s) {
154		this(s.comparator());
#	Line 154 | Line 156 | public class TreeSet<E>
156		}
157
158		/**
159	<	* Returns an iterator over the elements in this set.  The elements
158	<	* are returned in ascending order.
159	>	* Returns an iterator over the elements in this set in ascending order.
160		*
161	<	* @return an iterator over the elements in this set.
161	>	* @return an iterator over the elements in this set in ascending order
162		*/
163		public Iterator<E> iterator() {
164	<	return m.keySet().iterator();
164	>	return m.navigableKeySet().iterator();
165		}
166
167		/**
168	<	* Returns an iterator over the elements in this set.  The elements
168	<	* are returned in descending order.
168	>	* Returns an iterator over the elements in this set in descending order.
169		*
170	<	* @return an iterator over the elements in this set.
170	>	* @return an iterator over the elements in this set in descending order
171	>	* @since 1.6
172		*/
173		public Iterator<E> descendingIterator() {
174		return m.descendingKeySet().iterator();
175		}
176
177		/**
178	+	* @since 1.6
179	+	*/
180	+	public NavigableSet<E> descendingSet() {
181	+	return new TreeSet(m.descendingMap());
182	+	}
183	+
184	+	/**
185		* Returns the number of elements in this set (its cardinality).
186		*
187	<	* @return the number of elements in this set (its cardinality).
187	>	* @return the number of elements in this set (its cardinality)
188		*/
189		public int size() {
190		return m.size();
191		}
192
193		/**
194	<	* Returns <tt>true</tt> if this set contains no elements.
194	>	* Returns {@code true} if this set contains no elements.
195		*
196	<	* @return <tt>true</tt> if this set contains no elements.
196	>	* @return {@code true} if this set contains no elements
197		*/
198		public boolean isEmpty() {
199		return m.isEmpty();
200		}
201
202		/**
203	<	* Returns <tt>true</tt> if this set contains the specified element.
204	<	*
205	<	* @param o the object to be checked for containment in this set.
206	<	* @return <tt>true</tt> if this set contains the specified element.
203	>	* Returns {@code true} if this set contains the specified element.
204	>	* More formally, returns {@code true} if and only if this set
205	>	* contains an element {@code e} such that
206	>	* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
207		*
208	+	* @param o object to be checked for containment in this set
209	+	* @return {@code true} if this set contains the specified element
210		* @throws ClassCastException if the specified object cannot be compared
211	<	*            with the elements currently in the set.
212	<	* @throws NullPointerException if o is <tt>null</tt> and this map
213	<	* uses natural ordering and is non-empty, or its comparator does
214	<	* not tolerate <tt>null</tt> keys.
211	>	*         with the elements currently in the set
212	>	* @throws NullPointerException if the specified element is null
213	>	*         and this set uses natural ordering, or its comparator
214	>	*         does not permit null elements
215		*/
216		public boolean contains(Object o) {
217		return m.containsKey(o);
#	Line 209 | Line 219 | public class TreeSet<E>
219
220		/**
221		* Adds the specified element to this set if it is not already present.
222	<	*
223	<	* @param e element to be added to this set.
224	<	* @return <tt>true</tt> if the set did not already contain the specified
225	<	*         element.
226	<	*
222	>	* More formally, adds the specified element {@code e} to this set if
223	>	* the set contains no element {@code e2} such that
224	>	* <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
225	>	* If this set already contains the element, the call leaves the set
226	>	* unchanged and returns {@code false}.
227	>	*
228	>	* @param e element to be added to this set
229	>	* @return {@code true} if this set did not already contain the specified
230	>	*         element
231		* @throws ClassCastException if the specified object cannot be compared
232	<	*            with the elements currently in the set.
233	<	* @throws NullPointerException if e is <tt>null</tt> and this map
234	<	* uses natural ordering and is non-empty, or its comparator does
235	<	* not tolerate <tt>null</tt> keys.
232	>	*         with the elements currently in this set
233	>	* @throws NullPointerException if the specified element is null
234	>	*         and this set uses natural ordering, or its comparator
235	>	*         does not permit null elements
236		*/
237		public boolean add(E e) {
238		return m.put(e, PRESENT)==null;
#	Line 226 | Line 240 | public class TreeSet<E>
240
241		/**
242		* Removes the specified element from this set if it is present.
243	+	* More formally, removes an element {@code e} such that
244	+	* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
245	+	* if this set contains such an element.  Returns {@code true} if
246	+	* this set contained the element (or equivalently, if this set
247	+	* changed as a result of the call).  (This set will not contain the
248	+	* element once the call returns.)
249		*
250	<	* @param o object to be removed from this set, if present.
251	<	* @return <tt>true</tt> if the set contained the specified element.
232	<	*
250	>	* @param o object to be removed from this set, if present
251	>	* @return {@code true} if this set contained the specified element
252		* @throws ClassCastException if the specified object cannot be compared
253	<	*            with the elements currently in the set.
254	<	* @throws NullPointerException if o is <tt>null</tt> and this map
255	<	* uses natural ordering and is non-empty, or its comparator does
256	<	* not tolerate <tt>null</tt> keys.
253	>	*         with the elements currently in this set
254	>	* @throws NullPointerException if the specified element is null
255	>	*         and this set uses natural ordering, or its comparator
256	>	*         does not permit null elements
257		*/
258		public boolean remove(Object o) {
259		return m.remove(o)==PRESENT;
#	Line 242 | Line 261 | public class TreeSet<E>
261
262		/**
263		* Removes all of the elements from this set.
264	+	* The set will be empty after this call returns.
265		*/
266		public void clear() {
267		m.clear();
#	Line 250 | Line 270 | public class TreeSet<E>
270		/**
271		* Adds all of the elements in the specified collection to this set.
272		*
273	<	* @param c elements to be added
274	<	* @return <tt>true</tt> if this set changed as a result of the call.
255	<	*
273	>	* @param c collection containing elements to be added to this set
274	>	* @return {@code true} if this set changed as a result of the call
275		* @throws ClassCastException if the elements provided cannot be compared
276	<	*            with the elements currently in the set.
277	<	* @throws NullPointerException if the specified collection is
278	<	* <tt>null</tt> or if any element is <tt>null</tt> and this map
279	<	* uses natural ordering, or its comparator does not tolerate
261	<	* <tt>null</tt> keys.
276	>	*         with the elements currently in the set
277	>	* @throws NullPointerException if the specified collection is null or
278	>	*         if any element is null and this set uses natural ordering, or
279	>	*         its comparator does not permit null elements
280		*/
281		public  boolean addAll(Collection<? extends E> c) {
282		// Use linear-time version if applicable
#	Line 278 | Line 296 | public class TreeSet<E>
296		}
297
298		/**
299	<	* Returns a view of the portion of this set whose elements range
300	<	* from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
301	<	* exclusive.  (If <tt>fromElement</tt> and <tt>toElement</tt> are
302	<	* equal, the returned navigable set is empty.)  The returned
303	<	* navigable set is backed by this set, so changes in the returned
304	<	* navigable set are reflected in this set, and vice-versa.  The
305	<	* returned navigable set supports all optional Set operations.<p>
306	<	*
307	<	* The navigable set returned by this method will throw an
308	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert an
309	<	* element outside the specified range.<p>
310	<	*
311	<	* Note: this method always returns a <i>half-open range</i>
312	<	* (which includes its low endpoint but not its high endpoint).
313	<	* If you need a <i>closed range</i> (which includes both
314	<	* endpoints), and the element type allows for calculation of the
315	<	* successor of a specified value, merely request the subrange
316	<	* from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
317	<	* For example, suppose that <tt>s</tt> is a navigable set of
318	<	* strings.  The following idiom obtains a view containing all of
319	<	* the strings in <tt>s</tt> from <tt>low</tt> to <tt>high</tt>,
320	<	* inclusive:
321	<	* <pre> NavigableSet sub = s.navigableSubSet(low, high+"\0");
322	<	* </pre>
323	<	*
324	<	* A similar technique can be used to generate an <i>open range</i> (which
325	<	* contains neither endpoint).  The following idiom obtains a view
326	<	* containing all of the strings in <tt>s</tt> from <tt>low</tt> to
327	<	* <tt>high</tt>, exclusive: <pre>
328	<	*     NavigableSet sub = s.navigableSubSet(low+"\0", high);
329	<	* </pre>
330	<	*
331	<	* @param fromElement low endpoint (inclusive) of the range.
332	<	* @param toElement high endpoint (exclusive) of the range.
333	<	* @return a view of the portion of this set whose elements range from
334	<	*         <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
335	<	*         exclusive.
336	<	* @throws ClassCastException if <tt>fromElement</tt> and
337	<	*         <tt>toElement</tt> cannot be compared to one another using
338	<	*         this set's comparator (or, if the set has no comparator,
339	<	*         using natural ordering).
340	<	* @throws IllegalArgumentException if <tt>fromElement</tt> is greater than
341	<	*         <tt>toElement</tt>.
324	<	* @throws NullPointerException if <tt>fromElement</tt> or
325	<	*         <tt>toElement</tt> is <tt>null</tt> and this set uses natural
326	<	*         order, or its comparator does not tolerate <tt>null</tt>
327	<	*         elements.
328	<	*/
329	<	public NavigableSet<E> navigableSubSet(E fromElement, E toElement) {
330	<	return new TreeSet<E>(m.navigableSubMap(fromElement, toElement));
331	<	}
332	<
333	<	/**
334	<	* Returns a view of the portion of this set whose elements are
335	<	* strictly less than <tt>toElement</tt>.  The returned navigable
336	<	* set is backed by this set, so changes in the returned navigable
337	<	* set are reflected in this set, and vice-versa.  The returned
338	<	* navigable set supports all optional set operations.<p>
339	<	*
340	<	* The navigable set returned by this method will throw an
341	<	* <tt>IllegalArgumentException</tt> if the user attempts to
342	<	* insert an element greater than or equal to
343	<	* <tt>toElement</tt>.<p>
344	<	*
345	<	* Note: this method always returns a view that does not contain
346	<	* its (high) endpoint.  If you need a view that does contain this
347	<	* endpoint, and the element type allows for calculation of the
348	<	* successor of a specified value, merely request a headSet
349	<	* bounded by <tt>successor(highEndpoint)</tt>.  For example,
350	<	* suppose that <tt>s</tt> is a navigable set of strings.  The
351	<	* following idiom obtains a view containing all of the strings in
352	<	* <tt>s</tt> that are less than or equal to <tt>high</tt>:
353	<	* <pre> NavigableSet head = s.navigableHeadSet(high+"\0");</pre>
354	<	*
355	<	* @param toElement high endpoint (exclusive) of the headSet.
356	<	* @return a view of the portion of this set whose elements are strictly
357	<	*         less than <tt>toElement</tt>.
358	<	* @throws ClassCastException if <tt>toElement</tt> is not compatible
359	<	*         with this set's comparator (or, if the set has no comparator,
360	<	*         if <tt>toElement</tt> does not implement <tt>Comparable</tt>).
361	<	* @throws IllegalArgumentException if this set is itself a subset,
362	<	*         and <tt>toElement</tt> is not within the
363	<	*         specified range of the subset.
364	<	* @throws NullPointerException if <tt>toElement</tt> is <tt>null</tt> and
365	<	*         this set uses natural ordering, or its comparator does
366	<	*         not tolerate <tt>null</tt> elements.
367	<	*/
368	<	public NavigableSet<E> navigableHeadSet(E toElement) {
369	<	return new TreeSet<E>(m.navigableHeadMap(toElement));
370	<	}
371	<
372	<	/**
373	<	* Returns a view of the portion of this set whose elements are
374	<	* greater than or equal to <tt>fromElement</tt>.  The returned
375	<	* navigable set is backed by this set, so changes in the returned
376	<	* navigable set are reflected in this set, and vice-versa.  The
377	<	* returned navigable set supports all optional set operations.<p>
378	<	*
379	<	* The navigable set returned by this method will throw an
380	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert an
381	<	* element less than <tt>fromElement</tt>.
382	<	*
383	<	* Note: this method always returns a view that contains its (low)
384	<	* endpoint.  If you need a view that does not contain this
385	<	* endpoint, and the element type allows for calculation of the
386	<	* successor of a specified value, merely request a tailSet
387	<	* bounded by <tt>successor(lowEndpoint)</tt>.  For example,
388	<	* suppose that <tt>s</tt> is a navigable set of strings.  The
389	<	* following idiom obtains a view containing all of the strings in
390	<	* <tt>s</tt> that are strictly greater than <tt>low</tt>:
391	<	* <pre>  NavigableSet tail = s.navigableTailSet(low+"\0");
392	<	* </pre>
393	<	*
394	<	* @param fromElement low endpoint (inclusive) of the tailSet.
395	<	* @return a view of the portion of this set whose elements are
396	<	*         greater than or equal to <tt>fromElement</tt>.
397	<	* @throws ClassCastException if <tt>fromElement</tt> is not compatible
398	<	*         with this set's comparator (or, if the set has no comparator,
399	<	*         if <tt>fromElement</tt> does not implement <tt>Comparable</tt>).
400	<	* @throws IllegalArgumentException if this set is itself a subset,
401	<	*         and <tt>fromElement</tt> is not within the
402	<	*         specified range of the subset.
403	<	* @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>
404	<	*         and this set uses natural ordering, or its comparator does
405	<	*         not tolerate <tt>null</tt> elements.
406	<	*/
407	<	public NavigableSet<E> navigableTailSet(E fromElement) {
408	<	return new TreeSet<E>(m.navigableTailMap(fromElement));
409	<	}
410	<
411	<
412	<	/**
413	<	* Equivalent to <tt>navigableSubSet</tt> but with a return
414	<	* type conforming to the <tt>SortedSet</tt> interface.
415	<	* @param fromElement low endpoint (inclusive) of the range.
416	<	* @param toElement high endpoint (exclusive) of the range.
417	<	* @return a view of the portion of this set whose elements range from
418	<	*         <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
419	<	*         exclusive.
420	<	* @throws ClassCastException if <tt>fromElement</tt> and
421	<	*         <tt>toElement</tt> cannot be compared to one another using
422	<	*         this set's comparator (or, if the set has no comparator,
423	<	*         using natural ordering).
424	<	* @throws IllegalArgumentException if <tt>fromElement</tt> is greater than
425	<	*         <tt>toElement</tt>.
426	<	* @throws NullPointerException if <tt>fromElement</tt> or
427	<	*         <tt>toElement</tt> is <tt>null</tt> and this set uses natural
428	<	*         order, or its comparator does not tolerate <tt>null</tt>
429	<	*         elements.
299	>	* @throws ClassCastException {@inheritDoc}
300	>	* @throws NullPointerException if {@code fromElement} or {@code toElement}
301	>	*         is null and this set uses natural ordering, or its comparator
302	>	*         does not permit null elements
303	>	* @throws IllegalArgumentException {@inheritDoc}
304	>	* @since 1.6
305	>	*/
306	>	public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
307	>	E toElement,   boolean toInclusive) {
308	>	return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
309	>	toElement,   toInclusive));
310	>	}
311	>
312	>	/**
313	>	* @throws ClassCastException {@inheritDoc}
314	>	* @throws NullPointerException if {@code toElement} is null and
315	>	*         this set uses natural ordering, or its comparator does
316	>	*         not permit null elements
317	>	* @throws IllegalArgumentException {@inheritDoc}
318	>	* @since 1.6
319	>	*/
320	>	public NavigableSet<E> headSet(E toElement, boolean inclusive) {
321	>	return new TreeSet<E>(m.headMap(toElement, inclusive));
322	>	}
323	>
324	>	/**
325	>	* @throws ClassCastException {@inheritDoc}
326	>	* @throws NullPointerException if {@code fromElement} is null and
327	>	*         this set uses natural ordering, or its comparator does
328	>	*         not permit null elements
329	>	* @throws IllegalArgumentException {@inheritDoc}
330	>	* @since 1.6
331	>	*/
332	>	public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
333	>	return new TreeSet<E>(m.tailMap(fromElement, inclusive));
334	>	}
335	>
336	>	/**
337	>	* @throws ClassCastException {@inheritDoc}
338	>	* @throws NullPointerException if {@code fromElement} or
339	>	*         {@code toElement} is null and this set uses natural ordering,
340	>	*         or its comparator does not permit null elements
341	>	* @throws IllegalArgumentException {@inheritDoc}
342		*/
343		public SortedSet<E> subSet(E fromElement, E toElement) {
344	<	return new TreeSet<E>(m.navigableSubMap(fromElement, toElement));
344	>	return subSet(fromElement, true, toElement, false);
345		}
346
347		/**
348	<	* Equivalent to <tt>navigableHeadSet</tt> but with a return
349	<	* type conforming to the <tt>SortedSet</tt> interface.
350	<	*
351	<	* @param toElement high endpoint (exclusive) of the headSet.
352	<	* @return a view of the portion of this set whose elements are strictly
441	<	*         less than <tt>toElement</tt>.
442	<	* @throws ClassCastException if <tt>toElement</tt> is not compatible
443	<	*         with this set's comparator (or, if the set has no comparator,
444	<	*         if <tt>toElement</tt> does not implement <tt>Comparable</tt>).
445	<	* @throws IllegalArgumentException if this set is itself a subset,
446	<	*         and <tt>toElement</tt> is not within the
447	<	*         specified range of the subset.
448	<	* @throws NullPointerException if <tt>toElement</tt> is <tt>null</tt> and
449	<	*         this set uses natural ordering, or its comparator does
450	<	*         not tolerate <tt>null</tt> elements.
348	>	* @throws ClassCastException {@inheritDoc}
349	>	* @throws NullPointerException if {@code toElement} is null
350	>	*         and this set uses natural ordering, or its comparator does
351	>	*         not permit null elements
352	>	* @throws IllegalArgumentException {@inheritDoc}
353		*/
354		public SortedSet<E> headSet(E toElement) {
355	<	return new TreeSet<E>(m.navigableHeadMap(toElement));
355	>	return headSet(toElement, false);
356		}
357
358		/**
359	<	* Equivalent to <tt>navigableTailSet</tt> but with a return
360	<	* type conforming to the <tt>SortedSet</tt> interface.
361	<	* @param fromElement low endpoint (inclusive) of the tailSet.
362	<	* @return a view of the portion of this set whose elements are
363	<	*         greater than or equal to <tt>fromElement</tt>.
462	<	* @throws ClassCastException if <tt>fromElement</tt> is not compatible
463	<	*         with this set's comparator (or, if the set has no comparator,
464	<	*         if <tt>fromElement</tt> does not implement <tt>Comparable</tt>).
465	<	* @throws IllegalArgumentException if this set is itself a subset,
466	<	*         and <tt>fromElement</tt> is not within the
467	<	*         specified range of the subset.
468	<	* @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>
469	<	*         and this set uses natural ordering, or its comparator does
470	<	*         not tolerate <tt>null</tt> elements.
359	>	* @throws ClassCastException {@inheritDoc}
360	>	* @throws NullPointerException if {@code fromElement} is null
361	>	*         and this set uses natural ordering, or its comparator does
362	>	*         not permit null elements
363	>	* @throws IllegalArgumentException {@inheritDoc}
364		*/
365		public SortedSet<E> tailSet(E fromElement) {
366	<	return new TreeSet<E>(m.navigableTailMap(fromElement));
366	>	return tailSet(fromElement, true);
367		}
368
476	–	/**
477	–	* Returns the comparator used to order this sorted set, or <tt>null</tt>
478	–	* if this tree set uses its elements natural ordering.
479	–	*
480	–	* @return the comparator used to order this sorted set, or <tt>null</tt>
481	–	* if this tree set uses its elements natural ordering.
482	–	*/
369		public Comparator<? super E> comparator() {
370		return m.comparator();
371		}
372
373		/**
374	<	* Returns the first (lowest) element currently in this sorted set.
489	<	*
490	<	* @return the first (lowest) element currently in this sorted set.
491	<	* @throws    NoSuchElementException sorted set is empty.
374	>	* @throws NoSuchElementException {@inheritDoc}
375		*/
376		public E first() {
377		return m.firstKey();
378		}
379
380		/**
381	<	* Returns the last (highest) element currently in this sorted set.
499	<	*
500	<	* @return the last (highest) element currently in this sorted set.
501	<	* @throws    NoSuchElementException sorted set is empty.
381	>	* @throws NoSuchElementException {@inheritDoc}
382		*/
383		public E last() {
384		return m.lastKey();
#	Line 506 | Line 386 | public class TreeSet<E>
386
387		// NavigableSet API methods
388
509	–
510	–	/**
511	–	* Returns an element greater than or equal to the given element, or
512	–	* <tt>null</tt> if there is no such element.
513	–	*
514	–	* @param e the value to match
515	–	* @return an element greater than or equal to given element, or
516	–	* <tt>null</tt> if there is no such element.
517	–	* @throws ClassCastException if e cannot be compared with the elements
518	–	*            currently in the set.
519	–	* @throws NullPointerException if e is <tt>null</tt> and this map
520	–	* uses natural ordering and is non-empty, or its comparator does
521	–	* not tolerate <tt>null</tt> keys.
522	–	*/
523	–	public E ceiling(E e) {
524	–	return m.ceilingKey(e);
525	–	}
526	–
389		/**
390	<	* Returns an element strictly less than the given element, or
391	<	* <tt>null</tt> if there is no such element.
392	<	*
393	<	* @param e the value to match
394	<	* @return the greatest element less than the given element, or
533	<	* <tt>null</tt> if there is no such element.
534	<	* @throws ClassCastException if e cannot be compared with the elements
535	<	*            currently in the set.
536	<	* @throws NullPointerException if e is <tt>null</tt> and this map
537	<	* uses natural ordering and is non-empty, or its comparator does
538	<	* not tolerate <tt>null</tt> keys.
390	>	* @throws ClassCastException {@inheritDoc}
391	>	* @throws NullPointerException if the specified element is null
392	>	*         and this set uses natural ordering, or its comparator
393	>	*         does not permit null elements
394	>	* @since 1.6
395		*/
396		public E lower(E e) {
397		return m.lowerKey(e);
398		}
399
400		/**
401	<	* Returns an element less than or equal to the given element, or
402	<	* <tt>null</tt> if there is no such element.
403	<	*
404	<	* @param e the value to match
405	<	* @return the greatest element less than or equal to given
550	<	* element, or <tt>null</tt> if there is no such element.
551	<	* @throws ClassCastException if e cannot be compared with the elements
552	<	*            currently in the set.
553	<	* @throws NullPointerException if e is <tt>null</tt> and this map
554	<	* uses natural ordering and is non-empty, or its comparator does
555	<	* not tolerate <tt>null</tt> keys.
401	>	* @throws ClassCastException {@inheritDoc}
402	>	* @throws NullPointerException if the specified element is null
403	>	*         and this set uses natural ordering, or its comparator
404	>	*         does not permit null elements
405	>	* @since 1.6
406		*/
407		public E floor(E e) {
408		return m.floorKey(e);
409		}
410
411		/**
412	<	* Returns an element strictly greater than the given element, or
413	<	* <tt>null</tt> if there is no such element.
414	<	*
415	<	* @param e the value to match
416	<	* @return the least element greater than the given element, or
417	<	* <tt>null</tt> if there is no such element.
418	<	* @throws ClassCastException if e cannot be compared with the elements
419	<	*            currently in the set.
420	<	* @throws NullPointerException if e is <tt>null</tt> and this map
421	<	* uses natural ordering and is non-empty, or its comparator does
422	<	* not tolerate <tt>null</tt> keys.
412	>	* @throws ClassCastException {@inheritDoc}
413	>	* @throws NullPointerException if the specified element is null
414	>	*         and this set uses natural ordering, or its comparator
415	>	*         does not permit null elements
416	>	* @since 1.6
417	>	*/
418	>	public E ceiling(E e) {
419	>	return m.ceilingKey(e);
420	>	}
421	>
422	>	/**
423	>	* @throws ClassCastException {@inheritDoc}
424	>	* @throws NullPointerException if the specified element is null
425	>	*         and this set uses natural ordering, or its comparator
426	>	*         does not permit null elements
427	>	* @since 1.6
428		*/
429		public E higher(E e) {
430		return m.higherKey(e);
431		}
432
433		/**
434	<	* Retrieves and removes the first (lowest) element.
580	<	*
581	<	* @return the least element, or <tt>null</tt> if empty.
434	>	* @since 1.6
435		*/
436		public E pollFirst() {
437		Map.Entry<E,?> e = m.pollFirstEntry();
#	Line 586 | Line 439 | public class TreeSet<E>
439		}
440
441		/**
442	<	* Retrieves and removes the last (highest) element.
590	<	*
591	<	* @return the last element, or <tt>null</tt> if empty.
442	>	* @since 1.6
443		*/
444		public E pollLast() {
445		Map.Entry<E,?> e = m.pollLastEntry();
#	Line 596 | Line 447 | public class TreeSet<E>
447		}
448
449		/**
450	<	* Returns a shallow copy of this <tt>TreeSet</tt> instance. (The elements
450	>	* Returns a shallow copy of this {@code TreeSet} instance. (The elements
451		* themselves are not cloned.)
452		*
453	<	* @return a shallow copy of this set.
453	>	* @return a shallow copy of this set
454		*/
455		public Object clone() {
456		TreeSet<E> clone = null;
#	Line 610 | Line 461 | public class TreeSet<E>
461		}
462
463		clone.m = new TreeMap<E,Object>(m);
613	–
464		return clone;
465		}
466
467		/**
468	<	* Save the state of the <tt>TreeSet</tt> instance to a stream (that is,
468	>	* Save the state of the {@code TreeSet} instance to a stream (that is,
469		* serialize it).
470		*
471		* @serialData Emits the comparator used to order this set, or
472	<	*             <tt>null</tt> if it obeys its elements' natural ordering
473	<	*             (Object), followed by the size of the set (the number of
474	<	*             elements it contains) (int), followed by all of its
475	<	*             elements (each an Object) in order (as determined by the
476	<	*             set's Comparator, or by the elements' natural ordering if
472	>	*             {@code null} if it obeys its elements' natural ordering
473	>	*             (Object), followed by the size of the set (the number of
474	>	*             elements it contains) (int), followed by all of its
475	>	*             elements (each an Object) in order (as determined by the
476	>	*             set's Comparator, or by the elements' natural ordering if
477		*             the set has no Comparator).
478		*/
479		private void writeObject(java.io.ObjectOutputStream s)
#	Line 643 | Line 493 | public class TreeSet<E>
493		}
494
495		/**
496	<	* Reconstitute the <tt>TreeSet</tt> instance from a stream (that is,
496	>	* Reconstitute the {@code TreeSet} instance from a stream (that is,
497		* deserialize it).
498		*/
499		private void readObject(java.io.ObjectInputStream s)

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines