#include <stdlib.h>
/*	Hash Table Abstract Data Type
	Modified by: Peter Brusilovsky
*/

/*	HashTable ADT Type Defintions */

typedef struct hashtable {
		int *tableAry;
		int count;	
		int size;
	} HashTable;
        
/*	Prototype Declarations */
/* ADT interface */
	HashTable *createHT (int size);
	void destroyHT(HashTable *HT);
	int addHash (HashTable *HT, int key);
	int checkHash(HashTable  *HT, int key);
	
/* internal functions */
	static int hash(HashTable *HT, int key);
	static int rehash(HashTable *HT, int ind);

#define DENSITY 10

/*	=============== createHT ==============	*/
/*	Create empty Hash Table
	Pre		Nothing
	Post	Returns pointer to an empty Hash Table
			-or- NULL if overflow.
*/

HashTable *createHT (int size) {
	HashTable  *ht;
	int i;

	ht = (HashTable *) malloc( sizeof (HashTable) ) ;
	if (ht == NULL)
		return NULL ;
	/* Structure Allocated. Now initialize and allocate array. */
	ht->count = 0;
	ht->size = size;
	/* allocate array that is DENSITY times larger than size */
	ht->tableAry = (int *) malloc(size * DENSITY * sizeof(int));
	
	if(ht->tableAry == NULL) { /* free all allocated space if no more memory */
		free(ht);
		return NULL;
	}
	/* empty HT is filled with 0 */
	for (i = 0; i < size * DENSITY; ++i) ht->tableAry[i] = 0;
	
	return ht ;
}

/*	=============== destroyHT ============== */
/* 	This function releases all nodes to the heap.
	Pre		A Hash Table
	Post	memory released
*/

void destroyHT(HashTable *HT) {

	if (HT) {
		 /* Release HT array */
		 free(HT->tableAry);

		 /* Release HT head */
		 free(HT);
	}
}	/* destroyHT */


/*	=============== addHash ============== */
/*	Inserts data into a hash table.
	Pre		HT is a pointer to a valid Hash Table
			key is a key to be inserted
	Post		key inserted unless dupe key
	Return		-1 if overflow, 0 if successful, 1 if dupe key
*/
int addHash (HashTable *HT, int key) {
	int ind;

	if(HT->count == HT->size) return -1;
	
	ind = hash (HT, key);
	/* rehashing while space is found */
	while (HT->tableAry[ind] != 0 && HT->tableAry[ind] != key)
		ind = rehash(HT, ind); 
		
	/* handling dupe key */
	if(HT->tableAry[ind] == key)  return 1;
	else {
		HT->tableAry[ind] = key;
		++(HT->count);
		return 0;
	}
}	/* addHash */


/*	=============== checkHash ============== */
/*	This algorithm retrieves data in the hash table without
	changing it. 
	Pre		HT is a pointer to a valid Hash Table
			key is a key to be checked
	Return		1 if found, 
				0 if not found. 
*/
int checkHash(HashTable  *HT, int key) {
	int ind;
	
	ind = hash (HT, key);
	
	/* rehashing while space is found */
	while (HT->tableAry[ind] != 0 && HT->tableAry[ind] != key)
		ind = rehash(HT, ind); 
		
	/* found */
	if(HT->tableAry[ind] == key) 
		return 1;
	else
		return 0;
	
}	



/*	=============== hashCount =============== */
/*	Returns integer representing number of nodes in list.
	Pre		pList is a pointer to a valid list
	Return		count for number of nodes in list
*/
int hashCount(HashTable *HT)  {

	return HT->count;
	
}	/* hashCount */

/*	=============== printHash ============== */
/*	Prints Hash Table
	Pre		HT       is a pointer to a valid HashTable
	Post	HT is printed
*/
void printHash (HashTable  *HT) {
int i;

	for(i = 0; i < HT->size * DENSITY; ++i)
		if(HT->tableAry[i] != 0)
			printf("%3d --> %d\n", i, HT->tableAry[i]);
}
	

/*	=============== hash ============== */

/*	Maps a key into a position in a hash table
	Pre		HT       is a pointer to a valid HashTable
			key is a valid key
		
	Return  index
*/
static int hash(HashTable *HT, int key) {
	return((13 * key + 7) % HT->size);
}
	
	
	/*	=============== hash ============== */

/*	Maps an index into a another index in a hash table
	Pre		HT       is a pointer to a valid HashTable
			ind is a valid index in the table
		
	Return  index
*/
static int rehash(HashTable *HT, int ind) {
	return((ind + 1) % HT->size);
}