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

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

// Muestra las cadenas de una tabla, paso a paso. Se inserta al inicio de la cadena.
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

#include "chain_table.h"

void print_table(const ChainTable<int>& table) {
    for (std::size_t i = 0; i < table.capacity(); i++) {
        std::cout << "  " << i << ":";
        for (const std::string& key : table.chain_keys(i)) {
            std::cout << " " << key;
        }
        std::cout << "\n";
    }
}

int main() {
    std::cout << "Con la suma y 8 casillas\n";
    ChainTable<int> small(8, sum_hash);
    for (const std::string word : {"lima", "amor", "roma", "ad", "bc", "mora"}) {
        small.set(word, 1);
        std::cout << "set(" << word << "): suma " << sum_hash(word) << ", casilla " << sum_hash(word) % 8 << "\n";
    }
    print_table(small);
    std::cout << "comparaciones para mora: " << small.comparisons_for("mora") << ", para amor: "
              << small.comparisons_for("amor") << ", para ramo: " << small.comparisons_for("ramo") << "\n";

    const std::vector<std::string> cities = {"lima", "cusco", "puno", "tacna", "ica", "piura"};
    for (std::size_t capacity : {4u, 8u}) {
        std::cout << "Con FNV-1a y " << capacity << " casillas\n";
        ChainTable<int> table(capacity, fnv1a);
        for (const std::string& city : cities) {
            table.set(city, 1);
        }
        print_table(table);
    }
}

// ¿Cuántas claves entran antes de la primera colisión, con m casillas?
// Uso: first_collision archivo_de_palabras
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "hash_functions.h"
#include "word_file.h"

// Inserta palabras en orden hasta que dos caigan en la misma casilla.
std::size_t keys_until_collision(const std::vector<std::string>& words, std::size_t m) {
    std::vector<bool> taken(m, false);
    for (std::size_t i = 0; i < words.size(); i++) {
        std::size_t slot = fnv1a(words[i]) % m;
        if (taken[slot]) {
            return i + 1;
        }
        taken[slot] = true;
    }
    return words.size();
}

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: first_collision archivo_de_palabras\n";
        return 1;
    }
    std::vector<std::string> words = read_words(argv[1]);
    std::mt19937 rng(7);
    std::printf("%-11s %-8s %-8s %s\n", "m", "mediana", "raiz(m)", "repeticiones");
    for (std::size_t m : {1000u, 100000u, 1000000u, 10000000u}) {
        const int reps = 51;
        std::vector<std::size_t> counts;
        for (int r = 0; r < reps; r++) {
            // Basta barajar el comienzo: nunca llegamos a usar toda la lista.
            for (std::size_t i = 0; i < 20000 && i < words.size(); i++) {
                std::uniform_int_distribution<std::size_t> pick(i, words.size() - 1);
                std::swap(words[i], words[pick(rng)]);
            }
            counts.push_back(keys_until_collision(words, m));
        }
        std::sort(counts.begin(), counts.end());
        std::printf("%-11zu %-8zu %-8.0f %d\n", m, counts[reps / 2], std::sqrt(static_cast<double>(m)), reps);
    }
}

// Claves elegidas a propósito para que caigan todas en la misma casilla.
// Las tablas no tienen defensa: la función hash es pública y no usa ningún secreto.
#include <cstddef>
#include <cstdio>
#include <functional>
#include <string>
#include <unordered_map>
#include <vector>

#include "bench.h"
#include "chain_table.h"

// Las primeras claves "k0", "k1", ... cuyo hash es múltiplo de divisor.
template <typename Hash>
std::vector<std::string> crafted_keys(std::size_t count, std::size_t divisor, Hash hash) {
    std::vector<std::string> keys;
    for (std::size_t i = 0; keys.size() < count; i++) {
        std::string key = "k" + std::to_string(i);
        if (hash(key) % divisor == 0) {
            keys.push_back(key);
        }
    }
    return keys;
}

