#ifndef Hash_h_
#define Hash_h_

//
//  File:     hash.h
//  Author:   Chuck Stewart
//
// Purpose: 
//    This is a template class implementing a hash table that uses
//    separate chaining to store objects of type ElementType.  Each
//    object will have an associated key, which is used to determine
//    where it should be stored.  From the outside the class behaves
//    in a similar manner to a std::map.  It enforces uniqueness of
//    keys and provides a subscripting operator.  It does not do
//    is provide any ordered access to the values --- this is contrary
//    to structure of a hash table.  The result of insert and find
//    operations are pointers to entries in the hash table.  Each
//    entry is a std::pair containing a constant (string) and an
//    ElementType.  These are similar to the iterators returned from
//    map operations.  They are not called iterators, however, because
//    the term iterator connotes being able to move through the
//    structure in a predictable and intuitive way, which is not
//    possible for a hash table. 
//
//    Entries associated with each hash value are stored in a linked
//    list.  This is a bare-bones and efficient list implementation
//    because no sophisticated access is needed.
//
//    Finally and importantly, the hash table is dynamically resized
//    when the number of entries approaches the size of the table.
//    Doing this maintains the expected constant time access behavior
//    of hash tables regardless of the number of entries.  
//
//  Compilation notes:
//    Under g++ version 2.7.2 this does NOT compile
//    Under g++ version 2.8.1 (run setup gcc-2.8.1) it compiles cleanly.
//    Under VC 5.0 (the version in the labs), you need to append VC50
//      to "Preprocessor definitions" under Project => Settings => C/C++.
//      Compilation fails for the assignment operator on a pair involving
//      a const, something that is never used (and therefore shouldn't be
//      compiled!)
//    Under VC 6.0 (the new version) it compiles.

#ifdef GNU
#define std
#endif
#include <string>
#include <vector>

const unsigned int Default_Size = 13;
const float Max_Fraction=0.95;  // fraction full for resizing


template <class ElementType>
class HashTable {
public:
  typedef std::pair<const std::string, ElementType> entry_type;
  typedef entry_type* entry_ptr;

  // this second typedef for a pair is needed to strip off the const
  // when copying the entire hash table to a vector.
  typedef std::pair<std::string, ElementType> exported_type;
  
  class HNode {  // the internal nodes
  public:
    HNode( const std::string& s, const ElementType& e )
      : entry(s,e), next(0) {}
    entry_type entry;
    HNode * next;
  };
  typedef HNode* node_ptr;

  // Constructors.
  HashTable( unsigned int init_size = Default_Size );
  HashTable( const HashTable<ElementType>& old_table );

  // Destructor.
  ~HashTable( );

  // Assignment operator
  const HashTable<ElementType> &
    operator= ( const HashTable<ElementType> & value );

  // Subscripting operator giving the look of an associative structure. 
  // Creates the entry if it wasn't already there.
  ElementType& operator[] ( const std::string& key );

  // Find the (first) entry in the table having the given key.  Return an
  // entry_ptr that is a pointer to the entry.  Return 0 (NULL) if the
  // key is not in the table.
  entry_ptr Find( const std::string & Key ) const;

  // Insert the key and element into the table.  Returns a pointer to
  // the entry if successful and 0 (NULL) otherwise.  It fails it the
  // key is already in the hash table.
  entry_ptr Insert( const std::string& key, const ElementType & element );

  // Remove the (first) entry in the table having the given key.
  // Returns true if and only if the key was in the table.
  bool Remove( const std::string& key );

  // Print the keys and entries in the table to std::cout.
  void PrintTable() const;

  // Return copies of the table entries in a vector
  void ToVector( std::vector<exported_type>& v ) const;

private:
  // private versions of above functions to avoid redundant calculations
  // of the hash value
  entry_ptr Find( const std::string & Key, unsigned int hvalue ) const;
  entry_ptr Insert( const std::string & Key, const ElementType& element,
		    unsigned int hvalue );
  
  void AllocateTable();  // memory allocation utility
  void DeleteTable();    // delete entire table and entries
  void ExpandTable();    // double the table size
  void CopyTable( const HashTable<ElementType>& old_table);

   // In the following hash function << 5 is a left-shift by 5 bits,
   // which is equivalent to multiplying by 32.
   //
   static int
   Hash(const std::string& key, int tbl_size)
      {
         unsigned int value = 0;
         for ( int i=0; i<key.length(); i++ )
            value = ( value << 5 ) + key[i]; 
         return value % tbl_size;
      }

private:
  int table_size_;
  int num_stored_;
  node_ptr * lists_;
};


//  Base constructor.  Records the table size and then allocates the
//  actual table.
//
template <class ElementType>
HashTable<ElementType>::
HashTable( unsigned int init_size )
{
  table_size_ = init_size;
  num_stored_ = 0;
  AllocateTable();
}

//  Copy constructor.
//
template <class ElementType>
HashTable<ElementType>::
HashTable( const HashTable<ElementType>& old_table )
{
  CopyTable( old_table );
}


template <class ElementType>
HashTable<ElementType>::
~HashTable( )
{
  DeleteTable();
}


//  Overloaded assignment operator.
//
template <class ElementType>
const HashTable<ElementType> &
HashTable<ElementType>::
operator = ( const HashTable<ElementType> & value )
{
  if( this != &value ) {
    DeleteTable();
    CopyTable();
  }
  return *this;
}


