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.4 by dl, Tue Mar 29 15:00:48 2005 UTC vs.
Revision 1.12 by jsr166, Tue May 17 04:10:23 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
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 (<tt>add</tt>, <tt>remove</tt> and <tt>contains</tt>).
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
25	>	* performs all element comparisons using its <tt>compareTo</tt> (or
26	>	* <tt>compare</tt>) 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 <tt>Set</tt> interface.
30		*
31	<	* <b>Note that this implementation is not synchronized.</b> If multiple
31	>	* <p><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
#	Line 37 | Line 36 | package java.util;
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>
39	>	* </pre>
40		*
41	<	* The Iterators returned by this class's <tt>iterator</tt> method are
41	>	* <p>The iterators returned by this class's <tt>iterator</tt> method are
42		* <i>fail-fast</i>: if the set is modified at any time after the iterator is
43		* created, in any way except through the iterator's own <tt>remove</tt>
44	<	* method, the iterator will throw a <tt>ConcurrentModificationException</tt>.
44	>	* method, the iterator will throw a {@link ConcurrentModificationException}.
45		* Thus, in the face of concurrent modification, the iterator fails quickly
46		* and cleanly, rather than risking arbitrary, non-deterministic behavior at
47		* an undetermined time in the future.
#	Line 53 | Line 52 | package java.util;
52		* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
53		* Therefore, it would be wrong to write a program that depended on this
54		* exception for its correctness:   <i>the fail-fast behavior of iterators
55	<	* should be used only to detect bugs.</i><p>
55	>	* should be used only to detect bugs.</i>
56		*
57	<	* This class is a member of the
57	>	* <p>This class is a member of the
58		* <a href="{@docRoot}/../guide/collections/index.html">
59		* Java Collections Framework</a>.
60		*
61	+	* @param <E> the type of elements maintained by this set
62	+	*
63		* @author  Josh Bloch
64		* @version %I%, %G%
65		* @see     Collection
#	Line 81 | Line 82 | public class TreeSet<E>
82		private static final Object PRESENT = new Object();
83
84		/**
85	<	* Constructs a set backed by the specified sorted map.
85	>	* Constructs a set backed by the specified navigable map.
86		*/
87		private TreeSet(NavigableMap<E,Object> m) {
88		this.m = m;
89		}
90
91		/**
92	<	* Constructs a new, empty set, sorted according to the elements' natural
93	<	* order.  All elements inserted into the set must implement the
94	<	* <tt>Comparable</tt> interface.  Furthermore, all such elements must be
95	<	* <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt> must not throw a
92	>	* Constructs a new, empty tree set, sorted according to the
93	>	* natural ordering of its elements.  All elements inserted into
94	>	* the set must implement the {@link Comparable} interface.
95	>	* Furthermore, all such elements must be <i>mutually
96	>	* comparable</i>: <tt>e1.compareTo(e2)</tt> must not throw a
97		* <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
98	<	* <tt>e2</tt> in the set.  If the user attempts to add an element to the
99	<	* set that violates this constraint (for example, the user attempts to
100	<	* add a string element to a set whose elements are integers), the
101	<	* <tt>add(Object)</tt> call will throw a <tt>ClassCastException</tt>.
102	<	*
101	<	* @see Comparable
98	>	* <tt>e2</tt> in the set.  If the user attempts to add an element
99	>	* to the set that violates this constraint (for example, the user
100	>	* attempts to add a string element to a set whose elements are
101	>	* integers), the <tt>add(Object)</tt> call will throw a
102	>	* <tt>ClassCastException</tt>.
103		*/
104		public TreeSet() {
105		this(new TreeMap<E,Object>());
106		}
107
108		/**
109	<	* Constructs a new, empty set, sorted according to the specified
109	>	* Constructs a new, empty tree set, sorted according to the specified
110		* comparator.  All elements inserted into the set must be <i>mutually
111		* comparable</i> by the specified comparator: <tt>comparator.compare(e1,
112		* e2)</tt> must not throw a <tt>ClassCastException</tt> for any elements
#	Line 113 | Line 114 | public class TreeSet<E>
114		* an element to the set that violates this constraint, the
115		* <tt>add(Object)</tt> call will throw a <tt>ClassCastException</tt>.
116		*
117	<	* @param c the comparator that will be used to sort this set.  A
118	<	*        <tt>null</tt> value indicates that the elements' <i>natural
119	<	*        ordering</i> should be used.
117	>	* @param comparator the comparator that will be used to order this set.
118	>	*        If <tt>null</tt>, the {@linkplain Comparable natural
119	>	*        ordering} of the elements will be used.
120		*/
121	<	public TreeSet(Comparator<? super E> c) {
122	<	this(new TreeMap<E,Object>(c));
121	>	public TreeSet(Comparator<? super E> comparator) {
122	>	this(new TreeMap<E,Object>(comparator));
123		}
124
125		/**
126	<	* Constructs a new set containing the elements in the specified
127	<	* collection, sorted according to the elements' <i>natural order</i>.
128	<	* All keys inserted into the set must implement the <tt>Comparable</tt>
129	<	* interface.  Furthermore, all such keys must be <i>mutually
130	<	* comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
131	<	* <tt>ClassCastException</tt> for any elements <tt>k1</tt> and
132	<	* <tt>k2</tt> in the set.
132	<	*
133	<	* @param c The elements that will comprise the new set.
126	>	* Constructs a new tree set containing the elements in the specified
127	>	* collection, sorted according to the <i>natural ordering</i> of its
128	>	* elements.  All elements inserted into the set must implement the
129	>	* {@link Comparable} interface.  Furthermore, all such elements must be
130	>	* <i>mutually comparable</i>: <tt>e1.compareTo(e2)</tt> must not throw a
131	>	* <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
132	>	* <tt>e2</tt> in the set.
133		*
134	<	* @throws ClassCastException if the keys in the specified collection are
135	<	*         not comparable, or are not mutually comparable.
136	<	* @throws NullPointerException if the specified collection is null.
134	>	* @param c collection whose elements will comprise the new set
135	>	* @throws ClassCastException if the elements in <tt>c</tt> are
136	>	*         not {@link Comparable}, or are not mutually comparable
137	>	* @throws NullPointerException if the specified collection is null
138		*/
139		public TreeSet(Collection<? extends E> c) {
140		this();
#	Line 142 | Line 142 | public class TreeSet<E>
142		}
143
144		/**
145	<	* Constructs a new set containing the same elements as the specified
146	<	* sorted set, sorted according to the same ordering.
145	>	* Constructs a new tree set containing the same elements and
146	>	* using the same ordering as the specified sorted set.
147		*
148	<	* @param s sorted set whose elements will comprise the new set.
149	<	* @throws NullPointerException if the specified sorted set is null.
148	>	* @param s sorted set whose elements will comprise the new set
149	>	* @throws NullPointerException if the specified sorted set is null
150		*/
151		public TreeSet(SortedSet<E> s) {
152		this(s.comparator());
#	Line 157 | Line 157 | public class TreeSet<E>
157		* Returns an iterator over the elements in this set.  The elements
158		* are returned in ascending order.
159		*
160	<	* @return an iterator over the elements in this set.
160	>	* @return an iterator over the elements in this set
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.
169		*
170	<	* @return an iterator over the elements in this set.
170	>	* @return an iterator over the elements in this set
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 194 | Line 194 | public class TreeSet<E>
194		/**
195		* Returns <tt>true</tt> if this set contains the specified element.
196		*
197	<	* @param o the object to be checked for containment in this set.
198	<	* @return <tt>true</tt> if this set contains the specified element.
199	<	*
197	>	* @param o the object to be checked for containment in this set
198	>	* @return <tt>true</tt> if this set contains the specified element
199		* @throws ClassCastException if the specified object cannot be compared
200	<	*            with the elements currently in the set.
201	<	* @throws NullPointerException if o is <tt>null</tt> and this map
202	<	* uses natural ordering and is non-empty, or its comparator does
203	<	* not tolerate <tt>null</tt> keys.
200	>	*         with the elements currently in the set
201	>	* @throws NullPointerException if the specified element is null and
202	>	*         this set uses natural ordering and is non-empty, or its
203	>	*         comparator does not permit null elements
204		*/
205		public boolean contains(Object o) {
206		return m.containsKey(o);
#	Line 210 | Line 209 | public class TreeSet<E>
209		/**
210		* Adds the specified element to this set if it is not already present.
211		*
212	<	* @param o element to be added to this set.
212	>	* @param e element to be added to this set
213		* @return <tt>true</tt> if the set did not already contain the specified
214	<	*         element.
216	<	*
214	>	*         element
215		* @throws ClassCastException if the specified object cannot be compared
216	<	*            with the elements currently in the set.
217	<	* @throws NullPointerException if o is <tt>null</tt> and this map
218	<	* uses natural ordering and is non-empty, or its comparator does
219	<	* not tolerate <tt>null</tt> keys.
216	>	*         with the elements currently in the set
217	>	* @throws NullPointerException if the specified element is null and
218	>	*         this set uses natural ordering and is non-empty, or its
219	>	*         comparator does not permit null elements
220		*/
221	<	public boolean add(E o) {
222	<	return m.put(o, PRESENT)==null;
221	>	public boolean add(E e) {
222	>	return m.put(e, PRESENT)==null;
223		}
224
225		/**
226		* Removes the specified element from this set if it is present.
227		*
228	<	* @param o object to be removed from this set, if present.
229	<	* @return <tt>true</tt> if the set contained the specified element.
232	<	*
228	>	* @param o object to be removed from this set, if present
229	>	* @return <tt>true</tt> if the set contained the specified element
230		* @throws ClassCastException if the specified object cannot be compared
231	<	*            with the elements currently in the set.
232	<	* @throws NullPointerException if o is <tt>null</tt> and this map
233	<	* uses natural ordering and is non-empty, or its comparator does
234	<	* not tolerate <tt>null</tt> keys.
231	>	*         with the elements currently in the set
232	>	* @throws NullPointerException if the specified element is null and
233	>	*         this set uses natural ordering and is non-empty, or its
234	>	*         comparator does not permit null elements
235		*/
236		public boolean remove(Object o) {
237		return m.remove(o)==PRESENT;
#	Line 242 | Line 239 | public class TreeSet<E>
239
240		/**
241		* Removes all of the elements from this set.
242	+	* The set will be empty after this call returns.
243		*/
244		public void clear() {
245		m.clear();
#	Line 251 | Line 249 | public class TreeSet<E>
249		* Adds all of the elements in the specified collection to this set.
250		*
251		* @param c elements to be added
252	<	* @return <tt>true</tt> if this set changed as a result of the call.
255	<	*
252	>	* @return <tt>true</tt> if this set changed as a result of the call
253		* @throws ClassCastException if the elements provided cannot be compared
254	<	*            with the elements currently in the set.
255	<	* @throws NullPointerException if the specified collection is
256	<	* <tt>null</tt> or if any element is <tt>null</tt> and this map
257	<	* uses natural ordering, or its comparator does not tolerate
261	<	* <tt>null</tt> keys.
254	>	*         with the elements currently in the set
255	>	* @throws NullPointerException if the specified collection is null or
256	>	*         if any element is null and this set uses natural ordering, or
257	>	*         its comparator does not permit null elements
258		*/
259		public  boolean addAll(Collection<? extends E> c) {
260		// Use linear-time version if applicable
261		if (m.size()==0 && c.size() > 0 &&
262		c instanceof SortedSet &&
263		m instanceof TreeMap) {
264	<	SortedSet<Map.Entry<E, Object>> set = (SortedSet<Map.Entry<E, Object>>) (SortedSet) c;
264	>	SortedSet<? extends E> set = (SortedSet<? extends E>) c;
265		TreeMap<E,Object> map = (TreeMap<E, Object>) m;
266	<	Comparator<? super E> cc = (Comparator<E>) set.comparator();
266	>	Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
267		Comparator<? super E> mc = map.comparator();
268		if (cc==mc || (cc != null && cc.equals(mc))) {
269		map.addAllForTreeSet(set, PRESENT);
#	Line 278 | Line 274 | public class TreeSet<E>
274		}
275
276		/**
277	<	* Returns a view of the portion of this set whose elements range
282	<	* from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
283	<	* exclusive.  (If <tt>fromElement</tt> and <tt>toElement</tt> are
284	<	* equal, the returned navigable set is empty.)  The returned
285	<	* navigable set is backed by this set, so changes in the returned
286	<	* navigable set are reflected in this set, and vice-versa.  The
287	<	* returned navigable set supports all optional Set operations.<p>
288	<	*
289	<	* The navigable set returned by this method will throw an
290	<	* <tt>IllegalArgumentException</tt> if the user attempts to insert an
291	<	* element outside the specified range.<p>
292	<	*
293	<	* Note: this method always returns a <i>half-open range</i>
294	<	* (which includes its low endpoint but not its high endpoint).
295	<	* If you need a <i>closed range</i> (which includes both
296	<	* endpoints), and the element type allows for calculation of the
297	<	* successor of a specified value, merely request the subrange
298	<	* from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
299	<	* For example, suppose that <tt>s</tt> is a navigable set of
300	<	* strings.  The following idiom obtains a view containing all of
301	<	* the strings in <tt>s</tt> from <tt>low</tt> to <tt>high</tt>,
302	<	* inclusive:
303	<	* <pre> NavigableSet sub = s.navigableSubSet(low, high+"\0");
304	<	* </pre>
305	<	*
306	<	* A similar technique can be used to generate an <i>open range</i> (which
307	<	* contains neither endpoint).  The following idiom obtains a view
308	<	* containing all of the strings in <tt>s</tt> from <tt>low</tt> to
309	<	* <tt>high</tt>, exclusive: <pre>
310	<	*     NavigableSet sub = s.navigableSubSet(low+"\0", high);
311	<	* </pre>
312	<	*
313	<	* @param fromElement low endpoint (inclusive) of the range.
314	<	* @param toElement high endpoint (exclusive) of the range.
315	<	* @return a view of the portion of this set whose elements range from
316	<	*         <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
317	<	*         exclusive.
318	<	* @throws ClassCastException if <tt>fromElement</tt> and
319	<	*         <tt>toElement</tt> cannot be compared to one another using
320	<	*         this set's comparator (or, if the set has no comparator,
321	<	*         using natural ordering).
322	<	* @throws IllegalArgumentException if <tt>fromElement</tt> is greater than
323	<	*         <tt>toElement</tt>.
277	>	* @throws ClassCastException {@inheritDoc}
278		* @throws NullPointerException if <tt>fromElement</tt> or
279	<	*         <tt>toElement</tt> is <tt>null</tt> and this set uses natural
280	<	*         order, or its comparator does not tolerate <tt>null</tt>
281	<	*         elements.
279	>	*         <tt>toElement</tt> is null and this set uses natural ordering,
280	>	*         or its comparator does not permit null elements
281	>	* @throws IllegalArgumentException {@inheritDoc}
282		*/
283		public NavigableSet<E> navigableSubSet(E fromElement, E toElement) {
284		return new TreeSet<E>(m.navigableSubMap(fromElement, toElement));
285		}
286
287		/**
288	<	* Returns a view of the portion of this set whose elements are
289	<	* strictly less than <tt>toElement</tt>.  The returned navigable
290	<	* set is backed by this set, so changes in the returned navigable
291	<	* set are reflected in this set, and vice-versa.  The returned
292	<	* 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.
288	>	* @throws ClassCastException {@inheritDoc}
289	>	* @throws NullPointerException if <tt>toElement</tt> is null and
290	>	*         this set uses natural ordering, or its comparator does
291	>	*         not permit null elements
292	>	* @throws IllegalArgumentException {@inheritDoc}
293		*/
294		public NavigableSet<E> navigableHeadSet(E toElement) {
295		return new TreeSet<E>(m.navigableHeadMap(toElement));
296		}
297
298		/**
299	<	* Returns a view of the portion of this set whose elements are
300	<	* greater than or equal to <tt>fromElement</tt>.  The returned
301	<	* navigable set is backed by this set, so changes in the returned
302	<	* navigable set are reflected in this set, and vice-versa.  The
303	<	* 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.
299	>	* @throws ClassCastException {@inheritDoc}
300	>	* @throws NullPointerException if <tt>fromElement</tt> is null and
301	>	*         this set uses natural ordering, or its comparator does
302	>	*         not permit null elements
303	>	* @throws IllegalArgumentException {@inheritDoc}
304		*/
305		public NavigableSet<E> navigableTailSet(E fromElement) {
306		return new TreeSet<E>(m.navigableTailMap(fromElement));
307		}
308
411	–
309		/**
310	<	* Equivalent to <tt>navigableSubSet</tt> but with a return
311	<	* type conforming to the <tt>SortedSet</tt> interface.
312	<	* @param fromElement low endpoint (inclusive) of the range.
313	<	* @param toElement high endpoint (exclusive) of the range.
314	<	* @return a view of the portion of this set whose elements range from
315	<	*         <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>.
310	>	* Equivalent to {@link #navigableSubSet} but with a return type
311	>	* conforming to the <tt>SortedSet</tt> interface.
312	>	*
313	>	* <p>{@inheritDoc}
314	>	*
315	>	* @throws ClassCastException {@inheritDoc}
316		* @throws NullPointerException if <tt>fromElement</tt> or
317	<	*         <tt>toElement</tt> is <tt>null</tt> and this set uses natural
318	<	*         order, or its comparator does not tolerate <tt>null</tt>
319	<	*         elements.
317	>	*         <tt>toElement</tt> is null and this set uses natural ordering,
318	>	*         or its comparator does not permit null elements
319	>	* @throws IllegalArgumentException {@inheritDoc}
320		*/
321		public SortedSet<E> subSet(E fromElement, E toElement) {
322		return new TreeSet<E>(m.navigableSubMap(fromElement, toElement));
323		}
324
325		/**
326	<	* Equivalent to <tt>navigableHeadSet</tt> but with a return
327	<	* type conforming to the <tt>SortedSet</tt> interface.
326	>	* Equivalent to {@link #navigableHeadSet} but with a return type
327	>	* conforming to the <tt>SortedSet</tt> interface.
328		*
329	<	* @param toElement high endpoint (exclusive) of the headSet.
330	<	* @return a view of the portion of this set whose elements are strictly
331	<	*         less than <tt>toElement</tt>.
332	<	* @throws ClassCastException if <tt>toElement</tt> is not compatible
333	<	*         with this set's comparator (or, if the set has no comparator,
334	<	*         if <tt>toElement</tt> does not implement <tt>Comparable</tt>).
335	<	* @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.
329	>	* <p>{@inheritDoc}
330	>	*
331	>	* @throws ClassCastException {@inheritDoc}
332	>	* @throws NullPointerException if <tt>toElement</tt> is null
333	>	*         and this set uses natural ordering, or its comparator does
334	>	*         not permit null elements
335	>	* @throws IllegalArgumentException {@inheritDoc}
336		*/
337		public SortedSet<E> headSet(E toElement) {
338		return new TreeSet<E>(m.navigableHeadMap(toElement));
339		}
340
341		/**
342	<	* Equivalent to <tt>navigableTailSet</tt> but with a return
343	<	* type conforming to the <tt>SortedSet</tt> interface.
344	<	* @param fromElement low endpoint (inclusive) of the tailSet.
345	<	* @return a view of the portion of this set whose elements are
346	<	*         greater than or equal to <tt>fromElement</tt>.
347	<	* @throws ClassCastException if <tt>fromElement</tt> is not compatible
348	<	*         with this set's comparator (or, if the set has no comparator,
349	<	*         if <tt>fromElement</tt> does not implement <tt>Comparable</tt>).
350	<	* @throws IllegalArgumentException if this set is itself a subset,
351	<	*         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.
342	>	* Equivalent to {@link #navigableTailSet} but with a return type
343	>	* conforming to the <tt>SortedSet</tt> interface.
344	>	*
345	>	* <p>{@inheritDoc}
346	>	*
347	>	* @throws ClassCastException {@inheritDoc}
348	>	* @throws NullPointerException if <tt>fromElement</tt> is null
349	>	*         and this set uses natural ordering, or its comparator does
350	>	*         not permit null elements
351	>	* @throws IllegalArgumentException {@inheritDoc}
352		*/
353		public SortedSet<E> tailSet(E fromElement) {
354		return new TreeSet<E>(m.navigableTailMap(fromElement));
355		}
356
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	–	*/
357		public Comparator<? super E> comparator() {
358		return m.comparator();
359		}
360
361		/**
362	<	* 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.
362	>	* @throws NoSuchElementException {@inheritDoc}
363		*/
364		public E first() {
365		return m.firstKey();
366		}
367
368		/**
369	<	* 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.
369	>	* @throws NoSuchElementException {@inheritDoc}
370		*/
371		public E last() {
372		return m.lastKey();
#	Line 506 | Line 374 | public class TreeSet<E>
374
375		// NavigableSet API methods
376
377	+	/**
378	+	* @throws ClassCastException {@inheritDoc}
379	+	* @throws NullPointerException if the specified element is null and
380	+	*         this set uses natural ordering and is non-empty,
381	+	*         or its comparator does not permit null elements
382	+	*/
383	+	public E lower(E e) {
384	+	return m.lowerKey(e);
385	+	}
386
387		/**
388	<	* Returns an element greater than or equal to the given element, or
389	<	* <tt>null</tt> if there is no such element.
390	<	*
391	<	* @param o 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 o cannot be compared with the elements
518	<	*            currently in the set.
519	<	* @throws NullPointerException if o 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 o) {
524	<	return m.ceilingKey(o);
525	<	}
526	<
527	<	/**
528	<	* Returns an element strictly less than the given element, or
529	<	* <tt>null</tt> if there is no such element.
530	<	*
531	<	* @param o the value to match
532	<	* @return the greatest element less than the given element, or
533	<	* <tt>null</tt> if there is no such element.
534	<	* @throws ClassCastException if o cannot be compared with the elements
535	<	*            currently in the set.
536	<	* @throws NullPointerException if o 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.
539	<	*/
540	<	public E lower(E o) {
541	<	return m.lowerKey(o);
542	<	}
543	<
544	<	/**
545	<	* Returns an element less than or equal to the given element, or
546	<	* <tt>null</tt> if there is no such element.
547	<	*
548	<	* @param o the value to match
549	<	* @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 o cannot be compared with the elements
552	<	*            currently in the set.
553	<	* @throws NullPointerException if o 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.
556	<	*/
557	<	public E floor(E o) {
558	<	return m.floorKey(o);
559	<	}
560	<
561	<	/**
562	<	* Returns an element strictly greater than the given element, or
563	<	* <tt>null</tt> if there is no such element.
564	<	*
565	<	* @param o the value to match
566	<	* @return the least element greater than the given element, or
567	<	* <tt>null</tt> if there is no such element.
568	<	* @throws ClassCastException if o cannot be compared with the elements
569	<	*            currently in the set.
570	<	* @throws NullPointerException if o is <tt>null</tt> and this map
571	<	* uses natural ordering and is non-empty, or its comparator does
572	<	* not tolerate <tt>null</tt> keys.
388	>	* @throws ClassCastException {@inheritDoc}
389	>	* @throws NullPointerException if the specified element is null and
390	>	*         this set uses natural ordering and is non-empty,
391	>	*         or its comparator does not permit null elements
392		*/
393	<	public E higher(E o) {
394	<	return m.higherKey(o);
393	>	public E floor(E e) {
394	>	return m.floorKey(e);
395		}
396
397		/**
398	<	* Retrieves and removes the first (lowest) element.
399	<	*
400	<	* @return the least element, or <tt>null</tt> if empty.
398	>	* @throws ClassCastException {@inheritDoc}
399	>	* @throws NullPointerException if the specified element is null and
400	>	*         this set uses natural ordering and is non-empty,
401	>	*         or its comparator does not permit null elements
402		*/
403	+	public E ceiling(E e) {
404	+	return m.ceilingKey(e);
405	+	}
406	+
407	+	/**
408	+	* @throws ClassCastException {@inheritDoc}
409	+	* @throws NullPointerException if the specified element is null and
410	+	*         this set uses natural ordering and is non-empty,
411	+	*         or its comparator does not permit null elements
412	+	*/
413	+	public E higher(E e) {
414	+	return m.higherKey(e);
415	+	}
416	+
417		public E pollFirst() {
418		Map.Entry<E,?> e = m.pollFirstEntry();
419		return (e == null)? null : e.getKey();
420		}
421
588	–	/**
589	–	* Retrieves and removes the last (highest) element.
590	–	*
591	–	* @return the last element, or <tt>null</tt> if empty.
592	–	*/
422		public E pollLast() {
423		Map.Entry<E,?> e = m.pollLastEntry();
424		return (e == null)? null : e.getKey();
#	Line 599 | Line 428 | public class TreeSet<E>
428		* Returns a shallow copy of this <tt>TreeSet</tt> instance. (The elements
429		* themselves are not cloned.)
430		*
431	<	* @return a shallow copy of this set.
431	>	* @return a shallow copy of this set
432		*/
433		public Object clone() {
434		TreeSet<E> clone = null;
#	Line 619 | Line 448 | public class TreeSet<E>
448		* serialize it).
449		*
450		* @serialData Emits the comparator used to order this set, or
451	<	*             <tt>null</tt> if it obeys its elements' natural ordering
452	<	*             (Object), followed by the size of the set (the number of
453	<	*             elements it contains) (int), followed by all of its
454	<	*             elements (each an Object) in order (as determined by the
455	<	*             set's Comparator, or by the elements' natural ordering if
451	>	*             <tt>null</tt> if it obeys its elements' natural ordering
452	>	*             (Object), followed by the size of the set (the number of
453	>	*             elements it contains) (int), followed by all of its
454	>	*             elements (each an Object) in order (as determined by the
455	>	*             set's Comparator, or by the elements' natural ordering if
456		*             the set has no Comparator).
457		*/
458		private void writeObject(java.io.ObjectOutputStream s)
#	Line 652 | Line 481 | public class TreeSet<E>
481		s.defaultReadObject();
482
483		// Read in Comparator
484	<	Comparator<E> c = (Comparator<E>) s.readObject();
484	>	Comparator<? super E> c = (Comparator<? super E>) s.readObject();
485
486		// Create backing TreeMap
487		TreeMap<E,Object> tm;

Diff Legend

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