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:  * @author Tom Tromey (tromey@redhat.com)
  72:  * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
  73:  * @see Collection
  74:  * @see Set
  75:  * @see HashSet
  76:  * @see LinkedHashSet
  77:  * @see Comparable
  78:  * @see Comparator
  79:  * @see Collections#synchronizedSortedSet(SortedSet)
  80:  * @see TreeMap
  81:  * @since 1.2
  82:  * @status updated to 1.6
  83:  */
  84: public class TreeSet<T> extends AbstractSet<T>
  85:   implements NavigableSet<T>, Cloneable, Serializable
  86: {
  87:   /**
  88:    * Compatible with JDK 1.2.
  89:    */
  90:   private static final long serialVersionUID = -2479143000061671589L;
  91: 
  92:   /**
  93:    * The NavigableMap which backs this Set.
  94:    */
  95:   // Not final because of readObject. This will always be one of TreeMap or
  96:   // TreeMap.SubMap, which both extend AbstractMap.
  97:   private transient NavigableMap<T, String> map;
  98: 
  99:   /**
 100:    * Construct a new TreeSet whose backing TreeMap using the "natural"
 101:    * ordering of keys. Elements that are not mutually comparable will cause
 102:    * ClassCastExceptions down the road.
 103:    *
 104:    * @see Comparable
 105:    */
 106:   public TreeSet()
 107:   {
 108:     map = new TreeMap<T, String>();
 109:   }
 110: 
 111:   /**
 112:    * Construct a new TreeSet whose backing TreeMap uses the supplied
 113:    * Comparator. Elements that are not mutually comparable will cause
 114:    * ClassCastExceptions down the road.
 115:    *
 116:    * @param comparator the Comparator this Set will use
 117:    */
 118:   public TreeSet(Comparator<? super T> comparator)
 119:   {
 120:     map = new TreeMap<T, String>(comparator);
 121:   }
 122: 
 123:   /**
 124:    * Construct a new TreeSet whose backing TreeMap uses the "natural"
 125:    * orering of the keys and which contains all of the elements in the
 126:    * supplied Collection. This runs in n*log(n) time.
 127:    *
 128:    * @param collection the new Set will be initialized with all
 129:    *        of the elements in this Collection
 130:    * @throws ClassCastException if the elements of the collection are not
 131:    *         comparable
 132:    * @throws NullPointerException if the collection is null
 133:    * @see Comparable
 134:    */
 135:   public TreeSet(Collection<? extends T> collection)
 136:   {
 137:     map = new TreeMap<T, String>();
 138:     addAll(collection);
 139:   }
 140: 
 141:   /**
 142:    * Construct a new TreeSet, using the same key ordering as the supplied
 143:    * SortedSet and containing all of the elements in the supplied SortedSet.
 144:    * This constructor runs in linear time.
 145:    *
 146:    * @param sortedSet the new TreeSet will use this SortedSet's comparator
 147:    *        and will initialize itself with all its elements
 148:    * @throws NullPointerException if sortedSet is null
 149:    */
 150:   public TreeSet(SortedSet<T> sortedSet)
 151:   {
 152:     Iterator<T> itr;
 153: 
 154:     map = new TreeMap<T, String>
 155:       ((Comparator<? super T>)sortedSet.comparator());
 156:     itr = ((SortedSet<T>) sortedSet).iterator();
 157:     ((TreeMap<T, String>) map).putKeysLinear(itr, sortedSet.size(), "");
 158:   }
 159: 
 160:   /**
 161:    * This private constructor is used to implement the subSet() calls around
 162:    * a backing TreeMap.SubMap.
 163:    *
 164:    * @param backingMap the submap
 165:    */
 166:   private TreeSet(NavigableMap<T,String> backingMap)
 167:   {
 168:     map = backingMap;
 169:   }
 170: 
 171:   /**
 172:    * Adds the spplied Object to the Set if it is not already in the Set;
 173:    * returns true if the element is added, false otherwise.
 174:    *
 175:    * @param obj the Object to be added to this Set
 176:    * @throws ClassCastException if the element cannot be compared with objects
 177:    *         already in the set
 178:    */
 179:   public boolean add(T obj)
 180:   {
 181:     return map.put(obj, "") == null;
 182:   }
 183: 
 184:   /**
 185:    * Adds all of the elements in the supplied Collection to this TreeSet.
 186:    *
 187:    * @param c The collection to add
 188:    * @return true if the Set is altered, false otherwise
 189:    * @throws NullPointerException if c is null
 190:    * @throws ClassCastException if an element in c cannot be compared with
 191:    *         objects already in the set
 192:    */
 193:   public boolean addAll(Collection<? extends T> c)
 194:   {
 195:     boolean result = false;
 196:     int pos = c.size();
 197:     Iterator<? extends T> itr = c.iterator();
 198:     while (--pos >= 0)
 199:       result |= (map.put(itr.next(), "") == null);
 200:     return result;
 201:   }
 202: 
 203:   /**
 204:    * Removes all elements in this Set.
 205:    */
 206:   public void clear()
 207:   {
 208:     map.clear();
 209:   }
 210: 
 211:   /**
 212:    * Returns a shallow copy of this Set. The elements are not cloned.
 213:    *
 214:    * @return the cloned set
 215:    */
 216:   public Object clone()
 217:   {
 218:     TreeSet<T> copy = null;
 219:     try
 220:       {
 221:         copy = (TreeSet<T>) super.clone();
 222:         // Map may be either TreeMap or TreeMap.SubMap, hence the ugly casts.
 223:         copy.map = (NavigableMap<T, String>) ((AbstractMap<T, String>) map).clone();
 224:       }
 225:     catch (CloneNotSupportedException x)
 226:       {
 227:         // Impossible result.
 228:       }
 229:     return copy;
 230:   }
 231: 
 232:   /**
 233:    * Returns this Set's comparator.
 234:    *
 235:    * @return the comparator, or null if the set uses natural ordering
 236:    */
 237:   public Comparator<? super T> comparator()
 238:   {
 239:     return map.comparator();
 240:   }
 241: 
 242:   /**
 243:    * Returns true if this Set contains the supplied Object, false otherwise.
 244:    *
 245:    * @param obj the Object to check for
 246:    * @return true if it is in the set
 247:    * @throws ClassCastException if obj cannot be compared with objects
 248:    *         already in the set
 249:    */
 250:   public boolean contains(Object obj)
 251:   {
 252:     return map.containsKey(obj);
 253:   }
 254: 
 255:   /**
 256:    * Returns the first (by order) element in this Set.
 257:    *
 258:    * @return the first element
 259:    * @throws NoSuchElementException if the set is empty
 260:    */
 261:   public T first()
 262:   {
 263:     return map.firstKey();
 264:   }
 265: 
 266:   /**
 267:    * Returns a view of this Set including all elements less than
 268:    * <code>to</code>. The returned set is backed by the original, so changes
 269:    * in one appear in the other. The subset will throw an
 270:    * {@link IllegalArgumentException} for any attempt to access or add an
 271:    * element beyond the specified cutoff. The returned set does not include
 272:    * the endpoint; if you want inclusion, pass the successor element or
 273:    * call {@link #headSet(T,boolean)}.  This call is equivalent to
 274:    * <code>headSet(to, false)</code>.
 275:    *
 276:    * @param to the (exclusive) cutoff point
 277:    * @return a view of the set less than the cutoff
 278:    * @throws ClassCastException if <code>to</code> is not compatible with
 279:    *         the comparator (or is not Comparable, for natural ordering)
 280:    * @throws NullPointerException if to is null, but the comparator does not
 281:    *         tolerate null elements
 282:    */
 283:   public SortedSet<T> headSet(T to)
 284:   {
 285:     return headSet(to, false);
 286:   }
 287: 
 288:   /**
 289:    * Returns a view of this Set including all elements less than
 290:    * (or equal to, if <code>inclusive</code> is true) <code>to</code>.
 291:    * The returned set is backed by the original, so changes
 292:    * in one appear in the other. The subset will throw an
 293:    * {@link IllegalArgumentException} for any attempt to access or add an
 294:    * element beyond the specified cutoff.
 295:    *
 296:    * @param to the cutoff point
 297:    * @param inclusive true if <code>to</code> should be included.
 298:    * @return a view of the set for the specified range.
 299:    * @throws ClassCastException if <code>to</code> is not compatible with
 300:    *         the comparator (or is not Comparable, for natural ordering)
 301:    * @throws NullPointerException if to is null, but the comparator does not
 302:    *         tolerate null elements
 303:    */
 304:   public NavigableSet<T> headSet(T to, boolean inclusive)
 305:   {
 306:     return new TreeSet<T>(map.headMap(to, inclusive));
 307:   }
 308: 
 309:   /**
 310:    * Returns true if this Set has size 0, false otherwise.
 311:    *
 312:    * @return true if the set is empty
 313:    */
 314:   public boolean isEmpty()
 315:   {
 316:     return map.isEmpty();
 317:   }
 318: 
 319:   /**
 320:    * Returns in Iterator over the elements in this TreeSet, which traverses
 321:    * in ascending order.
 322:    *
 323:    * @return an iterator
 324:    */
 325:   public Iterator<T> iterator()
 326:   {
 327:     return map.keySet().iterator();
 328:   }
 329: 
 330:   /**
 331:    * Returns the last (by order) element in this Set.
 332:    *
 333:    * @return the last element
 334:    * @throws NoSuchElementException if the set is empty
 335:    */
 336:   public T last()
 337:   {
 338:     return map.lastKey();
 339:   }
 340: 
 341:   /**
 342:    * If the supplied Object is in this Set, it is removed, and true is
 343:    * returned; otherwise, false is returned.
 344:    *
 345:    * @param obj the Object to remove from this Set
 346:    * @return true if the set was modified
 347:    * @throws ClassCastException if obj cannot be compared to set elements
 348:    */
 349:   public boolean remove(Object obj)
 350:   {
 351:     return map.remove(obj) != null;
 352:   }
 353: 
 354:   /**
 355:    * Returns the number of elements in this Set
 356:    *
 357:    * @return the set size
 358:    */
 359:   public int size()
 360:   {
 361:     return map.size();
 362:   }
 363: 
 364:   /**
 365:    * Returns a view of this Set including all elements greater or equal to
 366:    * <code>from</code> and less than <code>to</code> (a half-open interval).
 367:    * The returned set is backed by the original, so changes in one appear in
 368:    * the other. The subset will throw an {@link IllegalArgumentException}
 369:    * for any attempt to access or add an element beyond the specified cutoffs.
 370:    * The returned set includes the low endpoint but not the high; if you want
 371:    * to reverse this behavior on either end, pass in the successor element
 372:    * or call {@link #subSet(T,boolean,T,boolean)}.  This is equivalent to
 373:    * calling <code>subSet(from,true,to,false)</code>.
 374:    *
 375:    * @param from the (inclusive) low cutoff point
 376:    * @param to the (exclusive) high cutoff point
 377:    * @return a view of the set between the cutoffs
 378:    * @throws ClassCastException if either cutoff is not compatible with
 379:    *         the comparator (or is not Comparable, for natural ordering)
 380:    * @throws NullPointerException if from or to is null, but the comparator
 381:    *         does not tolerate null elements
 382:    * @throws IllegalArgumentException if from is greater than to
 383:    */
 384:   public SortedSet<T> subSet(T from, T to)
 385:   {
 386:     return subSet(from, true, to, false);
 387:   }
 388: 
 389:   /**
 390:    * Returns a view of this Set including all elements greater than (or equal to,
 391:    * if <code>fromInclusive</code> is true</code> <code>from</code> and less than
 392:    * (or equal to, if <code>toInclusive</code> is true) <code>to</code>.
 393:    * The returned set is backed by the original, so changes in one appear in
 394:    * the other. The subset will throw an {@link IllegalArgumentException}
 395:    * for any attempt to access or add an element beyond the specified cutoffs.
 396:    *
 397:    * @param from the low cutoff point
 398:    * @param fromInclusive true if <code>from</code> should be included.
 399:    * @param to the high cutoff point
 400:    * @param toInclusive true if <code>to</code> should be included.
 401:    * @return a view of the set for the specified range.
 402:    * @throws ClassCastException if either cutoff is not compatible with
 403:    *         the comparator (or is not Comparable, for natural ordering)
 404:    * @throws NullPointerException if from or to is null, but the comparator
 405:    *         does not tolerate null elements
 406:    * @throws IllegalArgumentException if from is greater than to
 407:    */
 408:   public NavigableSet<T> subSet(T from, boolean fromInclusive,
 409:                                 T to, boolean toInclusive)
 410:   {
 411:     return new TreeSet<T>(map.subMap(from, fromInclusive,
 412:                                      to, toInclusive));
 413:   }
 414: 
 415:   /**
 416:    * Returns a view of this Set including all elements greater or equal to
 417:    * <code>from</code>. The returned set is backed by the original, so
 418:    * changes in one appear in the other. The subset will throw an
 419:    * {@link IllegalArgumentException} for any attempt to access or add an
 420:    * element beyond the specified cutoff. The returned set includes the
 421:    * endpoint; if you want to exclude it, pass in the successor element
 422:    * or call {@link #tailSet(T,boolean)}.  This is equivalent to calling
 423:    * <code>tailSet(from, true)</code>.
 424:    *
 425:    * @param from the (inclusive) low cutoff point
 426:    * @return a view of the set above the cutoff
 427:    * @throws ClassCastException if <code>from</code> is not compatible with
 428:    *         the comparator (or is not Comparable, for natural ordering)
 429:    * @throws NullPointerException if from is null, but the comparator
 430:    *         does not tolerate null elements
 431:    */
 432:   public SortedSet<T> tailSet(T from)
 433:   {
 434:     return tailSet(from, true);
 435:   }
 436: 
 437:   /**
 438:    * Returns a view of this Set including all elements greater (or equal to,
 439:    * if <code>inclusive</code> is true) <code>from</code>. The returned set
 440:    * is backed by the original, so changes in one appear in the other. The
 441:    * subset will throw an {@link IllegalArgumentException} for any attempt
 442:    * to access or add an element beyond the specified cutoff.
 443:    *
 444:    * @param from the low cutoff point.
 445:    * @param inclusive true if <code>from</code> should be included.
 446:    * @return a view of the set for the specified range.
 447:    * @throws ClassCastException if <code>from</code> is not compatible with
 448:    *         the comparator (or is not Comparable, for natural ordering)
 449:    * @throws NullPointerException if from is null, but the comparator
 450:    *         does not tolerate null elements
 451:    */
 452:   public NavigableSet<T> tailSet(T from, boolean inclusive)
 453:   {
 454:     return new TreeSet<T>(map.tailMap(from, inclusive));
 455:   }
 456: 
 457:   /**
 458:    * Serializes this object to the given stream.
 459:    *
 460:    * @param s the stream to write to
 461:    * @throws IOException if the underlying stream fails
 462:    * @serialData the <i>comparator</i> (Object), followed by the set size
 463:    *             (int), the the elements in sorted order (Object)
 464:    */
 465:   private void writeObject(ObjectOutputStream s) throws IOException
 466:   {
 467:     s.defaultWriteObject();
 468:     Iterator<T> itr = map.keySet().iterator();
 469:     int pos = map.size();
 470:     s.writeObject(map.comparator());
 471:     s.writeInt(pos);
 472:     while (--pos >= 0)
 473:       s.writeObject(itr.next());
 474:   }
 475: 
 476:   /**
 477:    * Deserializes this object from the given stream.
 478:    *
 479:    * @param s the stream to read from
 480:    * @throws ClassNotFoundException if the underlying stream fails
 481:    * @throws IOException if the underlying stream fails
 482:    * @serialData the <i>comparator</i> (Object), followed by the set size
 483:    *             (int), the the elements in sorted order (Object)
 484:    */
 485:   private void readObject(ObjectInputStream s)
 486:     throws IOException, ClassNotFoundException
 487:   {
 488:     s.defaultReadObject();
 489:     Comparator<? super T> comparator = (Comparator<? super T>) s.readObject();
 490:     int size = s.readInt();
 491:     map = new TreeMap<T, String>(comparator);
 492:     ((TreeMap<T, String>) map).putFromObjStream(s, size, "");
 493:   }
 494: 
 495:   /**
 496:    * Returns the least or lowest element in the set greater than or
 497:    * equal to the given element, or <code>null</code> if there is
 498:    * no such element.
 499:    *
 500:    * @param e the element relative to the returned element.
 501:    * @return the least element greater than or equal
 502:    *         to the given element, or <code>null</code> if there is
 503:    *         no such element.
 504:    * @throws ClassCastException if the specified element can not
 505:    *                            be compared with those in the map.
 506:    * @throws NullPointerException if the element is <code>null</code>
 507:    *                              and this set either uses natural
 508:    *                              ordering or a comparator that does
 509:    *                              not permit null elements.
 510:    * @since 1.6
 511:    */
 512:   public T ceiling(T e)
 513:   {
 514:     return map.ceilingKey(e);
 515:   }
 516: 
 517:   /**
 518:    * Returns an iterator over the elements of this set in descending
 519:    * order.  This is equivalent to calling
 520:    * <code>descendingSet().iterator()</code>.
 521:    *
 522:    * @return an iterator over the elements in descending order.
 523:    * @since 1.6
 524:    */
 525:   public Iterator<T> descendingIterator()
 526:   {
 527:     return descendingSet().iterator();
 528:   }
 529: 
 530:   /**
 531:    * Returns a view of the set in reverse order.  The descending set
 532:    * is backed by the original set, so that changes affect both sets.
 533:    * Any changes occurring to either set while an iteration is taking
 534:    * place (with the exception of a {@link Iterator#remove()} operation)
 535:    * result in undefined behaviour from the iteration.  The ordering
 536:    * of the descending set is the same as for a set with a
 537:    * {@link Comparator} given by {@link Collections#reverseOrder()},
 538:    * and calling {@link #descendingSet()} on the descending set itself
 539:    * results in a view equivalent to the original set.
 540:    *
 541:    * @return a reverse order view of the set.
 542:    * @since 1.6
 543:    */
 544:   public NavigableSet<T> descendingSet()
 545:   {
 546:     return map.descendingKeySet();
 547:   }
 548: 
 549:   /**
 550:    * Returns the greatest or highest element in the set less than or
 551:    * equal to the given element, or <code>null</code> if there is
 552:    * no such element.
 553:    *
 554:    * @param e the element relative to the returned element.
 555:    * @return the greatest element less than or equal
 556:    *         to the given element, or <code>null</code> if there is
 557:    *         no such element.
 558:    * @throws ClassCastException if the specified element can not
 559:    *                            be compared with those in the map.
 560:    * @throws NullPointerException if the element is <code>null</code>
 561:    *                              and this set either uses natural
 562:    *                              ordering or a comparator that does
 563:    *                              not permit null elements.
 564:    * @since 1.6
 565:    */
 566:   public T floor(T e)
 567:   {
 568:     return map.floorKey(e);
 569:   }
 570: 
 571:   /**
 572:    * Returns the least or lowest element in the set strictly greater
 573:    * than the given element, or <code>null</code> if there is
 574:    * no such element.
 575:    *
 576:    * @param e the element relative to the returned element.
 577:    * @return the least element greater than
 578:    *         the given element, or <code>null</code> if there is
 579:    *         no such element.
 580:    * @throws ClassCastException if the specified element can not
 581:    *                            be compared with those in the map.
 582:    * @throws NullPointerException if the element is <code>null</code>
 583:    *                              and this set either uses natural
 584:    *                              ordering or a comparator that does
 585:    *                              not permit null elements.
 586:    * @since 1.6
 587:    */
 588:   public T higher(T e)
 589:   {
 590:     return map.higherKey(e);
 591:   }
 592: 
 593:   /**
 594:    * Returns the greatest or highest element in the set strictly less
 595:    * than the given element, or <code>null</code> if there is
 596:    * no such element.
 597:    *
 598:    * @param e the element relative to the returned element.
 599:    * @return the greatest element less than
 600:    *         the given element, or <code>null</code> if there is
 601:    *         no such element.
 602:    * @throws ClassCastException if the specified element can not
 603:    *                            be compared with those in the map.
 604:    * @throws NullPointerException if the element is <code>null</code>
 605:    *                              and this set either uses natural
 606:    *                              ordering or a comparator that does
 607:    *                              not permit null elements.
 608:    * @since 1.6
 609:    */
 610:   public T lower(T e)
 611:   {
 612:     return map.lowerKey(e);
 613:   }
 614: 
 615:   /**
 616:    * Removes and returns the least or lowest element in the set,
 617:    * or <code>null</code> if the map is empty.
 618:    *
 619:    * @return the removed first element, or <code>null</code> if the
 620:    *         map is empty.
 621:    * @since 1.6
 622:    */
 623:   public T pollFirst()
 624:   {
 625:     return map.pollFirstEntry().getKey();
 626:   }
 627: 
 628:   /**
 629:    * Removes and returns the greatest or highest element in the set,
 630:    * or <code>null</code> if the map is empty.
 631:    *
 632:    * @return the removed last element, or <code>null</code> if the
 633:    *         map is empty.
 634:    * @since 1.6
 635:    */
 636:   public T pollLast()
 637:   {
 638:     return map.pollLastEntry().getKey();
 639:   }
 640: 
 641: }