std::vector<std::string> plain_keys(std::size_t count) {
    std::vector<std::string> keys;
    for (std::size_t i = 0; i < count; i++) {
        keys.push_back("k" + std::to_string(i));
    }
    return keys;
}

void own_table(const char* name, const std::vector<std::string>& keys, std::size_t m) {
    ChainTable<int> table(m, fnv1a);
    for (const std::string& key : keys) {
        table.set(key, 1);
    }
    std::size_t longest = 0;
    for (std::size_t i = 0; i < m; i++) {
        longest = std::max(longest, table.chain_length(i));
    }
    double total = 0;
    for (const std::string& key : keys) {
        total += static_cast<double>(table.comparisons_for(key));
    }
    std::printf("%-10s m=%-5zu la mayor cadena %5zu, comparaciones por busqueda %8.1f\n", name, m, longest,
                total / static_cast<double>(keys.size()));
}

void library_table(const char* name, const std::vector<std::string>& keys, std::size_t buckets) {
    std::size_t largest = 0;
    double seconds = median_seconds(5, [&] {
        std::unordered_map<std::string, int> table;
        table.reserve(buckets);
        for (const std::string& key : keys) {
            table[key] = 1;
        }
        largest = table.bucket_size(table.bucket(keys[0]));
        keep(table.size());
    });
    std::printf("%-10s la casilla de keys[0] tiene %5zu, %9.2f ms\n", name, largest, seconds * 1000);
}

int main() {
    const std::size_t n = 4000;
    // Si el hash es múltiplo de 8192, también lo es de 4096, 2048, ... Crecer hasta 8192 no ayuda.
    std::vector<std::string> crafted = crafted_keys(n, 8192, fnv1a);
    std::printf("%zu claves; la ultima elegida es %s\n", n, crafted.back().c_str());
    own_table("normales", plain_keys(n), 4096);
    own_table("elegidas", crafted, 4096);
    own_table("elegidas", crafted, 8192);

    std::unordered_map<std::string, int> probe;
    probe.reserve(n);
    std::size_t buckets = probe.bucket_count();
    std::printf("unordered_map con reserve(%zu): bucket_count %zu\n", n, buckets);
    std::vector<std::string> against_library = crafted_keys(n, buckets, std::hash<std::string>{});
    library_table("normales", plain_keys(n), n);
    library_table("elegidas", against_library, n);
}

// Sigue FNV-1a byte por byte: un cambio en un byte afecta a todos los que vienen después.
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>

void trace(const std::string& key) {
    std::uint64_t hash = 14695981039346656037ULL;
    std::cout << "clave \"" << key << "\"\n" << std::hex << std::setfill('0');
    std::cout << "  inicio        " << std::setw(16) << hash << "\n";
    for (char c : key) {
        hash ^= static_cast<unsigned char>(c);
        std::cout << "  xor  " << std::setw(2) << static_cast<int>(static_cast<unsigned char>(c))
                  << "       " << std::setw(16) << hash << "\n";
        hash *= 1099511628211ULL;
        std::cout << "  por el primo  " << std::setw(16) << hash << "\n";
    }
    std::cout << std::dec << std::setfill(' ');
}

int main() {
    trace("ab");
    trace("ba");
}

// Cuánto se reinserta en total si se duplica al superar α = 1, empezando con 8 casillas.
#include <cstddef>
#include <cstdio>
#include <initializer_list>

int main() {
    std::printf("%10s %10s %12s %12s\n", "n", "casillas", "reinsertadas", "por_insercion");
    for (std::size_t n : {1000u, 10000u, 100000u, 1000000u, 1048576u, 1048577u}) {
        std::size_t capacity = 8;
        std::size_t moved = 0;
        for (std::size_t size = 0; size < n; size++) {
            // Antes de insertar la clave número size + 1.
            if (size + 1 > capacity) {
                moved += size;
                capacity *= 2;
            }
        }
        std::printf("%10zu %10zu %12zu %12.2f\n", n, capacity, moved, static_cast<double>(moved) / static_cast<double>(n));
    }
}

