// Comprueba lo que afirman los apuntes. Se compila con sanitizers.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <numeric>
#include <random>
#include <set>
#include <string>
#include <vector>

#include "adversary.h"
#include "comparison_sorts.h"
#include "counting_sort.h"
#include "intervals.h"
#include "quicksort.h"

namespace {

// Ordenar 3 elementos: 3 comparaciones en el peor caso y 6 hojas distintas.
void test_sort_three() {
    std::vector<int> input = {1, 2, 3};
    long long worst = 0;
    std::set<std::string> leaves;
    do {
        std::vector<int> a = input;
        CountingLess less;
        sort_three(a, less);
        assert(std::is_sorted(a.begin(), a.end()));
        worst = std::max(worst, less.count());
        leaves.insert(less.path());
    } while (std::next_permutation(input.begin(), input.end()));
    assert(worst == 3);
    assert(leaves.size() == 6);
    assert(ceil_log2_factorial(3) == 3);
}

template <typename Sort>
void check_bound(int n, Sort sort_function, long long& best, long long& worst) {
    std::vector<int> input(static_cast<std::size_t>(n));
    std::iota(input.begin(), input.end(), 0);
    std::set<std::string> leaves;
    best = -1;
    worst = 0;
    do {
        std::vector<int> a = input;
        CountingLess less;
        sort_function(a, less);
        assert(std::is_sorted(a.begin(), a.end()));
        best = best < 0 ? less.count() : std::min(best, less.count());
        worst = std::max(worst, less.count());
        leaves.insert(less.path());
    } while (std::next_permutation(input.begin(), input.end()));
    std::size_t factorial = 1;
    for (int i = 2; i <= n; i++) factorial *= static_cast<std::size_t>(i);
    assert(leaves.size() == factorial);          // una hoja por permutación
    assert(worst >= ceil_log2_factorial(n));     // nadie baja de la cota
}

// Ningún ordenamiento real baja de la cota, aunque su mejor caso sí esté por debajo.
void test_lower_bound() {
    assert(ceil_log2_factorial(1) == 0);
    assert(ceil_log2_factorial(2) == 1);
    assert(ceil_log2_factorial(4) == 5);
    assert(ceil_log2_factorial(5) == 7);
    assert(ceil_log2_factorial(20) == 62);
    for (int n = 2; n <= 7; n++) {
        long long best = 0;
        long long worst = 0;
        check_bound(n, insertion_sort, best, worst);
        assert(best == n - 1);
        assert(worst == n * (n - 1) / 2);
        check_bound(n, merge_sort, best, worst);
    }
    // El mejor caso de inserción está por debajo de la cota: no la contradice.
    long long best = 0;
    long long worst = 0;
    check_bound(6, insertion_sort, best, worst);
    assert(best < ceil_log2_factorial(6));
}

// El adversario obliga a cualquier ordenamiento a llegar a la cota, y su entrada lo reproduce:
// el mismo algoritmo, corrido con esa entrada ya fija, hace las mismas comparaciones.
void test_adversary() {
    for (int n = 2; n <= 7; n++) {
        Adversary against_insertion(n);
        const auto order = insertion_order(n, [&](int i, int j) { return against_insertion.less(i, j); });
        assert(against_insertion.count() >= ceil_log2_factorial(n));
        assert(against_insertion.alive() == 1);  // si quedaran dos, el algoritmo no habría terminado
        const std::vector<int> input = against_insertion.witness();
        long long replay = 0;
        const auto again = insertion_order(n, [&](int i, int j) {
            replay++;
            return input[static_cast<std::size_t>(i)] < input[static_cast<std::size_t>(j)];
        });
        assert(replay == against_insertion.count());
        assert(again == order);

        Adversary against_merge(n);
        merge_order(n, [&](int i, int j) { return against_merge.less(i, j); });
        assert(against_merge.count() >= ceil_log2_factorial(n));
        assert(against_merge.alive() == 1);
    }
}

// La desigualdad de la demostración: log₂ n! ≥ (n/2) log₂(n/2) ≥ (n/4) log₂ n para n ≥ 4.
void test_factorial_inequality() {
    double log_factorial = std::log2(2.0) + std::log2(3.0);
    for (int n = 4; n <= 100000; n++) {
        log_factorial += std::log2(static_cast<double>(n));
        const double m = n;
        assert(log_factorial >= m / 2 * std::log2(m / 2));
        assert(m / 2 * std::log2(m / 2) >= m / 4 * std::log2(m) - 1e-9);
        assert(log_factorial <= m * std::log2(m));
    }
}

void test_counting_sort() {
    std::mt19937 rng(11);
    for (int round = 0; round < 200; round++) {
        const int k = 1 + static_cast<int>(rng() % 50);
        std::vector<int> a(rng() % 100);
        for (int& value : a) value = static_cast<int>(rng() % static_cast<unsigned>(k));
        std::vector<int> expected = a;
        std::sort(expected.begin(), expected.end());
        counting_sort(a, k);
        assert(a == expected);
    }
}

void test_quicksort() {
    std::mt19937 rng(12);
    // Todas las variantes ordenan, con repetidos o sin ellos.
    for (int round = 0; round < 300; round++) {
        std::vector<int> a(rng() % 200);
        const unsigned range = 1 + rng() % 300;
        for (int& value : a) value = static_cast<int>(rng() % range);
        std::vector<int> expected = a;
        std::sort(expected.begin(), expected.end());
        const int n = static_cast<int>(a.size());
        for (Pivot rule : {Pivot::First, Pivot::Random}) {
            std::vector<int> b = a;
            QuickStats s2;
            quicksort_two_way(b, 0, n, rule, rng, s2);
            assert(b == expected);
            std::vector<int> c = a;
            QuickStats s3;
            quicksort_three_way(c, 0, n, rule, rng, s3);
            assert(c == expected);
        }
    }

    const int n = 1000;
    std::vector<int> sorted(n);
    std::iota(sorted.begin(), sorted.end(), 0);

    // Primer elemento sobre una entrada ordenada: exactamente n(n-1)/2 y n-1 niveles.
    {
        std::vector<int> a = sorted;
        QuickStats s;
        quicksort_two_way(a, 0, n, Pivot::First, rng, s);
        assert(s.comparisons == n * (n - 1) / 2);
        assert(s.max_depth == n - 1);
    }
    // Pivote al azar sobre la misma entrada: niveles logarítmicos, con esta semilla fija.
    {
        std::mt19937 fixed(2026);
        std::vector<int> a = sorted;
        QuickStats s;
        quicksort_two_way(a, 0, n, Pivot::Random, fixed, s);
        assert(s.comparisons < n * (n - 1) / 20);
        assert(s.max_depth < 60);
    }
    // Todos iguales: el azar no salva a la partición en dos; la partición en tres sí.
    {
        std::vector<int> equal(n, 7);
        std::mt19937 fixed(2026);
        QuickStats two;
        quicksort_two_way(equal, 0, n, Pivot::Random, fixed, two);
        assert(two.comparisons == n * (n - 1) / 2);
        QuickStats three;
        quicksort_three_way(equal, 0, n, Pivot::Random, fixed, three);
        assert(three.max_depth == 1);
        assert(three.comparisons == 2 * (n - 1));
    }
}

// Intervalos semiabiertos: el borde no es un cruce.
void test_half_open() {
    assert(!overlap({8, 10}, {10, 12}));
    assert(!overlap({10, 12}, {8, 10}));
    assert(overlap({8, 10}, {9, 12}));
    assert(overlap({8, 12}, {9, 10}));
    assert(overlap({8, 10}, {8, 10}));
    assert(is_valid({{8, 10}, {10, 12}, {12, 14}}));
    assert(!is_valid({{8, 11}, {10, 12}}));

    const std::vector<Interval> touching = {{8, 10}, {10, 12}};
    assert(select_by_finish(touching).size() == 2);
    assert(max_simultaneous(touching) == 1);
    assert(rooms_used(assign_rooms(touching)) == 1);
    assert(min_rooms_brute(touching) == 1);
}

// Los tres contraejemplos: la respuesta es válida y aun así no es óptima, y la primera
// elección de la regla no está en ninguna solución óptima.
void test_counterexamples() {
    const std::vector<Interval> a = {{8, 18}, {9, 11}, {11, 13}, {13, 15}};
    assert(max_compatible_brute(a) == 3);
    assert(rule_earliest_start(a).size() == 1);
    assert(is_valid(rule_earliest_start(a)));
    assert(!in_some_optimum(a, 0));
    assert(select_by_finish(a).size() == 3);

    const std::vector<Interval> b = {{8, 12}, {12, 16}, {11, 13}};
    assert(max_compatible_brute(b) == 2);
    assert(rule_shortest(b).size() == 1);
    assert(is_valid(rule_shortest(b)));
    assert(!in_some_optimum(b, 2));
    assert(select_by_finish(b).size() == 2);

    const std::vector<Interval> c = {{0, 2}, {2, 4}, {4, 6}, {6, 8}, {1, 3}, {1, 3},
                                     {1, 3}, {3, 5}, {5, 7}, {5, 7}, {5, 7}};
    assert(max_compatible_brute(c) == 4);
    assert(conflicts(c, 7) == 2);
    for (std::size_t i = 0; i < c.size(); i++) {
        if (i != 7) assert(conflicts(c, i) > 2);  // la del centro es la única con menos cruces
    }
    assert(rule_fewest_conflicts(c).size() == 3);
    assert(is_valid(rule_fewest_conflicts(c)));
    assert(!in_some_optimum(c, 7));
    assert((fewest_conflicts_range(c) == std::pair<int, int>{3, 3}));
    assert(select_by_finish(c).size() == 4);
}

// Termina antes coincide con la fuerza bruta; aulas coincide con el máximo simultáneo y
// con la vuelta atrás. Tiempos en un rango chico para que abunden empates y bordes.
void test_random_against_brute() {
    std::mt19937 rng(13);
    for (int round = 0; round < 1500; round++) {
        const int n = 1 + static_cast<int>(rng() % 9);
        std::vector<Interval> classes;
        for (int i = 0; i < n; i++) {
            const int start = static_cast<int>(rng() % 10);
            classes.push_back({start, start + 1 + static_cast<int>(rng() % 5)});
        }
        const auto chosen = select_by_finish(classes);
        assert(is_valid(chosen));
        assert(static_cast<int>(chosen.size()) == max_compatible_brute(classes));
        assert(is_valid(rule_earliest_start(classes)));
        assert(is_valid(rule_shortest(classes)));
        assert(is_valid(rule_fewest_conflicts(classes)));

        const auto room = assign_rooms(classes);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                const auto ui = static_cast<std::size_t>(i);
                const auto uj = static_cast<std::size_t>(j);
                if (room[ui] == room[uj]) assert(!overlap(classes[ui], classes[uj]));
            }
        }
        const int depth = max_simultaneous(classes);
        assert(rooms_used(room) == depth);
        assert(min_rooms_brute(classes) == depth);
    }
}

