Save This Page
Home » openjdk-7 » java » util » [javadoc | source]
    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<>(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<>(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<>(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<>(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<>(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<>(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<>();
  528           else
  529               tm = new TreeMap<>(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   }

Save This Page
Home » openjdk-7 » java » util » [javadoc | source]