// Implementation of the hash table ADT

// !!! DO NOT MODIFY THIS FILE !!!

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

#include "HashTable.h"

#define INITIAL_NUM_SLOTS 11
#define MAX_LOAD_FACTOR 2.0

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

struct node {
    char *key;
    int value;
    struct node *next;
};

static void freeList(struct node *list);
static struct node *doInsert(HashTable ht, struct node *list,
                             char *key, int value);
static struct node *newNode(char *key, int value);
static struct node *doDelete(HashTable ht, struct node *list, char *key);
static inline unsigned int hash(char *key, int N);

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

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

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

    return ht;
}

void HashTableFree(HashTable ht) {
    for (int i = 0; i < ht->numSlots; i++) {
        freeList(ht->slots[i]);
    }
    free(ht->slots);
    free(ht);
}

static void freeList(struct node *list) {
    struct node *curr = list;
    while (curr != NULL) {
        struct node *temp = curr;
        curr = curr->next;

        free(temp->key);
        free(temp);
    }
}

void HashTableInsert(HashTable ht, char *key, int value) {
    if (ht->numItems >= MAX_LOAD_FACTOR * ht->numSlots) {
        printf("warning: resize not implemented!\n");
    }

    int i = hash(key, ht->numSlots);
    ht->slots[i] = doInsert(ht, ht->slots[i], key, value);
}

static struct node *doInsert(HashTable ht, struct node *list,
                             char *key, int value) {
    if (list == NULL) {
        ht->numItems++;
        return newNode(key, value);
    } else if (strcmp(list->key, key) == 0) {
        list->value = value;
        return list;
    } else {
        list->next = doInsert(ht, list->next, key, value);
        return list;
    }
}

static struct node *newNode(char *key, int value) {
    struct node *new = malloc(sizeof(struct node));
    if (new == NULL) {
        fprintf(stderr, "error: out of memory\n");
        exit(EXIT_FAILURE);
    }

    new->key = strdup(key);
    if (new->key == NULL) {
        fprintf(stderr, "error: out of memory\n");
        exit(EXIT_FAILURE);
    }

    new->value = value;
    new->next = NULL;
    return new;
}

void HashTableDelete(HashTable ht, char *key) {
    int i = hash(key, ht->numSlots);
    ht->slots[i] = doDelete(ht, ht->slots[i], key);
}

static struct node *doDelete(HashTable ht, struct node *list, char *key) {
    if (list == NULL) {
        return NULL;
    } else if (strcmp(list->key, key) == 0) {
        ht->numItems--;

        struct node *newHead = list->next;

        free(list->key);
        free(list);

        return newHead;
    } else {
        list->next = doDelete(ht, list->next, key);
        return list;
    }
}

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

    for (struct node *curr = ht->slots[i]; curr != NULL; curr = curr->next) {
        if (strcmp(curr->key, key) == 0) {
            return true;
        }
    }
    return false;
}

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

    for (struct node *curr = ht->slots[i]; curr != NULL; curr = curr->next) {
        if (strcmp(curr->key, key) == 0) {
            return curr->value;
        }
    }

    printf("error: key %s does not exist!\n", key);
    return -1;
}

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

static inline unsigned int hash(char *key, int N) {
    unsigned long h = 5381;
    int c;

    while ((c = *key++)) {
        h = ((h << 5) + h) + c;
    }

    return h % N;
}