void test_rooms_examples() {
    const std::vector<Interval> week = {{8, 10}, {9, 11}, {10, 12}, {11, 13}, {8, 13}, {12, 14}, {13, 15}, {15, 16}};
    assert(select_by_finish(week).size() == 4);
    assert(max_compatible_brute(week) == 4);
    // El intercambio de los apuntes: en cada paso sigue válida y con 4 clases.
    std::vector<Interval> optimal = {{9, 11}, {11, 13}, {13, 15}, {15, 16}};
    assert(is_valid(optimal));
    const auto chosen = select_by_finish(week);
    for (std::size_t j = 0; j < chosen.size(); j++) {
        assert(chosen[j].finish <= optimal[j].finish);
        optimal[j] = chosen[j];
        assert(is_valid(optimal));
    }
    assert(optimal == chosen);
    assert(max_simultaneous(week) == 3);
    assert(rooms_used(assign_rooms(week)) == 3);

    // Llenar aula por aula gasta una de más.
    const std::vector<Interval> tricky = {{10, 11}, {8, 12}, {11, 17}, {15, 16}};
    assert(rooms_by_repeated_selection(tricky) == 3);
    assert(rooms_used(assign_rooms(tricky)) == 2);
    assert(min_rooms_brute(tricky) == 2);
}

}  // namespace

int main() {
    test_sort_three();
    test_lower_bound();
    test_adversary();
    test_factorial_inequality();
    test_counting_sort();
    test_quicksort();
    test_half_open();
    test_counterexamples();
    test_random_against_brute();
    test_rooms_examples();
    std::cout << "Todas las pruebas de la semana 4 pasaron.\n";
}