import java.util.Enumeration;  // Iterator pattern: to linearize the structure.

import lrs.*;

/**
* Hash table implementation of IDictionary (See Binary search tree).  Uses external chaining.
* Readjusts the load factor by doubling the size of the table array each time the array is filled.
* @author Dung X. Nguyen - Copyright 2000 - All rights reserved.
* @since Dec. 05, 2000.
*/
public class HashTable implements IDictionary
{
   /**
	 * Key/Value Pair to be stored in hash table.
	 */
	private static class KeyValPair
   {
      public Object key;
      public Object val;

      public KeyValPair (Object key, Object val)
      {
         this.key = key;
         this.val = val;
      }

      public String toString ()
      {
         return "(" + key + "," + val + ")";
      }
   }

   /**
	 * Equivalence for KeyValPair.
	 */
	private static class EqKeyVal extends IEquivalence
   {
      private IEquivalence _eqKey;

      private EqKeyVal (IEquivalence eqKey)
      {
         _eqKey = eqKey;
      }

	   public boolean equ (Object x, Object y)
      {
         return _eqKey.equ (((KeyValPair)x).key,  ((KeyValPair)y).key);
      }
   }

   private LRStruct[] _table = new LRStruct[1];
   private int _tableOccupancy = 0;
   private IAlgo _inserter;
   private IAlgo _deleter;
   private IAlgo _finder;

   public HashTable (IEquivalence eq)
   {
      IEquivalence eqKV = new EqKeyVal (eq);
      _inserter = new LRSInserter (eqKV );
      _deleter = new LRSDeleter (eqKV);
      _finder = new LRSFinder (eqKV);
	   for (int i = 0; i < _table.length; i++)
	      _table[i] = new LRStruct();
   }

   public Enumeration enumeration()
   {
	   return new HashTableEnumeration ();
   }

    /**
     * If there is an object associated with key
     * then this object is returned else null is returned.
     */
   public Object retrieve (Object key)
   {
	   int index = key.hashCode() % _table.length;
	   return _table[index].execute (_finder, key);
   }

    /**
     * Afterwards, find(key) returns null, and if there is
     * an object associated with key then this object is
     * returned else null is returned.
     */
   public Object remove (Object key)
   {
	   int index = key.hashCode() % _table.length;
	   Object value = _table[index].execute (_deleter, key);
	   if (value == null)
      {
	      _tableOccupancy--;
      }
	   return value;
   }

    /**
     * (key, value) is stored in this container with no
     * duplication and such that find(key) returns value.
     */
   public void store (Object key, Object value)
   {
      if (_tableOccupancy == _table.length)
      {  // Create an array twice the size of _table, re-insert the existing data,
         // then re-assign _table to this new array.
         int i;
         final LRStruct newTable[] = new LRStruct[2*_table.length];
         for (i = 0; i < newTable.length; i++)
         {
            newTable[i] = new LRStruct();
         }
	      for (i = 0; i < _table.length; i++)
         {
            _table[i].execute (new IAlgo ()
               {
                  public Object forEmpty (LRStruct h, Object inp)
                  {
                     return null;
                  }

                  public Object forNonEmpty (LRStruct h, Object inp)
                  {
		               KeyValPair pair = (KeyValPair) h.getFirst ();
                     int index = pair.key.hashCode() % newTable.length;
                     newTable[index].execute (_inserter, pair);
                  }
               }, null);
         }
         _table = newTable;
      }
	   int index = key.hashCode() % _table.length;
	   _tableOccupancy++;
	   _table[index].execute (_inserter, new KeyValPair (key, value));
   }

   /**
   * Inner class to iterate over the hash table and enumerate all the values in the hash table.
   */
   class HashTableEnumeration implements Enumeration
   {
      private LRStruct _lrs; // the current list.
      private int _index;    // the current index in the _table array.

      HashTableEnumeration ()
      {
	      _index = 0;
         _lrs = _table[_index];
      }

      public boolean hasMoreElements()
      {
         if (_index >= _table.length)
         {
		      return false;
         }
         return ((Boolean)_lrs.execute (
            new IAlgo ()
            {
               public Object forEmpty (LRStruct h, Object inp)
               {
                  _index++;
                  if (_index >= _table.length)
                  {
		               return Boolean.FALSE;
                  }
                  _lrs = _table[index];
                  return _lrs.execute (this, null);
               }

               public Object forNonEmpty (LRStruct h, Object inp)
               {
                  return Boolean.TRUE;
               }
            },
            null)).booleanValue ();
      }

      public Object nextElement()
      {
         if (_index >= _table.length)
         {
		      throw new java.util.NoSuchElementException ("No more elements!");
         }

         return _lrs.execute (
            new IAlgo ()
            {
               public Object forEmpty (LRStruct h, Object inp)
               { // advance _lrs to the next LRStruct in the array, if any:
                  _index++;
                  if (_index >= _table.length)
                  {
		               throw new java.util.NoSuchElementException ("No more elements!");
                  }
                  _lrs = _table[_index];  // _lrs is now the next list in the array.
                  return _lrs.execute (this, null);
               }

               public Object forNonEmpty (LRStruct h, Object inp)
               {
                  KeyValPair res = (KeyValPair)h.getFirst ();
                  _lrs = h.getRest (); // _lrs is now "pointing" to the next element in the list.
                  return res.val;
               }
            },
            null);
      }
   }
}