// hashTable.c
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "StringHashTable.h"

#define defaultNumOffsets 4

// Node type for the chained hash table for C-strings.
struct _StringNode
{
	char *key;				  // ptr to proper C-string
	uint32_t *locations;	  // ptr to dynamic array of string locations
	uint32_t numLocations;	  // number of elements currently in locations array
	uint32_t maxLocations;	  // dimension of locations array
	struct _StringNode *next; // ptr to next node object in table slot
};

// Declare "private" helper functions here (one is already included):
static void StringNode_display(FILE *fp, const StringNode *const pNode);
static StringNode *createEntry(char *key, uint32_t locations);

///////////////////////////////////////////////////////////////// StringNode implementation
//
// You should write implementations of any "private" functions related to the
// StringNode type here; FWIW the reference solution includes two such functions
// in addition to the StringNode_display() function that's given:
//

/** Writes a formatted display of the fields of a StringNode object; for
 *  example:
 *            New Tank:    [359569, 411752, 857960, 942772]
 * 
 *  Pre:  fp is open on an output file
 *        pNode points to a valid StringNode object
 */
static void StringNode_display(FILE *fp, const StringNode *const pNode)
{
	assert(pNode != NULL);

	fprintf(fp, "     %s:  ", pNode->key);

	fprintf(fp, "  [%" PRIu32, pNode->locations[0]);
	for (uint32_t idx = 1; idx < pNode->numLocations; idx++)
	{
		fprintf(fp, ", %" PRIu32, pNode->locations[idx]);
	}
	fprintf(fp, "]\n");
}

///////////////////////////////////////////////////////////////// StringHashTable implementation
//
// You should complete the implementations of the "public" functions related to the
// StringHashTable type here:
//

/** Creates a new StringHashTable object such that:
 *    - the array has dimension Size
 *    - the slots in the array are set to NULL
 *    - the hash pointer is set to Hasher (so the hash table will use
 *      that user-supplied hash function)
 * 
 *  Pre: Size equals the desired number of slots in the table
 *       Hasher is the name of the hash function the table is to use,
 *         and that function conforms to the specified interface
 * 
 *  Returns: pointer to a newly-allocated StringHashTable object;
 *           blows up an assert() if creation fails
 */
StringHashTable *StringHashTable_create(uint32_t Size,
										uint32_t (*Hasher)(const char *str))
{
	StringHashTable *newTable = calloc(1, sizeof(StringHashTable));
	newTable->tableSz = Size;
	newTable->table = calloc(newTable->tableSz, sizeof(StringNode *));
	newTable->hash = Hasher;
	newTable->numEntries = 0;

	return newTable;
}

/** Adds an entry to the hash table corresponding to the given key/location.
 *  
 *  Pre:  pTable points to a proper StringHashTable object
 *        key points to a proper C-string
 *        location is set to a corresponding location
 * 
 *  Post: if the key/location pair is already in the table, fails; otherwise
 *        if the table does not contain an entry for key, a new index entry
 *           has been created and location has been installed in it;
 *        otherwise, location has been installed into the existing index entry
 *           for key;
 *        the user's C-string is duplicated, not linked to the table
 * 
 *  Returns: true iff the key/location have been properly added to the table
 */
bool StringHashTable_addEntry(StringHashTable *const pTable,
							  char *key, uint32_t location)
{
	int validIndex = (pTable->hash(key) % pTable->tableSz);
	StringNode *curr = pTable->table[validIndex];

	while (curr)
	{
		if (!strcmp(curr->key, key))
		{
			for (uint32_t i = 0; i < curr->numLocations; i++)
				if (curr->locations[i] == location)
					return false;

			if (curr->numLocations == curr->maxLocations)
			{
				curr->maxLocations += curr->maxLocations;
				curr->locations = realloc(curr->locations, curr->maxLocations * sizeof(uint32_t));
				if (!curr->locations)
					return false;
			}

			curr->locations[curr->numLocations] = location;
			curr->numLocations++;
			return true;
		}

		curr = curr->next;
	}

	StringNode *entry = createEntry(key, location);

	entry->next = pTable->table[validIndex];
	pTable->table[validIndex] = entry;
	pTable->numEntries++;
	return true;
}

/** Finds the locations, if any, that correspond to the given key.
 * 
 *  Pre:  pTable points to a proper StringHashTable object
 *        key points to a proper C-string
 * 
 *  Returns: NULL if there is no entry for key in the table; otherwise
 *           a pointer to an array storing the locations corresponding
 *           to the key, and terminated by a zero location (which would
 *           never be logically valid)
 */
uint32_t *StringHashTable_getLocationsOf(const StringHashTable *const pTable,
										 const char *key)
{
	int idx = pTable->hash(key) % pTable->tableSz;
	StringNode *curr = pTable->table[idx];

	while (curr)
	{
		if (!strcmp(curr->key, key))
		{
			uint32_t *locArray = calloc(curr->numLocations + 1, sizeof(uint32_t));
			memcpy(locArray, curr->locations, (curr->numLocations) * sizeof(uint32_t));
			return locArray;
		}
		curr = curr->next;
	}

	return NULL;
}

/** Deallocates memory associated with a StringHashTable.
 * 
 *  Pre:  pTable points to a proper StringHashTable object
 * 
 *  Post: the following have been deallocated
 *           - the key belonging to every index entry in the table
 *           - the array of locations belonging to every index entry in the table
 *           - every index entry in the table
 *           - the array for the table
 *
 *   Note: the function does not attempt to deallocate the StringHashTable object
 *         itself, because that object may or may not have been allocated dynamically;
 *         cleanup that up is the responsibility of the user.
 */
void StringHashTable_clear(StringHashTable *const pTable)
{
	uint32_t i = 0;
	while (i < pTable->tableSz)
	{
		StringNode *curr = pTable->table[i++];
		while (curr)
		{
			StringNode *temp = curr;
			free(curr->key);
			free(curr->locations);
			curr = curr->next;
			free(temp);
		}
	}

	free(pTable->table);
}

/** Writes a clearly-formatted display of the contents of a given
 *  StringHashTable.
 * 
 *  Pre:  fp points to an open file, or is stdout
 *        pTable points to a proper StringHashTable object
 */
void StringHashTable_display(FILE *fp, const StringHashTable *const pTable)
{
	fprintf(fp, "Hash table contains the following %" PRIu32 " entries:\n",
			pTable->numEntries);

	uint32_t pos = 0;
	while (pos < pTable->tableSz)
	{
		StringNode *currEntry = pTable->table[pos];
		if (currEntry != NULL)
		{
			fprintf(fp, "%5" PRIu32 ": ", pos);
			StringNode_display(fp, currEntry);
			currEntry = currEntry->next;
			while (currEntry != NULL)
			{
				fprintf(fp, "       ");
				StringNode_display(fp, currEntry);
				currEntry = currEntry->next;
			}
			fprintf(fp, "\n");
		}
		pos++;
	}
}

//
// You should write implementations of any "private" functions related to the
// StringHashTable type here; FWIW the reference solution includes one such
// function.
//
static StringNode *createEntry(char *key, uint32_t location)
{
	StringNode *entry = malloc(sizeof(StringNode));
	int keyLength = strlen(key) + 1;
	entry->key = calloc(keyLength, sizeof(char));
	strcpy(entry->key, key);
	entry->maxLocations = defaultNumOffsets;
	entry->locations = calloc(entry->maxLocations, sizeof(uint32_t));
	entry->locations[0] = location;
	entry->numLocations = 1;

	return entry;
}