KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > TreeSet


1 /*
2  * @(#)TreeSet.java 1.32 03/12/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */

7
8 package java.util;
9
10 /**
11  * This class implements the <tt>Set</tt> interface, backed by a
12  * <tt>TreeMap</tt> instance. This class guarantees that the sorted set will
13  * be in ascending element order, sorted according to the <i>natural order</i>
14  * of the elements (see <tt>Comparable</tt>), or by the comparator provided at
15  * set creation time, depending on which constructor is used.<p>
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>
19  *
20  * 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
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>
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>
41  *
42  * The Iterators returned by this class's <tt>iterator</tt> method are
43  * <i>fail-fast</i>: if the set is modified at any time after the iterator is
44  * created, in any way except through the iterator's own <tt>remove</tt>
45  * method, the iterator will throw a <tt>ConcurrentModificationException</tt>.
46  * Thus, in the face of concurrent modification, the iterator fails quickly
47  * and cleanly, rather than risking arbitrary, non-deterministic behavior at
48  * an undetermined time in the future.
49  *
50  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
51  * as it is, generally speaking, impossible to make any hard guarantees in the
52  * presence of unsynchronized concurrent modification. Fail-fast iterators
53  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
54  * Therefore, it would be wrong to write a program that depended on this
55  * exception for its correctness: <i>the fail-fast behavior of iterators
56  * should be used only to detect bugs.</i><p>
57  *
58  * This class is a member of the
59  * <a HREF="{@docRoot}/../guide/collections/index.html">
60  * Java Collections Framework</a>.
61  *
62  * @author Josh Bloch
63  * @version 1.32, 12/19/03
64  * @see Collection
65  * @see Set
66  * @see HashSet
67  * @see Comparable
68  * @see Comparator
69  * @see Collections#synchronizedSortedSet(SortedSet)
70  * @see TreeMap
71  * @since 1.2
72  */

