// Medidor de tiempos del curso. Compilar con -O2 y sin sanitizers.
#ifndef BENCH_H
#define BENCH_H

#include <algorithm>
#include <chrono>
#include <vector>

// Corre fn `reps` veces y devuelve la mediana en segundos.
template <typename Fn>
double median_seconds(int reps, Fn fn) {
    std::vector<double> times;
    times.reserve(reps);
    for (int i = 0; i < reps; i++) {
        auto start = std::chrono::steady_clock::now();
        fn();
        auto stop = std::chrono::steady_clock::now();
        times.push_back(std::chrono::duration<double>(stop - start).count());
    }
    std::sort(times.begin(), times.end());
    return times[times.size() / 2];
}

// Evita que el compilador borre un cálculo cuyo resultado no se usa.
template <typename T>
void keep(const T& value) {
    volatile T sink = value;
    (void)sink;
}

#endif

// 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;
}

// 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

"""Comportamiento real del dict de CPython. Se corre con python3 dict_demo.py."""
import sys


def show_order():
    d = {"lima": 0, "cusco": 1, "puno": 2}
    print("creado:         ", list(d))
    d["puno"] = 9
    print("reemplazar puno:", list(d))
    del d["cusco"]
    d["tacna"] = 3
    print("borrar cusco y agregar tacna:", list(d))
    d["cusco"] = 7
    print("volver a agregar cusco:      ", list(d))
    print("popitem saca el último:", d.popitem())


