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

#include <math.h>
#include "hashtable.h"

// primes to use as table size
static const unsigned int primes[] = {
53, 97, 193, 389,
769, 1543, 3079, 6151,
12289, 24593, 49157, 98317,
196613, 393241, 786433, 1572869,
3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189,
805306457, 1610612741
};

hashtable *createTable(unsigned int (*hashfn)(const void *),int (*compfn)(const void *, const void *));

int main()
{
	void *result;
	char* strkeys[10] = {"one","two","three","four","five","six","seven","eight","nine","ten"};
	int intvals[10] = {1,4,9,16,25,36,49,64,81,100};
	hashtable *stringkeys = createTable(hash_string,cmp_string);

	//insert ("one",1),("two",4),("three",9)
	printf("Inserting (%s,%i) : %i\n",strkeys[0],intvals[0],insert(stringkeys,strkeys[0],intvals));
	printf("Inserting (%s,%i) : %i\n",strkeys[1],intvals[1],insert(stringkeys,strkeys[1],intvals+1));
	printf("Inserting (%s,%i) : %i\n",strkeys[2],intvals[2],insert(stringkeys,strkeys[2],intvals+2));

	//search for "two"
	result = find(stringkeys,strkeys[1]);
	result == NULL ? printf("Key not found\n") : printf("Value is %i\n",*(int *)result);

	//search for "eight"
	result = find(stringkeys,"eight");
	result == NULL ? printf("Key not found\n") : printf("Value is %i\n",*(int *)result);

	//insert ("four",16)
	printf("Inserting (%s,%i) : %i\n",strkeys[3],intvals[3],insert(stringkeys,strkeys[3],intvals+3));

	//remove "one"
	result = removeKey(stringkeys,"one");
	result == NULL ? printf("Key not found\n") : printf("Value is %i\n",*(int *)result);

	//remove "eight"
	result = removeKey(stringkeys,"eight");
	result == NULL ? printf("Key not found\n") : printf("Value is %i\n",*(int *)result);

	//search for "one"
	result = find(stringkeys,"one");
	result == NULL ? printf("Key not found\n") : printf("Value is %i\n",*(int *)result);

	//delete table
	deleteTable(stringkeys);
	return 0;


}
unsigned int hash(hashtable *table, const void *key)
{
	// helps distribute the hashes from my poor hash functions more evenly
	// taken from online reference for Java's implimentation of hash tables
	unsigned int h = table->hash_function(key);
	h += ~(h << 9);
	h ^= (( h >> 14) | (h << 18));
	h += (h << 4);
	h ^= ((h >> 10) | (h << 22));
	return h;
}
int cmp_string(const void *a, const void *b)
{
	
	return strcmp((const char *)a, (const char *)b);
}

// uses the well-known djb2 hash algorithm for strings
unsigned int hash_string(const void *key)
{
	char *string = (char *)key;
	unsigned int hash = 0;
	int string_ch = 0;

	while((string_ch = *string++))
	{
		hash = ((hash << 5) + hash) ^ string_ch;
	}
	return hash;
}

int insert(hashtable *table, void *key, void *value)
{
	unsigned int index;
	hashentry *newentry;

	// check to see if the table is getting too full, and if so, enlarge it
	if((((double)table->count)/(table->size))>.6)
	{
		growTable(table);
	}

	newentry = (hashentry *)malloc(sizeof(hashentry));

	if(NULL == newentry)
	{
		return 1;
	}

	//hash the key to be added, and add the k,v pair to the struct
	newentry->hashvalue = hash(table,key);
	newentry->key = key;
	newentry->value = value;

	//find the array index where the new entry will go, and add it to the list of entries at that index
	index = indexOf(newentry->hashvalue,table->size);
	newentry->next = table->hash_array[index];
	table->hash_array[index] = newentry;
	table->count++;
	
	return 0;
}
int growTable(hashtable *table)
{
	hashentry **bigarray;
	hashentry *tempentry;
	int newsize;
	unsigned int arrayindex;
	int i = 0;
	// set the new array size to the next prime numbered size
	newsize = primes[++(table->sizeindex)];
	bigarray = (hashentry **)malloc(sizeof(hashentry *)*newsize);

	memset(bigarray,0,newsize*sizeof(hashentry *));

	for(i;i<table->size;i++)
	{
		while(tempentry = table->hash_array[i])
		{
			table->hash_array[i] = tempentry->next;
			arrayindex = indexOf(tempentry->hashvalue,newsize);
			tempentry->next = bigarray[arrayindex];
			bigarray[arrayindex] = tempentry;
		}
	}
	free(table->hash_array);
	table->hash_array = bigarray;
	table->size = newsize;
	if(NULL == table->hash_array)
	{
		return 1;
	}
	return 0;
}

