// Medidor pequeño para las semanas que comparan tiempos.
// Compilar las mediciones con -O2 y sin sanitizers.
#ifndef BENCH_H
#define BENCH_H

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstddef>
#include <vector>

// Mediana de una lista de números. Con cantidad par, promedia los dos del medio.
inline double median_of(std::vector<double> values) {
    assert(!values.empty());
    std::sort(values.begin(), values.end());
    std::size_t middle = values.size() / 2;
    if (values.size() % 2 == 1) {
        return values[middle];
    }
    return (values[middle - 1] + values[middle]) / 2.0;
}

// Corre fn `reps` veces y devuelve la mediana en segundos.
// Todo lo que pase dentro de fn cuenta como tiempo medido.
template <typename Fn>
double median_seconds(int reps, Fn fn) {
    assert(reps >= 1);
    std::vector<double> times;
    times.reserve(static_cast<std::size_t>(reps));
    for (int i = 0; i < reps; i++) {
        auto start = std::chrono::steady_clock::now();
        fn();
        auto stop = std::chrono::steady_clock::now();
        times.push_back(std::chrono::duration<double>(stop - start).count());
    }
    return median_of(times);
}

// Evita que el compilador borre un cálculo cuyo resultado no se usa.
// No genera ninguna instrucción: le avisa al compilador que este bloque vacío
// podría leer value y cualquier memoria. Es una extensión de g++ y clang, no
// parte del estándar de C++.
template <typename T>
void keep(const T& value) {
    asm volatile("" : : "r"(&value) : "memory");
}

#endif

// El mismo recorrido Θ(n), en dos órdenes: lo que O no ve.
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <numeric>
#include <random>
#include <utility>
#include <vector>

#include "bench.h"

// Sigue la cadena next[position] durante next.size() saltos.
std::uint32_t walk(const std::vector<std::uint32_t>& next) {
    std::uint32_t position = 0;
    for (std::size_t i = 0; i < next.size(); i++) {
        position = next[position];
    }
    return position;
}

// Un solo ciclo que pasa por todos, de i a i + 1.
std::vector<std::uint32_t> ordered_cycle(std::size_t n) {
    std::vector<std::uint32_t> next(n);
    for (std::size_t i = 0; i < n; i++) {
        next[i] = static_cast<std::uint32_t>((i + 1) % n);
    }
    return next;
}

// Un solo ciclo que pasa por todos, en un orden al azar.
std::vector<std::uint32_t> random_cycle(std::size_t n) {
    std::vector<std::uint32_t> order(n);
    std::iota(order.begin(), order.end(), 0);
    std::mt19937 generator(2026);
    for (std::size_t i = n - 1; i > 0; i--) {
        std::uniform_int_distribution<std::size_t> pick(0, i - 1);
        std::swap(order[i], order[pick(generator)]);
    }
    std::vector<std::uint32_t> next(n);
    for (std::size_t i = 0; i < n; i++) {
        next[order[i]] = order[(i + 1) % n];
    }
    return next;
}

int main() {
    std::printf("%10s %8s %12s %12s %7s\n", "n", "KiB", "ordenado", "al azar", "razon");
    for (std::size_t n : {1u << 12, 1u << 16, 1u << 20, 1u << 22}) {
        std::vector<std::uint32_t> ordered = ordered_cycle(n);
        std::vector<std::uint32_t> shuffled = random_cycle(n);
        double ordered_time = median_seconds(5, [&] { keep(walk(ordered)); });
        double shuffled_time = median_seconds(5, [&] { keep(walk(shuffled)); });
        double count = static_cast<double>(n);
        std::printf("%10zu %8zu %9.2f ns %9.2f ns %7.1f\n", n, n * sizeof(std::uint32_t) / 1024,
                    ordered_time / count * 1e9, shuffled_time / count * 1e9,
                    shuffled_time / ordered_time);
    }
    return 0;
}

// Cuenta llamadas, trabajo y profundidad de cuatro funciones recursivas.
#include <algorithm>
#include <cstdio>

