// Comprueba lo que afirman los apuntes de la semana. Falla con assert si algo no se cumple.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <limits>
#include <numeric>
#include <random>
#include <vector>

#include "comparison_count.h"
#include "copy_cost.h"
#include "from_code.h"
#include "inversions_brute.h"
#include "merge_sort.h"
#include "recurrences.h"

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

static void test_merge_sort() {
    std::vector<int> empty;
    merge_sort(empty);
    assert(empty.empty());
    std::vector<int> one = {7};
    merge_sort(one);
    assert(one == std::vector<int>{7});
    std::vector<int> two = {2, 1};
    merge_sort(two);
    assert((two == std::vector<int>{1, 2}));

    std::mt19937 rng(1);
    for (int round = 0; round < 2000; round++) {
        std::vector<int> a = random_values(rng, rng() % 40, round % 2 == 0 ? 5 : 1000);
        std::vector<int> expected = a;
        std::sort(expected.begin(), expected.end());
        merge_sort(a);
        assert(a == expected);
    }
}

struct Item {
    int key = 0;
    int tag = 0;
    bool operator<=(const Item& other) const { return key <= other.key; }
};

// Con <= en la mezcla, los elementos con la misma clave conservan su orden original.
static void test_stability() {
    std::mt19937 rng(2);
    for (int round = 0; round < 500; round++) {
        std::vector<Item> a(rng() % 50);
        for (std::size_t i = 0; i < a.size(); i++) {
            a[i] = {static_cast<int>(rng() % 4), static_cast<int>(i)};
        }
        merge_sort(a);
        for (std::size_t i = 1; i < a.size(); i++) {
            assert(a[i - 1].key <= a[i].key);
            assert(a[i - 1].key != a[i].key || a[i - 1].tag < a[i].tag);
        }
    }
}

// La invariante de los apuntes, comprobada en cada vuelta de la mezcla, con y sin repetidos.
static void test_merge_invariant() {
    std::mt19937 rng(3);
    for (int round = 0; round < 2000; round++) {
        std::vector<int> left = random_values(rng, rng() % 12, 6 + round % 50);
        std::vector<int> right = random_values(rng, rng() % 12, 6 + round % 50);
        std::sort(left.begin(), left.end());
        std::sort(right.begin(), right.end());
        std::vector<int> a = left;
        a.insert(a.end(), right.begin(), right.end());
        std::size_t mid = left.size();
        std::size_t hi = a.size();
        std::vector<int> buffer(hi);
        std::size_t i = 0;
        std::size_t j = mid;
        for (std::size_t k = 0; k <= hi; k++) {
            // (1) Se copiaron exactamente a[0, i) y a[mid, j).
            assert(i + (j - mid) == k);
            std::vector<int> copied(a.begin(), a.begin() + static_cast<std::ptrdiff_t>(i));
            copied.insert(copied.end(), a.begin() + static_cast<std::ptrdiff_t>(mid),
                          a.begin() + static_cast<std::ptrdiff_t>(j));
            std::sort(copied.begin(), copied.end());
            std::vector<int> prefix(buffer.begin(), buffer.begin() + static_cast<std::ptrdiff_t>(k));
            // (2) El prefijo está ordenado y tiene esos mismos elementos.
            assert(prefix == copied);
            // (3) Nada de lo copiado es mayor que algo de lo que falta.
            if (k > 0) {
                for (std::size_t p = i; p < mid; p++) {
                    assert(buffer[k - 1] <= a[p]);
                }
                for (std::size_t p = j; p < hi; p++) {
                    assert(buffer[k - 1] <= a[p]);
                }
            }
            if (k == hi) {
                break;
            }
            if (j == hi || (i < mid && a[i] <= a[j])) {
                buffer[k] = a[i++];
            } else {
                buffer[k] = a[j++];
            }
        }
    }
}

