// Una tabla con muy pocas claves vivas y muchas inserciones y borrados: cuenta cuántas casillas
// revisa una búsqueda sin éxito, con tres políticas. No mide tiempo: todo es conteo.
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <random>
#include <vector>

namespace {

constexpr std::size_t kSlots = 1024;
constexpr std::size_t kMask = kSlots - 1;
constexpr std::size_t kLive = 100;
constexpr std::uint64_t kEmpty = 0;
constexpr std::uint64_t kTombstone = 1;

// Un número al azar que no se confunde con las dos marcas.
std::uint64_t draw(std::mt19937_64& rng) {
    std::uint64_t key = rng();
    while (key <= kTombstone) {
        key = rng();
    }
    return key;
}

enum class Policy { never_clean, reuse, reuse_and_rebuild };

class Table {
public:
    explicit Table(Policy policy) : slots_(kSlots, kEmpty), policy_(policy) {}

    void insert(std::uint64_t key) {
        std::uint64_t i = key & kMask;
        std::size_t first_tombstone = kSlots;
        std::size_t walked = 0;
        while (slots_[i] != kEmpty && walked < kSlots) {
            if (slots_[i] == kTombstone && first_tombstone == kSlots) {
                first_tombstone = i;
            }
            i = (i + 1) & kMask;
            walked++;
        }
        if (policy_ != Policy::never_clean && first_tombstone != kSlots) {
            slots_[first_tombstone] = key;
            tombstones_--;
        } else {
            slots_[i] = key;
        }
        size_++;
        const double used = static_cast<double>(size_ + tombstones_);
        if (policy_ == Policy::reuse_and_rebuild && used > 0.7 * kSlots) {
            rebuild();
        }
    }

    void erase(std::uint64_t key) {
        std::uint64_t i = key & kMask;
        while (slots_[i] != key) {
            i = (i + 1) & kMask;
        }
        slots_[i] = kTombstone;
        size_--;
        tombstones_++;
    }

    // Casillas que revisa buscar una clave que no está.
    std::size_t miss_probes(std::uint64_t key) const {
        std::uint64_t i = key & kMask;
        std::size_t probes = 1;
        while (slots_[i] != kEmpty && probes < kSlots) {
            i = (i + 1) & kMask;
            probes++;
        }
        return probes;
    }

    std::size_t tombstones() const { return tombstones_; }
    std::size_t rebuilds() const { return rebuilds_; }

    bool full() const { return size_ + tombstones_ >= kSlots - 1; }

private:
    void rebuild() {
        std::vector<std::uint64_t> fresh(kSlots, kEmpty);
        for (std::uint64_t key : slots_) {
            if (key > kTombstone) {
                std::uint64_t i = key & kMask;
                while (fresh[i] != kEmpty) {
                    i = (i + 1) & kMask;
                }
                fresh[i] = key;
            }
        }
        slots_.swap(fresh);
        tombstones_ = 0;
        rebuilds_++;
    }

    std::vector<std::uint64_t> slots_;
    Policy policy_;
    std::size_t size_ = 0;
    std::size_t tombstones_ = 0;
    std::size_t rebuilds_ = 0;
};

void run(const char* name, Policy policy) {
    std::mt19937_64 rng(2026);
    Table table(policy);
    std::vector<std::uint64_t> live;
    for (std::size_t k = 0; k < kLive; k++) {
        live.push_back(draw(rng));
        table.insert(live.back());
    }
    std::printf("%s\n%10s %10s %12s %12s\n", name, "cambios", "tombstones", "casillas", "rebuilds");
    std::size_t changes = 0;
    for (std::size_t target : {std::size_t{0}, std::size_t{100}, std::size_t{500}, std::size_t{1000},
                               std::size_t{5000}, std::size_t{50000}}) {
        while (changes < target) {
            if (policy == Policy::never_clean && table.full()) {
                break;
            }
            const std::size_t victim = rng() % live.size();
            table.erase(live[victim]);
            live[victim] = draw(rng);
            table.insert(live[victim]);
            changes++;
        }
        std::uint64_t total = 0;
        std::mt19937_64 misses(7);
        for (int i = 0; i < 2000; i++) {
            total += table.miss_probes(draw(misses));
        }
        std::printf("%10zu %10zu %12.1f %12zu\n", changes, table.tombstones(),
                    static_cast<double>(total) / 2000.0, table.rebuilds());
        if (changes < target) {
            std::printf("(solo queda una casilla vacía: sin reusar tombstones ya no se puede insertar)\n");
            break;
        }
    }
    std::printf("\n");
}

}  // namespace

int main() {
    std::printf("Tabla de %zu casillas con %zu claves vivas (alfa real = %.2f).\n", kSlots, kLive,
                static_cast<double>(kLive) / kSlots);
    std::printf("Un cambio borra una clave e inserta otra. \"casillas\" es el promedio que revisa\n");
    std::printf("una búsqueda sin éxito, con 2000 búsquedas.\n\n");
    run("Nunca se limpia y nunca se reúsa:", Policy::never_clean);
    run("Se reúsan tombstones al insertar:", Policy::reuse);
    run("Se reúsan y se reconstruye al pasar 0.7:", Policy::reuse_and_rebuild);
    return 0;
}