package rpi.goldsd.container;

import java.util.Enumeration;

/**
 * The <tt>Table</tt> class provides a generic associative hashtable by
 * implementing the <tt>AssociativeContainer</tt> interface.  Objects
 * are identified by a unique key object that is also used in determining
 * the corresponding hash values.  The current implementation of the
 * hashtable consists of an array of references to <tt>LinkedList</tt> objects.
 * <p>
 * One of the current shortcomings of this class is the implicit
 * requirement that the <tt>Comparable</tt> key objects also implement
 * the <tt>Hashable</tt> interface.  Thus, instead of a compilation error
 * indicating that a key must be <tt>Hashable</tt>, a run-time exception
 * occurs.
 *
 * @see LinkedList
 * @see Comparable
 * @see Hashable
 * @see DuplicateElementException
 * @see EmptyEnumeration
 * @version 1.3, 3/27/98
 * @author David Goldschmidt
 */
public class Table implements AssociativeContainer
{
  /** The default table size used by the default constructor. */
  public final static int DEFAULT_SIZE = 101;


  /**
   * Encapsulates the information to be stored in this hashtable.
   * @version 1.0, 3/15/98
   * @author David Goldschmidt
   */
  protected class TableData implements Comparable
  {
    public TableData( int hashValue, Comparable key, Object data )
    {
      this.hashValue = hashValue;
      this.key = key;
      this.data = data;
    }

    public boolean isEqualTo( Comparable C )
    {
      if ( C instanceof TableData )
        return ( key.isEqualTo( ((TableData)C).key ) );
      else
        return ( key.isEqualTo( C ) );
    }

    public boolean isLessThan( Comparable C )
    {
      if ( C instanceof TableData )
        return ( key.isLessThan( ((TableData)C).key ) );
      else
        return ( key.isLessThan( C ) );
    }

    public int hashValue;
    public Comparable key;
    public Object data;
  }


  /**
   * Constructs a hashtable with the specified table size.
   * @param tableSize the number of hash "buckets" to construct.
   */
  public Table( int tableSize )
  {
    table = new LinkedList[tableSize];
    numElements = 0;
  }


  /** Constructs a hashtable with the default table size. */
  public Table()  { this( DEFAULT_SIZE ); }


  /**
   * Adds a new associative entry to this hashtable.  If the
   * <tt>Comparable</tt> key parameter does not also implement the
   * <tt>Hashable</tt> interface (which is a sub-interface of the
   * <tt>Comparable</tt> interface), then an <tt>IllegalArgumentException</tt>
   * is thrown.
   * <p>
   * This method performs in <b>O(n)</b> time in the worst-case,
   * where <tt>n</tt> is the number of elements in the hashtable.
   * Inherent in hashing, the average performance is significantly better
   * since the linked-list used to store the data should be very
   * small with an evenly distributed hash function.
   * @param keyAndData the unique key used to identify the associated
   *                   data which is simply the <tt>Comparable</tt> argument.
   * @exception java.lang.IllegalArgumentException if the given key
   *            object does not implement the <tt>Hashable</tt> interface.
   * @exception DuplicateElementException if the key used already
   *            exists in this table.
   */
  public synchronized void add( Comparable keyAndData )
    throws DuplicateElementException, IllegalArgumentException
  {
    add( keyAndData, keyAndData );
  }


  /**
   * Adds a new associative entry to this hashtable.  If the
   * <tt>Comparable</tt> key parameter does not also implement the
   * <tt>Hashable</tt> interface (which is a sub-interface of the
   * <tt>Comparable</tt> interface), then an <tt>IllegalArgumentException</tt>
   * is thrown.
   * <p>
   * This method performs in <b>O(n)</b> time in the worst-case,
   * where <tt>n</tt> is the number of elements in the hashtable.
   * Inherent in hashing, the average performance is significantly better
   * since the linked-list used to store the data should be very
   * small with an evenly distributed hash function.
   * @param key the unique key used to identify the associated data.
   * @param data the actual data to be stored.
   * @exception java.lang.IllegalArgumentException if the given key
   *            object does not implement the <tt>Hashable</tt> interface.
   * @exception DuplicateElementException if the key used already
   *            exists in this table.
   */
  public synchronized void add( Comparable key, Object data )
    throws DuplicateElementException, IllegalArgumentException
  {
    if ( ! ( key instanceof Hashable ) ) throw
      new IllegalArgumentException( "Key must implement Hashable." );

    int hashValue = hash( key );
    TableData node = new TableData( hashValue, key, data );

    if ( table[hashValue] == null )
      table[hashValue] = new LinkedList();
    else if ( table[hashValue].contains( node ) ) throw
      new DuplicateElementException( "Duplicate key: " + key + "." );

    table[hashValue].addToHead( new ListNode( node ) );
    numElements++;
  }


