// Implementation of the hash table module

#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "HashTable.h"

#define INITIAL_CAPACITY 10

#define MAX_LOAD_FACTOR 0.5

struct hashTable {
	struct slot *slots;
	int numSlots;
	int numItems;
};

struct slot {
	int key;
	int value;
	bool empty;
};

static inline unsigned int hash(int key, int N);
static void resize(HashTable ht);

HashTable HashTableNew(void) {
	HashTable ht = malloc(sizeof(*ht));
	if (ht == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	ht->slots = malloc(INITIAL_CAPACITY * sizeof(struct slot));
	if (ht->slots == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	for (int i = 0; i < INITIAL_CAPACITY; i++) {
		ht->slots[i].empty = true;
	}

	ht->numSlots = INITIAL_CAPACITY;
	ht->numItems = 0;
	return ht;
}

void HashTableFree(HashTable ht) {
	free(ht->slots);
	free(ht);
}

void HashTableInsert(HashTable ht, int key, int value) {
	if (ht->numItems >= ht->numSlots * MAX_LOAD_FACTOR) {
		resize(ht);
	}

	// This is a task in the week 9 lab exercise!
}

void HashTableDelete(HashTable ht, int key) {
	// This is a task in the week 9 lab exercise!
}

bool HashTableContains(HashTable ht, int key) {
	int i = hash(key, ht->numSlots);

	for (int j = 0; j < ht->numSlots; j++) {
		if (ht->slots[i].empty) {
			return false;
		}
		if (ht->slots[i].key == key) {
			return true;
		}
		i = (i + 1) % ht->numSlots;
	}

	return false;
}

int HashTableGet(HashTable ht, int key) {
	int i = hash(key, ht->numSlots);

	for (int j = 0; j < ht->numSlots; j++) {
		if (ht->slots[i].empty) {
			break;
		}
		if (ht->slots[i].key == key) {
			return ht->slots[i].value;
		}
		i = (i + 1) % ht->numSlots;
	}
	
	printf("error: key %d does not exist!\n", key);
	return -1;
}

int HashTableSize(HashTable ht) {
	return ht->numItems;
}

void HashTableShow(HashTable ht) {
	printf("%-5s %11s %11s\n", "index", "key", "value");
	for (int i = 0; i < ht->numSlots; i++) {
		printf("%-5d ", i);
		if (ht->slots[i].empty) {
			printf("%11s %11s\n", "---", "---");
		} else {
			printf("%11d %11d\n",
			       ht->slots[i].key,
			       ht->slots[i].value);
		}
	}
}

static inline unsigned int hash(int key, int N) {
	return key % N;
}

static void resize(HashTable ht) {
	int oldNumSlots = ht->numSlots;
	struct slot *oldSlots = ht->slots;

	ht->numItems = 0;
	ht->numSlots *= 2;
	ht->slots = malloc(ht->numSlots * sizeof(struct slot));
	for (int i = 0; i < ht->numSlots; i++) {
		ht->slots[i].empty = true;
	}

	for (int i = 0; i < oldNumSlots; i++) {
		if (!oldSlots[i].empty) {
			HashTableInsert(ht, oldSlots[i].key, oldSlots[i].value);
		}
	}

	free(oldSlots);
}