#include "table.h"

#include <stdexcept>

std::uint64_t hash(std::string const& s)
{
    // djb2
    std::uint64_t result { 5183 };
    for (char c : s)
        result = 33*result + c;
    return result;
}

// TODO: Ändra till kvadratsondering istället för linjärsondering

Hash_Table::Hash_Table()
    : table(1)
{
}

void Hash_Table::insert(std::string const& key, int value)
{
    unsigned index { find(key) };

    // om nyckeln redan finns uppdaterar vi värdet
    if (table[index].key == key)
        table[index].value = value;

    // tabellen är full
    if (table[index].valid)
    {
        resize(2 * table.size());
        index = find(key);
    }

    table[index].key   = key;
    table[index].value = value;
    table[index].valid = true;
}

void Hash_Table::remove(std::string const& key)
{
    unsigned index { find(key) };

    // nyckeln fanns ej
    if (table[index].key != key)
        return;

    table[index].valid = false;
}

int& Hash_Table::lookup(std::string const& key)
{
    unsigned index { find(key) };
    if (table[index].valid)
    {
        if (table[index].key == key)
            return table[index].value;
    }

    throw std::out_of_range{ "Key doesn't exist" };
}

bool Hash_Table::contains(std::string const& key) const
{
    // TODO: Implement
}

std::vector<std::string> Hash_Table::keys() const
{
    std::vector<std::string> result { };
    for (Entry const& entry : table)
    {
        if (entry.valid)
            result.push_back(entry.key);
    }
    return result;
}

unsigned Hash_Table::find(std::string const& key) const
{
    std::uint64_t begin { hash(key) % table.size() };
    std::uint64_t index { begin };

    for (unsigned i { 0 }; i < table.size(); ++i)
    {
        index = (begin + i) % table.size();
        if (not table[index].valid)
            break;
        else if (table[index].key == key)
            break;
    }

    return index;
}

void Hash_Table::resize(unsigned new_size)
{
    std::vector<Entry> old_table { table };

    table = std::vector<Entry>(new_size);
    for (Entry const& entry : old_table)
        insert(entry.key, entry.value);
}