struct Tally {
    long long calls = 0;
    long long work = 0;
    int deepest = 0;
};

// T(n) = T(n/2) + 1
void one_half(long long n, int depth, Tally& tally) {
    tally.calls++;
    tally.work++;
    tally.deepest = std::max(tally.deepest, depth);
    if (n <= 1) {
        return;
    }
    one_half(n / 2, depth + 1, tally);
}

// T(n) = 2 T(n/2) + 1
void two_halves(long long n, int depth, Tally& tally) {
    tally.calls++;
    tally.work++;
    tally.deepest = std::max(tally.deepest, depth);
    if (n <= 1) {
        return;
    }
    two_halves(n / 2, depth + 1, tally);
    two_halves(n / 2, depth + 1, tally);
}

// T(n) = 2 T(n/2) + n
void two_halves_linear(long long n, int depth, Tally& tally) {
    tally.calls++;
    tally.work += n;
    tally.deepest = std::max(tally.deepest, depth);
    if (n <= 1) {
        return;
    }
    two_halves_linear(n / 2, depth + 1, tally);
    two_halves_linear(n / 2, depth + 1, tally);
}

// T(n) = 2 T(n-1) + 1
void two_minus_one(long long n, int depth, Tally& tally) {
    tally.calls++;
    tally.work++;
    tally.deepest = std::max(tally.deepest, depth);
    if (n == 0) {
        return;
    }
    two_minus_one(n - 1, depth + 1, tally);
    two_minus_one(n - 1, depth + 1, tally);
}

using Recursive = void (*)(long long, int, Tally&);

void print_table(const char* title, Recursive fn, const long long* sizes, int count) {
    std::printf("%s\n", title);
    std::printf("%10s %12s %12s %8s\n", "n", "llamadas", "trabajo", "profund.");
    for (int i = 0; i < count; i++) {
        Tally tally;
        fn(sizes[i], 0, tally);
        std::printf("%10lld %12lld %12lld %8d\n", sizes[i], tally.calls, tally.work, tally.deepest);
    }
    std::printf("\n");
}

int main() {
    const long long powers[] = {8, 16, 1024, 2048};
    const long long others[] = {5, 6, 7, 9, 1000, 1500};
    const long long small[] = {5, 10, 20};

    print_table("T(n) = T(n/2) + 1", one_half, powers, 4);
    print_table("T(n) = 2 T(n/2) + 1", two_halves, powers, 4);
    print_table("T(n) = 2 T(n/2) + 1, n que no es potencia de 2", two_halves, others, 6);
    print_table("T(n) = 2 T(n/2) + n", two_halves_linear, powers, 4);
    print_table("T(n) = 2 T(n-1) + 1", two_minus_one, small, 3);
    return 0;
}

// Cuenta comparaciones en el mejor caso, el peor caso y el caso promedio.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <numeric>
#include <random>
#include <vector>

// Devuelve el índice de key, o -1. Suma a comparisons cada comparación con un elemento.
int linear_search(const std::vector<int>& values, int key, long long& comparisons) {
    for (std::size_t i = 0; i < values.size(); i++) {
        comparisons++;
        if (values[i] == key) {
            return static_cast<int>(i);
        }
    }
    return -1;
}

// Ordena values y devuelve cuántas comparaciones entre elementos hizo.
long long insertion_sort(std::vector<int>& values) {
    long long comparisons = 0;
    for (std::size_t i = 1; i < values.size(); i++) {
        int current = values[i];
        std::size_t j = i;
        while (j > 0) {
            comparisons++;
            if (values[j - 1] <= current) {
                break;
            }
            values[j] = values[j - 1];
            j--;
        }
        values[j] = current;
    }
    return comparisons;
}

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

    long long best = 0;
    linear_search(values, 0, best);
    long long worst = 0;
    linear_search(values, -1, worst);
    long long all_positions = 0;
    for (int key = 0; key < n; key++) {
        linear_search(values, key, all_positions);
    }
    double average = static_cast<double>(all_positions) / n;
    std::printf("%8d %8lld %12.1f %8lld\n", n, best, average, worst);
}

