// Sesión 1: mide sus ordenamientos, en comparaciones y en tiempo. Con -O2, sin sanitizers y
// con mediana de 5. Los tiempos dependen de la máquina; las comparaciones, casi no.
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <random>
#include <vector>

#include "bench.h"
#include "fixed_pivot.h"
#include "sorts.h"

namespace {

const int REPS = 5;

std::vector<int> random_values(std::size_t n, unsigned range) {
    std::mt19937 rng(2026);
    std::vector<int> items(n);
    for (int& value : items) {
        value = static_cast<int>(rng() % range);
    }
    return items;
}

std::vector<int> sorted_values(std::size_t n) {
    std::vector<int> items(n);
    for (std::size_t i = 0; i < n; i++) {
        items[i] = static_cast<int>(i);
    }
    return items;
}

template <typename Sort>
void cell(const std::vector<int>& input, Sort sort) {
    long long comparisons = 0;
    auto counting = [&comparisons](int a, int b) {
        comparisons++;
        return a < b;
    };
    std::vector<int> once = input;
    sort(once, counting);
    std::vector<std::vector<int>> copies(REPS, input);
    int rep = 0;
    double seconds = median_seconds(REPS, [&] {
        sort(copies[static_cast<std::size_t>(rep)], [](int a, int b) { return a < b; });
        keep(copies[static_cast<std::size_t>(rep)][0]);
        rep++;
    });
    std::printf(" %11lld %8.2f", comparisons, seconds * 1000);
}

void row(const char* name, std::size_t n, const std::vector<int>& input, bool with_first) {
    std::printf("%-10s %7zu", name, n);
    cell(input, [](std::vector<int>& v, auto less) { merge_sort(v, less); });
    cell(input, [](std::vector<int>& v, auto less) { quick_sort(v, less); });
    if (with_first) {
        cell(input, [](std::vector<int>& v, auto less) { quick_sort_first(v, less); });
    }
    std::printf("\n");
}

}  // namespace

int main() {
    std::printf("%-10s %7s %11s %8s %11s %8s %11s %8s\n", "entrada", "n", "merge cmp", "ms", "quick cmp", "ms",
                "primero cmp", "ms");
    // Con el pivote fijo, la entrada lenta se queda en n chicos: la recursión tiene n niveles.
    for (std::size_t n : {4000, 8000, 16000}) {
        row("al azar", n, random_values(n, 1000000000), true);
        row("ordenada", n, sorted_values(n), true);
        row("3 valores", n, random_values(n, 3), true);
        row("su entrada", n, slow_input(n), true);
    }
    for (std::size_t n : {250000, 500000, 1000000}) {
        row("al azar", n, random_values(n, 1000000000), false);
        row("ordenada", n, sorted_values(n), false);
        row("3 valores", n, random_values(n, 3), false);
    }
    return 0;
}