def expected_size(log2_size):
    """Lo que predice Objects/dictobject.c para claves de texto: 64 del objeto dict con el
    encabezado del recolector, 32 del encabezado de las claves, los índices y las entradas de
    16 bytes, 2/3 de las casillas."""
    size = 1 << log2_size
    index_bytes = 1 if size <= 128 else 2 if size <= 2**15 else 4
    return 64 + 32 + size * index_bytes + (size * 2 // 3) * 16


def show_sizes():
    """La predicción no mira a sys.getsizeof: sale de las reglas de dictobject.c. Se empieza con 8
    casillas y, cuando se acaban las entradas usables (2/3), el tamaño nuevo es la menor potencia
    de 2 que llegue a used * 3. Sin borrados, used es la cantidad de claves que ya hay."""
    print("claves  sys.getsizeof  casillas  usables  predicción")
    log2_size = 3
    d = {}
    last = sys.getsizeof(d)
    for i in range(400):
        used = len(d)
        if used == (1 << log2_size) * 2 // 3:
            log2_size = 3
            while (1 << log2_size) < used * 3:
                log2_size += 1
        d[f"clave{i}"] = i
        size = sys.getsizeof(d)
        if size != last:
            slots = 1 << log2_size
            print(f"{i + 1:6} {size:14} {slots:9} {slots * 2 // 3:8} {expected_size(log2_size):11}")
            last = size


def show_cleaning():
    """Con pocas claves vivas, la reconstrucción no crece: la tabla se achica."""
    d = {f"k{i}": i for i in range(1000)}
    before = sys.getsizeof(d)
    for i in range(990):
        del d[f"k{i}"]
    print(f"1000 claves: {before} bytes; al borrar 990: {sys.getsizeof(d)} bytes")
    i = 0
    while sys.getsizeof(d) == before:
        d[f"z{i}"] = i
        del d[f"z{i}"]
        i += 1
    print(f"tras {i} altas y bajas, con {len(d)} claves: {sys.getsizeof(d)} bytes")


def main():
    print("Python", sys.version.split()[0], sys.implementation.name)
    show_order()
    print()
    show_cleaning()
    print()
    show_sizes()


if __name__ == "__main__":
    main()

// Compara los 8 bytes de una palabra de control a la vez, con operaciones de bits.
#include <cinttypes>
#include <cstdint>
#include <cstdio>

#include "mini_swiss.h"

namespace {

void show(std::uint64_t ctrl, unsigned char h2) {
    std::printf("buscar h2 = %3u: casillas candidatas:", h2);
    std::uint64_t marks = match_h2(ctrl, h2);
    if (marks == 0) {
        std::printf(" ninguna");
    }
    while (marks != 0) {
        std::printf(" %d", first_marked(marks));
        marks &= marks - 1;
    }
    std::printf("\n");
}

}  // namespace

int main() {
    // El byte de la casilla 0 es el de menor peso.
    const unsigned char bytes[8] = {23, 89, 50, kCtrlEmpty, 89, kCtrlDeleted, 7, kCtrlEmpty};
    std::uint64_t ctrl = 0;
    for (int slot = 7; slot >= 0; slot--) {
        ctrl = (ctrl << 8) | bytes[slot];
    }
    std::printf("palabra de control: 0x%016" PRIx64 "\n", ctrl);
    std::printf("bytes por casilla:");
    for (unsigned char byte : bytes) {
        std::printf(" %u", byte);
    }
    std::printf("\n");
    show(ctrl, 89);
    show(ctrl, 50);
    show(ctrl, 100);
    std::printf("casillas vacías:");
    std::uint64_t marks = match_empty(ctrl);
    while (marks != 0) {
        std::printf(" %d", first_marked(marks));
        marks &= marks - 1;
    }
    std::printf("\n");

    // Un falso positivo: 0x03 justo después de una coincidencia real con 0x02.
    std::printf("otra palabra, bytes por casilla: 2 3 128 128 128 128 128 128\n");
    show(0x0302ULL | (kLowBits * kCtrlEmpty << 16), 2);
    return 0;
}

// Linear probing contra encadenamiento, con claves y valores enteros: las mismas claves, las mismas
// casillas y el mismo factor de carga. Mide búsquedas en orden al azar. -O2 y sin sanitizers.
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <random>
#include <vector>

#include "bench.h"
#include "demo_tables.h"

namespace {

constexpr std::size_t kLookups = 1000000;
constexpr int kReps = 5;

std::uint64_t draw(std::mt19937_64& rng) {
    std::uint64_t key = rng();
    while (key == 0) {
        key = rng();
    }
    return key;
}

template <typename Table>
double lookup_ns(const Table& table, const std::vector<std::uint64_t>& queries) {
    const double seconds = median_seconds(kReps, [&] {
        std::uint64_t sum = 0;
        for (std::uint64_t query : queries) {
            const std::uint64_t* value = table.find(query);
            sum += value == nullptr ? 1 : *value;
        }
        keep(sum);
    });
    return seconds * 1e9 / static_cast<double>(queries.size());
}

void compare(int log_slots, double alpha) {
    const std::size_t slots = std::size_t{1} << log_slots;
    const std::size_t n = static_cast<std::size_t>(alpha * static_cast<double>(slots));
    std::mt19937_64 rng(2026);
    std::vector<std::uint64_t> keys(n);
    for (std::uint64_t& key : keys) {
        key = draw(rng);
    }
    ProbingInts probing(slots);
    ChainedInts chained(slots);
    for (std::uint64_t key : keys) {
        probing.insert(key, key);
        chained.insert(key, key);
    }
    std::vector<std::uint64_t> hits(kLookups);
    std::vector<std::uint64_t> misses(kLookups);
    for (std::size_t i = 0; i < kLookups; i++) {
        hits[i] = keys[rng() % n];
        misses[i] = draw(rng);
    }
    const double probing_hit = lookup_ns(probing, hits);
    const double chained_hit = lookup_ns(chained, hits);
    const double probing_miss = lookup_ns(probing, misses);
    const double chained_miss = lookup_ns(chained, misses);
    std::printf("2^%-3d %5.2f %9.1f %9.1f %9.1f %9.1f %9.1f %9.1f\n", log_slots, alpha, probing_hit,
                chained_hit, probing_miss, chained_miss,
                static_cast<double>(probing.bytes()) / static_cast<double>(n),
                static_cast<double>(chained.bytes()) / static_cast<double>(n));
}

}  // namespace

int main() {
    std::printf("ns por búsqueda, mediana de %d rondas de %zu. Bytes por clave.\n", kReps, kLookups);
    std::printf("%-5s %5s %9s %9s %9s %9s %9s %9s\n", "cas.", "alfa", "lin.hit", "cad.hit", "lin.miss",
                "cad.miss", "lin.B", "cad.B");
    for (int log_slots : {12, 16, 20, 22}) {
        for (double alpha : {0.50, 0.75, 0.90}) {
            compare(log_slots, alpha);
        }
    }
    return 0;
}

// Una Swiss Table de juguete para la clase, escrita para contar y no para ser rápida. Sigue el
// diseño de los mapas de Go 1.24: grupos de 8 casillas, una palabra de control de 64 bits por
// grupo, y los 7 bits bajos del hash en el byte de cada casilla llena.
#ifndef MINI_SWISS_H
#define MINI_SWISS_H

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

#include "demo_tables.h"

constexpr std::uint64_t kLowBits = 0x0101010101010101ULL;
constexpr std::uint64_t kHighBits = 0x8080808080808080ULL;
constexpr unsigned char kCtrlEmpty = 0x80;    // 1000 0000
constexpr unsigned char kCtrlDeleted = 0xFE;  // 1111 1110

// Marca con el bit alto los bytes de la palabra que valen h2, sin revisar uno por uno.
// Puede dar falsos positivos raros, justo después de una coincidencia real, y nunca se pierde
// una: por eso siempre se compara la clave completa después.
inline std::uint64_t match_h2(std::uint64_t ctrl, unsigned char h2) {
    const std::uint64_t v = ctrl ^ (kLowBits * h2);
    return (v - kLowBits) & ~v & kHighBits;
}

// Marca los bytes vacíos: tienen el bit alto en 1 y el bit 1 en 0.
inline std::uint64_t match_empty(std::uint64_t ctrl) {
    return ctrl & ~(ctrl << 6) & kHighBits;
}

// Número de casilla (0 a 7) del primer byte marcado.
inline int first_marked(std::uint64_t marks) {
    return __builtin_ctzll(marks) / 8;
}

class MiniSwiss {
public:
    static constexpr std::size_t kGroupSlots = 8;

    // El total de casillas es group_count * 8, con group_count potencia de 2.
    explicit MiniSwiss(std::size_t group_count)
        : ctrl_(group_count, kLowBits * kCtrlEmpty), keys_(group_count * kGroupSlots), mask_(group_count - 1) {}

    void insert(const std::string& key) {
        const std::uint64_t hash = demo_hash(key);
        const unsigned char h2 = hash & 0x7F;
        std::uint64_t group = (hash >> 7) & mask_;
        std::uint64_t step = 0;
        while (match_empty(ctrl_[group]) == 0) {
            step++;
            group = (group + step) & mask_;  // quadratic probing entre grupos
        }
        const int slot = first_marked(match_empty(ctrl_[group]));
        set_byte(group, slot, h2);
        keys_[group * kGroupSlots + static_cast<std::size_t>(slot)] = key;
    }

    bool contains(const std::string& key) {
        const std::uint64_t hash = demo_hash(key);
        const unsigned char h2 = hash & 0x7F;
        std::uint64_t group = (hash >> 7) & mask_;
        std::uint64_t step = 0;
        while (true) {
            groups_read_++;
            std::uint64_t marks = match_h2(ctrl_[group], h2);
            while (marks != 0) {
                const int slot = first_marked(marks);
                comparisons_++;
                if (keys_[group * kGroupSlots + static_cast<std::size_t>(slot)] == key) {
                    return true;
                }
                marks &= marks - 1;
            }
            if (match_empty(ctrl_[group]) != 0) {
                return false;  // un grupo con una vacía termina la búsqueda
            }
            step++;
            group = (group + step) & mask_;
        }
    }

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

private:
    void set_byte(std::uint64_t group, int slot, unsigned char value) {
        const int shift = slot * 8;
        ctrl_[group] = (ctrl_[group] & ~(std::uint64_t{0xFF} << shift)) | (std::uint64_t{value} << shift);
    }

    std::vector<std::uint64_t> ctrl_;
    std::vector<std::string> keys_;
    std::uint64_t mask_;
    std::uint64_t comparisons_ = 0;
    std::uint64_t groups_read_ = 0;
};

#endif

// La secuencia de probing del dict de CPython: probe_order <casillas> <hash> [cuántas]
// Usa la recurrencia de Objects/dictobject.c: perturb >>= 5; i = (i*5 + perturb + 1) & mask.
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <iostream>

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: probe_order <casillas> <hash> [cuántas]\n";
        return 2;
    }
    const std::uint64_t slots = std::strtoull(argv[1], nullptr, 10);
    const std::uint64_t hash = std::strtoull(argv[2], nullptr, 10);
    const std::size_t count = argc > 3 ? std::strtoul(argv[3], nullptr, 10) : slots;
    const std::uint64_t mask = slots - 1;

    std::uint64_t perturb = hash;
    std::uint64_t i = hash & mask;
    std::cout << "casillas " << slots << ", hash " << hash << ":";
    for (std::size_t step = 0; step < count; step++) {
        std::cout << " " << i;
        perturb >>= 5;
        i = (i * 5 + perturb + 1) & mask;
    }
    std::cout << "\n";
    return 0;
}

