// 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 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 __unused hash(int key, int N);
static inline unsigned int __unused 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);
	}

	// TODO
}

void HashTableDelete(HashTable ht, int key) {
	// TODO
	// You will need to ensure that HashTableInsert, HashTableContains
	// and HashTableGet handle tombstones.
}

bool HashTableContains(HashTable ht, int key) {
	// TODO
	return false;
}

int HashTableGet(HashTable ht, int key) {
	// TODO
	return -1;
}

int HashTableSize(HashTable ht) {
	// TODO
	return 0;
}

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);
}