// Cuánto se usa cada casilla con cada función hash, sin construir ninguna tabla.
// Uso: hash_compare archivo_de_palabras
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <set>
#include <string>
#include <vector>

#include "hash_functions.h"
#include "word_file.h"

void report(const char* name, const std::vector<std::string>& words, std::size_t m, HashFunction hash) {
    std::vector<std::size_t> lengths(m, 0);
    for (const std::string& word : words) {
        lengths[hash(word) % m]++;
    }
    std::size_t used = 0;
    std::size_t longest = 0;
    double comparisons = 0;
    for (std::size_t length : lengths) {
        used += length > 0 ? 1 : 0;
        longest = std::max(longest, length);
        // En una cadena de c claves, buscar cada una cuesta 1, 2, ..., c comparaciones.
        comparisons += static_cast<double>(length) * static_cast<double>(length + 1) / 2;
    }
    std::printf("%-6s %9zu %6.2f %9zu %9zu %11.1f\n", name, m, static_cast<double>(words.size()) / static_cast<double>(m),
                used, longest, comparisons / static_cast<double>(words.size()));
}

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: hash_compare archivo_de_palabras\n";
        return 1;
    }
    std::vector<std::string> words = read_words(argv[1]);
    std::set<std::uint64_t> sums;
    for (const std::string& word : words) {
        sums.insert(sum_hash(word));
    }
    std::printf("%zu palabras; la suma da %zu valores distintos, de %llu a %llu\n", words.size(), sums.size(),
                static_cast<unsigned long long>(*sums.begin()), static_cast<unsigned long long>(*sums.rbegin()));
    std::printf("%-6s %9s %6s %9s %9s %11s\n", "hash", "m", "alfa", "usadas", "la_mayor", "comp_acierto");
    for (std::size_t m : {1024u, 32768u, 1048576u}) {
        report("suma", words, m, sum_hash);
        report("fnv1a", words, m, fnv1a);
    }
}

// Las dos funciones hash sobre unas pocas palabras, y la casilla que le toca a cada una.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "hash_functions.h"

int main() {
    const std::vector<std::string> words = {"amor", "roma", "mora", "ramo", "ad", "bc", "lima", "cusco"};
    std::cout << "palabra  suma  suma%8  fnv1a             fnv1a%8\n";
    for (const std::string& word : words) {
        std::cout << std::left << std::setw(9) << word << std::setw(6) << sum_hash(word)
                  << std::setw(8) << sum_hash(word) % 8 << std::hex << std::setfill('0')
                  << std::right << std::setw(16) << fnv1a(word) << std::dec << std::setfill(' ')
                  << "  " << fnv1a(word) % 8 << "\n";
    }
}

// Dos funciones hash para cadenas: la que falla y la que usaremos.
#ifndef HASH_FUNCTIONS_H
#define HASH_FUNCTIONS_H

#include <cstdint>
#include <string>

// Puntero a una función hash: las tablas de esta carpeta la reciben al construirse.
using HashFunction = std::uint64_t (*)(const std::string&);

// Suma los bytes de la clave. Es determinista y rápida, y reparte muy mal.
inline std::uint64_t sum_hash(const std::string& key) {
    std::uint64_t hash = 0;
    for (char c : key) {
        hash += static_cast<unsigned char>(c);
    }
    return hash;
}

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

#endif

// std::unordered_map por dentro, hasta donde la interfaz deja mirar.
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

void print_order(const std::unordered_map<std::string, int>& table) {
    for (const auto& entry : table) {
        std::cout << " " << entry.first;
    }
    std::cout << "\n";
}

