// Mide las dos representaciones del deque con el mismo código.
// Se compila con -O2 y sin sanitizers. Los tiempos dependen de la máquina.
#include <cstddef>
#include <cstdio>
#include <vector>

#include "alloc_counter.h"
#include "array_deque.h"
#include "bench.h"
#include "linked_deque.h"

namespace {

const int REPS = 5;
const std::size_t MIN_VISITS = 2000000;
const unsigned SEED = 2026;

struct Row {
    double ends_ns;
    double sum_ns;
    double sum_shuffled_ns;
    std::size_t allocations;
};

double per_element(double seconds, std::size_t count) {
    return seconds * 1e9 / static_cast<double>(count);
}

// Insertar n por detrás y por delante, y sacarlos: nanosegundos por operación.
template <typename D>
double measure_ends(std::size_t n) {
    double seconds = median_seconds(REPS, [&] {
        D deque;
        for (std::size_t i = 0; i < n; i++) {
            deque.push_back(static_cast<int>(i));
            deque.push_front(static_cast<int>(i));
        }
        for (std::size_t i = 0; i < n; i++) {
            keep(deque.front());
            deque.pop_front();
            keep(deque.back());
            deque.pop_back();
        }
    });
    return per_element(seconds, 4 * n);
}

template <typename D>
double measure_sum(const D& deque) {
    std::size_t n = deque.size();
    std::size_t passes = MIN_VISITS / n > 0 ? MIN_VISITS / n : 1;
    double seconds = median_seconds(REPS, [&] {
        for (std::size_t pass = 0; pass < passes; pass++) {
            long long sum = 0;
            for (int value : deque) {
                sum += value;
            }
            keep(sum);
        }
    });
    return per_element(seconds, passes * n);
}

template <typename D>
D filled(std::size_t n) {
    D deque;
    for (std::size_t i = 0; i < n; i++) {
        deque.push_back(static_cast<int>(i));
    }
    return deque;
}

template <typename D>
std::size_t count_allocations(std::size_t n) {
    std::size_t before = allocation_count();
    D deque = filled<D>(n);
    return allocation_count() - before;
}

}  // namespace

int main() {
    std::printf("Tiempos en ns: por operación en los extremos, por elemento al recorrer.\n");
    std::printf("%8s | %8s %8s %9s | %8s %8s %9s %9s\n", "n", "arr.ext", "arr.rec", "arr.res",
                "lis.ext", "lis.rec", "lis.baraj", "lis.res");
    for (std::size_t n = 4096; n <= 4194304; n *= 16) {
        using Array = ArrayDeque<int>;
        using Linked = LinkedDeque<int>;

        Array array_deque = filled<Array>(n);
        double array_sum = measure_sum(array_deque);
        double array_ends = measure_ends<Array>(n);

        double linked_ends = measure_ends<Linked>(n);
        Linked linked_deque = filled<Linked>(n);
        double linked_sum = measure_sum(linked_deque);
        linked_deque.shuffle_nodes(SEED);
        double linked_shuffled = measure_sum(linked_deque);

        std::printf("%8zu | %8.2f %8.2f %9zu | %8.2f %8.2f %9.2f %9zu\n", n, array_ends, array_sum,
                    count_allocations<Array>(n), linked_ends, linked_sum, linked_shuffled,
                    count_allocations<Linked>(n));
    }
    return 0;
}