//***************************************************************************
#include <iostream.h>
#include <stdlib.h>             /* ANSI C standard library routines */
#include <string.h>             /* ANSI standard string routines */
#include "hash.h"
//***************************************************************************
HashTable::HashTable (int Size)       // Constructor
{
H_Size = Size;
Cur_Val = 0;

Hash_Table = new Hash_Node *[H_Size];
Hash_Table_Consec = new Hash_Node_Consec *[H_Size];
if (!Hash_Table || !Hash_Table_Consec)
        {
         cerr << "Out of space in HashTable !!" << endl;
         exit(1);
        }

for (int i=0;i<H_Size;i++)	
	{
	 Hash_Table[i] = NULL;
	 Hash_Table_Consec[i] = NULL;
	}
}
//***************************************************************************
HashTable::~HashTable ( )       // Destructor
{
int i;
Hash_Node *Node_to_delete;

for (i=0;i<H_Size;i++)
         while (Hash_Table[i])
                {
                 Node_to_delete = Hash_Table[i];
                 Hash_Table[i] = Hash_Table[i]->Next;
                 delete Node_to_delete;
                }
delete [] Hash_Table;

for (i=0;i<Cur_Val;i++)
	{
	 delete Hash_Table_Consec[i]->Word;
	 delete Hash_Table_Consec[i];
	}
delete [] Hash_Table_Consec;
}
//***************************************************************************
unsigned HashTable::Hash (const char *s) 	// Hashing function
{
unsigned int Hash_Val = 0;

while (*s) Hash_Val = (Hash_Val << 5) + *s++;
	
return (Hash_Val%H_Size);	// Returns integer I s.t. 0 <= I < H_Size
}
//***************************************************************************
// Returns ID of word after inserting to Table if already not present
int HashTable::id_of (char *word)
{
unsigned int i = Hash(word);
Hash_Node *Temp = Hash_Table[i];

while (Temp && !strsame(word,Hash_Table_Consec[Temp->ID-1]->Word)) 
		Temp = Temp->Next;

if (Temp) 			// Word already exists
	return Temp->ID;	// Return the old ID

++Cur_Val;		// Insert the new Word
if (Cur_Val > H_Size)
        {
         cerr << "Number of vertices exceeds size of " << H_Size
	 	<< " in HashTable::id_of !" << endl;
	 cerr << "Exiting...." << endl;
         exit(-1);
        }

Hash_Table[i] = new Hash_Node(Cur_Val,Hash_Table[i]);
Hash_Table_Consec[Cur_Val-1] = new Hash_Node_Consec(word,i);
if (!Hash_Table[i] || !Hash_Table_Consec[Cur_Val-1])
        {
         cerr << "Out of space in HashTable !!" << endl;
         exit(1);
        }

return Cur_Val;		// Return new ID
}
//***************************************************************************
// Return the actual word if the input ID is valid
char *HashTable::name_of (int id)
{
if (id > Cur_Val) 
	{
	 cerr 	<< "name_of(ID=" << id 
	 	<< ") called with value greater than number"
		<< " of nodes (" << nodes_of() << ") !" << endl
		<< "Exiting.........." << endl;
	 exit(-1);
	}

return Hash_Table_Consec[id-1]->Word;
}
//***************************************************************************
// Return the number of unique words present in the hash table
int HashTable::nodes_of ()
{
return Cur_Val;
}
//***************************************************************************
// Returns ID of word if found else returns 0
int HashTable::find (char *word)
{
unsigned int i = Hash(word);
Hash_Node *Temp = Hash_Table[i];

while (Temp && !strsame(word,Hash_Table_Consec[Temp->ID-1]->Word)) 
	Temp = Temp->Next;

if (Temp) 			// Word found
	return Temp->ID;
else 				// Word not found
	return 0;
}
//***************************************************************************
// Allocate space for word "s" and return the pointer to its start
char *strsave(char *s)
{
char *p;

p = new char[(strlen(s)+1)];    /* +1 for '\0' */
if (!p) 
	{
         cerr << "Cannot find space for `" << s << "'" << endl;
         exit(0);
	}
return strcpy(p, s);
}
//***************************************************************************
// Compare word "s" to word "t" and return 1 if same and 0 if not same
int strsame(char *s, char *t)
{
return (strcmp(s,t) == 0);
}
//***************************************************************************