TreeSet.java

/* TreeSet.java -- a class providing a TreeMap-backet SortedSet
   Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

As a special exception, if you link this library with other files to
produce an executable, this library does not by itself cause the
resulting executable to be covered by the GNU General Public License.
This exception does not however invalidate any other reasons why the
executable file might be covered by the GNU General Public License. */


package java.util;

import java.io.IOException;
import java.io.Serializable;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;

/**
 * This class provides a TreeMap-backed implementation of the 
 * SortedSet interface.
 *
 * Each element in the Set is a key in the backing TreeMap; each key
 * maps to a static token, denoting that the key does, in fact, exist.
 *
 * Most operations are O(log n).
 *
 * TreeSet is a part of the JDK1.2 Collections API.
 *
 * @author      Jon Zeppieri
 */

public class TreeSet extends AbstractSet
  implements SortedSet, Cloneable, Serializable
{
  /** The TreeMap which backs this Set */
  transient SortedMap map;

  static final long serialVersionUID = -2479143000061671589L;

  /**
   * Construct a new TreeSet whose backing TreeMap using the "natural" 
   * ordering of keys.
   */
  public TreeSet()
  {
    map = new TreeMap();
  }

  /** 
   * Construct a new TreeSet whose backing TreeMap uses the supplied 
   * Comparator.
   *
   * @param     oComparator      the Comparator this Set will use
   */
  public TreeSet(Comparator comparator)
  {
    map = new TreeMap(comparator);
  }

  /** 
   * Construct a new TreeSet whose backing TreeMap uses the "natural"
   * orering of the keys and which contains all of the elements in the
   * supplied Collection.
   *
   * @param     oCollection      the new Set will be initialized with all
   *                             of the elements in this Collection
   */
  public TreeSet(Collection collection)
  {
    map = new TreeMap();
    addAll(collection);
  }

  /**
   * Construct a new TreeSet, using the same key ordering as the supplied
   * SortedSet and containing all of the elements in the supplied SortedSet.
   * This constructor runs in linear time.
   *
   * @param     sortedSet       the new TreeSet will use this SortedSet's
   *                            comparator and will initialize itself
   *                            with all of the elements in this SortedSet
   */
  public TreeSet(SortedSet sortedSet)
  {
    TreeMap map = new TreeMap(sortedSet.comparator());
    int i = 0;
    Iterator itr = sortedSet.iterator();
    map.putKeysLinear(itr, sortedSet.size());
    this.map = map;
  }
  
  /* This private constructor is used to implement the subSet() calls around
    a backing TreeMap.SubMap. */
  TreeSet(SortedMap backingMap)
  {
    map = backingMap;
  }

  /** 
   * Adds the spplied Object to the Set if it is not already in the Set;
   * returns true if the element is added, false otherwise
   *
   * @param       obj       the Object to be added to this Set
   */
  public boolean add(Object obj)
  {
    return (map.put(obj, Boolean.TRUE) == null);
  }

  /**
   * Adds all of the elements in the supplied Collection to this TreeSet.
   *
   * @param        c         All of the elements in this Collection
   *                         will be added to the Set.
   *
   * @return       true if the Set is altered, false otherwise
   */
  public boolean addAll(Collection c)
  {
    boolean result = false;
    int size = c.size();
    Iterator itr = c.iterator();

    for (int i = 0; i < size; i++)
      result |= (map.put(itr.next(), Boolean.TRUE) == null);

    return result;
  }

  /**
   * Removes all elements in this Set.
   */
  public void clear()
  {
    map.clear();
  }

  /** Returns a shallow copy of this Set. */
  public Object clone()
  {
    TreeSet copy = null;
    try
      {
        copy = (TreeSet) super.clone();
      }
    catch (CloneNotSupportedException x)
      {      
      }
    copy.map = (SortedMap) ((TreeMap) map).clone();
    return copy;
  }

  /** Returns this Set's comparator */
  public Comparator comparator()
  {
    return map.comparator();
  }

  /** 
   * Returns true if this Set contains the supplied Object, 
   * false otherwise 
   *
   * @param       oObject        the Object whose existence in the Set is
   *                             being tested
   */
  public boolean contains(Object obj)
  {
    return map.containsKey(obj);
  }

  /** Returns true if this Set has size 0, false otherwise */
  public boolean isEmpty()
  {
    return map.isEmpty();
  }

  /** Returns the number of elements in this Set */
  public int size()
  {
    return map.size();
  }

  /** 
   * If the supplied Object is in this Set, it is removed, and true is
   * returned; otherwise, false is returned.
   *
   * @param         obj        the Object we are attempting to remove
   *                           from this Set
   */
  public boolean remove(Object obj)
  {
    return (map.remove(obj) != null);
  }

  /** Returns the first (by order) element in this Set */
  public Object first()
  {
    return map.firstKey();
  }

  /** Returns the last (by order) element in this Set */
  public Object last()
  {
    return map.lastKey();
  }

  /**
   * Returns a view of this Set including all elements in the interval
   * [oFromElement, oToElement).
   *
   * @param       from  the resultant view will contain all
   *                    elements greater than or equal to this element
   * @param       to    the resultant view will contain all
   *                    elements less than this element
   */
  public SortedSet subSet(Object from, Object to)
  {
    return new TreeSet(map.subMap(from, to));
  }

  /**
   * Returns a view of this Set including all elements less than oToElement
   *
   * @param       toElement    the resultant view will contain all
   *                            elements less than this element
   */
  public SortedSet headSet(Object to)
  {
    return new TreeSet(map.headMap(to));
  }

  /**
   * Returns a view of this Set including all elements greater than or
   * equal to oFromElement.
   *
   * @param       from  the resultant view will contain all
   *              elements greater than or equal to this element
   */
  public SortedSet tailSet(Object from)
  {
    return new TreeSet(map.tailMap(from));
  }

  /** Returns in Iterator over the elements in this TreeSet */
  public Iterator iterator()
  {
    return map.keySet().iterator();
  }

  private void writeObject(ObjectOutputStream out) throws IOException
  {
    Iterator itr = map.keySet().iterator();
    int size = map.size();

    out.writeObject(map.comparator());
    out.writeInt(size);

    for (int i = 0; i < size; i++)
      out.writeObject(itr.next());
  }

  private void readObject(ObjectInputStream in)
    throws IOException, ClassNotFoundException
  {
    Comparator comparator = (Comparator) in.readObject();
    int size = in.readInt();
    TreeMap map = new TreeMap(comparator);    
    map.putFromObjStream(in, size, false);
    this.map = map;
  }
}