int main() {
    std::unordered_map<std::string, int> sizes;
    std::cout << "al inicio: bucket_count " << sizes.bucket_count() << ", max_load_factor "
              << sizes.max_load_factor() << "\n";
    std::cout << "crece en n =";
    std::size_t buckets = sizes.bucket_count();
    std::vector<std::size_t> history = {buckets};
    for (int i = 0; i < 2000; i++) {
        sizes["k" + std::to_string(i)] = i;
        if (sizes.bucket_count() != buckets) {
            buckets = sizes.bucket_count();
            std::cout << " " << sizes.size();
            history.push_back(buckets);
        }
    }
    std::cout << "\nbucket_count:";
    for (std::size_t value : history) {
        std::cout << " " << value;
    }
    std::cout << "\ncon n = " << sizes.size() << ": load_factor " << sizes.load_factor() << "\n";

    std::unordered_map<std::string, int> cities;
    for (const std::string city : {"lima", "cusco", "puno", "tacna", "ica", "piura"}) {
        cities[city] = static_cast<int>(city.size());
    }
    std::cout << "orden:";
    print_order(cities);
    cities.rehash(100);
    std::cout << "tras rehash(100), bucket_count " << cities.bucket_count() << ":";
    print_order(cities);

    std::cout << "contains(\"ica\") " << cities.contains("ica") << ", contains(\"nazca\") "
              << cities.contains("nazca") << ", size " << cities.size() << "\n";
    std::cout << "cities[\"nazca\"] " << cities["nazca"] << ", size " << cities.size() << "\n";
    std::cout << "hash(\"lima\") = " << std::hash<std::string>{}("lima") << "\n";
}

// Cuenta las comparaciones de una búsqueda con distintos factores de carga.
// Uso: load_experiment archivo_de_palabras
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "chain_table.h"
#include "word_file.h"

void measure(const std::vector<std::string>& words, std::size_t m, std::size_t n) {
    ChainTable<int> table(m, fnv1a);
    for (std::size_t i = 0; i < n; i++) {
        table.set(words[i], 1);
    }
    // Las n primeras están en la tabla. Las n siguientes, no.
    double hits = 0;
    double misses = 0;
    for (std::size_t i = 0; i < n; i++) {
        hits += static_cast<double>(table.comparisons_for(words[i]));
        misses += static_cast<double>(table.comparisons_for(words[n + i]));
    }
    double alpha = table.load_factor();
    double count = static_cast<double>(n);
    std::printf("%6zu %7zu %6.2f %9.2f %9.2f %9.2f %9.2f\n", m, n, alpha, hits / count, 1 + alpha / 2, misses / count, alpha);
}

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: load_experiment archivo_de_palabras\n";
        return 1;
    }
    std::vector<std::string> words = read_words(argv[1]);
    std::mt19937 rng(11);
    std::shuffle(words.begin(), words.end(), rng);
    std::printf("%6s %7s %6s %9s %9s %9s %9s\n", "m", "n", "alfa", "acierto", "1+alfa/2", "fallo", "alfa");
    measure(words, 100, 300);
    for (std::size_t n : {512u, 1024u, 2048u, 3072u, 5120u, 10240u, 102400u}) {
        measure(words, 1024, n);
    }
}

// Arreglo ordenado con búsqueda binaria contra std::unordered_map, sobre el mismo diccionario.
// Uso: lookup_bench archivo_de_palabras_ordenado
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <new>
#include <random>
#include <string>
#include <unordered_map>
#include <vector>

#include "bench.h"
#include "word_file.h"

namespace {
std::size_t live_bytes = 0;
// Cada bloque guarda su tamaño al inicio, para restarlo al liberarlo.
const std::size_t HEADER = 16;
}

// Cuenta los bytes reservados y todavía sin liberar, para comparar lo que ocupa cada estructura.
void* operator new(std::size_t size) {
    void* block = std::malloc(size + HEADER);
    if (block == nullptr) {
        throw std::bad_alloc();
    }
    *static_cast<std::size_t*>(block) = size;
    live_bytes += size;
    return static_cast<char*>(block) + HEADER;
}

