//hash.cp		Hashtable


#include "hash.h"

void doHashtable(void)
{
	cin.ignore(1);		//this gets the newline off the buffer.
	Hashtable *table = new Hashtable;
	table->doHashDemo();
	delete table;
}

Hashtable::Hashtable(void)
{
	register int x;
	for (x = 0; x < 50; x++)
	{
		myHash[x].key = null;
		myHash[x].val = null;
		myHash[x].next = null;
	}
	done = 0;
}

Hashtable::~Hashtable(void)
{
	this->clear();
}

/* Here's the hash algorithm itself 
Although I coded this, the idea came from Anirvan Chatterjee.
*/


int Hashtable::hash(char key[10])		
{
	char second;
	char last;
	int hashcode;
	
	if (strlen(key) == 1)	//it's only 1 letter long!!!
	{
		hashcode = key[0] * key[0] % 50;
	}
	else
	{
	        second = (key[1]);
		last = key[strlen(key)-1];
		hashcode = second*last%50;
	}
	return hashcode;
	
}

void Hashtable::clear(void)
{
	register int x;
	entry *currentRecord;
	
	for (x = 0; x < 50; x++)
	{
		if (myHash[x].key != null)
		{
				clearChain(&myHash[x]);
		}
		free(myHash->key);
		free(myHash->val);
		free(myHash->next);
		myHash->key = null;
		myHash->val = null;
		myHash->next = null;
	}
}



int Hashtable::put(char key[10], char val[30])
{
	int hashcode;
	
	hashcode = hash(key);
	if (myHash[hashcode].key != null)
	{
		return insertChain(&myHash[hashcode], key, val);
	}
	else
	{
		myHash[hashcode].key = (char *)malloc((strlen(key)+1)*sizeof(char));
		if (myHash[hashcode].key == null)
		{
			return kMemErr;
		}
		strcpy(myHash[hashcode].key, key);
		myHash[hashcode].val = (char *)malloc((strlen(val)+1)*sizeof(char));
		if (myHash[hashcode].val == null)
		{
			return kMemErr;
		}
		strcpy(myHash[hashcode].val, val);
	}
	return kNoErr;
}

int Hashtable::get(char key[10], char val[30])
{
	int hashcode;

	hashcode = hash(key);
	if(myHash[hashcode].key == null)
	  {
	    return kNotFoundErr;
	  }
	if(strcmp(myHash[hashcode].key, key) == 0)
	{
		strcpy(val,myHash[hashcode].val);
		return kNoErr;
	}
	else
	{
		return searchChain(&myHash[hashcode], key, val);
	}
}

int Hashtable::remove(char key[10])
{
	int hashcode;
	entry *junk;
	char val[30];
	
	hashcode = hash(key);
	if (this->get(key,val) == kNotFoundErr)	//doesn't exist
	{
		return kNotFoundErr;
	}
	else
	{
		if(strcmp(myHash[hashcode].key, key) == 0) //it's this one
		{
			if(myHash[hashcode].next != null)	//there's a chain here... dump the first one
			{
				junk = myHash[hashcode].next;
				myHash[hashcode].key = junk->key;
				myHash[hashcode].val = junk->val;
				myHash[hashcode].next = junk->next;
				free(junk);
			}
			else					//there's no chain... toss key and val
			{
				free(myHash[hashcode].key);
				free(myHash[hashcode].val);
				myHash[hashcode].key = null;
				myHash[hashcode].val = null;
			}
		}
		else
		{
			if(removeChain(myHash[hashcode].next, key) == 1)
			{
				free(myHash[hashcode].next);
				myHash[hashcode].next = null;
			}
		}
	}
	return kNoErr;
}