static void test_recurrences() {
    // Las formas cerradas de los apuntes, exactas con enteros, para n = 2^k.
    using Int = long long;
    for (int k = 0; k <= 20; k++) {
        Int n = Int{1} << k;
        auto one = [](int) -> Int { return 1; };
        auto linear = [](int m) -> Int { return Int{1} << m; };
        auto quadratic = [](int m) -> Int { return Int{1} << (2 * m); };
        auto n_log_n = [](int m) -> Int { return m * (Int{1} << m); };
        assert(solve_power_of_two<Int>(2, k, linear) == n * k + n);
        assert(solve_power_of_two<Int>(1, k, one) == k + 1);
        assert(solve_power_of_two<Int>(2, k, one) == 2 * n - 1);
        assert(solve_power_of_two<Int>(2, k, quadratic) == 2 * n * n - n);
        assert(solve_power_of_two<Int>(2, k, n_log_n) == n * k * (k + 1) / 2 + n);
        if (k <= 16) {
            assert(solve_power_of_two<Int>(8, k, quadratic) == 2 * n * n * n - n * n);
        }
        // 3T(n/2) + n: 3^(k+1) - 2n, donde 3^k = n^(log 3).
        Int power_of_three = 1;
        for (int i = 0; i <= k; i++) {
            power_of_three *= 3;
        }
        assert(solve_power_of_two<Int>(3, k, linear) == power_of_three - 2 * n);
    }
    // 2T(n/2) + n / log n: T(n) = n (H_k + 1), con H_k = 1 + 1/2 + ... + 1/k.
    long double harmonic = 0;
    for (int k = 1; k <= 200; k++) {
        harmonic += 1.0L / k;
        long double n = std::ldexp(1.0L, k);
        long double value = solve_power_of_two<long double>(2, k, f_n_over_log_n);
        assert(std::fabs(value / n - (harmonic + 1)) < 1e-12L);
        // Y cada nivel i cuesta n / (k - i).
        std::vector<long double> levels = level_work<long double>(2, k, f_n_over_log_n);
        for (int i = 0; i < k; i++) {
            assert(std::fabs(levels[static_cast<std::size_t>(i)] / n - 1.0L / (k - i)) < 1e-12L);
        }
    }
}

// Lo que cuesta cada función de from_code.h es lo que dice su recurrencia.
static void test_from_code() {
    for (int k = 0; k <= 10; k++) {
        int n = 1 << k;
        auto linear = [](int m) -> long long { return 1LL << m; };
        auto quadratic = [](int m) -> long long { return 1LL << (2 * m); };
        long long work = 0;
        two_calls_linear(n, work);
        assert(work == solve_power_of_two<long long>(2, k, linear));
        work = 0;
        three_calls_linear(n, work);
        assert(work == solve_power_of_two<long long>(3, k, linear));
        if (k <= 6) {
            work = 0;
            eight_calls_quadratic(n, work);
            assert(work == solve_power_of_two<long long>(8, k, quadratic));
        }
    }
}

static void test_copies() {
    for (int k = 0; k <= 13; k++) {
        int n = 1 << k;
        // Con el arreglo entero por valor: n copias por cada llamada, k + 2 llamadas contando la primera
        // y la del rango vacío.
        long long whole = 0;
        int calls = 0;
        std::vector<Counted> a = counted_range(n, &whole);
        assert(search_whole_copy(a, 0, a.size(), -1, calls) == -1);
        assert(calls == k + 2);
        assert(whole == static_cast<long long>(calls) * n);

        // Copiando la mitad: 2^(k-1) + 2^(k-2) + ... + 1 = n - 1 copias.
        long long half = 0;
        int half_calls = 0;
        std::vector<Counted> b = counted_range(n, &half);
        assert(!search_half_copy(b, -1, half_calls));
        assert(half == n - 1);

        // Por referencia, ninguna.
        long long reference = 0;
        int reference_calls = 0;
        std::vector<Counted> c = counted_range(n, &reference);
        assert(search_by_reference(c, 0, c.size(), -1, reference_calls) == -1);
        assert(reference == 0);
        assert(reference_calls == calls);
    }
    // Mergesort con el auxiliar por valor: 2n - 1 llamadas, cada una copia n elementos.
    for (int n : {1, 2, 3, 7, 100, 1000}) {
        long long copies = 0;
        std::vector<Counted> a = counted_range(n, &copies);
        std::reverse(a.begin(), a.end());
        copies = 0;  // Invertir también copia: solo interesan las copias de la recursión.
        sort_range_buffer_by_value(a, a, 0, a.size());
        assert(copies == (2LL * n - 1) * n);
        for (int i = 0; i < n; i++) {
            assert(a[static_cast<std::size_t>(i)].value == i);
        }
    }
}

static void test_comparisons() {
    for (std::size_t n = 1; n <= 2000; n++) {
        assert(worst_case_recurrence(n) == worst_case_formula(n));
        std::vector<int> sorted(n);
        std::iota(sorted.begin(), sorted.end(), 0);
        std::vector<int> worst = worst_case_input(sorted);
        assert(count_comparisons(worst) == worst_case_formula(n));
        // Y ninguna entrada se pasa de esa cota.
        assert(count_comparisons(sorted) <= worst_case_formula(n));
    }
    std::mt19937 rng(4);
    for (int round = 0; round < 2000; round++) {
        std::vector<int> a = random_values(rng, 1 + rng() % 64, 100);
        assert(count_comparisons(a) <= worst_case_formula(a.size()));
    }
    // En potencias de 2 la fórmula es n log n - n + 1.
    for (int k = 0; k <= 20; k++) {
        long long n = 1LL << k;
        assert(worst_case_formula(static_cast<std::size_t>(n)) == n * k - n + 1);
    }
}

