//********************************************
// Hash.h
// -------------------------------------------
// The hash table template
//
// Author: Leiwen Deng
// Date: 11/12/2005
//********************************************

#ifndef HASH_051112_H
#define HASH_051112_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//********************************************
// CHAIN_NODE class
// -------------------------------------------
// Chaining nodes of the hash table
// Each node contains:
//   a key
//   a pointer to the value
//   a pointer to the next chaining node
//********************************************

//********************************************
// Comments on the key and value types used in the hash table
// -------------------------------------------
// KEY_T should have the following functions correctly implemented:
//   operator=, operator==, constructor, destructor, Print( KEY_T& )
// VALUE_T should have the following functions correctly implemented:
//   operator=, constructor, destructor, Print( VALUE_T& )
//********************************************

template <class KEY_T, class VALUE_T>
class HASH_TABLE;

template <class KEY_T, class VALUE_T>
class CHAIN_NODE
{
  KEY_T key; // the key
  VALUE_T value; // pointer to the value
  CHAIN_NODE * next_node; // pointer to the next chaining node

public:
  // Constructor
  CHAIN_NODE( const KEY_T &key_in, const VALUE_T &value_in );

  // Destructor
  ~CHAIN_NODE( void );

  friend class HASH_TABLE<KEY_T, VALUE_T>;
};

//********************************************
// HASH_TABLE class
// -------------------------------------------
// Definition of the hash table
//********************************************

template <class KEY_T, class VALUE_T>
class HASH_TABLE
{
// the hash function type
typedef int HASH_FUNCTION( const KEY_T &key );

  int table_size; // size of the hash table
  int element_number; // number of elements stored in the hash table
  CHAIN_NODE<KEY_T, VALUE_T> ** table; // pointer to the hash table storage area
  HASH_FUNCTION * hash_function; // the hash function

  // Move a node from the original table to the rehashed table
  void RehashNode( CHAIN_NODE<KEY_T, VALUE_T> * node_in );

  // Rehash the whole table
  void Rehash( int new_table_size );

public:
  // Constructor
  HASH_TABLE( int initial_table_size, HASH_FUNCTION * hash_function_in );

  // Destructor
  ~HASH_TABLE( void );

  // Search an entry by its key
  VALUE_T * Find( const KEY_T &key ) const;

  // Insert an entry to the hash table
  bool Insert( const KEY_T &key, const VALUE_T &value );

  // Delete an entry from the hash table
  bool Delete( const KEY_T &key );

  // Display the hash table, for debug purpose
  void ShowTable( FILE * fp ) const;

  // Display the structure of hash table, for debug purpose
  void ShowTableStructure( FILE * fp ) const;
};

// Retrieve the closest prime number no less than <number>
int NextPrime( int number );

//********************************************
// CHAIN_NODE( key_in, value_in  )
// -------------------------------------------
// Constructor
// Constructs the node and sets values of "key" and "value" to <key_in> and <value_in>
//********************************************

template <class KEY_T, class VALUE_T>
CHAIN_NODE<KEY_T, VALUE_T>::CHAIN_NODE( const KEY_T &key_in, const VALUE_T &value_in  )
{
  key = key_in;
  value = value_in;
  next_node = NULL;
}

//********************************************
// ~CHAIN_NODE()
// -------------------------------------------
// Destructor
//********************************************

template <class KEY_T, class VALUE_T>
CHAIN_NODE<KEY_T, VALUE_T>::~CHAIN_NODE( void )
{}

//********************************************
// HASH_TABLE( initial_table_size, hash_function_in )
// -------------------------------------------
// Constructor
//   <initial_table_size> specifies the initial size of the hash table
//   <hash_function_in> specifies the hash function to be used
//********************************************

template <class KEY_T, class VALUE_T>
HASH_TABLE<KEY_T, VALUE_T>::HASH_TABLE( int initial_table_size, HASH_FUNCTION * hash_function_in )
{
  table_size = NextPrime( initial_table_size );
  element_number = 0;
  hash_function = hash_function_in;
  table = new CHAIN_NODE<KEY_T, VALUE_T> * [table_size];
  int i;
  for ( i = 0; i < table_size; i ++ )
    table[i] = NULL;
}

//********************************************
// ~HASH_TABLE()
// -------------------------------------------
// Destructor
//   Free the memory allocated for all elements in the hash table and the hash table itself
//********************************************

template <class KEY_T, class VALUE_T>
HASH_TABLE<KEY_T, VALUE_T>::~HASH_TABLE( void )
{
  int i;
  for ( i = 0; i < table_size; i ++ )
  {
    CHAIN_NODE<KEY_T, VALUE_T> * node = table[i];
    while( node )
    {
      CHAIN_NODE<KEY_T, VALUE_T> * current_node = node; 
      node = node->next_node;
      delete current_node;
    }
  }
  delete [] table;
}

//********************************************
// value = Find( key )
// -------------------------------------------
// Search an entry by its key
// Return the pointer to the value on success, return NULL on failure
//********************************************

