// Encadenamiento en su forma más simple: número fijo de casillas, sin borrar y sin crecer.
// HashMap, la del laboratorio, agrega lo que aquí falta.
#ifndef CHAIN_TABLE_H
#define CHAIN_TABLE_H

#include <cassert>
#include <cstddef>
#include <string>
#include <vector>

#include "hash_functions.h"

// Invariantes:
// - Cada nodo de la cadena i cumple hash_(key) % capacity_ == i.
// - Una clave aparece en un solo nodo.
// - size_ es el total de nodos.
template <typename V>
class ChainTable {
public:
    ChainTable(std::size_t capacity, HashFunction hash)
        : slots_(new Node*[capacity]()), capacity_(capacity), hash_(hash) {
        assert(capacity > 0);
    }

    ~ChainTable() {
        for (std::size_t i = 0; i < capacity_; i++) {
            Node* node = slots_[i];
            while (node != nullptr) {
                Node* next = node->next;
                delete node;
                node = next;
            }
        }
        delete[] slots_;
    }

    // La tabla es owner de sus nodos: para no repetir la regla de cinco, aquí no se copia.
    ChainTable(const ChainTable&) = delete;
    ChainTable& operator=(const ChainTable&) = delete;

    void set(const std::string& key, const V& value) {
        Node* node = find_node(key);
        if (node != nullptr) {
            node->value = value;
            return;
        }
        std::size_t slot = slot_of(key);
        slots_[slot] = new Node{key, value, slots_[slot]};
        size_++;
    }

    const V* get(const std::string& key) const {
        Node* node = find_node(key);
        return node == nullptr ? nullptr : &node->value;
    }

    std::size_t size() const { return size_; }
    std::size_t capacity() const { return capacity_; }
    double load_factor() const { return static_cast<double>(size_) / capacity_; }

    // Cuántas claves hay que comparar para buscar esta clave. No es parte del diccionario:
    // está para medir.
    std::size_t comparisons_for(const std::string& key) const {
        std::size_t count = 0;
        for (Node* node = slots_[slot_of(key)]; node != nullptr; node = node->next) {
            count++;
            if (node->key == key) {
                break;
            }
        }
        return count;
    }

    std::size_t chain_length(std::size_t slot) const {
        std::size_t length = 0;
        for (Node* node = slots_[slot]; node != nullptr; node = node->next) {
            length++;
        }
        return length;
    }

    // Las claves de una cadena, en orden. Está para mostrar la tabla en los ejemplos.
    std::vector<std::string> chain_keys(std::size_t slot) const {
        std::vector<std::string> keys;
        for (Node* node = slots_[slot]; node != nullptr; node = node->next) {
            keys.push_back(node->key);
        }
        return keys;
    }

    bool check_invariants() const {
        std::size_t total = 0;
        for (std::size_t i = 0; i < capacity_; i++) {
            for (Node* node = slots_[i]; node != nullptr; node = node->next) {
                total++;
                if (slot_of(node->key) != i) {
                    return false;
                }
                for (Node* other = node->next; other != nullptr; other = other->next) {
                    if (other->key == node->key) {
                        return false;
                    }
                }
            }
        }
        return total == size_;
    }

private:
    struct Node {
        std::string key;
        V value;
        Node* next;
    };

    std::size_t slot_of(const std::string& key) const {
        return hash_(key) % capacity_;
    }

    Node* find_node(const std::string& key) const {
        for (Node* node = slots_[slot_of(key)]; node != nullptr; node = node->next) {
            if (node->key == key) {
                return node;
            }
        }
        return nullptr;
    }

    Node** slots_;
    std::size_t capacity_;
    std::size_t size_ = 0;
    HashFunction hash_;
};

#endif