// Tablas de la clase, reducidas a lo que hace falta para medir y contar. No son el laboratorio.
#ifndef DEMO_TABLES_H
#define DEMO_TABLES_H

#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>

// FNV-1a de 64 bits, con las constantes oficiales.
inline std::uint64_t demo_hash(const std::string& key) {
    std::uint64_t hash = 14695981039346656037ULL;
    for (char c : key) {
        hash ^= static_cast<unsigned char>(c);
        hash *= 1099511628211ULL;
    }
    return hash;
}

// Enteros con linear probing: entradas contiguas en un arreglo. 0 marca una casilla vacía.
class ProbingInts {
public:
    explicit ProbingInts(std::size_t slots) : entries_(slots), mask_(slots - 1) {}

    void insert(std::uint64_t key, std::uint64_t value) {
        std::uint64_t i = key & mask_;
        while (entries_[i].key != 0) {
            i = (i + 1) & mask_;
        }
        entries_[i] = {key, value};
    }

    const std::uint64_t* find(std::uint64_t key) const {
        std::uint64_t i = key & mask_;
        while (entries_[i].key != 0) {
            if (entries_[i].key == key) {
                return &entries_[i].value;
            }
            i = (i + 1) & mask_;
        }
        return nullptr;
    }

    // Bytes de la tabla.
    std::size_t bytes() const { return entries_.size() * sizeof(Entry); }

private:
    struct Entry {
        std::uint64_t key = 0;
        std::uint64_t value = 0;
    };

    std::vector<Entry> entries_;
    std::uint64_t mask_;
};

// Enteros con encadenamiento: cada entrada es un nodo reservado por separado.
class ChainedInts {
public:
    explicit ChainedInts(std::size_t slots) : heads_(slots, nullptr), mask_(slots - 1) {}

    ChainedInts(const ChainedInts&) = delete;
    ChainedInts& operator=(const ChainedInts&) = delete;

    ~ChainedInts() {
        for (Node* node : heads_) {
            while (node != nullptr) {
                Node* next = node->next;
                delete node;
                node = next;
            }
        }
    }

    void insert(std::uint64_t key, std::uint64_t value) {
        Node*& head = heads_[key & mask_];
        head = new Node{key, value, head};
        count_++;
    }

    const std::uint64_t* find(std::uint64_t key) const {
        for (const Node* node = heads_[key & mask_]; node != nullptr; node = node->next) {
            if (node->key == key) {
                return &node->value;
            }
        }
        return nullptr;
    }

    // Bytes pedidos con new, sin contar lo que agrega el reservador de memoria.
    std::size_t bytes() const { return heads_.size() * sizeof(Node*) + count_ * sizeof(Node); }

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

    std::vector<Node*> heads_;
    std::uint64_t mask_;
    std::size_t count_ = 0;
};

// Conjunto de cadenas con linear probing, que cuenta comparaciones de claves.
class CountingLinear {
public:
    explicit CountingLinear(std::size_t slots) : keys_(slots), used_(slots, 0), mask_(slots - 1) {}

    void insert(const std::string& key) {
        std::uint64_t i = demo_hash(key) & mask_;
        while (used_[i]) {
            i = (i + 1) & mask_;
        }
        keys_[i] = key;
        used_[i] = 1;
    }

    bool contains(const std::string& key) {
        std::uint64_t i = demo_hash(key) & mask_;
        while (used_[i]) {
            comparisons_++;
            if (keys_[i] == key) {
                return true;
            }
            i = (i + 1) & mask_;
        }
        return false;
    }

    std::uint64_t comparisons() const { return comparisons_; }
    void reset() { comparisons_ = 0; }

private:
    std::vector<std::string> keys_;
    std::vector<char> used_;
    std::uint64_t mask_;
    std::uint64_t comparisons_ = 0;
};

#endif