// Implementation of the hash table module

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

#include "HashTable.h"

// When using double hashing, the hash table size should be prime
#define INITIAL_CAPACITY 11

#define MAX_LOAD_FACTOR 0.9

enum slotState {
	EMPTY,
	OCCUPIED,
	TOMBSTONE,
};

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

struct slot {
	int key;
	int value;
	enum slotState state;
};

static int findSuitableMod(int N);
static bool isPrime(int num);

static inline unsigned int hash(int key, int N);
static inline unsigned int hash2(int key, int hash2Mod);
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].state = EMPTY;
	}

	ht->numSlots = INITIAL_CAPACITY;
	ht->numItems = 0;
	ht->hash2Mod = findSuitableMod(INITIAL_CAPACITY);
	return ht;
}

static int findSuitableMod(int N) {
	for (int i = N - 1; i >= 2; i--) {
		if (isPrime(i)) {
			return i;
		}
	}
	return 2;
}

static bool isPrime(int num) {
	for (int i = 2; i * i <= num; i++) {
		if (num % i == 0) {
			return false;
		}
	}
	return true;
}

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

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

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

	if (ht->slots[i].state == OCCUPIED && ht->slots[i].key == key) {
		ht->slots[i].value = value;
		return;
	}

	if (ht->slots[i].state != EMPTY) {
		int inc = hash2(key, ht->hash2Mod);
		
		for (int j = 1; j < ht->numSlots; j++) {
			i = (i + inc) % ht->numSlots;

			if (ht->slots[i].state == EMPTY) {
				break;
			} else if (ht->slots[i].state == OCCUPIED &&
					ht->slots[i].key == key) {
				ht->slots[i].value = value;
				return;
			}
		}
	}

	ht->slots[i].key = key;
	ht->slots[i].value = value;
	ht->slots[i].state = OCCUPIED;
	ht->numItems++;
}

void HashTableDelete(HashTable ht, int key) {
	// This is left as an exercise :D
	// Note: You may need to modify HashTableInsert,
	//       HashTableContains and HashTableGet to handle tombstones
}

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

	if (ht->slots[i].state == EMPTY) {
		return false;
	}

	if (ht->slots[i].state == OCCUPIED && ht->slots[i].key == key) {
		return true;
	}

	int inc = hash2(key, ht->hash2Mod);
	for (int j = 1; j < ht->numSlots; j++) {
		i = (i + inc) % ht->numSlots;

		if (ht->slots[i].state == EMPTY) {
			return false;
		}

		if (ht->slots[i].state == OCCUPIED &&
				ht->slots[i].key == key) {
			return true;
		}
	}

	return false;
}

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

	if (ht->slots[i].state == OCCUPIED && ht->slots[i].key == key) {
		return ht->slots[i].value;
	}

	if (ht->slots[i].state != EMPTY) {
		int inc = hash2(key, ht->hash2Mod);

		for (int j = 1; j < ht->numSlots; j++) {
			i = (i + inc) % ht->numSlots;

			if (ht->slots[i].state == EMPTY) {
				break;
			}

			if (ht->slots[i].state == OCCUPIED &&
					ht->slots[i].key == key) {
				return ht->slots[i].value;
			}
		}
	}

	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].state == EMPTY) {
			printf("%11s %11s\n", "---", "---");
		} else if (ht->slots[i].state == TOMBSTONE) {
			printf("%11s %11s\n", "DEL", "DEL");
		} 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 inline unsigned int hash2(int key, int hash2Mod) {
	return key % hash2Mod + 1;
}

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

	ht->numItems = 0;
	ht->numSlots = 2 * ht->numSlots + 1;
	while (!isPrime(ht->numSlots)) {
		ht->numSlots += 2;
	}
	ht->hash2Mod = findSuitableMod(ht->numSlots);
	ht->slots = malloc(ht->numSlots * sizeof(struct slot));
	for (int i = 0; i < ht->numSlots; i++) {
		ht->slots[i].state = EMPTY;
	}

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

	free(oldSlots);
}