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.32 by jsr166, Fri Oct 22 05:18:30 2010 UTC

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

Diff Legend

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