73
74 public class TreeSet<E>
75     extends AbstractSet JavaDoc<E>
76     implements SortedSet JavaDoc<E>, Cloneable JavaDoc, java.io.Serializable JavaDoc
77 {
78     private transient SortedMap JavaDoc<E,Object JavaDoc> m; // The backing Map
79
private transient Set JavaDoc<E> keySet; // The keySet view of the backing Map
80

81     // Dummy value to associate with an Object in the backing Map
82
private static final Object JavaDoc PRESENT = new Object JavaDoc();
83
84     /**
85      * Constructs a set backed by the specified sorted map.
86      */

87     private TreeSet(SortedMap JavaDoc<E,Object JavaDoc> m) {
88         this.m = m;
89         keySet = m.keySet();
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
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      *
103      * @see Comparable
104      */

105     public TreeSet() {
106     this(new TreeMap JavaDoc<E,Object JavaDoc>());
107     }
108
109     /**
110      * Constructs a new, empty 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
114      * <tt>e1</tt> and <tt>e2</tt> in the set. If the user attempts to add
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.
121      */

122     public TreeSet(Comparator JavaDoc<? super E> c) {
123     this(new TreeMap JavaDoc<E,Object JavaDoc>(c));
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.
134      *
135      * @param c The elements that will comprise the new set.
136      *
137      * @throws ClassCastException if the keys in the specified collection are
138      * not comparable, or are not mutually comparable.
139      * @throws NullPointerException if the specified collection is null.
140      */

141     public TreeSet(Collection JavaDoc<? extends E> c) {
142         this();
143         addAll(c);
144     }
145
146     /**
147      * Constructs a new set containing the same elements as the specified
148      * sorted set, sorted according to the same ordering.
149      *
150      * @param s sorted set whose elements will comprise the new set.
151      * @throws NullPointerException if the specified sorted set is null.
152      */

153     public TreeSet(SortedSet JavaDoc<E> s) {
154         this(s.comparator());
155     addAll(s);
156     }
157
158     /**
159      * Returns an iterator over the elements in this set. The elements
160      * are returned in ascending order.
161      *
162      * @return an iterator over the elements in this set.
163      */

164     public Iterator JavaDoc<E> iterator() {
165     return keySet.iterator();
166     }
167
168     /**
169      * Returns the number of elements in this set (its cardinality).
170      *
171      * @return the number of elements in this set (its cardinality).
172      */

173     public int size() {
174     return m.size();
175     }
176
177     /**
178      * Returns <tt>true</tt> if this set contains no elements.
179      *
180      * @return <tt>true</tt> if this set contains no elements.
181      */

182     public boolean isEmpty() {
183     return m.isEmpty();
184     }
185
186     /**
187      * Returns <tt>true</tt> if this set contains the specified element.
188      *
189      * @param o the object to be checked for containment in this set.
190      * @return <tt>true</tt> if this set contains the specified element.
191      *
192      * @throws ClassCastException if the specified object cannot be compared
193      * with the elements currently in the set.
194      */

195     public boolean contains(Object JavaDoc o) {
196     return m.containsKey(o);
197     }
198
199     /**
200      * Adds the specified element to this set if it is not already present.
201      *
202      * @param o element to be added to this set.
203      * @return <tt>true</tt> if the set did not already contain the specified
204      * element.
205      *
206      * @throws ClassCastException if the specified object cannot be compared
207      * with the elements currently in the set.
208      */

209     public boolean add(E o) {
210     return m.put(o, PRESENT)==null;
211     }
212
213     /**
214      * Removes the specified element from this set if it is present.
215      *
216      * @param o object to be removed from this set, if present.
217      * @return <tt>true</tt> if the set contained the specified element.
218      *
219      * @throws ClassCastException if the specified object cannot be compared
220      * with the elements currently in the set.
221      */

222     public boolean remove(Object JavaDoc o) {
223     return m.remove(o)==PRESENT;
224     }
225
226     /**
227      * Removes all of the elements from this set.
228      */

229     public void clear() {
230     m.clear();
231     }
232
233     /**
234      * Adds all of the elements in the specified collection to this set.
235      *
236      * @param c elements to be added
237      * @return <tt>true</tt> if this set changed as a result of the call.
238      *
239      * @throws ClassCastException if the elements provided cannot be compared
240      * with the elements currently in the set.
241      * @throws NullPointerException of the specified collection is null.
242      */

243     public boolean addAll(Collection JavaDoc<? extends E> c) {
244         // Use linear-time version if applicable
245
if (m.size()==0 && c.size() > 0 &&
246         // FIXME(VFORCE) Work-around for bug in compiler
247
c instanceof SortedSet JavaDoc &&
248             m instanceof TreeMap JavaDoc) {
249             SortedSet JavaDoc<Map.Entry JavaDoc<E, Object JavaDoc>> set = (SortedSet JavaDoc<Map.Entry JavaDoc<E, Object JavaDoc>>) (SortedSet JavaDoc) c;
250             TreeMap JavaDoc<E,Object JavaDoc> map = (TreeMap JavaDoc<E, Object JavaDoc>) m;
251             Comparator JavaDoc<? super E> cc = (Comparator JavaDoc<E>) set.comparator();
252             Comparator JavaDoc<? super E> mc = map.comparator();
253             if (cc==mc || (cc != null && cc.equals(mc))) {
254                 map.addAllForTreeSet(set, PRESENT);
255                 return true;
256             }
257         }
258         return super.addAll(c);
259     }
260
261     /**
262      * Returns a view of the portion of this set whose elements range from
263      * <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive. (If
264      * <tt>fromElement</tt> and <tt>toElement</tt> are equal, the returned
265      * sorted set is empty.) The returned sorted set is backed by this set,
266      * so changes in the returned sorted set are reflected in this set, and
267      * vice-versa. The returned sorted set supports all optional Set
268      * operations.<p>
269      *
270      * The sorted set returned by this method will throw an
271      * <tt>IllegalArgumentException</tt> if the user attempts to insert an
272      * element outside the specified range.<p>
273      *
274      * Note: this method always returns a <i>half-open range</i> (which
275      * includes its low endpoint but not its high endpoint). If you need a
276      * <i>closed range</i> (which includes both endpoints), and the element
277      * type allows for calculation of the successor of a specified value,
278      * merely request the subrange from <tt>lowEndpoint</tt> to
279      * <tt>successor(highEndpoint)</tt>. For example, suppose that <tt>s</tt>
280      * is a sorted set of strings. The following idiom obtains a view
281      * containing all of the strings in <tt>s</tt> from <tt>low</tt> to
282      * <tt>high</tt>, inclusive: <pre>
283      * SortedSet sub = s.subSet(low, high+"\0");
284      * </pre>
285      *
286      * A similar technique can be used to generate an <i>open range</i> (which
287      * contains neither endpoint). The following idiom obtains a view
288      * containing all of the strings in <tt>s</tt> from <tt>low</tt> to
289      * <tt>high</tt>, exclusive: <pre>
290      * SortedSet sub = s.subSet(low+"\0", high);
291      * </pre>
292      *
293      * @param fromElement low endpoint (inclusive) of the subSet.
294      * @param toElement high endpoint (exclusive) of the subSet.
295      * @return a view of the portion of this set whose elements range from
296      * <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
297      * exclusive.
298      * @throws ClassCastException if <tt>fromElement</tt> and
299      * <tt>toElement</tt> cannot be compared to one another using
300      * this set's comparator (or, if the set has no comparator,
301      * using natural ordering).
302      * @throws IllegalArgumentException if <tt>fromElement</tt> is greater than
303      * <tt>toElement</tt>.
304      * @throws NullPointerException if <tt>fromElement</tt> or
305      * <tt>toElement</tt> is <tt>null</tt> and this set uses natural
306      * order, or its comparator does not tolerate <tt>null</tt>
307      * elements.
308      */

309     public SortedSet JavaDoc<E> subSet(E fromElement, E toElement) {
310     return new TreeSet JavaDoc<E>(m.subMap(fromElement, toElement));
311     }
312
313     /**
314      * Returns a view of the portion of this set whose elements are strictly
315      * less than <tt>toElement</tt>. The returned sorted set is backed by
316      * this set, so changes in the returned sorted set are reflected in this
317      * set, and vice-versa. The returned sorted set supports all optional set
318      * operations.<p>
319      *
320      * The sorted set returned by this method will throw an
321      * <tt>IllegalArgumentException</tt> if the user attempts to insert an
322      * element greater than or equal to <tt>toElement</tt>.<p>
323      *
324      * Note: this method always returns a view that does not contain its
325      * (high) endpoint. If you need a view that does contain this endpoint,
326      * and the element type allows for calculation of the successor of a
327      * specified value, merely request a headSet bounded by
328      * <tt>successor(highEndpoint)</tt>. For example, suppose that <tt>s</tt>
329      * is a sorted set of strings. The following idiom obtains a view
330      * containing all of the strings in <tt>s</tt> that are less than or equal
331      * to <tt>high</tt>: <pre> SortedSet head = s.headSet(high+"\0");</pre>
332      *
333      * @param toElement high endpoint (exclusive) of the headSet.
334      * @return a view of the portion of this set whose elements are strictly
335      * less than toElement.
336      * @throws ClassCastException if <tt>toElement</tt> is not compatible
337      * with this set's comparator (or, if the set has no comparator,
338      * if <tt>toElement</tt> does not implement <tt>Comparable</tt>).
339      * @throws IllegalArgumentException if this set is itself a subSet,
340      * headSet, or tailSet, and <tt>toElement</tt> is not within the
341      * specified range of the subSet, headSet, or tailSet.
342      * @throws NullPointerException if <tt>toElement</tt> is <tt>null</tt> and
343      * this set uses natural ordering, or its comparator does
344      * not tolerate <tt>null</tt> elements.
345      */

346     public SortedSet JavaDoc<E> headSet(E toElement) {
347     return new TreeSet JavaDoc<E>(m.headMap(toElement));
348     }
349
350     /**
351      * Returns a view of the portion of this set whose elements are
352      * greater than or equal to <tt>fromElement</tt>. The returned sorted set
353      * is backed by this set, so changes in the returned sorted set are
354      * reflected in this set, and vice-versa. The returned sorted set
355      * supports all optional set operations.<p>
356      *
357      * The sorted set returned by this method will throw an
358      * <tt>IllegalArgumentException</tt> if the user attempts to insert an
359      * element less than <tt>fromElement</tt>.
360      *
361      * Note: this method always returns a view that contains its (low)
362      * endpoint. If you need a view that does not contain this endpoint, and
363      * the element type allows for calculation of the successor of a specified
364      * value, merely request a tailSet bounded by
365      * <tt>successor(lowEndpoint)</tt>. For example, suppose that <tt>s</tt>
366      * is a sorted set of strings. The following idiom obtains a view
367      * containing all of the strings in <tt>s</tt> that are strictly greater
368      * than <tt>low</tt>: <pre>
369      * SortedSet tail = s.tailSet(low+"\0");
370      * </pre>
371      *
372      * @param fromElement low endpoint (inclusive) of the tailSet.
373      * @return a view of the portion of this set whose elements are
374      * greater than or equal to <tt>fromElement</tt>.
375      * @throws ClassCastException if <tt>fromElement</tt> is not compatible
376      * with this set's comparator (or, if the set has no comparator,
377      * if <tt>fromElement</tt> does not implement <tt>Comparable</tt>).
378      * @throws IllegalArgumentException if this set is itself a subSet,
379      * headSet, or tailSet, and <tt>fromElement</tt> is not within the
380      * specified range of the subSet, headSet, or tailSet.
381      * @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>
382      * and this set uses natural ordering, or its comparator does
383      * not tolerate <tt>null</tt> elements.
384      */

385     public SortedSet JavaDoc<E> tailSet(E fromElement) {
386     return new TreeSet JavaDoc<E>(m.tailMap(fromElement));
387     }
388
389     /**
390      * Returns the comparator used to order this sorted set, or <tt>null</tt>
391      * if this tree set uses its elements natural ordering.
392      *
393      * @return the comparator used to order this sorted set, or <tt>null</tt>
394      * if this tree set uses its elements natural ordering.
395      */

396     public Comparator JavaDoc<? super E> comparator() {
397         return m.comparator();
398     }
399
400     /**
401      * Returns the first (lowest) element currently in this sorted set.
402      *
403      * @return the first (lowest) element currently in this sorted set.
404      * @throws NoSuchElementException sorted set is empty.
405      */

406     public E first() {
407         return m.firstKey();
408     }
409
410     /**
411      * Returns the last (highest) element currently in this sorted set.
412      *
413      * @return the last (highest) element currently in this sorted set.
414      * @throws NoSuchElementException sorted set is empty.
415      */

416     public E last() {
417         return m.lastKey();
418     }
419
420     /**
421      * Returns a shallow copy of this <tt>TreeSet</tt> instance. (The elements
422      * themselves are not cloned.)
423      *
424      * @return a shallow copy of this set.
425      */

426     public Object JavaDoc clone() {
427         TreeSet JavaDoc<E> clone = null;
428     try {
429         clone = (TreeSet JavaDoc<E>) super.clone();
430     } catch (CloneNotSupportedException JavaDoc e) {
431         throw new InternalError JavaDoc();
432     }
433
434         clone.m = new TreeMap JavaDoc<E,Object JavaDoc>(m);
435         clone.keySet = clone.m.keySet();
436
437         return clone;
438     }
439
440     /**
441      * Save the state of the <tt>TreeSet</tt> instance to a stream (that is,
442      * serialize it).
443      *
444      * @serialData Emits the comparator used to order this set, or
445      * <tt>null</tt> if it obeys its elements' natural ordering
446      * (Object), followed by the size of the set (the number of
447      * elements it contains) (int), followed by all of its
448      * elements (each an Object) in order (as determined by the
449      * set's Comparator, or by the elements' natural ordering if
450      * the set has no Comparator).
451      */

452     private void writeObject(java.io.ObjectOutputStream JavaDoc s)
453         throws java.io.IOException JavaDoc {
454     // Write out any hidden stuff
455
s.defaultWriteObject();
456
457         // Write out Comparator
458
s.writeObject(m.comparator());
459
460         // Write out size
461
s.writeInt(m.size());
462
463     // Write out all elements in the proper order.
464
for (Iterator JavaDoc i=m.keySet().iterator(); i.hasNext(); )
465             s.writeObject(i.next());
466     }
467
468     /**
469      * Reconstitute the <tt>TreeSet</tt> instance from a stream (that is,
470      * deserialize it).
471      */

472     private void readObject(java.io.ObjectInputStream JavaDoc s)
473         throws java.io.IOException JavaDoc, ClassNotFoundException JavaDoc {
474     // Read in any hidden stuff
475
s.defaultReadObject();
476
477         // Read in Comparator
478
Comparator JavaDoc<E> c = (Comparator JavaDoc<E>) s.readObject();
479
480         // Create backing TreeMap and keySet view
481
TreeMap JavaDoc<E,Object JavaDoc> tm;
482     if (c==null)
483         tm = new TreeMap JavaDoc<E,Object JavaDoc>();
484     else
485         tm = new TreeMap JavaDoc<E,Object JavaDoc>(c);
486     m = tm;
487         keySet = m.keySet();
488
489         // Read in size
490
int size = s.readInt();
491
492         tm.readTreeSet(size, s, PRESENT);
493     }
494
495     private static final long serialVersionUID = -2479143000061671589L;
496 }
497
Popular Tags