1 /*
   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  * 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.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle 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;
  27 
  28 /**
  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  * <p>This implementation provides guaranteed log(n) time cost for the basic
  35  * operations ({@code add}, {@code remove} and {@code contains}).
  36  *
  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 {@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 {@code Set} interface.
  48  *
  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  * <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 {@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.
  67  *
  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 {@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>
  75  *
  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  * @see     Collection
  84  * @see     Set
  85  * @see     HashSet
  86  * @see     Comparable
  87  * @see     Comparator
  88  * @see     TreeMap
  89  * @since   1.2
  90  */
  91 
  92 public class TreeSet<E> extends AbstractSet<E>
  93     implements NavigableSet<E>, Cloneable, java.io.Serializable
  94 {
  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 navigable map.
 105      */
 106     TreeSet(NavigableMap<E,Object> m) {
 107         this.m = m;
 108     }
 109 
 110     /**
 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>());
 125     }
 126 
 127     /**
 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: {@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      * {@code add} call will throw a {@code ClassCastException}.
 135      *
 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> comparator) {
 141         this(new TreeMap<E,Object>(comparator));
 142     }
 143 
 144     /**
 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 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();
 160         addAll(c);
 161     }
 162 
 163     /**
 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
 169      */
 170     public TreeSet(SortedSet<E> s) {
 171         this(s.comparator());
 172         addAll(s);
 173     }
 174 
 175     /**
 176      * Returns an iterator over the elements in this set in ascending order.
 177      *
 178      * @return an iterator over the elements in this set in ascending order
 179      */
 180     public Iterator<E> iterator() {
 181         return m.navigableKeySet().iterator();
 182     }
 183 
 184     /**
 185      * Returns an iterator over the elements in this set in descending order.
 186      *
 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();
 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)
 205      */
 206     public int size() {
 207         return m.size();
 208     }
 209 
 210     /**
 211      * Returns {@code true} if this set contains no elements.
 212      *
 213      * @return {@code true} if this set contains no elements
 214      */
 215     public boolean isEmpty() {
 216         return m.isEmpty();
 217     }
 218 
 219     /**
 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 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);
 235     }
 236 
 237     /**
 238      * Adds the specified element to this set if it is not already present.
 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 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 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 {@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 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;
 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();
 285     }
 286 
 287     /**
 288      * Adds all of the elements in the specified collection to this set.
 289      *
 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 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 &&
 302             m instanceof TreeMap) {
 303             SortedSet<? extends E> set = (SortedSet<? extends E>) c;
 304             TreeMap<E,Object> map = (TreeMap<E, Object>) m;
 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);
 309                 return true;
 310             }
 311         }
 312         return super.addAll(c);
 313     }
 314 
 315     /**
 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      * @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      * @throws NoSuchElementException {@inheritDoc}
 392      */
 393     public E first() {
 394         return m.firstKey();
 395     }
 396 
 397     /**
 398      * @throws NoSuchElementException {@inheritDoc}
 399      */
 400     public E last() {
 401         return m.lastKey();
 402     }
 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      * @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 floor(E e) {
 425         return m.floorKey(e);
 426     }
 427 
 428     /**
 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();
 456     }
 457 
 458     /**
 459      * @since 1.6
 460      */
 461     public E pollLast() {
 462         Map.Entry<E,?> e = m.pollLastEntry();
 463         return (e == null) ? null : e.getKey();
 464     }
 465 
 466     /**
 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
 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         }
 479 
 480         clone.m = new TreeMap<E,Object>(m);
 481         return clone;
 482     }
 483 
 484     /**
 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      *             {@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();
 500 
 501         // Write out Comparator
 502         s.writeObject(m.comparator());
 503 
 504         // Write out size
 505         s.writeInt(m.size());
 506 
 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 {@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();
 520 
 521         // Read in Comparator
 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;
 531 
 532         // Read in size
 533         int size = s.readInt();
 534 
 535         tm.readTreeSet(size, s, PRESENT);
 536     }
 537 
 538     private static final long serialVersionUID = -2479143000061671589L;
 539 }
--- EOF ---















































































   1 /*
   2  * Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   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.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle 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;
  27 
  28 /**
  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  * <p>This implementation provides guaranteed log(n) time cost for the basic
  35  * operations ({@code add}, {@code remove} and {@code contains}).
  36  *
  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 {@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 {@code Set} interface.
  48  *
  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  * <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 {@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.
  67  *
  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 {@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>
  75  *
  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  * @see     Collection
  84  * @see     Set
  85  * @see     HashSet
  86  * @see     Comparable
  87  * @see     Comparator
  88  * @see     TreeMap
  89  * @since   1.2
  90  */
  91 
  92 public class TreeSet<E> extends AbstractSet<E>
  93     implements NavigableSet<E>, Cloneable, java.io.Serializable
  94 {
  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 navigable map.
 105      */
 106     TreeSet(NavigableMap<E,Object> m) {
 107         this.m = m;
 108     }
 109 
 110     /**
 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>());
 125     }
 126 
 127     /**
 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: {@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      * {@code add} call will throw a {@code ClassCastException}.
 135      *
 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> comparator) {
 141         this(new TreeMap<E,Object>(comparator));
 142     }
 143 
 144     /**
 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 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();
 160         addAll(c);
 161     }
 162 
 163     /**
 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
 169      */
 170     public TreeSet(SortedSet<E> s) {
 171         this(s.comparator());
 172         addAll(s);
 173     }
 174 
 175     /**
 176      * Returns an iterator over the elements in this set in ascending order.
 177      *
 178      * @return an iterator over the elements in this set in ascending order
 179      */
 180     public Iterator<E> iterator() {
 181         return m.navigableKeySet().iterator();
 182     }
 183 
 184     /**
 185      * Returns an iterator over the elements in this set in descending order.
 186      *
 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();
 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)
 205      */
 206     public int size() {
 207         return m.size();
 208     }
 209 
 210     /**
 211      * Returns {@code true} if this set contains no elements.
 212      *
 213      * @return {@code true} if this set contains no elements
 214      */
 215     public boolean isEmpty() {
 216         return m.isEmpty();
 217     }
 218 
 219     /**
 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 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);
 235     }
 236 
 237     /**
 238      * Adds the specified element to this set if it is not already present.
 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 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 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 {@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 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;
 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();
 285     }
 286 
 287     /**
 288      * Adds all of the elements in the specified collection to this set.
 289      *
 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 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 &&
 302             m instanceof TreeMap) {
 303             SortedSet<? extends E> set = (SortedSet<? extends E>) c;
 304             TreeMap<E,Object> map = (TreeMap<E, Object>) m;
 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);
 309                 return true;
 310             }
 311         }
 312         return super.addAll(c);
 313     }
 314 
 315     /**
 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      * @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      * @throws NoSuchElementException {@inheritDoc}
 392      */
 393     public E first() {
 394         return m.firstKey();
 395     }
 396 
 397     /**
 398      * @throws NoSuchElementException {@inheritDoc}
 399      */
 400     public E last() {
 401         return m.lastKey();
 402     }
 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      * @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 floor(E e) {
 425         return m.floorKey(e);
 426     }
 427 
 428     /**
 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();
 456     }
 457 
 458     /**
 459      * @since 1.6
 460      */
 461     public E pollLast() {
 462         Map.Entry<E,?> e = m.pollLastEntry();
 463         return (e == null) ? null : e.getKey();
 464     }
 465 
 466     /**
 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
 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         }
 479 
 480         clone.m = new TreeMap<E,Object>(m);
 481         return clone;
 482     }
 483 
 484     /**
 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      *             {@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();
 500 
 501         // Write out Comparator
 502         s.writeObject(m.comparator());
 503 
 504         // Write out size
 505         s.writeInt(m.size());
 506 
 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 {@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();
 520 
 521         // Read in Comparator
 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;
 531 
 532         // Read in size
 533         int size = s.readInt();
 534 
 535         tm.readTreeSet(size, s, PRESENT);
 536     }
 537 
 538     private static final long serialVersionUID = -2479143000061671589L;
 539 }
--- EOF ---