void operator delete(void* pointer) noexcept {
    if (pointer != nullptr) {
        void* block = static_cast<char*>(pointer) - HEADER;
        live_bytes -= *static_cast<std::size_t*>(block);
        std::free(block);
    }
}

void operator delete(void* pointer, std::size_t) noexcept {
    operator delete(pointer);
}

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: lookup_bench archivo_de_palabras_ordenado\n";
        return 1;
    }
    std::size_t before = live_bytes;
    const std::vector<std::string> words = read_words(argv[1]);
    std::size_t vector_bytes = live_bytes - before;
    if (!std::is_sorted(words.begin(), words.end())) {
        std::cerr << "el archivo debe estar ordenado por bytes\n";
        return 1;
    }

    before = live_bytes;
    std::unordered_map<std::string, int> table;
    double build_seconds = median_seconds(1, [&] {
        for (std::size_t i = 0; i < words.size(); i++) {
            table[words[i]] = static_cast<int>(i);
        }
    });
    std::size_t table_bytes = live_bytes - before;

    // Mismas consultas para las dos, en un orden que no favorece a ninguna.
    std::mt19937 rng(5);
    std::uniform_int_distribution<std::size_t> pick(0, words.size() - 1);
    std::vector<std::string> queries;
    for (int i = 0; i < 200000; i++) {
        queries.push_back(words[pick(rng)]);
    }

    double sorted_seconds = median_seconds(5, [&] {
        std::size_t hits = 0;
        for (const std::string& query : queries) {
            auto it = std::lower_bound(words.begin(), words.end(), query);
            hits += (it != words.end() && *it == query) ? 1 : 0;
        }
        keep(hits);
    });
    double table_seconds = median_seconds(5, [&] {
        std::size_t hits = 0;
        for (const std::string& query : queries) {
            hits += table.contains(query) ? 1 : 0;
        }
        keep(hits);
    });

    std::size_t comparisons = 0;
    for (const std::string& query : queries) {
        auto it = std::lower_bound(words.begin(), words.end(), query, [&](const std::string& a, const std::string& b) {
            comparisons++;
            return a < b;
        });
        keep(it == words.end());
    }
    double chain_cost = 0;
    for (std::size_t b = 0; b < table.bucket_count(); b++) {
        double length = static_cast<double>(table.bucket_size(b));
        chain_cost += length * (length + 1) / 2;
    }

    double count = static_cast<double>(queries.size());
    std::printf("%zu palabras, %zu consultas\n", words.size(), queries.size());
    std::printf("%-22s %12s %16s %10s\n", "", "ns/consulta", "comparaciones", "MB");
    std::printf("%-22s %12.0f %16.1f %10.1f\n", "arreglo ordenado", sorted_seconds * 1e9 / count,
                static_cast<double>(comparisons) / count, static_cast<double>(vector_bytes) / 1e6);
    std::printf("%-22s %12.0f %16.1f %10.1f\n", "std::unordered_map", table_seconds * 1e9 / count,
                chain_cost / static_cast<double>(words.size()), static_cast<double>(table_bytes) / 1e6);
    std::printf("construir la tabla: %.0f ms\n", build_seconds * 1000);

    // Lo que la tabla no sabe hacer: un rango de claves.
    auto first = std::lower_bound(words.begin(), words.end(), std::string("cas"));
    auto last = std::lower_bound(words.begin(), words.end(), std::string("cat"));
    std::printf("empiezan con cas: %td, de %s a %s\n", last - first, first->c_str(), (last - 1)->c_str());
    std::size_t scanned = 0;
    for (const auto& entry : table) {
        scanned += entry.first.starts_with("cas") ? 1 : 0;
    }
    std::printf("la tabla debe revisar %zu claves para hallar las mismas %zu\n", table.size(), scanned);

    // El orden es por bytes: las palabras con tilde inicial quedan después de la z.
    auto a_accent = std::lower_bound(words.begin(), words.end(), std::string("á"));
    auto b_start = std::lower_bound(words.begin(), words.end(), std::string("b"));
    std::printf("antes de la primera b: %s; ultima antes de la primera con a acentuada: %s; primera: %s\n",
                (b_start - 1)->c_str(), (a_accent - 1)->c_str(), a_accent->c_str());
}

