import java.util.Enumeration;  // Iterator pattern: to linearize the structure.
// import java.util.Iterator;  // This is the latest version of iterators in Java.

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.
* Uses an abstract equivalence relation to match "equivalent" keys.
* @author Dung X. Nguyen - Copyright 2001 - All rights reserved.
* @since Nov. 28, 2001.
*/
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 k, Object v) {
            key = k;
            val = v;
        }

        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) {
        // Create an array twice the size of _table, re-insert the existing data,
        // then re-assign _table to this new array.
        if (_tableOccupancy == _table.length) {
            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 emptyCase(LRStruct h, Object inp) {
                        return null;
                    }

                    public Object nonEmptyCase(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 KeyValPai(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 emptyCase(LRStruct h, Object inp) {
                    _index++;
                    if (_index >= _table.length) {
                        return Boolean.FALSE;
                    }
                    _lrs = _table[index];
                    return _lrs.execute(this, null);
                }

                public Object nonEmptyCase(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() {
                // advance _lrs to the next LRStruct in the array, if any:
                public Object emptyCase(LRStruct h, Object inp) {
                    _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 nonEmptyCase(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);
        }
    }  // end of HashTableEnumeration
}