#include <iostream>
#include <vector>
using std::cerr;
using std::cout;
using std::endl;
#include <string>

using std::string;

#include <fstream>
using std::ifstream;

#include <cstdlib>

template <typename HashedObj>                          //Figure 5.6 from the texts. Type declaration for separate chaining hash table//
class HashTable
{
	public:

explicit HashTable(int size = 101)
{
	(theLists.resize(size) );
	currentSize = 0;
}

int myhash( const HashedObj & x ) const            //Figure 5.7 from the text. Figure 5.7 is the myhash
{                                                  // member function for hashtables.
	int hashVal = hash ( x );

	hashVal %= theLists.size ();
	if (hashVal < 0)
		hashVal += theLists.size();

	return hashVal;
}

void makeEmpty ()
{
	for( int i = 0; i < theLists.size( ); i++)
		theLists[ i ].clear( );
}

bool contains( const HashedObj & x ) const                   //Figure 5.9 makeEmpty, contains, and remove routines for separate chaining hash table //
{
	const list<HashedObj> & whichList = theLists[ myhash(x)];
	return find( whichList.begin( ), whichList.end(), x) != whichList.end( );
}

bool remove(const HashedObj & x)
{
	list<HashedObj> & whichList = theLists[ myhash(x)];
	list<HashedObj>::iterator itr = find (whichList.begin( ), whichList.end( ), x );

	if( itr == whichList.end())
		return false;

	whichList.erase ( itr );
	--currentSize;
	return true;
}

bool insert( const HashedObj & x)
{
	list<HashedObj> & whichList = theLists[ myhash( x )];
	if( find( whichList.begin( ), whichList.end(), x) != whichList.end( ) )
		return false;
	whichList.push_back( x );

	//Rehash//
	if( ++currentSize > theLists.size())                              // Figure 5.10 insert routine for separate chaining hash table //
		rehash( );

	return true;
}

/**
* A hash routine for string objects.
  Figure 5.4 from Textbook
*/

unsigned int  hash( const string & key, int tableSize)
{
	int hashVal = 0;

	for( int i = 0; i < key.length(  ); i++)
		hashVal = 37 * hashVal + key [ i ];

	hashVal %= tablesize;
	if (hashVal < 0)
		hashVal += tableSize;

	return hashVal;
}

void HashTable:: printStats()
{
  // Compute statistics on hash table //
	for (i=0; i<table_size; i++)
	{
		j = 0;
		if ((table[i].next_ptr == NULL) && (table[i].key != 0)) j = 1;
		if (table[i].next_ptr != NULL)
	{
      j++;
      ptr = &table[i].key;
      do
      {
        ptr = ptr->next_ptr;
        j++;
      }
      while (ptr->next_ptr != NULL);
    }
    count[j]++;
  }
	  // Compute mean chain length //
	  mean_chain_len = 0.0;
	for (i=0; i<table_size; i++)
    mean_chain_len = mean_chain_len + i * ((double) count[i] / table_size);

}
};

/* class myClass
 {
	public:
	explicit HashTable(int size);
	bool contains(const HashedObj & x ) const;
	void makeEmpty();
	void insert( const HashedObj & x);
	void remove( const HashedObj & x);
	void HashTable::printStats();

	private:
	std::vector<int><list<HashedObj> > theLists;                     // The array of Lists
	int currentSize;

	void rehash();
	int myhash ( const HashedObj & x) const;

	unsigned int hash( const string & key, int tableSize);
};*/