// Crecer copiando las casillas, sin reinsertar: las claves siguen ahí, y ya no se encuentran.
// Uso: naive_copy archivo_de_palabras
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

#include "hash_functions.h"
#include "word_file.h"

using Slots = std::vector<std::vector<std::string>>;

bool found(const Slots& slots, const std::string& word) {
    const std::vector<std::string>& chain = slots[fnv1a(word) % slots.size()];
    return std::find(chain.begin(), chain.end(), word) != chain.end();
}

std::size_t count_found(const Slots& slots, const std::vector<std::string>& words) {
    std::size_t count = 0;
    for (const std::string& word : words) {
        count += found(slots, word) ? 1 : 0;
    }
    return count;
}

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: naive_copy archivo_de_palabras\n";
        return 1;
    }
    std::vector<std::string> words = read_words(argv[1]);
    for (const std::string word : {"lima", "cusco", "tacna", "puno", "arequipa"}) {
        std::uint64_t hash = fnv1a(word);
        std::cout << word << ": hash % 8 = " << hash % 8 << ", hash % 16 = " << hash % 16 << "\n";
    }
    Slots slots(1024);
    for (const std::string& word : words) {
        slots[fnv1a(word) % slots.size()].push_back(word);
    }
    std::cout << "con 1024 casillas: " << count_found(slots, words) << " de " << words.size() << " encontradas\n";
    Slots copied = slots;
    copied.resize(2048);
    std::cout << "copiando a 2048:   " << count_found(copied, words) << " de " << words.size() << " encontradas\n";
    Slots reinserted(2048);
    for (const std::string& word : words) {
        reinserted[fnv1a(word) % reinserted.size()].push_back(word);
    }
    std::cout << "reinsertando:      " << count_found(reinserted, words) << " de " << words.size() << " encontradas\n";
}

// Tipo para las pruebas: cuenta cuántos objetos viven y cuántas copias y movimientos hubo.
#ifndef TRACKED_H
#define TRACKED_H

#include <utility>

class Tracked {
public:
    struct Counts {
        long live = 0;
        long copies = 0;
        long moves = 0;
    };

    static Counts& counts() {
        static Counts values;
        return values;
    }

    Tracked() { counts().live++; }
    explicit Tracked(int value) : value_(value) { counts().live++; }
    Tracked(const Tracked& other) : value_(other.value_) {
        counts().live++;
        counts().copies++;
    }
    Tracked(Tracked&& other) noexcept : value_(std::exchange(other.value_, 0)) {
        counts().live++;
        counts().moves++;
    }
    Tracked& operator=(const Tracked& other) {
        value_ = other.value_;
        counts().copies++;
        return *this;
    }
    Tracked& operator=(Tracked&& other) noexcept {
        value_ = std::exchange(other.value_, 0);
        counts().moves++;
        return *this;
    }
    ~Tracked() { counts().live--; }

    int value() const { return value_; }
    bool operator==(const Tracked& other) const { return value_ == other.value_; }

private:
    int value_ = 0;
};

#endif

// Lee una lista de palabras. Si una línea trae un tabulador, como en terminos.tsv
// (frecuencia<TAB>término), la palabra es lo que viene después.
#ifndef WORD_FILE_H
#define WORD_FILE_H

#include <cstdlib>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

inline std::vector<std::string> read_words(const std::string& path) {
    std::ifstream file(path);
    if (!file) {
        std::cerr << "no se pudo abrir " << path << "\n";
        std::exit(1);
    }
    std::vector<std::string> words;
    std::string line;
    while (std::getline(file, line)) {
        std::size_t tab = line.find('\t');
        words.push_back(tab == std::string::npos ? line : line.substr(tab + 1));
    }
    return words;
}