void *find(hashtable *table, void *key)
{
	hashentry *temp;

	//find the hash for the key to search for, and find its location in the array
	unsigned int hashval = hash(table,key);
	int arrayindex = indexOf(hashval,table->size);

	//search through the entries in the array location to find our desired element
	temp = table->hash_array[arrayindex];
	while(temp)
	{
		if(temp->hashvalue == hashval)
		{
			// if we find the desired key, we will return it
			if(table->compare(temp->key,key) == 0)
			{
				return temp->value;
			}
		}
		temp = temp->next;
	}
	// if the key is not found, return null
	return NULL;
}

void *removeKey(hashtable *table, void *key)
{
	//find the hash and corresponding index for our key
	hashentry *temp, **pointer;
	void *result;
	unsigned int hashval = hash(table,key);
	unsigned int arrayindex = indexOf(hashval,table->size);

	// creates a placeholder pointer to the current position in the list, so we can delete things
	pointer = &(table->hash_array[arrayindex]);
	temp = *pointer;

	while(temp)
	{
		if(temp->hashvalue == hashval)
		{
			if(table->compare(temp->key,key) == 0)
			{
				*pointer = temp->next;
				result = temp->value;
				
				free(temp);
				table->count--;
				return result;
			}
		}
			pointer = &(temp->next);
			temp = temp->next;
		}
		return NULL;
}


// takes hash and gives an array index
unsigned int indexOf(unsigned int hashv, int tableLength)
{
	return hashv % tableLength;
}

// creates a new hashtable and assigns the hash function and comparison function to the table			
hashtable *createTable(unsigned int (*hashfn)(const void *),int (*compfn)(const void *, const void *))
{
	hashtable *table;
	unsigned int start;
	int index = 0;
	table = (hashtable *)malloc(sizeof(hashtable));
	start = primes[index];
	table->size = start;
	table->sizeindex = index;
	table->count = 0;

	if(NULL == table)
	{
		return NULL;
	}
	table->hash_array = (hashentry **)malloc(sizeof(hashentry *) * start);

	if(NULL == table->hash_array)
	{
		return NULL;
	}
	memset(table->hash_array,NULL,sizeof(hashentry *)*start);
	table->hash_function = hashfn;
	table->compare = compfn;

	return table;
}


// delete all of the entries in the table and free their memory
void deleteTable(hashtable *table)
{
	hashentry *temp, *temp2;
	hashentry **temparray;
	int i = 0;
	temparray = table->hash_array;

	for(i;i<table->size;i++)
	{
		temp = temparray[i];
		while(temp)
		{
			temp2 = temp;
			temp = temp->next;
			
			free(temp2);
		}
	}
	free(table->hash_array);
	free(table);
}
int cmp_double(const void *a, const void *b)
{
	if((*(double *)a) == (*(double *)b))
	{
		return 0;
	}
	return 1;
}
int cmp_int(const void *a, const void *b)
{
	if((*(int *)a) == (*(int *)b))
	{
		return 0;
	}
	return 1;
}

unsigned int hash_int(const void *key)
{
	return (*(int *)key) *(*(int *)key);
}
unsigned int hash_double(const void *key)
{
	return (unsigned int)floor((*(double *)key)*(*(double *)key));
}