///////    File: HashTable.C    ///////
#include <iostream.h>
#include <string.h>
#include <limits.h>
#include "HashTable.h"

template <class T>
HashTable<T>::HashTable
(Uint k /* = 8 */, Uint m /* = H_MULT */)
:     bits(k), mult(m), len(0)
{    int size = 1 << bits;
     ht = new List<T>*[size];
     for ( int i = 0; i < size; i++ )
          ht[i] = NULL;
}

template <class T>
HashTable<T>::~HashTable()
{    int size = 1 << bits;
     for ( int i = 0; i < size; i++ )
         if ( ht[i] ) delete(ht[i]);
     delete(ht);
}

Uint str_to_u(const char *str)     // intentional file scope function
{    Uint value = 7u; 
     char c;
      while ( (c = *str) != '\0' )
      {    value *= c;
           str++;
      }
      return(value);
}

template <class T>
Uint HashTable<T>::hash(const char* key)
{    Uint val = 0;
     val = str_to_u(key);
     return( (val*mult) >> (CHAR_BIT*sizeof(Uint) - bits));
}

template <class T>
int HashTable<T>::get(const char* key, T& rval)
{    List<T>* a = ht[hash(key)];
     if ( !a ) return(noe);
     ListIterator<T> next(*a);
     T item;
     while ( next(item) ) 
        if ( strcmp (key, getkey(item)) == 0 )
        {    rval = item;
             return( ! noe);      // entry found 
        }
     return(noe);                 // not found
}

template <class T>
int HashTable<T>::is_on(char* key)   // record already on table?
{    List<T>* a = ht[hash(key)];
     if ( !a || ! on_list(*a, key) )
        return(noe);
     return( !noe );
}

template <class T>           // static private member function
int HashTable<T>::on_list
(List<T>& l, char* key)
{    T item;
     ListIterator<T> next(l);
     while ( next(item) ) 
        if ( strcmp (key, getkey(item)) == 0 )
             return(1);      // entry found 
     return(0);              // not found
}

template <class T>
int HashTable<T>::rid(const char* key)
{    Uint code = hash(key);
     List<T>* a = ht[code];
     if ( !a ) return(noe);
     ListIterator<T> next(*a);
     T item;
     while ( next(item) ) 
        if ( strcmp (key, getkey(item)) == 0 )
        {  next.del();  len--;
           if ( a->is_empty() )
               ht[code] = NULL;
           return(! noe);
        }
     return(noe);
}

// enter new entry into hash table
template <class T>
void HashTable<T>::put(T& a)         // enter a into hash table
{    char *key = getkey(a);
     Uint hc = hash(key);
     List<T>* l = ht[hc];
     if ( l == NULL )                // loccation not used before
     {   ht[hc] = new List<T>(a);
         len++; return;
     }
     if ( ! on_list(*l, key) )       // if not already in table
     {  len++;  l->put_on(a); }      // put record on table
     return;
}