static void test_inversions() {
    assert(count_inversions_brute({3, 1, 4, 2}) == 3);
    assert(count_inversions_brute({5, 2, 6, 1, 4, 3}) == 9);
    assert(count_inversions_brute({}) == 0);
    assert(count_inversions_brute({1}) == 0);
    assert(count_inversions_brute({2, 2, 2}) == 0);

    // El máximo es n(n-1)/2, y entre permutaciones solo lo alcanza la invertida.
    for (int n = 1; n <= 8; n++) {
        std::vector<int> p(static_cast<std::size_t>(n));
        std::iota(p.begin(), p.end(), 0);
        long long best = 0;
        int attained = 0;
        do {
            long long count = count_inversions_brute(p);
            if (count > best) {
                best = count;
                attained = 1;
            } else if (count == best) {
                attained++;
            }
        } while (std::next_permutation(p.begin(), p.end()));
        assert(best == n * (n - 1) / 2);
        assert(attained == 1);
    }
    // Con n = 65 537 ya no cabe en int; con 65 536, todavía sí.
    assert(65536LL * 65535 / 2 <= std::numeric_limits<int>::max());
    assert(65537LL * 65536 / 2 > std::numeric_limits<int>::max());

    std::mt19937 rng(5);
    for (int round = 0; round < 2000; round++) {
        std::vector<int> a = random_values(rng, rng() % 30, round % 2 == 0 ? 4 : 100);
        std::size_t mid = a.size() / 2;
        // Inversiones = dentro de la izquierda + dentro de la derecha + cruzadas.
        assert(count_inversions_brute(a) == count_inversions_brute(a, 0, mid) + count_inversions_brute(a, mid, a.size()) +
                                                count_cross_brute(a, 0, mid, a.size()));
        // Ordenar cada mitad no cambia las cruzadas.
        std::vector<int> halves = a;
        std::sort(halves.begin(), halves.begin() + static_cast<std::ptrdiff_t>(mid));
        std::sort(halves.begin() + static_cast<std::ptrdiff_t>(mid), halves.end());
        assert(count_cross_brute(a, 0, mid, a.size()) == count_cross_brute(halves, 0, mid, a.size()));
    }
}

// Cada intercambio de vecinos cambia las inversiones en exactamente 1, y ordenar intercambiando
// vecinos desordenados hace tantos intercambios como inversiones había.
static void test_adjacent_swaps() {
    std::mt19937 rng(6);
    for (int round = 0; round < 1000; round++) {
        std::vector<int> a(1 + rng() % 25);
        std::iota(a.begin(), a.end(), 0);
        for (std::size_t i = a.size() - 1; i > 0; i--) {
            std::swap(a[i], a[rng() % (i + 1)]);
        }
        long long inversions = count_inversions_brute(a);
        long long swaps = 0;
        for (std::size_t pass = 0; pass < a.size(); pass++) {
            for (std::size_t i = 0; i + 1 < a.size(); i++) {
                if (a[i] > a[i + 1]) {
                    long long before = count_inversions_brute(a);
                    std::swap(a[i], a[i + 1]);
                    assert(count_inversions_brute(a) == before - 1);
                    swaps++;
                }
            }
        }
        assert(swaps == inversions);
    }
}

// En una mezcla, cuando pasa un elemento de la derecha, los que quedan a la izquierda son justo los
// mayores que él. Sumar 1 por cada uno, en cambio, se queda corto. Se compara con los pares contados uno por uno.
static void test_merge_step() {
    // El ejemplo de los apuntes: 3 pasos desde la derecha, pero 7 pares cruzados.
    std::vector<int> example = {2, 5, 6, 1, 3, 4};
    assert(count_cross_brute(example, 0, 3, 6) == 7);

    std::mt19937 rng(7);
    for (int round = 0; round < 3000; round++) {
        std::vector<int> left = random_values(rng, rng() % 15, round % 2 == 0 ? 5 : 100);
        std::vector<int> right = random_values(rng, rng() % 15, round % 2 == 0 ? 5 : 100);
        std::sort(left.begin(), left.end());
        std::sort(right.begin(), right.end());
        std::size_t i = 0;
        std::size_t j = 0;
        while (i < left.size() || j < right.size()) {
            if (j == right.size() || (i < left.size() && left[i] <= right[j])) {
                i++;
            } else {
                auto greater = static_cast<std::size_t>(
                    std::count_if(left.begin(), left.end(), [&](int x) { return x > right[j]; }));
                assert(greater == left.size() - i);
                j++;
            }
        }
    }
}

int main() {
    test_merge_sort();
    test_stability();
    test_merge_invariant();
    test_recurrences();
    test_from_code();
    test_copies();
    test_comparisons();
    test_inversions();
    test_adjacent_swaps();
    test_merge_step();
    std::cout << "todas las pruebas pasaron\n";
}