void sort_table(int n, std::mt19937& generator) {
    std::vector<int> ascending(static_cast<std::size_t>(n));
    std::iota(ascending.begin(), ascending.end(), 0);

    std::vector<int> descending(ascending.rbegin(), ascending.rend());
    std::vector<int> shuffled = ascending;
    std::shuffle(shuffled.begin(), shuffled.end(), generator);

    long long best = insertion_sort(ascending);
    long long random = insertion_sort(shuffled);
    long long worst = insertion_sort(descending);
    assert(std::is_sorted(ascending.begin(), ascending.end()));
    assert(std::is_sorted(shuffled.begin(), shuffled.end()));
    assert(std::is_sorted(descending.begin(), descending.end()));
    std::printf("%8d %10lld %12lld %10lld\n", n, best, random, worst);
}

int main() {
    std::printf("busqueda lineal: comparaciones\n");
    std::printf("%8s %8s %12s %8s\n", "n", "mejor", "promedio", "peor");
    for (int n : {1000, 2000, 4000}) {
        search_table(n);
    }

    std::printf("\nordenamiento por insercion: comparaciones\n");
    std::printf("%8s %10s %12s %10s\n", "n", "ordenado", "al azar", "invertido");
    std::mt19937 generator(2026);
    for (int n : {1000, 2000, 4000}) {
        sort_table(n, generator);
    }
    return 0;
}

// Cuenta las vueltas de los patrones de ciclos de los apuntes.
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>

long long two_in_sequence(long long n) {
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        count++;
    }
    for (long long i = 0; i < n; i++) {
        count++;
    }
    return count;
}

long long nested_full(long long n) {
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 0; j < n; j++) {
            count++;
        }
    }
    return count;
}

long long nested_triangle(long long n) {
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 0; j < i; j++) {
            count++;
        }
    }
    return count;
}

long long halving(long long n) {
    long long count = 0;
    for (long long j = n; j > 0; j /= 2) {
        count++;
    }
    return count;
}

long long nested_halving(long long n) {
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = i; j > 0; j /= 2) {
            count++;
        }
    }
    return count;
}

struct Pattern {
    std::string name;
    long long (*fn)(long long);
};

int main() {
    const std::vector<Pattern> patterns = {
        {"secuencia", two_in_sequence},
        {"anidados", nested_full},
        {"triangulo", nested_triangle},
        {"divide", halving},
        {"triangulo_divide", nested_halving},
    };
    const long long sizes[] = {1000, 2000, 4000, 8000};

    assert(two_in_sequence(1000) == 2 * 1000);
    assert(nested_full(1000) == 1000 * 1000);
    assert(nested_triangle(1000) == 1000 * 999 / 2);
    assert(halving(1024) == 11);

    std::printf("%-18s %10s %10s %10s %10s %7s\n", "patron", "n=1000", "n=2000", "n=4000", "n=8000",
                "razon");
    for (const Pattern& pattern : patterns) {
        std::printf("%-18s", pattern.name.c_str());
        long long previous = 0;
        long long last = 0;
        for (long long n : sizes) {
            previous = last;
            last = pattern.fn(n);
            std::printf(" %10lld", last);
        }
        std::printf(" %7.2f\n", static_cast<double>(last) / static_cast<double>(previous));
    }
    return 0;
}

// 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;
}

// Primera medición: un reloj, una suma, varias repeticiones.
#include <algorithm>
#include <chrono>
#include <cstddef>
#include <cstdio>
#include <numeric>
#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;
}

// El salto más pequeño que se alcanza a ver entre dos lecturas seguidas del reloj.
double smallest_tick() {
    double smallest = 1.0;
    for (int i = 0; i < 100000; i++) {
        auto first = std::chrono::steady_clock::now();
        auto second = std::chrono::steady_clock::now();
        while (second == first) {
            second = std::chrono::steady_clock::now();
        }
        smallest = std::min(smallest, std::chrono::duration<double>(second - first).count());
    }
    return smallest;
}