void Hashtable::doHashDemo(void)
{
	register int x,y;
	char buffer[30];
	int cmd = 0;
	char cmdstr[30];
	char key[10];
	char val[30];
	int err;
	
	cout << "Entering Hashtable Mode..." << endl << "Type help if you need some." << endl;
	while(done == 0)
	{
		cout << "Command >" << endl;
		cin.getline(buffer, 30, '\n');
		for (x = 0; x < 30; x++) //get the command.
		{
			//split on a space, newline, or null... 
			if ((buffer[x] == ' ') || (buffer[x] == '\n') || (buffer[x] == '\0'))
			{
				cmdstr[x] = '\0';
				break;
			}
			else
			{
				cmdstr[x] = buffer[x];
			}
		}
	//Wish I could switch this but you can't switch on strings...
	if (strcmp(cmdstr,"get") == 0)
	{
		cmd = kGet;
	}
	else if(strcmp(cmdstr,"put") == 0)
	{
		cmd = kPut;
	}
	else if(strcmp(cmdstr,"remove") == 0)
	{
		cmd = kRemove;
	}
	else if(strcmp(cmdstr,"help") == 0)
	{
		cmd = kHelp;
	}
	else if(strcmp(cmdstr,"quit") == 0)
	{
		cmd = kQuit;
	}
	//if cmd is still 0 at this point we didn't match
	if (cmd == 0)
	{
		cmd = kBadCmd;
	}
	switch (cmd)
	{
		case (kGet) :	cout << "Get selected." << endl << "Please enter key>" << endl;
						cin.getline(key, 10, '\n');
       						if (strlen(key) == 0)
						{
							cout << "Key too short!" << endl;
							break;
						}
						err = get(key, val);
						if (err != kNoErr)
						{
							doError(err);
							break;
						}
						else
						{
							cout << "Value associated with " << key << ": " << val << endl;
							break;
						}
		case (kPut) :	cout << "Put selected. " << endl << "Please enter key>" << endl;
						cin.getline(key, 10, '\n');
						if (strlen(key) == 0)
						{
							cout << "Key too short!" << endl;
							break;
						}
						cout << "Please enter value to store with key: " << key << " > " << endl;
						cin.getline(val, 30, '\n');
						if (strlen(val) == 0)
						{
							cout << "Value too short!" << endl;
							break;
						}
						err = put(key, val);
						if (err != kNoErr)
						{
							doError(err);
							break;
						}
						else
						{
							cout << "Stored." << endl;				
							break;
						}
		case (kRemove) :cout << "Remove selected." << endl << "Please enter key>" << endl;
						cin.getline(key, 10, '\n');
						if (strlen(key) == 0)
						{
							cout << "Key too short!" << endl;
							break;
						}
						err = remove(key);
						if (err != kNoErr)
						{
							doError(err);
							break;
						}
						else
						{
							cout << "Removed." << endl;
							break;
						}
		case (kQuit) :	cout << "Exiting hashtable mode" << endl;
						done = 1;
						break;
		case (kHelp) :	cout << "Commands:" << endl;
						cout << "Please enter one of: put, get, remove, quit or help" << endl;
						break;
		case (kBadCmd) :cout << "Command not found.  Please try again." << endl;
						break;
	}
}
			
}	

void Hashtable::clearChain(entry *target) 
{
	if (target->next != null)
	{
		clearChain(target->next);
	}
	else
	{
		free(target->key);
		free(target->val);
		if (target->next != null)
		{
		free(target->next);
		}
	}

}

int Hashtable::insertChain(entry *target, char key[10], char val[30])
{
	if (target->next == null)
	{
		target->next = (entry *)malloc(sizeof(entry));
		target->next->key = (char *)malloc((strlen(key)+1)*sizeof(char));
		if (target->next->key == null)
		{
			return kMemErr;
		}
		strcpy(target->next->key, key);
		target->next->val = (char *)malloc((strlen(val)+1)*sizeof(char));
		if (target->next->key == null)
		{
			return kMemErr;
		}
		strcpy(target->next->val, val);
		target->next->next = null;
	}
	else 
	{
		insertChain(target->next, key, val);
	}
	return kNoErr;
}

int Hashtable::searchChain(entry *target, char key[10], char *val)
{
	if (strcmp(target->key, key) == 0)
	{
		strcpy(val, target->val);
		return kNoErr;
	}
	else
	{
		if (target->next == null)
		{
			return kNotFoundErr;
		}
		else
		{
			return searchChain(target->next, key, val);
		}
	}
}
/*
This function is interesting.  There are three conditions that could occur:
1) the key is not valid
2) the key is valid and it's record is in the middle of the chain
3) the key is valid and it's record is at the end of the chain

condition 1 and 2 can be dealt with easily.. but if the key is at the end, we need to somehow
free the current record and set the previous record's next to null.  So...
if a recursive call returns a 1, delete the next record
if it returns 0 return normally

*/
int Hashtable::removeChain(entry *target, char *key)
{
	entry *junk;
	if (strcmp(target->key, key) == 0)
	{
		if (target->next != null)
		{
			junk = target->next;
			target->key = target->next->key; 	//copy the next record into the current 
			target->val = target->next->val;	//and wipe the current
			target->next = target->next->next;
			free(junk->key);
			free(junk->val);
			free(junk);			//don't free junk.next... it's still valid!
			return kReturnNormal;
		}
		else	//this is icky... we're at the end of the chain
		{
		free(target->key);
		free(target->val);
		return kDeleteNext;
		}
	}
	else
	{
		if (target->next == null)
		{
			return kNotFoundErr;
		}
		else
		{
			if(removeChain(target->next, key) == kDeleteNext)
			{
				free(target->next);
				target->next = null;
			}
			return kNoErr;
		}
	}
}

void Hashtable::doError(int err)
{
	switch(err)
	{
		case (kNotFoundErr)	:	cout << "Record not found." << endl;
								break;
		case (kMemErr)		:	cout << "Memmory error.\nAborting!" << endl;
								myExit(0);
								break;
		default				:	cout << "Unknown error has occured.\nAborting!" << endl;
								myExit(0);
								break;
	}
}