// Una tabla de enteros con h(k) = k mod m y linear probing, que muestra cada paso.
// probe_trace <m> <órdenes>. Órdenes: i10 inserta, f31 busca, e17 borra vaciando la casilla
// (está mal, a propósito), t17 borra con tombstone.
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

namespace {

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

class TraceTable {
public:
    explicit TraceTable(std::size_t slots) : slots_(slots, kEmpty) {}

    void insert(int key) {
        std::size_t i = home(key);
        std::cout << "insertar " << key << " (inicio " << i << "):";
        // Basta para esta demostración: no revisa si la clave ya está.
        while (slots_[i] >= 0) {
            std::cout << " " << i;
            i = (i + 1) % slots_.size();
        }
        std::cout << " " << i << " <- aquí\n";
        slots_[i] = key;
    }

    // Devuelve la casilla donde está la clave, o -1.
    int find(int key, bool show = true) const {
        std::size_t i = home(key);
        std::size_t probes = 0;
        std::string path;
        int where = -1;
        while (probes < slots_.size()) {
            probes++;
            path += " " + std::to_string(i);
            if (slots_[i] == key) {
                where = static_cast<int>(i);
                break;
            }
            if (slots_[i] == kEmpty) {
                break;
            }
            i = (i + 1) % slots_.size();
        }
        if (show) {
            std::cout << "buscar " << key << " (inicio " << home(key) << "):" << path << " -> "
                      << (where >= 0 ? "está" : "no está") << ", " << probes << " casillas\n";
        }
        return where;
    }