int main() {
    const std::size_t n = 1000000;
    std::vector<int> values(n);
    std::iota(values.begin(), values.end(), 0);

    auto start = std::chrono::steady_clock::now();
    long long total = sum_values(values);
    auto stop = std::chrono::steady_clock::now();
    keep(total);
    double seconds = std::chrono::duration<double>(stop - start).count();
    std::printf("una medicion: %.0f us\n", seconds * 1e6);

    std::vector<double> times;
    for (int i = 0; i < 9; i++) {
        times.push_back(median_seconds(1, [&] { keep(sum_values(values)); }));
    }
    double mean = std::accumulate(times.begin(), times.end(), 0.0) / static_cast<double>(times.size());
    std::printf("nueve mediciones (us):");
    for (double time : times) {
        std::printf(" %.0f", time * 1e6);
    }
    std::printf("\nmedia %.0f us, mediana %.0f us\n", mean * 1e6, median_of(times) * 1e6);
    std::printf("salto minimo del reloj: %.0f ns\n", smallest_tick() * 1e9);
    return 0;
}

// Tabla de crecimiento, y el mayor n que cabe en un presupuesto de operaciones.
#include <cmath>
#include <cstdio>
#include <initializer_list>

using Cost = double (*)(double);

double cost_log(double n) { return std::log2(n); }
double cost_linear(double n) { return n; }
double cost_n_log(double n) { return n * std::log2(n); }
double cost_square(double n) { return n * n; }
double cost_cube(double n) { return n * n * n; }
double cost_exp(double n) { return std::pow(2.0, n); }

// El mayor entero n, desde 2, con cost(n) <= budget. Búsqueda binaria.
long long largest_n(Cost cost, double budget) {
    long long low = 2;
    long long high = 4;
    while (cost(static_cast<double>(high)) <= budget) {
        high *= 2;
    }
    while (high - low > 1) {
        long long middle = low + (high - low) / 2;
        if (cost(static_cast<double>(middle)) <= budget) {
            low = middle;
        } else {
            high = middle;
        }
    }
    return low;
}

int main() {
    std::printf("%8s %8s %10s %10s %10s %10s\n", "n", "log2 n", "n", "n log2 n", "n^2", "2^n");
    for (double n : {10.0, 20.0, 40.0, 80.0, 1000.0, 1000000.0}) {
        std::printf("%8.0f %8.1f %10.3g %10.3g %10.3g %10.3g\n", n, cost_log(n), n, cost_n_log(n),
                    cost_square(n), cost_exp(n));
    }

    const double budget = 1e9;
    std::printf("\ncon %.0f operaciones\n", budget);
    std::printf("%10s %14lld\n", "n", largest_n(cost_linear, budget));
    std::printf("%10s %14lld\n", "n log2 n", largest_n(cost_n_log, budget));
    std::printf("%10s %14lld\n", "n^2", largest_n(cost_square, budget));
    std::printf("%10s %14lld\n", "n^3", largest_n(cost_cube, budget));
    std::printf("%10s %14lld\n", "2^n", largest_n(cost_exp, budget));
    return 0;
}

// Dos operaciones medidas: se compila con y sin sanitizers para comparar.
#include <cstddef>
#include <cstdio>
#include <numeric>
#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;
}

void many_small_blocks(int count) {
    for (int i = 0; i < count; i++) {
        std::vector<int> block(8, i);
        keep(block);
    }
}

int main() {
    std::vector<int> values(1000000);
    std::iota(values.begin(), values.end(), 0);
    double sum_time = median_seconds(9, [&] { keep(sum_values(values)); });
    double block_time = median_seconds(9, [] { many_small_blocks(100000); });
    std::printf("suma de 1000000 enteros: %9.0f us\n", sum_time * 1e6);
    std::printf("100000 bloques pequenos: %9.0f us\n", block_time * 1e6);
    std::printf("bloques / suma:          %9.2f\n", block_time / sum_time);
    return 0;
}

