/////////////////////////////////////////////////////////////////////////////
// HashSet.java -- a class providing a HashMap-backet Set
//
// Copyright (c) 1998 by Jon A. Zeppieri (jon@eease.com)
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU Library General Public License as published
// by the Free Software Foundation, version 2. (see COPYING.LIB)
//
// This program 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 Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public License
// along with this program; if not, write to the Free Software Foundation
// Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307 USA
/////////////////////////////////////////////////////////////////////////////
package java.util;

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

/**
 * This class provides a HashMap-backed implementation of the 
 * Set interface.
 *
 * Each element in the Set is a key in the backing HashMap; each key
 * maps to a static token, denoting that the key does, in fact, exist.
 *
 * Most operations are O(1), assuming no hash collisions.  In the worst
 * case (where all hases collide), operations are O(n).
 *
 * HashSet is a part of the JDK1.2 Collections API.
 *
 * @author      Jon Zeppieri
 * @version     $Revision: 1.1.1.1 $
 * @modified    $Id: HashSet.java,v 1.1.1.1 2000/02/17 08:14:11 hugg Exp $
 */
public class HashSet extends AbstractSet 
    implements Set, Cloneable, Serializable
{
    // INSTANCE VARIABLES -------------------------------------------------
    /** the HashMap which backs this Set */
    private HashMap map;


    // CONSTRUCTORS ---------------------------------------------------------

    /**
     * construct a new, empty HashSet whose backing HashMap has the default 
     * capacity and loadFacor
     */
    public HashSet()
    {
	map = new HashMap();
    }

    /**
     * construct a new, empty HashSet whose backing HashMap has the supplied
     * capacity and the default load factor
     *
     * @param          initialCapacity          the initial capacity of the backing
     *                                          HashMap
     */
    public HashSet(int initialCapacity)
    {
	map = new HashMap(initialCapacity);
    }

    /**
     * construct a new, empty HashSet whose backing HashMap has the supplied
     * capacity and load factor
     *
     * @param          initialCapacity          the initial capacity of the backing
     *                                          HashMap
     * @param          loadFactor               the load factor of the backing HashMap
     */
    public HashSet(int initialCapacity, float loadFactor)
    {
	map =  new HashMap(initialCapacity, loadFactor);
    }

    /**
     * construct a new HashSet with the same elements as are in the supplied
     * collection (eliminating any duplicates, of course; the backing HashMap
     * will have the default capacity and load factor
     *
     * @param          c          a collection containing the elements with
     *                            which this set will be initialized
     */
    public HashSet(Collection c)
    {
	map = new HashMap();
	addAll(c);
    }
    
    
    // PUBLIC METHODS ---------------------------------------------------------

    /**
     * adds the given Object to the set if it is not already in the Set,
     * returns true if teh element was added, false otherwise
     *
     * @param       o       the Object to add to this Set
     */
    public boolean add(Object o)
    {
	if (map.containsKey(o))
	    {
		return false;
	    }
	else
	    {
		internalAdd(o);
		return true;
	    }
    }

    /**
     * empties this Set of all elements; this is a fast operation [O(1)]
     */
    public void clear()
    {
	map.clear();
    }

    /**
     * returns a shallow copy of this Set (the Set itself is cloned; its 
     * elements are not)
     */
    public Object clone()
    {
	Iterator it = iterator();
	HashSet clone = new HashSet(map.capacity, map.loadFactor);
	while (it.hasNext())
	    clone.internalAdd(it.next());
	return clone;
    }

    /**
     * returns true if the supplied element is in this Set, false otherwise
     *
     * @param        o         the Object whose presence in this Set we are testing for
     */
    public boolean contains(Object o)
    {
	return map.containsKey(o);
    }

    /** 
     * returns true if this set has no elements in it (size() == 0)
     */
    public boolean isEmpty()
    {
	return map.isEmpty();
    }

    /**
     * returns an Iterator over the elements of this Set; the Iterator allows
     * removal of elements
     */
    public Iterator iterator()
    {
	return map.keySet().iterator();
    }
    
    /**
     * removes the supplied Object from this Set if it is in the Set; returns
     * true if an element was removed, false otherwise
     */
    public boolean remove(Object o)
    {
	return (map.remove(o) != null);
    }

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


    // PRIVATE METHODS -----------------------------------------------------------

    /** 
     * adds the supplied element to this Set; this private method is used
     * internally [clone()] instead of add(), because add() can be overridden
     * to do unexpected things
     *
     * @param         o        the Object to add to this Set
     */
    private void internalAdd(Object o)
    {
	map.put(o, Boolean.TRUE);
    }

    /** Serialize this Object in a manner which is binary-compatible with the JDK */
    private void writeObject(ObjectOutputStream s) throws IOException
    {
	Iterator it = iterator();
	s.writeInt(map.capacity);
	s.writeFloat(map.loadFactor);
	s.writeInt(size());
	while (it.hasNext())
	    s.writeObject(it.next());
    }

    /** Deserialize this Object in a manner which is binary-compatible with the JDK */
    private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException
    {
      int i, iSize, iCapacity;
      float fLoadFactor;
      Object oElement;

      iCapacity = s.readInt();
      fLoadFactor = s.readFloat();
      iSize = s.readInt();

      map = new HashMap(iCapacity, fLoadFactor);

      for (i = 0; i < iSize; i++)
	{
	  oElement = s.readObject();
	  internalAdd(oElement);
	}
    }
}
