// Θ(U + n) contra Θ(n²), con valores distintos: con n pequeño, gana el cuadrático.
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <initializer_list>
#include <numeric>
#include <random>
#include <vector>

#include "bench.h"

// Los valores están entre 0 y TABLE_SIZE - 1.
constexpr std::size_t TABLE_SIZE = 1 << 20;

// Con valores distintos, Θ(n²): compara cada par.
bool has_duplicate_pairs(const std::vector<int>& values) {
    for (std::size_t i = 0; i < values.size(); i++) {
        for (std::size_t j = i + 1; j < values.size(); j++) {
            if (values[i] == values[j]) {
                return true;
            }
        }
    }
    return false;
}

// Θ(TABLE_SIZE + n): una pasada, y siempre limpia una tabla de TABLE_SIZE casillas.
bool has_duplicate_table(const std::vector<int>& values) {
    std::vector<char> seen(TABLE_SIZE, 0);
    for (int value : values) {
        std::size_t position = static_cast<std::size_t>(value);
        if (seen[position] != 0) {
            return true;
        }
        seen[position] = 1;
    }
    return false;
}

int main() {
    std::vector<int> all(TABLE_SIZE);
    std::iota(all.begin(), all.end(), 0);
    std::mt19937 generator(2026);
    std::shuffle(all.begin(), all.end(), generator);

    std::printf("%8s %14s %14s %12s\n", "n", "pares (us)", "tabla (us)", "pares/tabla");
    for (std::size_t n : {10u, 100u, 1000u, 4000u, 16000u, 32000u}) {
        // Valores distintos, posibles porque n <= TABLE_SIZE: el peor caso de las dos.
        std::vector<int> values(all.begin(), all.begin() + static_cast<std::ptrdiff_t>(n));
        int reps = n <= 4000 ? 15 : 3;
        double pairs = median_seconds(reps, [&] { keep(has_duplicate_pairs(values)); });
        double table = median_seconds(reps, [&] { keep(has_duplicate_table(values)); });
        std::printf("%8zu %14.2f %14.2f %12.3f\n", n, pairs * 1e6, table * 1e6, pairs / table);
    }
    return 0;
}