// Θ(U + n) contra Θ(n²), con valores distintos: con n pequeño, gana el cuadrático.
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <initializer_list>
#include <numeric>
#include <random>
#include <vector>

#include "bench.h"

// Los valores están entre 0 y TABLE_SIZE - 1.
constexpr std::size_t TABLE_SIZE = 1 << 20;

// Con valores distintos, Θ(n²): compara cada par.
bool has_duplicate_pairs(const std::vector<int>& values) {
    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]) {
                return true;
            }
        }
    }
    return false;
}

// Θ(TABLE_SIZE + n): una pasada, y siempre limpia una tabla de TABLE_SIZE casillas.
bool has_duplicate_table(const std::vector<int>& values) {
    std::vector<char> seen(TABLE_SIZE, 0);
    for (int value : values) {
        std::size_t position = static_cast<std::size_t>(value);
        if (seen[position] != 0) {
            return true;
        }
        seen[position] = 1;
    }
    return false;
}

int main() {
    std::vector<int> all(TABLE_SIZE);
    std::iota(all.begin(), all.end(), 0);
    std::mt19937 generator(2026);
    std::shuffle(all.begin(), all.end(), generator);

    std::printf("%8s %14s %14s %12s\n", "n", "pares (us)", "tabla (us)", "pares/tabla");
    for (std::size_t n : {10u, 100u, 1000u, 4000u, 16000u, 32000u}) {
        // Valores distintos, posibles porque n <= TABLE_SIZE: el peor caso de las dos.
        std::vector<int> values(all.begin(), all.begin() + static_cast<std::ptrdiff_t>(n));
        int reps = n <= 4000 ? 15 : 3;
        double pairs = median_seconds(reps, [&] { keep(has_duplicate_pairs(values)); });
        double table = median_seconds(reps, [&] { keep(has_duplicate_table(values)); });
        std::printf("%8zu %14.2f %14.2f %12.3f\n", n, pairs * 1e6, table * 1e6, pairs / table);
    }
    return 0;
}

// Error a propósito: un ciclo que el compilador reemplaza por una fórmula.
#include <cstdio>
#include <initializer_list>

#include "../bench.h"

long long nested_count(long long n) {
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 0; j < n; j++) {
            count++;
        }
    }
    return count;
}

int main() {
    for (long long n : {1000LL, 2000LL, 4000LL, 8000LL}) {
        long long count = 0;
        double seconds = median_seconds(9, [&] {
            count = nested_count(n);
            keep(count);
        });
        std::printf("n = %5lld   vueltas = %9lld   %8.0f ns\n", n, count, seconds * 1e9);
    }
    return 0;
}

// Error a propósito: mide un cálculo cuyo resultado nadie usa.
#include <cstddef>
#include <cstdio>
#include <numeric>
#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;
}

int main() {
    for (std::size_t n : {1000000, 2000000, 4000000}) {
        std::vector<int> values(n);
        std::iota(values.begin(), values.end(), 0);
        double seconds = median_seconds(9, [&] { sum_values(values); });
        std::printf("n = %8zu   sin keep: %10.0f ns\n", n, seconds * 1e9);
        seconds = median_seconds(9, [&] { keep(sum_values(values)); });
        std::printf("n = %8zu   con keep: %10.0f ns\n", n, seconds * 1e9);
    }
    return 0;
}

// Error a propósito: repite la medición siempre con los mismos datos.
#include <algorithm>
#include <cstddef>
#include <cstdio>
#include <initializer_list>
#include <random>
#include <vector>

#include "../bench.h"

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;
}