template <class ElementType>
ElementType &
HashTable<ElementType>::
operator[] ( const std::string& key )
{
  unsigned int hvalue = Hash( key, table_size_ );
  entry_ptr e_ptr = Find( key, hvalue );
  if ( !e_ptr )
    e_ptr = Insert( key, ElementType(), hvalue );  // default ElementType
  return e_ptr->second;
}
  

template <class ElementType>
HashTable<ElementType>::entry_ptr
HashTable<ElementType>::
Find( const std::string & key ) const
{
  unsigned int hvalue = Hash( key, table_size_ );
  return Find( key, hvalue );
}

template <class ElementType>
HashTable<ElementType>::entry_ptr
HashTable<ElementType>::
Find( const std::string & key, unsigned int hvalue ) const
{
  node_ptr p = lists_[hvalue];
  while ( p && p->entry.first != key ) 
    p = p->next;
  return p ? &(p->entry) : 0;
}

//  Insert operator dynamically resizes the table if there are too
//  many entries.  Then it does the insert as described above.
//
template <class ElementType>
HashTable<ElementType>::entry_ptr
HashTable<ElementType>::
Insert( const std::string& key, const ElementType & element )
{
  if ( num_stored_ > table_size_ * Max_Fraction )
    ExpandTable();
  unsigned int hvalue = Hash( key, table_size_ );
  entry_ptr e_ptr = Find( key, hvalue );
  if ( e_ptr )
    return 0;  // insert fails because key is already there
  else
    return Insert( key, element, hvalue );
}


//  private Insert.  It is only called after ensuring that the
//  key is not in the table.
//
template <class ElementType>
HashTable<ElementType>::entry_ptr
HashTable<ElementType>::
Insert( const std::string & key, const ElementType & element,
	unsigned int hvalue )
{
  //  node_ptr p = new HNode<ElementType>(key,element);
  node_ptr p = new HNode(key,element);
  p->next = lists_[hvalue];
  lists_[hvalue] = p;
  ++ num_stored_;
  return &(p->entry);
}



template <class ElementType>
bool 
HashTable<ElementType>::
Remove( const std::string& key )
{
  unsigned int hvalue = Hash( key, table_size_ );
  node_ptr prev=0, p=lists_[hvalue];
  while ( p && p->entry.first != key ) {
    prev = p; p = p->next;
  }
  if ( p ) {
    if ( prev ) 
      prev->next = p->next;
    else   // p == lists_[hvalue]
      lists_[hvalue] = p->next;
    delete p;
    return true;
  }
  else
    return false;
}



template <class ElementType>
void
HashTable<ElementType>::
AllocateTable()
{
  lists_ = new node_ptr[table_size_] ;
  for ( int i=0; i<table_size_; ++ i ) lists_[i] = 0;
}


template <class ElementType>
void
HashTable<ElementType>::
DeleteTable( )
{
  for ( int i=0; i<table_size_; i++ ) {
    node_ptr p = lists_[i];
    while ( p ) {
      node_ptr n = p->next;
      delete p;
      p = n;
    }
  }
  delete [] lists_;
}


//  Increase the size of the table and rehash keys based on the new
//  size.  No reallocation of nodes is necessary.
template <class ElementType>
void
HashTable<ElementType>::
ExpandTable( )
{
  int old_size = table_size_;
  node_ptr * old_lists = lists_;
  table_size_ = 2*table_size_ + 1;
  AllocateTable();

  for ( int i=0; i<old_size; i++ ) {
    node_ptr p = old_lists[i];
    while ( p ) {
      int hash_val = Hash( p->entry.first, table_size_ );
      node_ptr temp = p->next;
      p->next = lists_[hash_val];
      lists_[hash_val] = p;
      p = temp;
    }
  }
  delete [] old_lists;
}


template <class ElementType>
void
HashTable<ElementType>::
CopyTable( const HashTable<ElementType>& old_table)
{
  table_size_ = old_table.table_size_;
  num_stored_ = old_table.num_stored_;
  lists_ = new node_ptr[table_size_];
  for ( int i=0; i<table_size_; i++ ) {
    lists_[i] = 0;
    node_ptr p=0;
    for ( node_ptr old_p = old_table.lists_[i]; old_p; old_p=old_p->next ) {
      node_ptr new_p
	= new HNode(old_p->entry.first, old_p->entry.second);
      if ( p ) 
	p->next = new_p;
      else
	lists_[i] = new_p;
      p = new_p;
    }
  }
}

	  
template <class ElementType>
void
HashTable<ElementType>::
PrintTable() const
{
  std::cout << "\nTable size: " << table_size_ << "\n";
  for ( int i=0; i<table_size_; i++ ) {
    std::cout << i << ":  ";
    for ( node_ptr p=lists_[i]; p; p = p->next ) {
      std::cout << "    " << p->entry.first
		<< " , " << p->entry.second;
    }
    std::cout << std::endl;
  }
}


template <class ElementType>
void
HashTable<ElementType>::
ToVector( std::vector<HashTable<ElementType>::exported_type>& v ) const
{
  v.erase( v.begin(), v.end() );
  for ( int i=0; i<table_size_; i++ ) {
    for ( node_ptr p=lists_[i]; p; p = p->next ) {
      v.push_back( exported_type(p->entry.first, p->entry.second) );
    }
  }
}

#endif