| TreeSet.java |
1 /*
2 * %W% %E%
3 *
4 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved.
5 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6 */
7
8 package java.util;
9
10 /**
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 * <p>This implementation provides guaranteed log(n) time cost for the basic
17 * operations ({@code add}, {@code remove} and {@code contains}).
18 *
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 {@code Set} interface. (See {@code Comparable}
22 * or {@code Comparator} for a precise definition of <i>consistent with
23 * equals</i>.) This is so because the {@code Set} interface is defined in
24 * terms of the {@code equals} operation, but a {@code TreeSet} instance
25 * performs all element comparisons using its {@code compareTo} (or
26 * {@code compare}) 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 {@code Set} interface.
30 *
31 * <p><strong>Note that this implementation is not synchronized.</strong>
32 * If multiple threads access a tree set concurrently, and at least one
33 * of the threads modifies the set, it <i>must</i> be synchronized
34 * externally. This is typically accomplished by synchronizing on some
35 * object that naturally encapsulates the set.
36 * If no such object exists, the set should be "wrapped" using the
37 * {@link Collections#synchronizedSortedSet Collections.synchronizedSortedSet}
38 * method. This is best done at creation time, to prevent accidental
39 * unsynchronized access to the set: <pre>
40 * SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));</pre>
41 *
42 * <p>The iterators returned by this class's {@code iterator} 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 {@code remove}
45 * method, the iterator will throw a {@link ConcurrentModificationException}.
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 {@code ConcurrentModificationException} 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>
57 *
58 * <p>This class is a member of the
59 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
60 * Java Collections Framework</a>.
61 *
62 * @param <E> the type of elements maintained by this set
63 *
64 * @author Josh Bloch
65 * @version %I%, %G%
66 * @see Collection
67 * @see Set
68 * @see HashSet
69 * @see Comparable
70 * @see Comparator
71 * @see TreeMap
72 * @since 1.2
73 */
74
75 public class TreeSet<E> extends AbstractSet<E>
76 implements NavigableSet<E>, Cloneable, java.io.Serializable
77 {
78 /**
79 * The backing map.
80 */
81 private transient NavigableMap<E,Object> m;
82
83 // Dummy value to associate with an Object in the backing Map
84 private static final Object PRESENT = new Object();
85
86 /**
87 * Constructs a set backed by the specified navigable map.
88 */
89 TreeSet(NavigableMap<E,Object> m) {
90 this.m = m;
91 }
92
93 /**
94 * Constructs a new, empty tree set, sorted according to the
95 * natural ordering of its elements. All elements inserted into
96 * the set must implement the {@link Comparable} interface.
97 * Furthermore, all such elements must be <i>mutually
98 * comparable</i>: {@code e1.compareTo(e2)} must not throw a
99 * {@code ClassCastException} for any elements {@code e1} and
100 * {@code e2} in the set. If the user attempts to add an element
101 * to the set that violates this constraint (for example, the user
102 * attempts to add a string element to a set whose elements are
103 * integers), the {@code add} call will throw a
104 * {@code ClassCastException}.
105 */
106 public TreeSet() {
107 this(new TreeMap<E,Object>());
108 }
109
110 /**
111 * Constructs a new, empty tree set, sorted according to the specified
112 * comparator. All elements inserted into the set must be <i>mutually
113 * comparable</i> by the specified comparator: {@code comparator.compare(e1,
114 * e2)} must not throw a {@code ClassCastException} for any elements
115 * {@code e1} and {@code e2} in the set. If the user attempts to add
116 * an element to the set that violates this constraint, the
117 * {@code add} call will throw a {@code ClassCastException}.
118 *
119 * @param comparator the comparator that will be used to order this set.
120 * If {@code null}, the {@linkplain Comparable natural
121 * ordering} of the elements will be used.
122 */
123 public TreeSet(Comparator<? super E> comparator) {
124 this(new TreeMap<E,Object>(comparator));
125 }
126
127 /**
128 * Constructs a new tree set containing the elements in the specified
129 * collection, sorted according to the <i>natural ordering</i> of its
130 * elements. All elements inserted into the set must implement the
131 * {@link Comparable} interface. Furthermore, all such elements must be
132 * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a
133 * {@code ClassCastException} for any elements {@code e1} and
134 * {@code e2} in the set.
135 *
136 * @param c collection whose elements will comprise the new set
137 * @throws ClassCastException if the elements in {@code c} are
138 * not {@link Comparable}, or are not mutually comparable
139 * @throws NullPointerException if the specified collection is null
140 */
141 public TreeSet(Collection<? extends E> c) {
142 this();
143 addAll(c);
144 }
145
146 /**
147 * Constructs a new tree set containing the same elements and
148 * using the same ordering as the specified sorted set.
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<E> s) {
154 this(s.comparator());
155 addAll(s);
156 }
157
158 /**
159 * Returns an iterator over the elements in this set in ascending order.
160 *
161 * @return an iterator over the elements in this set in ascending order
162 */
163 public Iterator<E> iterator() {
164 return m.navigableKeySet().iterator();
165 }
166
167 /**
168 * Returns an iterator over the elements in this set in descending order.
169 *
170 * @return an iterator over the elements in this set in descending order
171 * @since 1.6
172 */
173 public Iterator<E> descendingIterator() {
174 return m.descendingKeySet().iterator();
175 }
176
177 /**
178 * @since 1.6
179 */
180 public NavigableSet<E> descendingSet() {
181 return new TreeSet(m.descendingMap());
182 }
183
184 /**
185 * Returns the number of elements in this set (its cardinality).
186 *
187 * @return the number of elements in this set (its cardinality)
188 */
189 public int size() {
190 return m.size();
191 }
192
193 /**
194 * Returns {@code true} if this set contains no elements.
195 *
196 * @return {@code true} if this set contains no elements
197 */
198 public boolean isEmpty() {
199 return m.isEmpty();
200 }
201
202 /**
203 * Returns {@code true} if this set contains the specified element.
204 * More formally, returns {@code true} if and only if this set
205 * contains an element {@code e} such that
206 * <tt>(o==null ? e==null : o.equals(e))</tt>.
207 *
208 * @param o object to be checked for containment in this set
209 * @return {@code true} if this set contains the specified element
210 * @throws ClassCastException if the specified object cannot be compared
211 * with the elements currently in the set
212 * @throws NullPointerException if the specified element is null
213 * and this set uses natural ordering, or its comparator
214 * does not permit null elements
215 */
216 public boolean contains(Object o) {
217 return m.containsKey(o);
218 }
219
220 /**
221 * Adds the specified element to this set if it is not already present.
222 * More formally, adds the specified element {@code e} to this set if
223 * the set contains no element {@code e2} such that
224 * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
225 * If this set already contains the element, the call leaves the set
226 * unchanged and returns {@code false}.
227 *
228 * @param e element to be added to this set
229 * @return {@code true} if this set did not already contain the specified
230 * element
231 * @throws ClassCastException if the specified object cannot be compared
232 * with the elements currently in this set
233 * @throws NullPointerException if the specified element is null
234 * and this set uses natural ordering, or its comparator
235 * does not permit null elements
236 */
237 public boolean add(E e) {
238 return m.put(e, PRESENT)==null;
239 }
240
241 /**
242 * Removes the specified element from this set if it is present.
243 * More formally, removes an element {@code e} such that
244 * <tt>(o==null ? e==null : o.equals(e))</tt>,
245 * if this set contains such an element. Returns {@code true} if
246 * this set contained the element (or equivalently, if this set
247 * changed as a result of the call). (This set will not contain the
248 * element once the call returns.)
249 *
250 * @param o object to be removed from this set, if present
251 * @return {@code true} if this set contained the specified element
252 * @throws ClassCastException if the specified object cannot be compared
253 * with the elements currently in this set
254 * @throws NullPointerException if the specified element is null
255 * and this set uses natural ordering, or its comparator
256 * does not permit null elements
257 */
258 public boolean remove(Object o) {
259 return m.remove(o)==PRESENT;
260 }
261
262 /**
263 * Removes all of the elements from this set.
264 * The set will be empty after this call returns.
265 */
266 public void clear() {
267 m.clear();
268 }
269
270 /**
271 * Adds all of the elements in the specified collection to this set.
272 *
273 * @param c collection containing elements to be added to this set
274 * @return {@code true} if this set changed as a result of the call
275 * @throws ClassCastException if the elements provided cannot be compared
276 * with the elements currently in the set
277 * @throws NullPointerException if the specified collection is null or
278 * if any element is null and this set uses natural ordering, or
279 * its comparator does not permit null elements
280 */
281 public boolean addAll(Collection<? extends E> c) {
282 // Use linear-time version if applicable
283 if (m.size()==0 && c.size() > 0 &&
284 c instanceof SortedSet &&
285 m instanceof TreeMap) {
286 SortedSet<? extends E> set = (SortedSet<? extends E>) c;
287 TreeMap<E,Object> map = (TreeMap<E, Object>) m;
288 Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
289 Comparator<? super E> mc = map.comparator();
290 if (cc==mc || (cc != null && cc.equals(mc))) {
291 map.addAllForTreeSet(set, PRESENT);
292 return true;
293 }
294 }
295 return super.addAll(c);
296 }
297
298 /**
299 * @throws ClassCastException {@inheritDoc}
300 * @throws NullPointerException if {@code fromElement} or {@code toElement}
301 * is null and this set uses natural ordering, or its comparator
302 * does not permit null elements
303 * @throws IllegalArgumentException {@inheritDoc}
304 * @since 1.6
305 */
306 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
307 E toElement, boolean toInclusive) {
308 return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
309 toElement, toInclusive));
310 }
311
312 /**
313 * @throws ClassCastException {@inheritDoc}
314 * @throws NullPointerException if {@code toElement} is null and
315 * this set uses natural ordering, or its comparator does
316 * not permit null elements
317 * @throws IllegalArgumentException {@inheritDoc}
318 * @since 1.6
319 */
320 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
321 return new TreeSet<E>(m.headMap(toElement, inclusive));
322 }
323
324 /**
325 * @throws ClassCastException {@inheritDoc}
326 * @throws NullPointerException if {@code fromElement} is null and
327 * this set uses natural ordering, or its comparator does
328 * not permit null elements
329 * @throws IllegalArgumentException {@inheritDoc}
330 * @since 1.6
331 */
332 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
333 return new TreeSet<E>(m.tailMap(fromElement, inclusive));
334 }
335
336 /**
337 * @throws ClassCastException {@inheritDoc}
338 * @throws NullPointerException if {@code fromElement} or
339 * {@code toElement} is null and this set uses natural ordering,
340 * or its comparator does not permit null elements
341 * @throws IllegalArgumentException {@inheritDoc}
342 */
343 public SortedSet<E> subSet(E fromElement, E toElement) {
344 return subSet(fromElement, true, toElement, false);
345 }
346
347 /**
348 * @throws ClassCastException {@inheritDoc}
349 * @throws NullPointerException if {@code toElement} is null
350 * and this set uses natural ordering, or its comparator does
351 * not permit null elements
352 * @throws IllegalArgumentException {@inheritDoc}
353 */
354 public SortedSet<E> headSet(E toElement) {
355 return headSet(toElement, false);
356 }
357
358 /**
359 * @throws ClassCastException {@inheritDoc}
360 * @throws NullPointerException if {@code fromElement} is null
361 * and this set uses natural ordering, or its comparator does
362 * not permit null elements
363 * @throws IllegalArgumentException {@inheritDoc}
364 */
365 public SortedSet<E> tailSet(E fromElement) {
366 return tailSet(fromElement, true);
367 }
368
369 public Comparator<? super E> comparator() {
370 return m.comparator();
371 }
372
373 /**
374 * @throws NoSuchElementException {@inheritDoc}
375 */
376 public E first() {
377 return m.firstKey();
378 }
379
380 /**
381 * @throws NoSuchElementException {@inheritDoc}
382 */
383 public E last() {
384 return m.lastKey();
385 }
386
387 // NavigableSet API methods
388
389 /**
390 * @throws ClassCastException {@inheritDoc}
391 * @throws NullPointerException if the specified element is null
392 * and this set uses natural ordering, or its comparator
393 * does not permit null elements
394 * @since 1.6
395 */
396 public E lower(E e) {
397 return m.lowerKey(e);
398 }
399
400 /**
401 * @throws ClassCastException {@inheritDoc}
402 * @throws NullPointerException if the specified element is null
403 * and this set uses natural ordering, or its comparator
404 * does not permit null elements
405 * @since 1.6
406 */
407 public E floor(E e) {
408 return m.floorKey(e);
409 }
410
411 /**
412 * @throws ClassCastException {@inheritDoc}
413 * @throws NullPointerException if the specified element is null
414 * and this set uses natural ordering, or its comparator
415 * does not permit null elements
416 * @since 1.6
417 */
418 public E ceiling(E e) {
419 return m.ceilingKey(e);
420 }
421
422 /**
423 * @throws ClassCastException {@inheritDoc}
424 * @throws NullPointerException if the specified element is null
425 * and this set uses natural ordering, or its comparator
426 * does not permit null elements
427 * @since 1.6
428 */
429 public E higher(E e) {
430 return m.higherKey(e);
431 }
432
433 /**
434 * @since 1.6
435 */
436 public E pollFirst() {
437 Map.Entry<E,?> e = m.pollFirstEntry();
438 return (e == null)? null : e.getKey();
439 }
440
441 /**
442 * @since 1.6
443 */
444 public E pollLast() {
445 Map.Entry<E,?> e = m.pollLastEntry();
446 return (e == null)? null : e.getKey();
447 }
448
449 /**
450 * Returns a shallow copy of this {@code TreeSet} instance. (The elements
451 * themselves are not cloned.)
452 *
453 * @return a shallow copy of this set
454 */
455 public Object clone() {
456 TreeSet<E> clone = null;
457 try {
458 clone = (TreeSet<E>) super.clone();
459 } catch (CloneNotSupportedException e) {
460 throw new InternalError();
461 }
462
463 clone.m = new TreeMap<E,Object>(m);
464 return clone;
465 }
466
467 /**
468 * Save the state of the {@code TreeSet} instance to a stream (that is,
469 * serialize it).
470 *
471 * @serialData Emits the comparator used to order this set, or
472 * {@code null} if it obeys its elements' natural ordering
473 * (Object), followed by the size of the set (the number of
474 * elements it contains) (int), followed by all of its
475 * elements (each an Object) in order (as determined by the
476 * set's Comparator, or by the elements' natural ordering if
477 * the set has no Comparator).
478 */
479 private void writeObject(java.io.ObjectOutputStream s)
480 throws java.io.IOException {
481 // Write out any hidden stuff
482 s.defaultWriteObject();
483
484 // Write out Comparator
485 s.writeObject(m.comparator());
486
487 // Write out size
488 s.writeInt(m.size());
489
490 // Write out all elements in the proper order.
491 for (Iterator i=m.keySet().iterator(); i.hasNext(); )
492 s.writeObject(i.next());
493 }
494
495 /**
496 * Reconstitute the {@code TreeSet} instance from a stream (that is,
497 * deserialize it).
498 */
499 private void readObject(java.io.ObjectInputStream s)
500 throws java.io.IOException, ClassNotFoundException {
501 // Read in any hidden stuff
502 s.defaultReadObject();
503
504 // Read in Comparator
505 Comparator<? super E> c = (Comparator<? super E>) s.readObject();
506
507 // Create backing TreeMap
508 TreeMap<E,Object> tm;
509 if (c==null)
510 tm = new TreeMap<E,Object>();
511 else
512 tm = new TreeMap<E,Object>(c);
513 m = tm;
514
515 // Read in size
516 int size = s.readInt();
517
518 tm.readTreeSet(size, s, PRESENT);
519 }
520
521 private static final long serialVersionUID = -2479143000061671589L;
522 }
523