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.1 by dl, Tue Dec 28 12:14:07 2004 UTC vs.
Revision 1.18 by jsr166, Mon Jul 18 01:14:34 2005 UTC

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

Diff Legend

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