// El mismo recorrido Θ(n), en dos órdenes: lo que O no ve.
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <numeric>
#include <random>
#include <utility>
#include <vector>

#include "bench.h"

// Sigue la cadena next[position] durante next.size() saltos.
std::uint32_t walk(const std::vector<std::uint32_t>& next) {
    std::uint32_t position = 0;
    for (std::size_t i = 0; i < next.size(); i++) {
        position = next[position];
    }
    return position;
}

// Un solo ciclo que pasa por todos, de i a i + 1.
std::vector<std::uint32_t> ordered_cycle(std::size_t n) {
    std::vector<std::uint32_t> next(n);
    for (std::size_t i = 0; i < n; i++) {
        next[i] = static_cast<std::uint32_t>((i + 1) % n);
    }
    return next;
}

// Un solo ciclo que pasa por todos, en un orden al azar.
std::vector<std::uint32_t> random_cycle(std::size_t n) {
    std::vector<std::uint32_t> order(n);
    std::iota(order.begin(), order.end(), 0);
    std::mt19937 generator(2026);
    for (std::size_t i = n - 1; i > 0; i--) {
        std::uniform_int_distribution<std::size_t> pick(0, i - 1);
        std::swap(order[i], order[pick(generator)]);
    }
    std::vector<std::uint32_t> next(n);
    for (std::size_t i = 0; i < n; i++) {
        next[order[i]] = order[(i + 1) % n];
    }
    return next;
}

int main() {
    std::printf("%10s %8s %12s %12s %7s\n", "n", "KiB", "ordenado", "al azar", "razon");
    for (std::size_t n : {1u << 12, 1u << 16, 1u << 20, 1u << 22}) {
        std::vector<std::uint32_t> ordered = ordered_cycle(n);
        std::vector<std::uint32_t> shuffled = random_cycle(n);
        double ordered_time = median_seconds(5, [&] { keep(walk(ordered)); });
        double shuffled_time = median_seconds(5, [&] { keep(walk(shuffled)); });
        double count = static_cast<double>(n);
        std::printf("%10zu %8zu %9.2f ns %9.2f ns %7.1f\n", n, n * sizeof(std::uint32_t) / 1024,
                    ordered_time / count * 1e9, shuffled_time / count * 1e9,
                    shuffled_time / ordered_time);
    }
    return 0;
}