home *** CD-ROM | disk | FTP | other *** search
/ Java 1.2 How-To / JavaHowTo.iso / 3rdParty / jbuilder / unsupported / JDK1.2beta3 / SOURCE / SRC.ZIP / java / util / TreeSet.java < prev    next >
Encoding:
Java Source  |  1998-03-20  |  11.6 KB  |  333 lines
  1. /*
  2.  * @(#)TreeSet.java    1.7 98/03/18
  3.  *
  4.  * Copyright 1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. /**
  18.  * This class implements the Set interface, backed by a TreeMap.  This class
  19.  * guarantees that the Map will be in ascending key order, sorted according
  20.  * to the <i>natural sort method</i> for the key Class (see Comparable), or
  21.  * by the Comparator provided at TreeSet creation time, depending on which
  22.  * constructor is used.  Note that this ordering must be <em>total</em>
  23.  * in order for the Tree to function properly.  (A total ordering is 
  24.  * an ordering for which a.compareTo(b)==0 implies that a.equals(b).)
  25.  * <p>
  26.  * This implementation provides guaranteed log(n) time cost for the basic
  27.  * operations (add, remove and contains).
  28.  * <p>
  29.  * <strong>Note that this implementation is not synchronized.</strong> If
  30.  * multiple threads access a TreeSet concurrently, and at least one of the
  31.  * threads modifies the TreeSet, it <em>must</em> be synchronized externally.
  32.  * This is typically accomplished by synchronizing on some object that
  33.  * naturally encapsulates the TreeSet.  If no such object exists, the TreeSet
  34.  * should be "wrapped" using the Collections.synchronizedSet method.  This is
  35.  * best done at creation time, to prevent accidental unsynchronized access to
  36.  * the TreeSet:
  37.  * <pre>
  38.  *    Set s = Collections.synchronizedSet(new TreeSet(...));
  39.  * </pre>
  40.  * <p>
  41.  * The Iterators returned by TreeSet's iterator method are
  42.  * <em>fail-fast</em>: if the HashSet is modified at any time after the
  43.  * Iterator is created, in any way except through the Iterator's own remove
  44.  * method, the Iterator will throw a ConcurrentModificationException.  Thus,
  45.  * in the face of concurrent modification, the Iterator fails quickly and
  46.  * cleanly, rather than risking arbitrary, non-deterministic behavior at an
  47.  * undetermined time in the future.
  48.  *
  49.  * @author  Josh Bloch
  50.  * @version 1.7 03/18/98
  51.  * @see        Collection
  52.  * @see        Set
  53.  * @see        HashSet
  54.  * @see        ArraySet
  55.  * @see     Comparable
  56.  * @see     Comparator
  57.  * @see        Collections.synchronizedSet
  58.  * @see        TreeMap
  59.  * @since JDK1.2
  60.  */
  61.  
  62. public class TreeSet extends AbstractSet
  63.              implements SortedSet, Cloneable, java.io.Serializable
  64. {
  65.     private transient SortedMap m;     // The backing Map
  66.     private transient Set           keySet; // The keySet view of the backing Map
  67.  
  68.     // Dummy value to associate with an Object in the backing Map
  69.     private static final Object PRESENT = new Object();
  70.  
  71.     /**
  72.      * Constructs a TreeSet backed by the given SortedMap.
  73.      */
  74.     private TreeSet(SortedMap m) {
  75.         this.m = m;
  76.         keySet = m.keySet();
  77.     }
  78.  
  79.     /**
  80.      * Constructs a new, empty TreeSet, sorted according to the elements'
  81.      * natural sort method.  All elements inserted into the TreeSet must
  82.      * implement the Comparable interface.  Furthermore, all such elements
  83.      * must be <i>mutually comparable</i>: e1.compareTo(e2) must not throw a
  84.      * typeMismatchException for any elements e1 and e2 in the TreeSet.  If
  85.      * the user attempts to add an element to the TreeSet that violates this
  86.      * constraint (for example, the user attempts to add a String element to
  87.      * a TreeSet whose elements are Integers), the add(Object) call will throw
  88.      * a ClassCastException.
  89.      * @see Comparable
  90.      */
  91.     public TreeSet() {
  92.     this(new TreeMap());
  93.     }
  94.  
  95.     /**
  96.      * Constructs a new, empty TreeSet, sorted according to the given
  97.      * comparator.  All elements inserted into the TreeSet must be <i>mutually
  98.      * comparable</i> by the given comparator: comparator.compare(e1, e2)
  99.      * must not throw a typeMismatchException for any elements e1 and e2
  100.      * in the TreeSet.  If the user attempts to add an element to the
  101.      * TreeSet that violates this constraint, the add(Object) call will throw
  102.      * a ClassCastException.
  103.      */
  104.     public TreeSet(Comparator c) {
  105.     this(new TreeMap(c));
  106.     }
  107.  
  108.     /**
  109.      * Constructs a new TreeSet containing the elements in the specified
  110.      * Collection, sorted according to the elements' <i>natural sort
  111.      * method</i>.  All keys inserted into the TreeSet must implement the
  112.      * Comparable interface.  Furthermore, all such keys must be <i>mutually
  113.      * comparable</i>: k1.compareTo(k2) must not throw a typeMismatchException
  114.      * for any elements k1 and k2 in the TreeSet.
  115.      *
  116.      * @exception ClassCastException the keys in t are not Comparable, or
  117.      *          are not mutually comparable.
  118.      */
  119.     public TreeSet(Collection c) {
  120.         this();
  121.         addAll(c);        
  122.     }
  123.  
  124.     /**
  125.      * Constructs a new TreeSet containing the same elements as the given
  126.      * SortedSet, sorted according to the same ordering.
  127.      */
  128.     public TreeSet(SortedSet s) {
  129.         this(s.comparator());
  130.     addAll(s);  // ***COULD BE LINEAR INSTEAD OF N*LOG(N)***
  131.     }
  132.  
  133.     /**
  134.      * Returns an Iterator over the elements in this TreeSet.  The elements
  135.      * are returned in ascending order.
  136.      */
  137.     public Iterator iterator() {
  138.     return keySet.iterator();
  139.     }
  140.  
  141.     /**
  142.      * Returns the number of elements in this TreeSet (its cardinality).
  143.      */
  144.     public int size() {
  145.     return m.size();
  146.     }
  147.  
  148.     /**
  149.      * Returns true if this TreeSet contains no elements.
  150.      */
  151.     public boolean isEmpty() {
  152.     return m.isEmpty();
  153.     }
  154.  
  155.     /**
  156.      * Returns true if this TreeSet contains the specified element.
  157.      */
  158.     public boolean contains(Object o) {
  159.     return m.containsKey(o);
  160.     }
  161.  
  162.     /**
  163.      * Adds the specified element to this Set if it is not already present.
  164.      *
  165.      * @param o element to be added to this Set.
  166.      * @return true if the Set did not already contain the specified element.
  167.      */
  168.     public boolean add(Object o) {
  169.     return m.put(o, PRESENT)==null;
  170.     }
  171.  
  172.     /**
  173.      * Removes the given element from this Set if it is present.
  174.      *
  175.      * @param o object to be removed from this Set, if present.
  176.      * @return true if the Set contained the specified element.
  177.      */
  178.     public boolean remove(Object o) {
  179.     return m.remove(o)==PRESENT;
  180.     }
  181.  
  182.     /**
  183.      * Removes all of the elements from this Set.
  184.      */
  185.     public void clear() {
  186.     m.clear();
  187.     }
  188.  
  189.     /**
  190.      * Returns a view of the portion of this TreeSet whose elements range
  191.      * from fromElement, inclusive, to toElement, exclusive.  The returned Set
  192.      * is backed by this TreeSet, so changes in the returned Set are
  193.      * reflected in this TreeSet, and vice-versa.  The returned Set supports
  194.      * all optional Set operations.  It does not support the subSet
  195.      * operation.
  196.      * <p>
  197.      * The Set returned by this method will throw an IllegalArgumentException
  198.      * if the user attempts to insert an element outside the specified range.
  199.      *
  200.      * @param fromElement low endpoint (inclusive) of the subSet.
  201.      * @param fromElement high endpoint (exclusive) of the subSet.
  202.      * @exception ClassCastException fromElement or toElement cannot be
  203.      *          compared 
  204.      *          with the elements currently in the TreeSet.
  205.      * @exception NullPointerException fromElement or toElement is null and
  206.      *          this TreeSet uses natural sort method, or its comparator
  207.      *          does not tolerate null elements.
  208.      * @exception IllegalArgumentException fromElement is greater than
  209.      *          toElement.
  210.      */
  211.     public SortedSet subSet(Object fromElement, Object toElement) {
  212.     return new TreeSet(m.subMap(fromElement, toElement));
  213.     }
  214.  
  215.     /**
  216.      * Returns a view of the portion of this TreeSet whose elements are
  217.      * strictly less than toElement.  The returned Set is backed by this
  218.      * TreeSet, so changes in the returned Set are reflected in this TreeSet,
  219.      * and vice-versa.  The returned Set supports all optional Set operations.
  220.      * It does not support the subSet operation, as it is not a TreeSet.
  221.      * <p>
  222.      * The Set returned by this method will throw an IllegalArgumentException
  223.      * if the user attempts to insert an element greater than or equal to
  224.      * toElement.
  225.      *
  226.      * @param toElement high endpoint (exclusive) of the headSet.
  227.      * @exception ClassCastException toElement cannot be compared
  228.      *          with the elements currently in the TreeSet.
  229.      * @exception NullPointerException toElement is null and this
  230.      *          TreeSet uses natural sort method, or its comparator does
  231.      *          not tolerate null elements.
  232.      */
  233.     public SortedSet headSet(Object toElement) {
  234.     return new TreeSet(m.headMap(toElement));
  235.     }
  236.  
  237.     /**
  238.      * Returns a view of the portion of this TreeSet whose elements are
  239.      * strictly less than toElement.  The returned Set is backed by this
  240.      * TreeSet, so changes in the returned Set are reflected in this TreeSet,
  241.      * and vice-versa.  The returned Set supports all optional Set operations.
  242.      * It does not support the subSet operation, as it is not a TreeSet.
  243.      * <p>
  244.      * The Set returned by this method will throw an IllegalArgumentException
  245.      * if the user attempts to insert an element greater than or equal to
  246.      * toElement.
  247.      *
  248.      * @param toElement high endpoint (exclusive) of the headSet.
  249.      * @exception ClassCastException toElement cannot be compared
  250.      *          with the elements currently in the TreeSet.
  251.      * @exception NullPointerException toElement is null and this
  252.      *          TreeSet uses natural sort method, or its comparator does
  253.      *          not tolerate null elements.
  254.      */
  255.     public SortedSet tailSet(Object fromElement) {
  256.     return new TreeSet(m.tailMap(fromElement));
  257.     }
  258.  
  259.     /**
  260.      * Returns the comparator used to order this TreeMap, or null if this
  261.      * TreeMap uses its keys natural sort method.
  262.      */
  263.     public Comparator comparator() {
  264.         return m.comparator();
  265.     }
  266.  
  267.     /**
  268.      * Returns the first (lowest) element currently in this TreeSet.
  269.      *
  270.      * @return the first (lowest) element currently in this TreeSet.
  271.      * @exception NoSuchElementException Set is empty.
  272.      */
  273.     public Object first() {
  274.         return m.firstKey();
  275.     }
  276.  
  277.     /**
  278.      * Returns the last (highest) element currently in this TreeSet.
  279.      *
  280.      * @return the last (highest) element currently in this TreeSet.
  281.      * @exception NoSuchElementException Set is empty.
  282.      */
  283.     public Object last() {
  284.         return m.lastKey();
  285.     }
  286.  
  287.     /**
  288.      * Returns a shallow copy of this TreeSet. (The elements themselves
  289.      * are not cloned.)
  290.      */
  291.     public Object clone() {
  292.         return new TreeSet(this);
  293.     }
  294.  
  295.     /**
  296.      * Save the state of the TreeSet to a stream (i.e., serialize it).
  297.      */
  298.     private synchronized void writeObject(java.io.ObjectOutputStream s)
  299.         throws java.io.IOException {
  300.     // Write out any hidden stuff
  301.     s.defaultWriteObject();
  302.  
  303.         // Write out size
  304.         s.writeInt(m.size());
  305.  
  306.     // Write out all elements in the proper order.
  307.     for (Iterator i=m.keySet().iterator(); i.hasNext(); )
  308.             s.writeObject(i.next());
  309.     }
  310.  
  311.     /**
  312.      * Reconstitute the LinkedList from a stream (i.e., deserialize it).
  313.      */
  314.     private synchronized void readObject(java.io.ObjectInputStream s)
  315.         throws java.io.IOException, ClassNotFoundException {
  316.     // Read in any hidden stuff
  317.     s.defaultReadObject();
  318.  
  319.         // Create backing TreeMap and keySet view
  320.         m = new TreeMap();
  321.         keySet = m.keySet();
  322.  
  323.         // Read in size
  324.         int size = s.readInt();
  325.  
  326.     // Read in all elements in the proper order.
  327.     for (int i=0; i<size; i++) {
  328.             Object e = s.readObject();
  329.             m.put(e, PRESENT);
  330.         }
  331.     }
  332. }
  333.