#endif

// Error a propósito: no compila. En std::unordered_map la clave es const.
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> table;
    table["lima"] = 10;
    for (auto& entry : table) {
        entry.first = "cusco";
    }
}

// Error a propósito: calcular la casilla en una tabla sin casillas, como la que queda después de mover.
#include <cstddef>
#include <iostream>
#include <string>

#include "../hash_functions.h"

int main() {
    std::size_t capacity = 0;
    std::cout << "casilla: " << fnv1a("lima") % capacity << "\n";
}

// Error a propósito: se cambia una clave que ya está en la tabla.
// La tabla sigue teniendo el dato, pero en una casilla que ya no le corresponde.
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>

#include "../hash_functions.h"

class LeakyTable {
public:
    void set(const std::string& key, int value) {
        slots_[fnv1a(key) % slots_.size()].push_back(Entry{key, value});
    }
    const int* get(const std::string& key) const {
        for (const Entry& entry : slots_[fnv1a(key) % slots_.size()]) {
            if (entry.key == key) {
                return &entry.value;
            }
        }
        return nullptr;
    }
    // El error de diseño: entrega la clave sin const.
    std::string* key_of(const std::string& key) {
        for (Entry& entry : slots_[fnv1a(key) % slots_.size()]) {
            if (entry.key == key) {
                return &entry.key;
            }
        }
        return nullptr;
    }
    std::size_t size() const {
        std::size_t total = 0;
        for (const std::vector<Entry>& slot : slots_) {
            total += slot.size();
        }
        return total;
    }
    bool check_invariants() const {
        for (std::size_t i = 0; i < slots_.size(); i++) {
            for (const Entry& entry : slots_[i]) {
                if (fnv1a(entry.key) % slots_.size() != i) {
                    return false;
                }
            }
        }
        return true;
    }

private:
    struct Entry {
        std::string key;
        int value;
    };
    std::vector<std::vector<Entry>> slots_ = std::vector<std::vector<Entry>>(8);
};

int main() {
    LeakyTable table;
    table.set("lima", 10);
    std::cout << "invariantes: " << table.check_invariants() << "\n";
    *table.key_of("lima") = "cusco";
    std::cout << "size: " << table.size() << "\n";
    std::cout << "get(\"lima\"): " << (table.get("lima") == nullptr ? "no está" : "está") << "\n";
    std::cout << "get(\"cusco\"): " << (table.get("cusco") == nullptr ? "no está" : "está") << "\n";
    std::cout << "invariantes: " << table.check_invariants() << "\n";
}

// Error a propósito: sumar los char sin convertirlos a unsigned char.
// Compilen con -funsigned-char y con -fsigned-char: según la plataforma, char tiene signo o no.
#include <cstdint>
#include <iostream>
#include <string>

std::uint64_t bad_sum(const std::string& key) {
    std::uint64_t hash = 0;
    for (char c : key) {
        hash += c;
    }
    return hash;
}

int main() {
    std::cout << "bad_sum(\"lima\") = " << bad_sum("lima") << "\n";
    std::cout << "bad_sum(\"ñandú\") = " << bad_sum("ñandú") << "\n";
}

"""Corre los ejemplos de la semana y comprueba lo que se puede contar: nunca tiempos absolutos."""
import os
import pathlib
import subprocess
import unittest

HERE = pathlib.Path(__file__).parent
DATA = os.environ.get("DATA", "../../data")
SAN = ["g++", "-Wall", "-Wextra", "-std=c++20", "-g", "-fsanitize=address,undefined"]


def run(*command):
    return subprocess.run(
        list(command), cwd=HERE, text=True, encoding="utf-8", stdin=subprocess.DEVNULL,
        stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=120,
    )


