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