  /**
   * Removes all elements from this hashtable.
   * <p>
   * This method performs in constant time <b>O(1)</b>.
   */
  public synchronized void clear()
  {
    int tableSize = table.length;
    table = new LinkedList[tableSize];
    numElements = 0;
  }


  /**
   * Returns <tt>true</tt> if the given key maps to an element in the
   * associative container.  This method makes use of the <tt>map()</tt>
   * method.
   * <p>
   * This method performs in <b>O(n)</b> in the worst-case; however,
   * performance is substantially better in the average case, provided
   * that the hash function provides an even distribution of hash values.
   * @param key the unique key used to identify an element in the
   *            associative container.
   * @return <tt>true</tt> if the given key maps to an element in
   *         the associative container; <tt>false</tt> otherwise.
   */
  public boolean contains( Comparable key )
  {
    return ( map( key ) != null );
  }


  /**
   * Provides an enumeration of the elements in this hashtable.
   * <p>
   * This method performs in constant time <b>O(1)</b>.
   * @return an enumeration of the elements stored in this hashtable.
   */
  public synchronized Enumeration elements()
  {
    return ( new Enumeration() {
      int tablePosition = 0;
      int elementsReturned = 0;
      Enumeration e = null;

      public boolean hasMoreElements()
      {
        return ( elementsReturned < numElements );
      }

      public Object nextElement()
      {
        if ( ! hasMoreElements() )
          return null;

        if ( e == null || ! e.hasMoreElements() )
        {
          while ( table[tablePosition] == null )
            tablePosition++;
          e = table[tablePosition++].elements();
        }

        ListNode N = (ListNode)e.nextElement();
        elementsReturned++;
        return ( ((TableData)N.getData()).data );
      }
    } );
  }


  /**
   * Provides an enumeration of the elements in this hashtable for
   * a specific hash value (i.e. an enumeration of the elements in
   * the linked list for the given hash value).
   * <p>
   * This method performs in constant time <b>O(1)</b>.
   * @param hashValue the hash value to look up.
   * @return an enumeration of the elements stored in this hashtable
   *         for a specific hash value.
   */
  public synchronized Enumeration elements( final int hashValue )
  {
    if ( table[hashValue % table.length] == null )
      return new EmptyEnumeration();
    else
    {
      return ( new Enumeration() {
        int tablePosition = hashValue % table.length;
        Enumeration e = table[tablePosition].elements();
        public boolean hasMoreElements()  { return e.hasMoreElements(); }
        public Object nextElement()
        {
          ListNode N = (ListNode)e.nextElement();
          TableData D = (TableData)N.getData();
          return ( D.data );
        }
      } );
    }
  }


  /**
   * Returns the number of elements in this hashtable.
   * <p>
   * This method performs in constant time <b>O(1)</b>.
   * @return the number of elements in this hashtable.
   */
  public synchronized int getSize()  { return numElements; }


  /**
   * Returns the size of the hashtable.
   * <p>
   * This method performs in constant time <b>O(1)</b>.
   * @return the size of the hashtable.
   */
  public synchronized int getTableSize()  { return table.length; }


  /**
   * Determines the hash value based on the <tt>Comparable</tt> key.
   * <p>
   * This method performs in constant time <b>O(1)</b>.
   * @exception IllegalArgumentException if the given key object
   *            does not implement the <tt>Hashable</tt> interface.
   */
  protected synchronized int hash( Comparable key )
  {
    if ( ! ( key instanceof Hashable ) ) throw
      new IllegalArgumentException( "Key must implement Hashable." );

    return ( ((Hashable)key).hash( table.length ) );
  }