    void erase_wrong(int key) {
        const int i = find(key, false);
        std::cout << "borrar " << key << " vaciando la casilla " << i << "\n";
        if (i >= 0) {
            slots_[static_cast<std::size_t>(i)] = kEmpty;
        }
    }

    void erase_tombstone(int key) {
        const int i = find(key, false);
        std::cout << "borrar " << key << " con tombstone en la casilla " << i << "\n";
        if (i >= 0) {
            slots_[static_cast<std::size_t>(i)] = kTombstone;
        }
    }

    void print() const {
        std::cout << "tabla:";
        for (std::size_t i = 0; i < slots_.size(); i++) {
            std::cout << " [" << i << ":";
            if (slots_[i] == kEmpty) {
                std::cout << "_";
            } else if (slots_[i] == kTombstone) {
                std::cout << "X";
            } else {
                std::cout << slots_[i];
            }
            std::cout << "]";
        }
        std::cout << "\n";
    }

private:
    std::size_t home(int key) const { return static_cast<std::size_t>(key) % slots_.size(); }

    std::vector<int> slots_;
};

}  // namespace

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "uso: probe_trace <m> <órdenes: i10 f31 e17 t17>\n";
        return 2;
    }
    TraceTable table(std::strtoul(argv[1], nullptr, 10));
    for (int a = 2; a < argc; a++) {
        const char order = argv[a][0];
        const int key = std::atoi(argv[a] + 1);
        if (order == 'i') {
            table.insert(key);
        } else if (order == 'f') {
            table.find(key);
        } else if (order == 'e') {
            table.erase_wrong(key);
        } else if (order == 't') {
            table.erase_tombstone(key);
        } else if (order == 'p') {
            table.print();
        }
    }
    table.print();
    return 0;
}

