#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "hash_table.h"

#define INITIAL_CAPACITY 16

// ----- Slot definition -----
struct slot {
    Key key;
    Value value;
    bool empty;
    bool tombstone;
};

// ----- Hash table -----
struct hashtable {
    struct slot *slots;
    int numSlots;
    int numItems;
};

// ----- Hash function -----
static int hash(Key key, int N) {
    return key % N;
}

// ----- Create -----
HashTable HashTableNew(void) {
    HashTable ht = malloc(sizeof(*ht));

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

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

    return ht;
}

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

// ----- Insert -----
void HashTableInsert(HashTable ht, Key key, Value value) {
    int i = hash(key, ht->numSlots);
    int firstTombstone = -1;

    for (int j = 0; j < ht->numSlots; j++) {

        if (ht->slots[i].empty) {
            int target = (firstTombstone != -1) ? firstTombstone : i;

            ht->slots[target].key = key;
            ht->slots[target].value = value;
            ht->slots[target].empty = false;
            ht->slots[target].tombstone = false;

            ht->numItems++;
            return;
        }

        if (ht->slots[i].tombstone) {
            if (firstTombstone == -1) {
                firstTombstone = i;
            }
        } else if (ht->slots[i].key == key) {
            // replace existing value
            ht->slots[i].value = value;
            return;
        }

        i = (i + 1) % ht->numSlots;
    }

    // table full but reuse tombstone if found
    if (firstTombstone != -1) {
        ht->slots[firstTombstone].key = key;
        ht->slots[firstTombstone].value = value;
        ht->slots[firstTombstone].empty = false;
        ht->slots[firstTombstone].tombstone = false;
        ht->numItems++;
        return;
    }
    printf("Error! No empty slots!\n");
    return;
}

// ----- Contains -----
bool HashTableContains(HashTable ht, Key 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].tombstone &&
            ht->slots[i].key == key) {
            return true;
        }

        i = (i + 1) % ht->numSlots;
    }

    return false;
}

// ----- Get -----
Value HashTableGet(HashTable ht, Key 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].tombstone &&
            ht->slots[i].key == key) {
            return ht->slots[i].value;
        }

        i = (i + 1) % ht->numSlots;
    }
    printf("Error! No key not in table!\n");
    return -1;
}

// ----- Delete -----
void HashTableDelete(HashTable ht, Key key) {
    int i = hash(key, ht->numSlots);

    for (int j = 0; j < ht->numSlots; j++) {
        if (ht->slots[i].empty) return;

        if (!ht->slots[i].tombstone &&
            ht->slots[i].key == key) {

            ht->slots[i].tombstone = true;
            ht->numItems--;
            return;
        }

        i = (i + 1) % ht->numSlots;
    }
}

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

void HashTableShow(HashTable ht) {
    printf("{ ");
    for (int i = 0; i < ht->numSlots; i++) {
        if (!ht->slots[i].empty && !ht->slots[i].tombstone) {
            printf("%d ", ht->slots[i].key);
        }
    }
    printf("}\n");
}