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