// Cuenta casillas revisadas por búsqueda, sin medir tiempo: linear probing, double hashing (sin
// agrupamiento primario) y encadenamiento, contra las fórmulas clásicas.
// Las claves son números al azar de 64 bits, con semilla fija, así que k mod m reparte bien.
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <random>
#include <vector>

namespace {

constexpr std::size_t kSlots = 1u << 20;
constexpr std::size_t kMask = kSlots - 1;
constexpr std::uint64_t kEmpty = 0;

struct Counts {
    double hit;
    double miss;
};

// Un número al azar distinto de kEmpty. No se fuerza ningún bit: eso dejaría casillas sin uso.
std::uint64_t draw(std::mt19937_64& rng) {
    std::uint64_t key = rng();
    while (key == kEmpty) {
        key = rng();
    }
    return key;
}

// El paso es impar, para que el probing visite todas las casillas de una tabla de 2^k.
std::uint64_t step_for(std::uint64_t key, bool linear) {
    return linear ? 1 : ((key >> 32) | 1);
}

Counts open_addressing(const std::vector<std::uint64_t>& keys, std::size_t n,
                       const std::vector<std::uint64_t>& absent, bool linear) {
    std::vector<std::uint64_t> table(kSlots, kEmpty);
    for (std::size_t k = 0; k < n; k++) {
        const std::uint64_t step = step_for(keys[k], linear);
        std::uint64_t i = keys[k] & kMask;
        while (table[i] != kEmpty) {
            i = (i + step) & kMask;
        }
        table[i] = keys[k];
    }
    std::uint64_t probes = 0;
    for (std::size_t k = 0; k < n; k++) {
        const std::uint64_t step = step_for(keys[k], linear);
        std::uint64_t i = keys[k] & kMask;
        probes++;
        while (table[i] != keys[k]) {
            i = (i + step) & kMask;
            probes++;
        }
    }
    const double hit = static_cast<double>(probes) / static_cast<double>(n);
    probes = 0;
    for (std::uint64_t key : absent) {
        const std::uint64_t step = step_for(key, linear);
        std::uint64_t i = key & kMask;
        probes++;
        while (table[i] != kEmpty) {
            i = (i + step) & kMask;
            probes++;
        }
    }
    return {hit, static_cast<double>(probes) / static_cast<double>(absent.size())};
}

// Con encadenamiento se cuentan nodos visitados: buscar sin éxito recorre toda la lista.
Counts chaining(const std::vector<std::uint64_t>& keys, std::size_t n,
                const std::vector<std::uint64_t>& absent) {
    std::vector<std::uint32_t> length(kSlots, 0);
    std::uint64_t nodes = 0;
    for (std::size_t k = 0; k < n; k++) {
        length[keys[k] & kMask]++;
        // Al insertar al final, la clave k-ésima se encontrará recorriendo esta cantidad de nodos.
        nodes += length[keys[k] & kMask];
    }
    const double hit = static_cast<double>(nodes) / static_cast<double>(n);
    nodes = 0;
    for (std::uint64_t key : absent) {
        nodes += length[key & kMask];
    }
    return {hit, static_cast<double>(nodes) / static_cast<double>(absent.size())};
}

}  // namespace

