/****************************************************************************/
/*                                                                          */
/*  Copyright (c) 1994-1996                                                 */
/*  Jeremy Levitt                                                           */
/*                                                                          */
/****************************************************************************/

#ifndef _hash_h_
#define _hash_h_

#include <iostream.h>
#include "misc.h"

#ifndef NULL
#define NULL 0
#endif

const int HASH_TABLE_SIZE = 1024;
const int HASH_TABLE_GROW_THRESHOLD = 1;
const int HASH_TABLE_GROW_FACTOR = 2;
typedef void *void_pointer;

template <class _Key, class _Data> class Hash_Table;
template <class _Key, class _Data> class Hash_Entry;
template <class _Key, class _Data> class Hash_Ptr;

/****************************************************************************/
/*  class Hash_Entry                                                        */
/****************************************************************************/
template <class _Key, class _Data>
class Hash_Entry {
private:
  _Key _key;
  _Data _data;
  Hash_Entry *_next;
  Hash_Entry(const _Key &key, const _Data &data) : 
  _key(key), _data(data), _next(NULL) {}
  Hash_Entry(const Hash_Entry &rhs) : 
  _key(rhs._key), _data(rhs._data), _next(NULL) {}
  ~Hash_Entry() {}
  friend class Hash_Table<_Key, _Data>;
  
public:
  Hash_Entry* Next() const { return _next; } 
  _Key Key() const { return _key; }
  _Data& Data() { return _data; }
  IF_DEBUG(
    void Print();
  )
};


/****************************************************************************/
/*  class Hash_Table                                                        */
/****************************************************************************/
template <class _Key, class _Data>
class Hash_Table {
private:
  Hash_Entry<_Key, _Data> **_hashTbl;
  int (*_hashFunc)(const _Key);               // must return a positive int
  int (*_matchFunc)(const _Key, const _Key);  // return (k1==k2) ? 1 : 0
  int _size;
  int _growThreshold;
  int _growFactor;
  int _numEntries;
  Hash_Entry<_Key, _Data>** Find_Hash_Entry(_Key&);
  void Copy(const Hash_Table &rhs);
  void Resize(int size);
  void Destroy();
  friend class Hash_Ptr<_Key, _Data>;
  
public:
  Hash_Table(int (*hashFunction)(const _Key),
	     int (*matchFunc)(const _Key, const _Key),
       int size = HASH_TABLE_SIZE, int threshold = HASH_TABLE_GROW_THRESHOLD,
       int factor = HASH_TABLE_GROW_FACTOR);
  Hash_Table(const Hash_Table &hash) { Copy(hash); }
  ~Hash_Table() { Destroy(); }
  int Insert(_Key key, _Data data);
  int Delete(_Key key);
  void Clear();
  Hash_Table& operator= (const Hash_Table &rhs);
  _Data* Fetch(_Key key);
  _Data& operator[] (_Key key);
  int Size() const { return _size; }
  int NumEntries() const { return _numEntries; }
  IF_DEBUG(
    void Print();
  )
};


/****************************************************************************/
/*  class Hash_Ptr                                                          */
/****************************************************************************/
template <class _Key, class _Data>
class Hash_Ptr {
private:
  Hash_Table<_Key, _Data> *_hash;
  int _index;
  Hash_Entry<_Key, _Data> *_hashEntry;
  void Set_Next_Hash_Entry();
  
public:
  Hash_Ptr() : _hash(0), _index(0), _hashEntry(0) {}
  Hash_Ptr(Hash_Table<_Key, _Data> *hash) : 
  _hash(hash), _index(0), _hashEntry(hash->_hashTbl[0]) 
    { if (_hashEntry == NULL) Set_Next_Hash_Entry(); }
  Hash_Ptr(const Hash_Table<_Key, _Data> *hash) :
    _hash((Hash_Table<_Key, _Data>*)hash), _index(0),
    _hashEntry(hash->_hashTbl[0])
    { if (_hashEntry == NULL) Set_Next_Hash_Entry(); }
  Hash_Entry<_Key, _Data>* operator-> () { return _hashEntry; }
  Hash_Entry<_Key, _Data>& operator* () 
    { ASSERT(_hashEntry);  return *_hashEntry; }
  operator void_pointer() const { return void_pointer(_hashEntry); }
  int Null() const { return _hashEntry == NULL; }
  void operator++ () { Set_Next_Hash_Entry(); }
  void Reset(Hash_Table<_Key, _Data> *hash)
    { *this = Hash_Ptr(hash); }
};   