int main() {
    std::mt19937 generator(2026);
    const int reps = 200;
    std::printf("%8s %14s %14s\n", "n", "mismo (us)", "distintos (us)");
    for (std::size_t n : {1000u, 4000u, 16000u}) {
        // Primero 200 veces una copia del mismo arreglo.
        std::vector<int> original = random_values(n, generator);
        std::vector<std::vector<int>> copies(reps, original);
        std::size_t next = 0;
        double same = median_seconds(reps, [&] {
            std::sort(copies[next].begin(), copies[next].end());
            keep(copies[next]);
            next++;
        });

        // Después 200 arreglos distintos.
        std::vector<std::vector<int>> arrays;
        for (int i = 0; i < reps; i++) {
            arrays.push_back(random_values(n, generator));
        }
        next = 0;
        double different = median_seconds(reps, [&] {
            std::sort(arrays[next].begin(), arrays[next].end());
            keep(arrays[next]);
            next++;
        });
        std::printf("%8zu %14.1f %14.1f\n", n, same * 1e6, different * 1e6);
    }
    return 0;
}

// Pruebas de bench.h. No comprueban tiempos: cuentan llamadas y calculan medianas.
#include <string>
#include <vector>

#include "bench.h"
#include "check.h"

int main() {
    check(median_of({3.0}) == 3.0, "mediana de un valor");
    check(median_of({5.0, 1.0, 3.0}) == 3.0, "mediana con cantidad impar");
    check(median_of({4.0, 1.0, 3.0, 2.0}) == 2.5, "mediana con cantidad par");
    check(median_of({1.0, 1.0, 1.0, 1.0, 900.0}) == 1.0, "un valor atípico no mueve la mediana");

    int calls = 0;
    double seconds = median_seconds(7, [&] { calls++; });
    check(calls == 7, "median_seconds llama a fn exactamente reps veces");
    check(seconds >= 0, "un tiempo no es negativo");

    calls = 0;
    median_seconds(4, [&] { calls++; });
    check(calls == 4, "también con reps par");

    int number = 7;
    std::vector<int> values = {1, 2, 3};
    std::string text = "hola";
    keep(number);
    keep(values);
    keep(text);
    keep(number + 1);
    check(number == 7 && values.size() == 3 && text == "hola", "keep no cambia nada");

    std::printf("ok\n");
    return 0;
}

"""Pruebas del laboratorio. LAB_DIR dice dónde está el código: lab o solution.

Ninguna prueba compara tiempos, porque dependen de la máquina. Comparan cuentas de pasos,
resultados y el formato del CSV y del informe.
"""
import csv
import os
import pathlib
import re
import subprocess
import tempfile
import unittest

HERE = pathlib.Path(__file__).parent
LAB_DIR = os.environ.get("LAB_DIR", "solution")
SOURCE = HERE / LAB_DIR
BUILD = HERE / "build" / LAB_DIR
MYSTERIES = ["mystery_" + letter for letter in "abcdef"]
SESSION2 = ["push_back", "insert_front", "linear_search", "binary_search"]
CLASSES = ["1", "log n", "n", "n log n", "n^2", "2^n"]


def run(*command):
    return subprocess.run(
        [str(part) for part in command], cwd=HERE, text=True, encoding="utf-8",
        stdin=subprocess.DEVNULL, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=180,
    )


def read_csv(path):
    with open(path, encoding="utf-8", newline="") as source:
        return list(csv.DictReader(source))


def class_from_steps(rows):
    """La clase que se deduce de los pasos contados, que no dependen de la máquina."""
    steps = [int(row["steps"]) for row in rows]
    sizes = [int(row["n"]) for row in rows]
    last_ratio = steps[-1] / steps[-2]
    if steps[-1] == steps[-2]:
        return "1"
    if last_ratio > 8:
        return "2^n"
    if last_ratio > 3:
        return "n^2"
    if last_ratio < 1.5:
        return "log n"
    if (steps[-1] / sizes[-1]) / (steps[0] / sizes[0]) > 1.2:
        return "n log n"
    return "n"


def report_rows(text):
    rows = {}
    for line in text.splitlines():
        cells = [cell.strip() for cell in line.strip().strip("|").split("|")]
        if cells and cells[0] in MYSTERIES:
            rows[cells[0]] = cells
    return rows