int main() {
    std::mt19937_64 rng(2026);
    std::vector<std::uint64_t> keys(kSlots);
    for (std::uint64_t& key : keys) {
        key = draw(rng);
    }
    std::vector<std::uint64_t> absent(200000);
    for (std::uint64_t& key : absent) {
        key = draw(rng);
    }
    std::printf("Con éxito: casillas o nodos revisados por búsqueda, promedio\n");
    std::printf("%5s %8s %8s %8s %8s\n", "alfa", "linear", "fórmula", "double", "cadenas");
    const double alphas[] = {0.25, 0.5, 0.7, 0.8, 0.9, 0.95, 0.99};
    std::vector<Counts> line;
    std::vector<Counts> twice;
    std::vector<Counts> chain;
    for (double alpha : alphas) {
        const std::size_t n = static_cast<std::size_t>(alpha * static_cast<double>(kSlots));
        line.push_back(open_addressing(keys, n, absent, true));
        twice.push_back(open_addressing(keys, n, absent, false));
        chain.push_back(chaining(keys, n, absent));
    }
    for (std::size_t a = 0; a < line.size(); a++) {
        const double alpha = alphas[a];
        const double formula = 0.5 * (1.0 + 1.0 / (1.0 - alpha));
        std::printf("%5.2f %8.2f %8.2f %8.2f %8.2f\n", alpha, line[a].hit, formula, twice[a].hit, chain[a].hit);
    }
    std::printf("\nSin éxito: casillas o nodos revisados por búsqueda, promedio\n");
    std::printf("%5s %8s %8s %8s %8s\n", "alfa", "linear", "fórmula", "double", "cadenas");
    for (std::size_t a = 0; a < line.size(); a++) {
        const double alpha = alphas[a];
        const double formula = 0.5 * (1.0 + 1.0 / ((1.0 - alpha) * (1.0 - alpha)));
        std::printf("%5.2f %8.2f %8.2f %8.2f %8.2f\n", alpha, line[a].miss, formula, twice[a].miss, chain[a].miss);
    }
    return 0;
}

// Cuenta comparaciones de claves completas: linear probing contra una Swiss Table de juguete, en la
// misma cantidad de casillas y con las mismas palabras. swiss_counts <palabras.txt>
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "mini_swiss.h"

namespace {

constexpr std::size_t kSlots = std::size_t{1} << 20;

void compare(const std::vector<std::string>& words, double alpha) {
    const std::size_t n = static_cast<std::size_t>(alpha * static_cast<double>(kSlots));
    CountingLinear linear(kSlots);
    MiniSwiss swiss(kSlots / MiniSwiss::kGroupSlots);
    for (std::size_t i = 0; i < n; i++) {
        linear.insert(words[i]);
        swiss.insert(words[i]);
    }
    const double total = static_cast<double>(n);
    for (std::size_t i = 0; i < n; i++) {
        linear.contains(words[i]);
        swiss.contains(words[i]);
    }
    const double linear_hit = static_cast<double>(linear.comparisons()) / total;
    const double swiss_hit = static_cast<double>(swiss.comparisons()) / total;
    const double groups_hit = static_cast<double>(swiss.groups_read()) / total;
    linear.reset();
    swiss.reset();
    for (std::size_t i = 0; i < n; i++) {
        linear.contains(words[i] + "#");  // ninguna palabra lleva #
        swiss.contains(words[i] + "#");
    }
    std::printf("%5.2f %12.2f %12.2f %8.2f %12.2f %12.4f %8.2f\n", alpha, linear_hit, swiss_hit, groups_hit,
                static_cast<double>(linear.comparisons()) / total, static_cast<double>(swiss.comparisons()) / total,
                static_cast<double>(swiss.groups_read()) / total);
}

}  // namespace

int main(int argc, char** argv) {
    if (argc < 2) {
        std::cerr << "uso: swiss_counts <palabras.txt>\n";
        return 2;
    }
    std::ifstream in(argv[1]);
    if (!in) {
        std::cerr << "no se pudo abrir " << argv[1] << "\n";
        return 2;
    }
    std::vector<std::string> words;
    std::string word;
    while (std::getline(in, word)) {
        words.push_back(word);
    }
    std::mt19937 rng(2026);
    std::shuffle(words.begin(), words.end(), rng);

    std::printf("%zu casillas. Promedios por búsqueda.\n", kSlots);
    std::printf("%5s %25s %8s %25s %8s\n", "", "--- con éxito: compara ---", "", "--- sin éxito: compara ---", "");
    std::printf("%5s %12s %12s %8s %12s %12s %8s\n", "alfa", "linear", "swiss", "grupos", "linear", "swiss", "grupos");
    for (double alpha : {0.25, 0.50, 0.70, 0.80, 0.875}) {
        compare(words, alpha);
    }
    return 0;
}

// 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;
}