/****************************************************************************/
/*    Hash_Table::Hash_Table()                                              */
/****************************************************************************/
template <class _Key, class _Data>
Hash_Table<_Key, _Data>::Hash_Table
(int (*hashFunc)(const _Key), int (*matchFunc)(const _Key, const _Key),
 int size, int threshold, int factor)
: _hashFunc(hashFunc), _matchFunc(matchFunc), _size(size),
  _growThreshold(threshold), _growFactor(factor), _numEntries(0)
{
  ASSERT(_growFactor >= HASH_TABLE_GROW_FACTOR);
  ASSERT(_growThreshold >= HASH_TABLE_GROW_THRESHOLD);

  _hashTbl = new Hash_Entry<_Key, _Data> *[_size];
  for(int i=0; i<_size; i++)
    _hashTbl[i] = NULL;
}


/****************************************************************************/
/*    Hash_Table::Destroy()                                                 */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::Destroy()
{
  for (int i=0; i<_size; i++) {
    Hash_Entry<_Key, _Data> *tmp = _hashTbl[i];

    while(tmp != NULL) {
      Hash_Entry<_Key, _Data> *next = tmp->_next;
      delete tmp;
      tmp = next;
    }
  }

  delete [] _hashTbl;
}


/****************************************************************************/
/*    Hash_Table::Copy()                                                    */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::Copy(const Hash_Table<_Key, _Data> &rhs)
{
  _hashFunc = rhs._hashFunc;
  _matchFunc = rhs._matchFunc;
  _numEntries = rhs._numEntries;
  _size = rhs._size;
  _growThreshold = rhs._growThreshold;
  _growFactor = rhs._growFactor;
  _hashTbl = new Hash_Entry<_Key, _Data> *[rhs._size];

  for (int i=0; i<rhs._size; i++) {
    Hash_Entry<_Key, _Data> *tmp = rhs._hashTbl[i];
    Hash_Entry<_Key, _Data> **copy = &(_hashTbl[i] = NULL);

    while(tmp != NULL) {
      *copy = new Hash_Entry<_Key, _Data>(*tmp);
      copy = &(*copy)->_next;
      tmp = tmp->_next;
    }
  }
}


/****************************************************************************/
/*    Hash_Table::Resize()                                                  */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::Resize(int size)
{
  Hash_Table<_Key, _Data> tmp(_hashFunc, _matchFunc, size);

  Hash_Ptr<_Key, _Data> ptr(this);
  for (;!ptr.Null(); ++ptr) {
    _Key key = ptr->Key();
    tmp.Insert(key, ptr->Data());
  }

  Destroy();
  Copy(tmp);
}


/****************************************************************************/
/*   Hash_Table::operator=                                                  */
/****************************************************************************/
template <class _Key, class _Data>
Hash_Table<_Key, _Data>& Hash_Table<_Key, _Data>::operator=
(const Hash_Table<_Key, _Data> &rhs)
{
  if (this != &rhs) {
    Destroy();
    Copy(rhs);
  }

  return *this;
}


/****************************************************************************/
/*    Hash_Table::Find_Hash_Entry()                                         */
/*                                                                          */
/*    Return a pointer to the element if found, or a pointer to where       */
/*    the element should be if not found.                                   */
/****************************************************************************/
template <class _Key, class _Data>
Hash_Entry<_Key, _Data>** 
Hash_Table<_Key, _Data>::Find_Hash_Entry(_Key &key)
{
  int index = (*_hashFunc)(key) % _size;
  ASSERT(index >=0);
  Hash_Entry<_Key, _Data>** link = &_hashTbl[index];
  
  while (*link != NULL && !_matchFunc((*link)->_key, key))
    link = &((*link)->_next);

  return link;
}


