// El experimento de duplicar con tres cálculos sobre un arreglo.
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <random>
#include <vector>

#include "bench.h"

long long sum_values(const std::vector<int>& values) {
    long long total = 0;
    for (int value : values) {
        total += value;
    }
    return total;
}

// Pares (i, j) con i < j y values[i] > values[j].
long long count_inversions(const std::vector<int>& values) {
    long long count = 0;
    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]) {
                count++;
            }
        }
    }
    return count;
}

// Cuántas veces repetir fn para que la tanda completa dure al menos 2 ms.
template <typename Fn>
long long batch_size(Fn fn) {
    long long batch = 1;
    while (true) {
        double seconds = median_seconds(1, [&] {
            for (long long i = 0; i < batch; i++) {
                fn();
            }
        });
        if (seconds >= 0.002) {
            return batch;
        }
        batch *= 2;
    }
}

// Tiempo de una llamada a fn: mediana de 7 tandas, entre el tamaño de la tanda.
template <typename Fn>
double seconds_per_call(Fn fn) {
    long long batch = batch_size(fn);
    double seconds = median_seconds(7, [&] {
        for (long long i = 0; i < batch; i++) {
            fn();
        }
    });
    return seconds / static_cast<double>(batch);
}

std::vector<int> random_values(std::size_t n, std::mt19937& generator) {
    std::vector<int> values(n);
    for (int& value : values) {
        value = static_cast<int>(generator());
    }
    return values;
}

// Ordena 15 arreglos distintos, cada uno una sola vez: ordenar otra vez el mismo no sirve.
double sort_seconds(std::size_t n, std::mt19937& generator) {
    std::vector<std::vector<int>> arrays;
    for (int i = 0; i < 15; i++) {
        arrays.push_back(random_values(n, generator));
    }
    std::size_t next = 0;
    return median_seconds(15, [&] {
        std::sort(arrays[next].begin(), arrays[next].end());
        keep(arrays[next]);
        next++;
    });
}

void print_header(const char* title) {
    std::printf("%s\n", title);
    std::printf("%10s %12s %7s %9s\n", "n", "T(n) en us", "razon", "T/n (ns)");
}

void print_row(std::size_t n, double seconds, double previous) {
    double per_item = seconds * 1e9 / static_cast<double>(n);
    if (previous == 0) {
        std::printf("%10zu %12.2f %7s %9.2f\n", n, seconds * 1e6, "-", per_item);
    } else {
        std::printf("%10zu %12.2f %7.2f %9.2f\n", n, seconds * 1e6, seconds / previous, per_item);
    }
}

int main() {
    std::mt19937 generator(2026);

    print_header("suma");
    double previous = 0;
    for (std::size_t n = 8000; n <= 256000; n *= 2) {
        std::vector<int> values = random_values(n, generator);
        double seconds = seconds_per_call([&] { keep(sum_values(values)); });
        print_row(n, seconds, previous);
        previous = seconds;
    }

    print_header("\nstd::sort");
    previous = 0;
    for (std::size_t n = 8000; n <= 256000; n *= 2) {
        double seconds = sort_seconds(n, generator);
        print_row(n, seconds, previous);
        previous = seconds;
    }

    print_header("\ninversiones");
    previous = 0;
    for (std::size_t n = 1000; n <= 16000; n *= 2) {
        std::vector<int> values = random_values(n, generator);
        double seconds = seconds_per_call([&] { keep(count_inversions(values)); });
        print_row(n, seconds, previous);
        previous = seconds;
    }
    return 0;
}