Source for java.util.TreeSet

   1: /* TreeSet.java -- a class providing a TreeMap-backed SortedSet
   2:    Copyright (C) 1999, 2000, 2001, 2004, 2005  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., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 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.ObjectInputStream;
  43: import java.io.ObjectOutputStream;
  44: import java.io.Serializable;
  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: }