/****************************************************************************/
/*    Hash_Table::Insert()                                                  */
/*                                                                          */
/*    Return 0 if the element was successfully inserted                     */
/*    Return 1 if insertion fails becuase an entry with the same key        */
/*    is already present                                                    */
/****************************************************************************/
template <class _Key, class _Data>
int Hash_Table<_Key, _Data>::Insert(_Key key, _Data data)
{
  if (_numEntries>_size*_growThreshold)
    Resize(_size*_growFactor);

  Hash_Entry<_Key, _Data>* hash_entry = 
    new Hash_Entry<_Key, _Data>(key, data);
  Hash_Entry<_Key, _Data>** link = Find_Hash_Entry(key);
  
  if (*link != NULL) {
    delete hash_entry;
    return 1;
  }
  
  _numEntries++;
  *link = hash_entry;
  return 0;
}


/****************************************************************************/
/*    Hash_Table::Delete()                                                  */
/*                                                                          */
/*    Return 0 if the element was successfully deleted and 1                */
/*    if the deletion failed becuase the entry could not be found.          */
/****************************************************************************/
template <class _Key, class _Data>
int Hash_Table<_Key, _Data>::Delete(_Key key)
{
  Hash_Entry<_Key, _Data>** link = Find_Hash_Entry(key);
  Hash_Entry<_Key, _Data>* tmp;
  
  if (*link == NULL)
    return 1;
  
  _numEntries--;
  tmp = (*link);
  *link = (*link)->_next;
  delete tmp;
  return 0;
}


/****************************************************************************/
/*    Hash_Table::Clear()                                                   */
/*                                                                          */
/*    Delete all elements in the hash table.                                */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::Clear()
{
  for (int i=0; i<_size; i++) {
    Hash_Entry<_Key, _Data> *tmp = _hashTbl[i];
    _hashTbl[i] = NULL;

    while(tmp != NULL) {
      Hash_Entry<_Key, _Data> *next = tmp->_next;
      delete tmp;
      tmp = next;
    }
  }
  _numEntries = 0;
}


/****************************************************************************/
/*    Hash_Table::Fetch()                                                   */
/*                                                                          */
/*    Return a pointer to the element if it was found, otherwise return     */
/*    a NULL pointer.                                                       */
/****************************************************************************/
template <class _Key, class _Data>
_Data* Hash_Table<_Key, _Data>::Fetch(_Key key)
{
  Hash_Entry<_Key, _Data>** link = Find_Hash_Entry(key);
  return (*link) ? &(*link)->Data() : (_Data *)NULL;
}


/****************************************************************************/
/*    Hash_Table::operator[]                                                */
/****************************************************************************/
template <class _Key, class _Data>
_Data& Hash_Table<_Key, _Data>::operator[] (_Key key)
{
  _Data* result = Fetch(key);
  ASSERT(result != NULL);
  return *result;
}


/****************************************************************************/
/*    Hash_Ptr::Set_Next_Hash_Entry()                                       */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Ptr<_Key, _Data>::Set_Next_Hash_Entry()
{
  if (_hashEntry != NULL && _hashEntry->Next() != NULL) {
    _hashEntry = _hashEntry->Next();
    return;
  }
  
  while (++_index < _hash->_size)
    if (_hash->_hashTbl[_index] != NULL) {
      _hashEntry = _hash->_hashTbl[_index];
      return;
    }
  
  _hashEntry = NULL;
}


template <class _Key, class _Data>
void HashUpdateIntData(Hash_Table<_Key, _Data>& t, _Key key, _Data i)
{
  _Data *tmp = t.Fetch(key);
  if (tmp) *tmp = *tmp + i;
  else t.Insert(key, i);
}


#ifdef DEBUG
/****************************************************************************/
/*    Hash_Entry::operator<<                                                */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Entry<_Key, _Data>::Print()
{ 
  cout << "key: \"" << Key() << "\" data: " << Data() << '\n';
}


/****************************************************************************/
/*    Hash_Table::operator<<                                                */
/****************************************************************************/
template <class _Key, class _Data>
void Hash_Table<_Key, _Data>::Print()
{ 
  for (Hash_Ptr<_Key, _Data> ptr(this); !ptr.Null(); ++ptr) 
    ptr->Print();
}
#endif


#endif /* _hash_h_ */