// El diseño del dict de CPython, reducido: un arreglo de índices y otro de entradas. Muestra los
// dos arreglos después de cada operación. Usa la misma recurrencia de probing y las mismas reglas
// de tamaño que Objects/dictobject.c de Python 3.14, pero FNV-1a en vez del hash de Python.
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "demo_tables.h"

namespace {

constexpr int kEmpty = -1;
constexpr int kDummy = -2;

class CompactDict {
public:
    CompactDict() : indices_(8, kEmpty) {}

    void set(const std::string& key, int value) {
        const std::size_t slot = find_slot(key);
        if (indices_[slot] >= 0) {
            entries_[static_cast<std::size_t>(indices_[slot])].value = value;
            return;
        }
        if (entries_.size() == usable()) {
            resize();
        }
        indices_[first_free_slot(key)] = static_cast<int>(entries_.size());
        entries_.push_back({key, value, true});
        used_++;
    }

    void erase(const std::string& key) {
        const std::size_t slot = find_slot(key);
        if (indices_[slot] >= 0) {
            entries_[static_cast<std::size_t>(indices_[slot])].alive = false;
            indices_[slot] = kDummy;
            used_--;
        }
    }

    void print() const {
        std::cout << "  índices (" << indices_.size() << "):";
        for (int index : indices_) {
            if (index == kEmpty) {
                std::cout << " _";
            } else if (index == kDummy) {
                std::cout << " X";
            } else {
                std::cout << " " << index;
            }
        }
        std::cout << "\n  entradas:";
        for (std::size_t i = 0; i < entries_.size(); i++) {
            std::cout << " " << i << ":";
            if (entries_[i].alive) {
                std::cout << entries_[i].key << "=" << entries_[i].value;
            } else {
                std::cout << "(borrada)";
            }
        }
        std::cout << "\n";
    }

    void print_in_order() const {
        std::cout << "  recorrer:";
        for (const Entry& entry : entries_) {
            if (entry.alive) {
                std::cout << " " << entry.key;
            }
        }
        std::cout << "\n";
    }

private:
    struct Entry {
        std::string key;
        int value;
        bool alive;
    };

    std::size_t usable() const { return indices_.size() * 2 / 3; }

    // La casilla con la clave o, si no está, la casilla vacía donde termina el probing.
    std::size_t find_slot(const std::string& key) const {
        const std::uint64_t hash = demo_hash(key);
        const std::uint64_t mask = indices_.size() - 1;
        std::uint64_t perturb = hash;
        std::uint64_t i = hash & mask;
        while (indices_[i] != kEmpty) {
            if (indices_[i] >= 0 && entries_[static_cast<std::size_t>(indices_[i])].key == key) {
                return i;
            }
            perturb >>= 5;
            i = (i * 5 + perturb + 1) & mask;
        }
        return i;
    }

    // Donde se inserta una clave nueva: reúsa el primer tombstone del camino, como una vacía.
    std::size_t first_free_slot(const std::string& key) const {
        const std::uint64_t hash = demo_hash(key);
        const std::uint64_t mask = indices_.size() - 1;
        std::uint64_t perturb = hash;
        std::uint64_t i = hash & mask;
        while (indices_[i] >= 0) {
            perturb >>= 5;
            i = (i * 5 + perturb + 1) & mask;
        }
        return i;
    }

    // Tamaño nuevo: la menor potencia de 2 que llegue a used * 3. Sin tombstones ni entradas borradas.
    void resize() {
        std::size_t size = 8;
        while (size < used_ * 3) {
            size *= 2;
        }
        std::cout << "  (reconstruye: " << used_ << " en uso, " << indices_.size() << " -> " << size << " índices)\n";
        std::vector<Entry> old = std::move(entries_);
        entries_.clear();
        indices_.assign(size, kEmpty);
        for (Entry& entry : old) {
            if (entry.alive) {
                indices_[first_free_slot(entry.key)] = static_cast<int>(entries_.size());
                entries_.push_back(std::move(entry));
            }
        }
    }

    std::vector<int> indices_;
    std::vector<Entry> entries_;
    std::size_t used_ = 0;
};

}  // namespace

int main() {
    CompactDict dict;
    const char* names[] = {"lima", "cusco", "puno", "tacna", "ica"};
    for (int i = 0; i < 5; i++) {
        std::cout << "d[" << names[i] << "] = " << i << "\n";
        dict.set(names[i], i);
    }
    dict.print();
    dict.print_in_order();

    std::cout << "del d[cusco]\n";
    dict.erase("cusco");
    dict.print();
    dict.print_in_order();

    std::cout << "d[puno] = 9 (reemplaza: no cambia de lugar)\n";
    dict.set("puno", 9);
    dict.print();

    std::cout << "d[cusco] = 7 (vuelve, y va al final)\n";
    dict.set("cusco", 7);
    dict.print();
    dict.print_in_order();
    return 0;
}