001: /*
002: * @(#)TreeSet.java 1.27 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package java.util;
029:
030: /**
031: * This class implements the <tt>Set</tt> interface, backed by a
032: * <tt>TreeMap</tt> instance. This class guarantees that the sorted set will
033: * be in ascending element order, sorted according to the <i>natural order</i>
034: * of the elements (see <tt>Comparable</tt>), or by the comparator provided at
035: * set creation time, depending on which constructor is used.<p>
036: *
037: * This implementation provides guaranteed log(n) time cost for the basic
038: * operations (<tt>add</tt>, <tt>remove</tt> and <tt>contains</tt>).<p>
039: *
040: * Note that the ordering maintained by a set (whether or not an explicit
041: * comparator is provided) must be <i>consistent with equals</i> if it is to
042: * correctly implement the <tt>Set</tt> interface. (See <tt>Comparable</tt>
043: * or <tt>Comparator</tt> for a precise definition of <i>consistent with
044: * equals</i>.) This is so because the <tt>Set</tt> interface is defined in
045: * terms of the <tt>equals</tt> operation, but a <tt>TreeSet</tt> instance
046: * performs all key comparisons using its <tt>compareTo</tt> (or
047: * <tt>compare</tt>) method, so two keys that are deemed equal by this method
048: * are, from the standpoint of the set, equal. The behavior of a set
049: * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
050: * just fails to obey the general contract of the <tt>Set</tt> interface.<p>
051: *
052: * <b>Note that this implementation is not synchronized.</b> If multiple
053: * threads access a set concurrently, and at least one of the threads modifies
054: * the set, it <i>must</i> be synchronized externally. This is typically
055: * accomplished by synchronizing on some object that naturally encapsulates
056: * the set. If no such object exists, the set should be "wrapped" using the
057: * <tt>Collections.synchronizedSet</tt> method. This is best done at creation
058: * time, to prevent accidental unsynchronized access to the set: <pre>
059: * SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
060: * </pre><p>
061: *
062: * The Iterators returned by this class's <tt>iterator</tt> method are
063: * <i>fail-fast</i>: if the set is modified at any time after the iterator is
064: * created, in any way except through the iterator's own <tt>remove</tt>
065: * method, the iterator will throw a <tt>ConcurrentModificationException</tt>.
066: * Thus, in the face of concurrent modification, the iterator fails quickly
067: * and cleanly, rather than risking arbitrary, non-deterministic behavior at
068: * an undetermined time in the future.
069: *
070: * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
071: * as it is, generally speaking, impossible to make any hard guarantees in the
072: * presence of unsynchronized concurrent modification. Fail-fast iterators
073: * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
074: * Therefore, it would be wrong to write a program that depended on this
075: * exception for its correctness: <i>the fail-fast behavior of iterators
076: * should be used only to detect bugs.</i><p>
077: *
078: * This class is a member of the
079: * <a href="{@docRoot}/../guide/collections/index.html">
080: * Java Collections Framework</a>.
081: *
082: * @author Josh Bloch
083: * @version 1.20, 02/02/00
084: * @see Collection
085: * @see Set
086: * @see HashSet
087: * @see Comparable
088: * @see Comparator
089: * @see Collections#synchronizedSortedSet(SortedSet)
090: * @see TreeMap
091: * @since 1.2
092: */
093:
094: public class TreeSet extends AbstractSet implements SortedSet,
095: Cloneable, java.io.Serializable {
096: private transient SortedMap m; // The backing Map
097: private transient Set keySet; // The keySet view of the backing Map
098:
099: // Dummy value to associate with an Object in the backing Map
100: private static final Object PRESENT = new Object();
101:
102: /**
103: * Constructs a set backed by the specified sorted map.
104: */
105: private TreeSet(SortedMap m) {
106: this .m = m;
107: keySet = m.keySet();
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
122: */
123: public TreeSet() {
124: this (new TreeMap());
125: }
126:
127: /**
128: * Constructs a new, empty 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
133: * an element to the set that violates this constraint, the
134: * <tt>add(Object)</tt> call will throw a <tt>ClassCastException</tt>.
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.
139: */
140: public TreeSet(Comparator c) {
141: this (new TreeMap(c));
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.
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.
157: * @throws NullPointerException if the specified collection is null.
158: */
159: public TreeSet(Collection c) {
160: this ();
161: addAll(c);
162: }
163:
164: /**
165: * Constructs a new set containing the same elements as the specified
166: * sorted set, sorted according to the same ordering.
167: *
168: * @param s sorted set whose elements will comprise the new set.
169: * @throws NullPointerException if the specified sorted set is null.
170: */
171: public TreeSet(SortedSet s) {
172: this (s.comparator());
173: addAll(s);
174: }
175:
176: /**
177: * Returns an iterator over the elements in this set. The elements
178: * are returned in ascending order.
179: *
180: * @return an iterator over the elements in this set.
181: */
182: public Iterator iterator() {
183: return keySet.iterator();
184: }
185:
186: /**
187: * Returns the number of elements in this set (its cardinality).
188: *
189: * @return the number of elements in this set (its cardinality).
190: */
191: public int size() {
192: return m.size();
193: }
194:
195: /**
196: * Returns <tt>true</tt> if this set contains no elements.
197: *
198: * @return <tt>true</tt> if this set contains no elements.
199: */
200: public boolean isEmpty() {
201: return m.isEmpty();
202: }
203:
204: /**
205: * Returns <tt>true</tt> if this set contains the specified element.
206: *
207: * @param o the object to be checked for containment in this set.
208: * @return <tt>true</tt> if this set contains the specified element.
209: *
210: * @throws ClassCastException if the specified object cannot be compared
211: * with the elements currently in the set.
212: */
213: public boolean contains(Object o) {
214: return m.containsKey(o);
215: }
216:
217: /**
218: * Adds the specified element to this set if it is not already present.
219: *
220: * @param o element to be added to this set.
221: * @return <tt>true</tt> if the set did not already contain the specified
222: * element.
223: *
224: * @throws ClassCastException if the specified object cannot be compared
225: * with the elements currently in the set.
226: */
227: public boolean add(Object o) {
228: return m.put(o, PRESENT) == null;
229: }
230:
231: /**
232: * Removes the specified element from this set if it is present.
233: *
234: * @param o object to be removed from this set, if present.
235: * @return <tt>true</tt> if the set contained the specified element.
236: *
237: * @throws ClassCastException if the specified object cannot be compared
238: * with the elements currently in the set.
239: */
240: public boolean remove(Object o) {
241: return m.remove(o) == PRESENT;
242: }
243:
244: /**
245: * Removes all of the elements from this set.
246: */
247: public void clear() {
248: m.clear();
249: }
250:
251: /**
252: * Adds all of the elements in the specified collection to this set.
253: *
254: * @param c elements to be added
255: * @return <tt>true</tt> if this set changed as a result of the call.
256: *
257: * @throws ClassCastException if the elements provided cannot be compared
258: * with the elements currently in the set.
259: * @throws NullPointerException of the specified collection is null.
260: */
261: public boolean addAll(Collection c) {
262: // Use linear-time version if applicable
263: if (m.size() == 0 && c.size() > 0 && c instanceof SortedSet
264: && m instanceof TreeMap) {
265: SortedSet set = (SortedSet) c;
266: TreeMap map = (TreeMap) m;
267: Comparator cc = set.comparator();
268: Comparator mc = map.comparator();
269: if (cc == mc || (cc != null && cc.equals(mc))) {
270: map.addAllForTreeSet(set, PRESENT);
271: return true;
272: }
273: }
274: return super .addAll(c);
275: }
276:
277: /**
278: * Returns a view of the portion of this set whose elements range from
279: * <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>, exclusive. (If
280: * <tt>fromElement</tt> and <tt>toElement</tt> are equal, the returned
281: * sorted set is empty.) The returned sorted set is backed by this set,
282: * so changes in the returned sorted set are reflected in this set, and
283: * vice-versa. The returned sorted set supports all optional Set
284: * operations.<p>
285: *
286: * The sorted set returned by this method will throw an
287: * <tt>IllegalArgumentException</tt> if the user attempts to insert an
288: * element outside the specified range.<p>
289: *
290: * Note: this method always returns a <i>half-open range</i> (which
291: * includes its low endpoint but not its high endpoint). If you need a
292: * <i>closed range</i> (which includes both endpoints), and the element
293: * type allows for calculation of the successor of a specified value,
294: * merely request the subrange from <tt>lowEndpoint</tt> to
295: * <tt>successor(highEndpoint)</tt>. For example, suppose that <tt>s</tt>
296: * is a sorted set of strings. The following idiom obtains a view
297: * containing all of the strings in <tt>s</tt> from <tt>low</tt> to
298: * <tt>high</tt>, inclusive: <pre>
299: * SortedSet sub = s.subSet(low, high+"\0");
300: * </pre>
301: *
302: * A similar technique can be used to generate an <i>open range</i> (which
303: * contains neither endpoint). The following idiom obtains a view
304: * containing all of the strings in <tt>s</tt> from <tt>low</tt> to
305: * <tt>high</tt>, exclusive: <pre>
306: * SortedSet sub = s.subSet(low+"\0", high);
307: * </pre>
308: *
309: * @param fromElement low endpoint (inclusive) of the subSet.
310: * @param toElement high endpoint (exclusive) of the subSet.
311: * @return a view of the portion of this set whose elements range from
312: * <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
313: * exclusive.
314: * @throws ClassCastException if <tt>fromElement</tt> and
315: * <tt>toElement</tt> cannot be compared to one another using
316: * this set's comparator (or, if the set has no comparator,
317: * using natural ordering).
318: * @throws IllegalArgumentException if <tt>fromElement</tt> is greater than
319: * <tt>toElement</tt>.
320: * @throws NullPointerException if <tt>fromElement</tt> or
321: * <tt>toElement</tt> is <tt>null</tt> and this set uses natural
322: * order, or its comparator does not tolerate <tt>null</tt>
323: * elements.
324: */
325: public SortedSet subSet(Object fromElement, Object toElement) {
326: return new TreeSet(m.subMap(fromElement, toElement));
327: }
328:
329: /**
330: * Returns a view of the portion of this set whose elements are strictly
331: * less than <tt>toElement</tt>. The returned sorted set is backed by
332: * this set, so changes in the returned sorted set are reflected in this
333: * set, and vice-versa. The returned sorted set supports all optional set
334: * operations.<p>
335: *
336: * The sorted set returned by this method will throw an
337: * <tt>IllegalArgumentException</tt> if the user attempts to insert an
338: * element greater than or equal to <tt>toElement</tt>.<p>
339: *
340: * Note: this method always returns a view that does not contain its
341: * (high) endpoint. If you need a view that does contain this endpoint,
342: * and the element type allows for calculation of the successor of a
343: * specified value, merely request a headSet bounded by
344: * <tt>successor(highEndpoint)</tt>. For example, suppose that <tt>s</tt>
345: * is a sorted set of strings. The following idiom obtains a view
346: * containing all of the strings in <tt>s</tt> that are less than or equal
347: * to <tt>high</tt>: <pre> SortedSet head = s.headSet(high+"\0");</pre>
348: *
349: * @param toElement high endpoint (exclusive) of the headSet.
350: * @return a view of the portion of this set whose elements are strictly
351: * less than toElement.
352: * @throws ClassCastException if <tt>toElement</tt> is not compatible
353: * with this set's comparator (or, if the set has no comparator,
354: * if <tt>toElement</tt> does not implement <tt>Comparable</tt>).
355: * @throws IllegalArgumentException if this set is itself a subSet,
356: * headSet, or tailSet, and <tt>toElement</tt> is not within the
357: * specified range of the subSet, headSet, or tailSet.
358: * @throws NullPointerException if <tt>toElement</tt> is <tt>null</tt> and
359: * this set uses natural ordering, or its comparator does
360: * not tolerate <tt>null</tt> elements.
361: */
362: public SortedSet headSet(Object toElement) {
363: return new TreeSet(m.headMap(toElement));
364: }
365:
366: /**
367: * Returns a view of the portion of this set whose elements are
368: * greater than or equal to <tt>fromElement</tt>. The returned sorted set
369: * is backed by this set, so changes in the returned sorted set are
370: * reflected in this set, and vice-versa. The returned sorted set
371: * supports all optional set operations.<p>
372: *
373: * The sorted set returned by this method will throw an
374: * <tt>IllegalArgumentException</tt> if the user attempts to insert an
375: * element less than <tt>fromElement</tt>.
376: *
377: * Note: this method always returns a view that contains its (low)
378: * endpoint. If you need a view that does not contain this endpoint, and
379: * the element type allows for calculation of the successor of a specified
380: * value, merely request a tailSet bounded by
381: * <tt>successor(lowEndpoint)</tt>. For example, suppose that <tt>s</tt>
382: * is a sorted set of strings. The following idiom obtains a view
383: * containing all of the strings in <tt>s</tt> that are strictly greater
384: * than <tt>low</tt>: <pre>
385: * SortedSet tail = s.tailSet(low+"\0");
386: * </pre>
387: *
388: * @param fromElement low endpoint (inclusive) of the tailSet.
389: * @return a view of the portion of this set whose elements are
390: * greater than or equal to <tt>fromElement</tt>.
391: * @throws ClassCastException if <tt>fromElement</tt> is not compatible
392: * with this set's comparator (or, if the set has no comparator,
393: * if <tt>fromElement</tt> does not implement <tt>Comparable</tt>).
394: * @throws IllegalArgumentException if this set is itself a subSet,
395: * headSet, or tailSet, and <tt>fromElement</tt> is not within the
396: * specified range of the subSet, headSet, or tailSet.
397: * @throws NullPointerException if <tt>fromElement</tt> is <tt>null</tt>
398: * and this set uses natural ordering, or its comparator does
399: * not tolerate <tt>null</tt> elements.
400: */
401: public SortedSet tailSet(Object fromElement) {
402: return new TreeSet(m.tailMap(fromElement));
403: }
404:
405: /**
406: * Returns the comparator used to order this sorted set, or <tt>null</tt>
407: * if this tree set uses its elements natural ordering.
408: *
409: * @return the comparator used to order this sorted set, or <tt>null</tt>
410: * if this tree set uses its elements natural ordering.
411: */
412: public Comparator comparator() {
413: return m.comparator();
414: }
415:
416: /**
417: * Returns the first (lowest) element currently in this sorted set.
418: *
419: * @return the first (lowest) element currently in this sorted set.
420: * @throws NoSuchElementException sorted set is empty.
421: */
422: public Object first() {
423: return m.firstKey();
424: }
425:
426: /**
427: * Returns the last (highest) element currently in this sorted set.
428: *
429: * @return the last (highest) element currently in this sorted set.
430: * @throws NoSuchElementException sorted set is empty.
431: */
432: public Object last() {
433: return m.lastKey();
434: }
435:
436: /**
437: * Returns a shallow copy of this <tt>TreeSet</tt> instance. (The elements
438: * themselves are not cloned.)
439: *
440: * @return a shallow copy of this set.
441: */
442: public Object clone() {
443: TreeSet clone = null;
444: try {
445: clone = (TreeSet) super .clone();
446: } catch (CloneNotSupportedException e) {
447: throw new InternalError();
448: }
449:
450: clone.m = new TreeMap(m);
451: clone.keySet = clone.m.keySet();
452:
453: return clone;
454: }
455:
456: /**
457: * Save the state of the <tt>TreeSet</tt> instance to a stream (that is,
458: * serialize it).
459: *
460: * @serialData Emits the comparator used to order this set, or
461: * <tt>null</tt> if it obeys its elements' natural ordering
462: * (Object), followed by the size of the set (the number of
463: * elements it contains) (int), followed by all of its
464: * elements (each an Object) in order (as determined by the
465: * set's Comparator, or by the elements' natural ordering if
466: * the set has no Comparator).
467: */
468: private void writeObject(java.io.ObjectOutputStream s)
469: throws java.io.IOException {
470: // Write out any hidden stuff
471: s.defaultWriteObject();
472:
473: // Write out Comparator
474: s.writeObject(m.comparator());
475:
476: // Write out size
477: s.writeInt(m.size());
478:
479: // Write out all elements in the proper order.
480: for (Iterator i = m.keySet().iterator(); i.hasNext();)
481: s.writeObject(i.next());
482: }
483:
484: /**
485: * Reconstitute the <tt>TreeSet</tt> instance from a stream (that is,
486: * deserialize it).
487: */
488: private void readObject(java.io.ObjectInputStream s)
489: throws java.io.IOException, ClassNotFoundException {
490: // Read in any hidden stuff
491: s.defaultReadObject();
492:
493: // Read in Comparator
494: Comparator c = (Comparator) s.readObject();
495:
496: // Create backing TreeMap and keySet view
497: m = (c == null ? new TreeMap() : new TreeMap(c));
498: keySet = m.keySet();
499:
500: // Read in size
501: int size = s.readInt();
502:
503: ((TreeMap) m).readTreeSet(size, s, PRESENT);
504: }
505:
506: private static final long serialVersionUID = -2479143000061671589L;
507: }
|