// Recorre n enteros sumándolos, con cuatro formas de guardarlos o de visitarlos.
// Compilar con -O2 y sin sanitizers. Los tiempos dependen de la máquina.
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <numeric>
#include <random>
#include <vector>

#include "bench.h"
#include "dlist.h"

namespace {

const int REPS = 5;
// Cada medición toca al menos esta cantidad de elementos, para que dure lo suficiente.
const std::size_t MIN_VISITS = 2000000;
const unsigned SEED = 2026;

template <typename Walk>
double nanos_per_element(std::size_t n, Walk walk) {
    std::size_t passes = std::max<std::size_t>(1, MIN_VISITS / n);
    double seconds = median_seconds(REPS, [&] {
        for (std::size_t pass = 0; pass < passes; pass++) {
            walk();
        }
    });
    return seconds * 1e9 / static_cast<double>(passes * n);
}

// Porcentaje de saltos entre elementos seguidos que avanzan exactamente `gap` bytes.
double percent_adjacent(const DList<int>& list, std::ptrdiff_t gap) {
    std::size_t hits = 0;
    std::size_t hops = 0;
    const int* previous = nullptr;
    for (const int& value : list) {
        if (previous != nullptr) {
            auto jump = reinterpret_cast<std::intptr_t>(&value) - reinterpret_cast<std::intptr_t>(previous);
            hits += jump == gap ? 1 : 0;
            hops++;
        }
        previous = &value;
    }
    return 100.0 * static_cast<double>(hits) / static_cast<double>(hops);
}

void measure(std::size_t n) {
    std::vector<int> values(n);
    std::iota(values.begin(), values.end(), 0);

    std::vector<std::size_t> order(n);
    std::iota(order.begin(), order.end(), std::size_t{0});
    std::mt19937 rng(SEED);
    std::shuffle(order.begin(), order.end(), rng);

    DList<int> list;
    for (std::size_t i = 0; i < n; i++) {
        list.push_back(values[i]);
    }

    long long expected = 0;
    for (int value : values) {
        expected += value;
    }

    auto sum_array = [&] {
        long long sum = 0;
        for (int value : values) {
            sum += value;
        }
        keep(sum);
    };
    auto sum_array_shuffled = [&] {
        long long sum = 0;
        for (std::size_t i : order) {
            sum += values[i];
        }
        keep(sum);
    };
    auto sum_list = [&] {
        long long sum = 0;
        for (int value : list) {
            sum += value;
        }
        keep(sum);
    };

    double array_ns = nanos_per_element(n, sum_array);
    double array_shuffled_ns = nanos_per_element(n, sum_array_shuffled);
    double list_ns = nanos_per_element(n, sum_list);
    double adjacent = percent_adjacent(list, 32);

    list.shuffle_nodes(SEED);
    list.check_invariants();
    double list_shuffled_ns = nanos_per_element(n, sum_list);
    double adjacent_shuffled = percent_adjacent(list, 32);

    long long check = 0;
    for (int value : list) {
        check += value;
    }

    std::printf("%8zu %8.2f %9.2f %8.2f %9.2f %8.1f %9.1f %7.1f%% %7.1f%% %s\n",
                n, array_ns, array_shuffled_ns, list_ns, list_shuffled_ns,
                list_ns / array_ns, list_shuffled_ns / list_ns,
                adjacent, adjacent_shuffled, check == expected ? "ok" : "MAL");
}

}  // namespace

int main() {
    std::printf("%8s %8s %9s %8s %9s %8s %9s %8s %8s\n",
                "n", "arreglo", "arr.baraj", "lista", "lis.baraj",
                "lis/arr", "lb/lista", "cont", "cont.b");
    for (std::size_t n = 1024; n <= 4194304; n *= 4) {
        measure(n);
    }
    return 0;
}