class Examples(unittest.TestCase):
    def test_structures_pass(self):
        done = run("build/test_structures")
        self.assertEqual(done.returncode, 0, done.stdout)

    def test_hashes_with_signed_char(self):
        """El mismo resultado aunque char tenga signo, como en x86-64."""
        done = run(*SAN, "-fsigned-char", "test_structures.cpp", "-o", "build/test_structures_signed")
        self.assertEqual(done.returncode, 0, done.stdout)
        done = run("build/test_structures_signed")
        self.assertEqual(done.returncode, 0, done.stdout)

    def test_sum_hash_uses_few_values(self):
        lines = run("build/hash_compare", f"{DATA}/terminos.tsv").stdout.splitlines()
        rows = [line.split() for line in lines[2:]]
        by_m = {}
        for row in rows:
            by_m.setdefault(row[1], {})[row[0]] = row
        # Más casillas no ayudan a la suma: se queda con los mismos valores.
        self.assertEqual(by_m["32768"]["suma"][3], by_m["1048576"]["suma"][3])
        self.assertGreater(int(by_m["1048576"]["suma"][4]), 20 * int(by_m["1048576"]["fnv1a"][4]))

    def test_load_experiment_follows_the_formula(self):
        rows = [line.split() for line in run("build/load_experiment", f"{DATA}/palabras.txt").stdout.splitlines()[1:]]
        self.assertEqual(rows[0][:3], ["100", "300", "3.00"])
        for row in rows:
            alpha, hit, hit_formula, miss = float(row[2]), float(row[3]), float(row[4]), float(row[5])
            with self.subTest(alpha=alpha):
                self.assertLess(abs(hit - hit_formula), 0.25 + 0.05 * alpha)
                self.assertLess(abs(miss - alpha), 0.25 + 0.1 * alpha)

    def test_naive_copy_loses_about_half(self):
        lines = run("build/naive_copy", f"{DATA}/terminos.tsv").stdout.splitlines()
        counts = [line.split(":")[1].split() for line in lines if "encontradas" in line]
        total = int(counts[0][2])
        self.assertEqual(int(counts[0][0]), total)
        self.assertEqual(int(counts[2][0]), total)
        self.assertLess(abs(int(counts[1][0]) / total - 0.5), 0.05)

    def test_flood_puts_every_key_in_one_slot(self):
        lines = run("build/flood").stdout.splitlines()
        self.assertTrue(any("elegidas" in line and "m=4096" in line and "cadena  4000" in line for line in lines))
        self.assertTrue(any("elegidas" in line and "m=8192" in line and "cadena  4000" in line for line in lines))
        self.assertTrue(any("elegidas" in line and "tiene  4000" in line for line in lines))

    def test_hash_is_stable_within_this_library(self):
        lines = [run("build/library_demo").stdout.splitlines()[-1] for _ in range(2)]
        self.assertEqual(lines[0], lines[1])

    def test_programs_exit_cleanly(self):
        for name in ["hash_demo", "fnv_trace", "chain_trace", "growth_count", "library_demo"]:
            with self.subTest(program=name):
                self.assertEqual(run(f"build/{name}").returncode, 0)


class DeliberateErrors(unittest.TestCase):
    def test_mutated_key(self):
        run(*SAN, "errors/mutated_key.cpp", "-o", "build/mutated_key")
        done = run("build/mutated_key")
        self.assertEqual(done.returncode, 0, done.stdout)
        self.assertIn('get("lima"): no está', done.stdout)
        self.assertIn("invariantes: 0", done.stdout)

    def test_modulo_zero(self):
        run(*SAN, "errors/modulo_zero.cpp", "-o", "build/modulo_zero")
        done = run("build/modulo_zero")
        self.assertIn("division by zero", done.stdout)

    def test_const_key_does_not_compile(self):
        done = run("g++", "-std=c++20", "-c", "errors/const_key.cpp", "-o", "build/const_key.o")
        self.assertNotEqual(done.returncode, 0)
        self.assertIn("no match for 'operator='", done.stdout.replace("‘", "'").replace("’", "'"))


if __name__ == "__main__":
    unittest.main()