@unittest.skipUnless(SOURCE.exists(), "falta la carpeta del laboratorio")
class Lab(unittest.TestCase):
    def test_unit_tests(self):
        done = run(BUILD / "lab_tests")
        self.assertEqual(done.returncode, 0, done.stdout)

    def test_doubling_csv(self):
        with tempfile.TemporaryDirectory() as folder:
            path = pathlib.Path(folder) / "doubling.csv"
            done = run(BUILD / "run_doubling", path)
            self.assertEqual(done.returncode, 0, done.stdout)
            rows = read_csv(path)
        names = {row["function"] for row in rows}
        self.assertEqual(names, set(MYSTERIES))
        for name in MYSTERIES:
            own = [row for row in rows if row["function"] == name]
            self.assertGreater(len(own), 3, name)
            sizes = [int(row["n"]) for row in own]
            self.assertEqual(sizes, [sizes[0] * 2 ** i for i in range(len(sizes))], name)
            self.assertTrue(all(float(row["seconds"]) > 0 for row in own), name)

    def test_session2_csv(self):
        with tempfile.TemporaryDirectory() as folder:
            path = pathlib.Path(folder) / "session2.csv"
            done = run(BUILD / "run_session2", path)
            self.assertEqual(done.returncode, 0, done.stdout)
            rows = read_csv(path)
        for name in SESSION2:
            own = [row for row in rows if row["function"] == name]
            self.assertGreater(len(own), 3, f"faltan filas de {name}")
            self.assertTrue(all(float(row["seconds"]) > 0 for row in own), name)
        linear = [row for row in rows if row["function"] == "linear_search"]
        binary = [row for row in rows if row["function"] == "binary_search"]
        self.assertTrue(all(int(row["steps"]) == int(row["n"]) for row in linear),
                        "la lineal debe medirse en su peor caso")
        for row in binary:
            self.assertLess(int(row["steps"]), 2 + len(bin(int(row["n"]))), "binaria: demasiados pasos")

    def test_report(self):
        text = (SOURCE / "report.md").read_text(encoding="utf-8")
        self.assertNotIn("PENDIENTE", text, "todavía hay partes sin llenar en el informe")
        rows = report_rows(text)
        self.assertEqual(set(rows), set(MYSTERIES))
        with tempfile.TemporaryDirectory() as folder:
            path = pathlib.Path(folder) / "doubling.csv"
            run(BUILD / "run_doubling", path)
            measured = read_csv(path)
        for name, cells in rows.items():
            self.assertEqual(len(cells), 5, name)
            self.assertIn(cells[1], CLASSES, f"{name}: la predicción no es una clase de la lista")
            self.assertIn(cells[4], CLASSES, f"{name}: la clase medida no es de la lista")
            self.assertRegex(cells[3], r"\d", f"{name}: faltan las razones medidas")
            own = [row for row in measured if row["function"] == name]
            self.assertEqual(cells[4], class_from_steps(own), f"{name}: revisen la clase medida")
        for title in ["push_back", "lineal", "-O0", "Conclusión"]:
            match = re.search(r"^#+ .*%s.*\n((?:(?!^#).*\n?)*)" % re.escape(title), text, re.M)
            self.assertIsNotNone(match, f"falta la sección de {title}")
            self.assertRegex(match.group(1), r"\d", f"la sección de {title} debe citar números")


@unittest.skipUnless((HERE / "solution").exists(), "falta la solución")
class StarterFails(unittest.TestCase):
    """El laboratorio sin resolver debe compilar y no pasar las pruebas."""

    def test_starter_compiles_and_fails(self):
        built = run("make", "--no-print-directory", "LAB_DIR=lab", "lab")
        self.assertEqual(built.returncode, 0, built.stdout)
        self.assertNotIn("warning", built.stdout)
        done = run(HERE / "build" / "lab" / "lab_tests")
        self.assertNotEqual(done.returncode, 0, "el laboratorio sin resolver pasa las pruebas")
        self.assertIn("PENDIENTE", (HERE / "lab" / "report.md").read_text(encoding="utf-8"))


if __name__ == "__main__":
    unittest.main()