// Mide quicksort: los conteos son exactos y salen iguales con la misma semilla.
// Los tiempos dependen de la máquina. Compilado con -O2.
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "quicksort.h"

using Sorter = void (*)(std::vector<int>&, int, int, Pivot, std::mt19937&, QuickStats&, int);

std::vector<int> make_input(const std::string& kind, int n, std::mt19937& rng) {
    std::vector<int> a(static_cast<std::size_t>(n));
    if (kind == "iguales") return a;
    std::iota(a.begin(), a.end(), 0);
    if (kind == "al azar") {
        for (std::size_t i = a.size(); i > 1; i--) std::swap(a[i - 1], a[rng() % i]);
    }
    return a;
}

void row(const std::string& name, Sorter sorter, Pivot rule, const std::string& kind, int n) {
    std::mt19937 rng(2026);
    std::vector<int> a = make_input(kind, n, rng);
    QuickStats stats;
    const auto begin = std::chrono::steady_clock::now();
    sorter(a, 0, n, rule, rng, stats, 1);
    const std::chrono::duration<double, std::milli> ms = std::chrono::steady_clock::now() - begin;
    if (!std::is_sorted(a.begin(), a.end())) std::cout << "NO QUEDO ORDENADO\n";
    std::cout << std::left << std::setw(18) << name << std::setw(10) << kind << std::right
              << std::setw(7) << n << std::setw(12) << stats.comparisons << std::setw(8)
              << stats.max_depth << std::setw(8) << std::setprecision(2) << std::fixed
              << static_cast<double>(stats.comparisons) / (n * std::log2(n)) << std::setw(10)
              << std::setprecision(1) << ms.count() << '\n';
}

int main() {
    std::cout << "pivote y partición  entrada       n  comparac.  niveles  c/nlogn      ms\n";
    Sorter two = quicksort_two_way;
    Sorter three = quicksort_three_way;
    for (int n : {4000, 16000, 64000}) {
        row("primero, en dos", two, Pivot::First, "ordenada", n);
        row("primero, en dos", two, Pivot::First, "al azar", n);
        row("azar, en dos", two, Pivot::Random, "ordenada", n);
        row("azar, en dos", two, Pivot::Random, "al azar", n);
        row("azar, en dos", two, Pivot::Random, "iguales", n);
        row("azar, en tres", three, Pivot::Random, "iguales", n);
        row("azar, en tres", three, Pivot::Random, "ordenada", n);
        std::cout << '\n';
    }

    // La misma entrada ordenada, con 1000 semillas: lo único que cambia es el azar.
    const int n = 64000;
    long long min_c = -1;
    long long max_c = 0;
    long long sum_c = 0;
    int min_d = n;
    int max_d = 0;
    long long sum_d = 0;
    long long calls = 0;
    long long good = 0;
    const int seeds = 1000;
    for (int seed = 1; seed <= seeds; seed++) {
        std::mt19937 rng(static_cast<unsigned>(seed));
        std::vector<int> a = make_input("ordenada", n, rng);
        QuickStats stats;
        quicksort_two_way(a, 0, n, Pivot::Random, rng, stats, 1);
        min_c = min_c < 0 ? stats.comparisons : std::min(min_c, stats.comparisons);
        max_c = std::max(max_c, stats.comparisons);
        sum_c += stats.comparisons;
        min_d = std::min(min_d, stats.max_depth);
        max_d = std::max(max_d, stats.max_depth);
        sum_d += stats.max_depth;
        calls += stats.large_calls;
        good += stats.good_pivots;
    }
    std::cout << "entrada ordenada, n = " << n << ", " << seeds << " semillas\n";
    std::cout << "comparaciones: mínimo " << min_c << ", promedio " << sum_c / seeds << ", máximo " << max_c << '\n';
    std::cout << "niveles:       mínimo " << min_d << ", promedio " << sum_d / seeds << ", máximo " << max_d << '\n';
    std::cout << "pivotes buenos, en llamadas de 16 o más elementos: " << std::setprecision(1)
              << 100.0 * static_cast<double>(good) / static_cast<double>(calls) << " %\n";
}