libjava/java/util/TreeSet.java

   1 /* TreeSet.java -- a class providing a TreeMap-backed SortedSet
   2    Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38
  39 package java.util;
  40
  41 import java.io.IOException;
  42 import java.io.Serializable;
  43 import java.io.ObjectInputStream;
  44 import java.io.ObjectOutputStream;
  45
  46 /**
  47  * This class provides a TreeMap-backed implementation of the SortedSet
  48  * interface. The elements will be sorted according to their <i>natural
  49  * order</i>, or according to the provided <code>Comparator</code>.<p>
  50  *
  51  * Most operations are O(log n), but there is so much overhead that this
  52  * makes small sets expensive. Note that the ordering must be <i>consistent
  53  * with equals</i> to correctly implement the Set interface. If this
  54  * condition is violated, the set is still well-behaved, but you may have
  55  * suprising results when comparing it to other sets.<p>
  56  *
  57  * This implementation is not synchronized. If you need to share this between
  58  * multiple threads, do something like:<br>
  59  * <code>SortedSet s
  60  *       = Collections.synchronizedSortedSet(new TreeSet(...));</code><p>
  61  *
  62  * The iterators are <i>fail-fast</i>, meaning that any structural
  63  * modification, except for <code>remove()</code> called on the iterator
  64  * itself, cause the iterator to throw a
  65  * <code>ConcurrentModificationException</code> rather than exhibit
  66  * non-deterministic behavior.
  67  *
  68  * @author Jon Zeppieri
  69  * @author Bryce McKinlay
  70  * @author Eric Blake <ebb9@email.byu.edu>
  71  * @see Collection
  72  * @see Set
  73  * @see HashSet
  74  * @see LinkedHashSet
  75  * @see Comparable
  76  * @see Comparator
  77  * @see Collections#synchronizedSortedSet(SortedSet)
  78  * @see TreeMap
  79  * @since 1.2
  80  * @status updated to 1.4
  81  */
  82 public class TreeSet extends AbstractSet
  83   implements SortedSet, Cloneable, Serializable
  84 {
  85   /**
  86    * Compatible with JDK 1.2.
  87    */
  88   private static final long serialVersionUID = -2479143000061671589L;
  89
  90   /**
  91    * The SortedMap which backs this Set.
  92    */
  93   // Not final because of readObject. This will always be one of TreeMap or
  94   // TreeMap.SubMap, which both extend AbstractMap.
  95   private transient SortedMap map;
  96
  97   /**
  98    * Construct a new TreeSet whose backing TreeMap using the "natural"
  99    * ordering of keys. Elements that are not mutually comparable will cause
 100    * ClassCastExceptions down the road.
 101    *
 102    * @see Comparable
 103    */
 104   public TreeSet()
 105   {
 106     map = new TreeMap();
 107   }
 108
 109   /**
 110    * Construct a new TreeSet whose backing TreeMap uses the supplied
 111    * Comparator. Elements that are not mutually comparable will cause
 112    * ClassCastExceptions down the road.
 113    *
 114    * @param comparator the Comparator this Set will use
 115    */
 116   public TreeSet(Comparator comparator)
 117   {
 118     map = new TreeMap(comparator);
 119   }
 120
 121   /**
 122    * Construct a new TreeSet whose backing TreeMap uses the "natural"
 123    * orering of the keys and which contains all of the elements in the
 124    * supplied Collection. This runs in n*log(n) time.
 125    *
 126    * @param collection the new Set will be initialized with all
 127    *        of the elements in this Collection
 128    * @throws ClassCastException if the elements of the collection are not
 129    *         comparable
 130    * @throws NullPointerException if the collection is null
 131    * @see Comparable
 132    */
 133   public TreeSet(Collection collection)
 134   {
 135     map = new TreeMap();
 136     addAll(collection);
 137   }
 138
 139   /**
 140    * Construct a new TreeSet, using the same key ordering as the supplied
 141    * SortedSet and containing all of the elements in the supplied SortedSet.
 142    * This constructor runs in linear time.
 143    *
 144    * @param sortedSet the new TreeSet will use this SortedSet's comparator
 145    *        and will initialize itself with all its elements
 146    * @throws NullPointerException if sortedSet is null
 147    */
 148   public TreeSet(SortedSet sortedSet)
 149   {
 150     map = new TreeMap(sortedSet.comparator());
 151     Iterator itr = sortedSet.iterator();
 152     ((TreeMap) map).putKeysLinear(itr, sortedSet.size());
 153   }
 154
 155   /**
 156    * This private constructor is used to implement the subSet() calls around
 157    * a backing TreeMap.SubMap.
 158    *
 159    * @param backingMap the submap
 160    */
 161   private TreeSet(SortedMap backingMap)
 162   {
 163     map = backingMap;
 164   }
 165
 166   /**
 167    * Adds the spplied Object to the Set if it is not already in the Set;
 168    * returns true if the element is added, false otherwise.
 169    *
 170    * @param obj the Object to be added to this Set
 171    * @throws ClassCastException if the element cannot be compared with objects
 172    *         already in the set
 173    */
 174   public boolean add(Object obj)
 175   {
 176     return map.put(obj, "") == null;
 177   }
 178
 179   /**
 180    * Adds all of the elements in the supplied Collection to this TreeSet.
 181    *
 182    * @param c The collection to add
 183    * @return true if the Set is altered, false otherwise
 184    * @throws NullPointerException if c is null
 185    * @throws ClassCastException if an element in c cannot be compared with
 186    *         objects already in the set
 187    */
 188   public boolean addAll(Collection c)
 189   {
 190     boolean result = false;
 191     int pos = c.size();
 192     Iterator itr = c.iterator();
 193     while (--pos >= 0)
 194       result |= (map.put(itr.next(), "") == null);
 195     return result;
 196   }
 197
 198   /**
 199    * Removes all elements in this Set.
 200    */
 201   public void clear()
 202   {
 203     map.clear();
 204   }
 205
 206   /**
 207    * Returns a shallow copy of this Set. The elements are not cloned.
 208    *
 209    * @return the cloned set
 210    */
 211   public Object clone()
 212   {
 213     TreeSet copy = null;
 214     try
 215       {
 216         copy = (TreeSet) super.clone();
 217         // Map may be either TreeMap or TreeMap.SubMap, hence the ugly casts.
 218         copy.map = (SortedMap) ((AbstractMap) map).clone();
 219       }
 220     catch (CloneNotSupportedException x)
 221       {
 222         // Impossible result.
 223       }
 224     return copy;
 225   }
 226
 227   /**
 228    * Returns this Set's comparator.
 229    *
 230    * @return the comparator, or null if the set uses natural ordering
 231    */
 232   public Comparator comparator()
 233   {
 234     return map.comparator();
 235   }
 236
 237   /**
 238    * Returns true if this Set contains the supplied Object, false otherwise.
 239    *
 240    * @param obj the Object to check for
 241    * @return true if it is in the set
 242    * @throws ClassCastException if obj cannot be compared with objects
 243    *         already in the set
 244    */
 245   public boolean contains(Object obj)
 246   {
 247     return map.containsKey(obj);
 248   }
 249
 250   /**
 251    * Returns the first (by order) element in this Set.
 252    *
 253    * @return the first element
 254    * @throws NoSuchElementException if the set is empty
 255    */
 256   public Object first()
 257   {
 258     return map.firstKey();
 259   }
 260
 261   /**
 262    * Returns a view of this Set including all elements less than
 263    * <code>to</code>. The returned set is backed by the original, so changes
 264    * in one appear in the other. The subset will throw an
 265    * {@link IllegalArgumentException} for any attempt to access or add an
 266    * element beyond the specified cutoff. The returned set does not include
 267    * the endpoint; if you want inclusion, pass the successor element.
 268    *
 269    * @param to the (exclusive) cutoff point
 270    * @return a view of the set less than the cutoff
 271    * @throws ClassCastException if <code>to</code> is not compatible with
 272    *         the comparator (or is not Comparable, for natural ordering)
 273    * @throws NullPointerException if to is null, but the comparator does not
 274    *         tolerate null elements
 275    */
 276   public SortedSet headSet(Object to)
 277   {
 278     return new TreeSet(map.headMap(to));
 279   }
 280
 281   /**
 282    * Returns true if this Set has size 0, false otherwise.
 283    *
 284    * @return true if the set is empty
 285    */
 286   public boolean isEmpty()
 287   {
 288     return map.isEmpty();
 289   }
 290
 291   /**
 292    * Returns in Iterator over the elements in this TreeSet, which traverses
 293    * in ascending order.
 294    *
 295    * @return an iterator
 296    */
 297   public Iterator iterator()
 298   {
 299     return map.keySet().iterator();
 300   }
 301
 302   /**
 303    * Returns the last (by order) element in this Set.
 304    *
 305    * @return the last element
 306    * @throws NoSuchElementException if the set is empty
 307    */
 308   public Object last()
 309   {
 310     return map.lastKey();
 311   }
 312
 313   /**
 314    * If the supplied Object is in this Set, it is removed, and true is
 315    * returned; otherwise, false is returned.
 316    *
 317    * @param obj the Object to remove from this Set
 318    * @return true if the set was modified
 319    * @throws ClassCastException if obj cannot be compared to set elements
 320    */
 321   public boolean remove(Object obj)
 322   {
 323     return map.remove(obj) != null;
 324   }
 325
 326   /**
 327    * Returns the number of elements in this Set
 328    *
 329    * @return the set size
 330    */
 331   public int size()
 332   {
 333     return map.size();
 334   }
 335
 336   /**
 337    * Returns a view of this Set including all elements greater or equal to
 338    * <code>from</code> and less than <code>to</code> (a half-open interval).
 339    * The returned set is backed by the original, so changes in one appear in
 340    * the other. The subset will throw an {@link IllegalArgumentException}
 341    * for any attempt to access or add an element beyond the specified cutoffs.
 342    * The returned set includes the low endpoint but not the high; if you want
 343    * to reverse this behavior on either end, pass in the successor element.
 344    *
 345    * @param from the (inclusive) low cutoff point
 346    * @param to the (exclusive) high cutoff point
 347    * @return a view of the set between the cutoffs
 348    * @throws ClassCastException if either cutoff is not compatible with
 349    *         the comparator (or is not Comparable, for natural ordering)
 350    * @throws NullPointerException if from or to is null, but the comparator
 351    *         does not tolerate null elements
 352    * @throws IllegalArgumentException if from is greater than to
 353    */
 354   public SortedSet subSet(Object from, Object to)
 355   {
 356     return new TreeSet(map.subMap(from, to));
 357   }
 358
 359   /**
 360    * Returns a view of this Set including all elements greater or equal to
 361    * <code>from</code>. The returned set is backed by the original, so
 362    * changes in one appear in the other. The subset will throw an
 363    * {@link IllegalArgumentException} for any attempt to access or add an
 364    * element beyond the specified cutoff. The returned set includes the
 365    * endpoint; if you want to exclude it, pass in the successor element.
 366    *
 367    * @param from the (inclusive) low cutoff point
 368    * @return a view of the set above the cutoff
 369    * @throws ClassCastException if <code>from</code> is not compatible with
 370    *         the comparator (or is not Comparable, for natural ordering)
 371    * @throws NullPointerException if from is null, but the comparator
 372    *         does not tolerate null elements
 373    */
 374   public SortedSet tailSet(Object from)
 375   {
 376     return new TreeSet(map.tailMap(from));
 377   }
 378
 379   /**
 380    * Serializes this object to the given stream.
 381    *
 382    * @param s the stream to write to
 383    * @throws IOException if the underlying stream fails
 384    * @serialData the <i>comparator</i> (Object), followed by the set size
 385    *             (int), the the elements in sorted order (Object)
 386    */
 387   private void writeObject(ObjectOutputStream s) throws IOException
 388   {
 389     s.defaultWriteObject();
 390     Iterator itr = map.keySet().iterator();
 391     int pos = map.size();
 392     s.writeObject(map.comparator());
 393     s.writeInt(pos);
 394     while (--pos >= 0)
 395       s.writeObject(itr.next());
 396   }
 397
 398   /**
 399    * Deserializes this object from the given stream.
 400    *
 401    * @param s the stream to read from
 402    * @throws ClassNotFoundException if the underlying stream fails
 403    * @throws IOException if the underlying stream fails
 404    * @serialData the <i>comparator</i> (Object), followed by the set size
 405    *             (int), the the elements in sorted order (Object)
 406    */
 407   private void readObject(ObjectInputStream s)
 408     throws IOException, ClassNotFoundException
 409   {
 410     s.defaultReadObject();
 411     Comparator comparator = (Comparator) s.readObject();
 412     int size = s.readInt();
 413     map = new TreeMap(comparator);
 414     ((TreeMap) map).putFromObjStream(s, size, false);
 415   }
 416 }