  /**
   * Returns <tt>true</tt> if this hashtable contains no elements.
   * <p>
   * This method performs in constant time <b>O(1)</b>.
   * @return <tt>true</tt> if this hashtable contains no elements;
   *         <tt>false</tt> otherwise.
   */
  public synchronized boolean isEmpty()  { return ( numElements == 0 ); }


  /**
   * Provides an enumeration of the keys stored in this hashtable.
   * <p>
   * This method performs in constant time <b>O(1)</b>.
   * @return an enumeration of the keys stored in this hashtable.
   */
  public synchronized Enumeration keys()
  {
    return ( new Enumeration() {
      int tablePosition = 0;
      int elementsReturned = 0;
      Enumeration e = null;

      public boolean hasMoreElements()
      {
        return ( elementsReturned < numElements );
      }

      public Object nextElement()
      {
        if ( ! hasMoreElements() )
          return null;

        if ( e == null || ! e.hasMoreElements() )
        {
          while ( table[tablePosition] == null )
            tablePosition++;
          e = table[tablePosition++].elements();
        }

        ListNode nextOne = (ListNode)e.nextElement();
        elementsReturned++;
        return ( ((TableData)nextOne.getData()).key );
      }
    } );
  }


  /**
   * Provides a mechanism for mapping a given key to its corresponding data.
   * <p>
   * This method performs in <b>O(n)</b> time in the worst case,
   * where <tt>n</tt> is the number of elements in the hashtable.
   * Inherent in hashing, the average performance is substantially better
   * since the linked-list used to store the data should be very
   * small with an evenly distributed hash value.
   * @param key the key used to identify and locate the associated data.
   * @return the data stored in this hashtable identified by the
   *         given <tt>key</tt>; or <tt>null</tt> if the given <tt>key</tt>
   *         does not identify an element in this hashtable.
   * @exception IllegalArgumentException if the given <tt>key</tt> object
   *            does not implement the <tt>Hashable</tt> interface.
   */
  public synchronized Object map( Comparable key )
  {
    if ( ! ( key instanceof Hashable ) ) throw
      new IllegalArgumentException( "Key must implement Hashable." );

    int hashValue = hash( key );

    if ( table[hashValue] == null )
      return null;

    ListNode result = table[hashValue].find( key );

    if ( result == null )
      return null;
    else
      return ( ((TableData)result.getData()).data );
  }


  /**
   * Removes a data element from this hashtable identified by the
   * given <tt>key</tt>.
   * <p>
   * This method performs in <b>O(n)</b> time in the worst-case,
   * where <tt>n</tt> is the number of elements in the hashtable.
   * Inherent in hashing, the average performance is substantially better
   * since the linked-list used to store the data should be very
   * small with an evenly distributed hash value.
   * @param key the key used to identify and locate the associated data.
   * @return the object that is removed from this hashtable.
   * @exception IllegalArgumentException if the given <tt>key</tt> object
   *            does not implement the <tt>Hashable</tt> interface.
   */
  public synchronized Object remove( Comparable key )
  {
    if ( ! ( key instanceof Hashable ) ) throw
      new IllegalArgumentException( "Key must implement Hashable." );

    int hashValue = hash( key );

    if ( table[hashValue] == null ) return null;

    ListNode result = table[hashValue].find( key );

    if ( result == null ) return null;

    table[hashValue].remove( result );
    numElements--;

    if ( table[hashValue].isEmpty() )
      table[hashValue] = null;

    return ( ((TableData)result.getData()).data );
  }


  /**
   * The <tt>toString()</tt> method is the default method used to display
   * the keys and corresponding data elements of this hashtable.
   * <p>
   * This method performs in <b>O(n)</b> time since each individual
   * node of the hashtable must be visited once.
   * @return a <tt>String</tt> representing the keys and corresponding data
   *         elements of this hashtable.
   */
  public synchronized String toString()
  {
    String s = "";
    Enumeration e = elements();
    Enumeration k = keys();

    while ( e.hasMoreElements() && k.hasMoreElements() )
      s += k.nextElement() + ": " + e.nextElement() + "\n";

    return s;
  }


  /** The number of associated elements in this hashtable. */
  protected int numElements;


  /** The array of references to <tt>LinkedList</tt> objects. */
  protected LinkedList[] table;
}