template <class KEY_T, class VALUE_T>
VALUE_T * HASH_TABLE<KEY_T, VALUE_T>::Find( const KEY_T &key ) const
{
  int index = hash_function( key ) % table_size;
  CHAIN_NODE<KEY_T, VALUE_T> * node = table[index];
  while ( node )
  {
    if ( node->key == key )
      // Found the element
      return &(node->value);
    node = node->next_node;
  }
  // Not found
  return NULL;
}

//********************************************
// true/false = Insert( key, value )
// -------------------------------------------
// Insert an entry to the hash table
//   <key> speicfies the key of this entry
//   <value> points to the value to store into the table
// Return "false" if the key already exists, otherwise return "true"
//********************************************

template <class KEY_T, class VALUE_T>
bool HASH_TABLE<KEY_T, VALUE_T>::Insert( const KEY_T &key, const VALUE_T &value )
{
  int index = hash_function( key ) % table_size;
  CHAIN_NODE<KEY_T, VALUE_T> ** node = table + index;
  while ( *node )
  {
    if ( (*node)->key == key )
      return false;
    node = &( (*node)->next_node );
  }
  *node = new CHAIN_NODE<KEY_T, VALUE_T>( key, value );
  if ( ++ element_number > ( table_size << 1 ) )
    Rehash( table_size << 1 );
  return true;
}

//********************************************
// true/false = Delete( key )
// -------------------------------------------
// Delete an entry from the hash table
//   <key> speicfies the key of this entry
// Return "false" if the key does not exist, otherwise return "true"
//********************************************

template <class KEY_T, class VALUE_T>
bool HASH_TABLE<KEY_T, VALUE_T>::Delete( const KEY_T &key )
{
  int index = hash_function( key ) % table_size;
  CHAIN_NODE<KEY_T, VALUE_T> ** node = table + index;
  while ( *node )
  {
    if ( (*node)->key == key )
    {
      CHAIN_NODE<KEY_T, VALUE_T> * temp = (*node)->next_node;
      delete *node;
      *node = temp;
      element_number --;
      return true;
    }
    node = &( (*node)->next_node );
  }
  return false;
}

//********************************************
// RehashNode( node_in )
// -------------------------------------------
// Move a node from the original table to the rehashed table
//   <node_in> points to the node to move
//********************************************

template <class KEY_T, class VALUE_T>
void HASH_TABLE<KEY_T, VALUE_T>::RehashNode( CHAIN_NODE<KEY_T, VALUE_T> * node_in )
{
  int index = hash_function( node_in->key ) % table_size;
  CHAIN_NODE<KEY_T, VALUE_T> ** node = table + index;
  while ( *node )
  {
    node = &( (*node)->next_node );
  }
  *node = node_in;
}

//********************************************
// Rehash( new_table_size )
// -------------------------------------------
// Rehash the whole table
//   <new_table_size> speicfies the size of the new table
//********************************************

template <class KEY_T, class VALUE_T>
void HASH_TABLE<KEY_T, VALUE_T>::Rehash( int new_table_size )
{
  int old_table_size = table_size;
  CHAIN_NODE<KEY_T, VALUE_T> ** old_table = table;
  table_size = NextPrime( new_table_size );
  table = new CHAIN_NODE<KEY_T, VALUE_T> * [table_size];
  int i;
  for ( i = 0; i < table_size; i ++ )
    table[i] = NULL;
  for ( i = 0; i < old_table_size; i ++ )
  {
    CHAIN_NODE<KEY_T, VALUE_T> * node = old_table[i];
    while( node )
    {
      RehashNode( node );
      CHAIN_NODE<KEY_T, VALUE_T> * next_node = node->next_node;
      node->next_node = NULL;
      node = next_node;
    }
  }
  delete old_table;
}

//********************************************
// ShowTable( fp )
// -------------------------------------------
// Display the hash table, for debug purpose
//********************************************

template <class KEY_T, class VALUE_T>
void HASH_TABLE<KEY_T, VALUE_T>::ShowTable( FILE * fp ) const
{
  int i, c = 1;
  fprintf( fp, "element_number = %d\n", element_number );
  for ( i = 0; i < table_size; i ++ )
  {
    CHAIN_NODE<KEY_T, VALUE_T> * node = table[i];
    while( node )
    {
      fprintf( fp, "%5d: <%s> (%s)\n", c ++, Print( node->key ), Print( node->value ) );
      node = node->next_node;
    }
  }
}

//********************************************
// ShowTableStructure( fp )
// -------------------------------------------
// Display the structure of hash table, for debug purpose
//********************************************

template <class KEY_T, class VALUE_T>
void HASH_TABLE<KEY_T, VALUE_T>::ShowTableStructure( FILE * fp ) const
{
  int i;
  fprintf( fp, "table_size = %d, element_number = %d\n", table_size, element_number );
  for ( i = 0; i < table_size; i ++ )
  {
    CHAIN_NODE<KEY_T, VALUE_T> * node = table[i];
    fprintf( fp, "%5d: ", i + 1 );
    while( node )
    {
      fprintf( fp, "<%s> --> ", Print( node->key ) );
      node = node->next_node;
    }
    fprintf( fp, "NULL\n" );
  }
}

#endif