// Comprueba lo que afirman los apuntes. Corre con ASan y UBSan.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#include "instances.h"
#include "power.h"
#include "search.h"

namespace {

// Todas las búsquedas sobre arreglos ordenados, con repetidos y sin ellos.
void test_binary_search() {
    std::mt19937 gen(1);
    for (int n = 0; n <= 40; n++) {
        for (int round = 0; round < 30; round++) {
            std::vector<int> a(n);
            for (int& value : a) {
                value = static_cast<int>(gen() % 25);
            }
            std::sort(a.begin(), a.end());
            for (int x = -1; x <= 26; x++) {
                int expected = static_cast<int>(std::lower_bound(a.begin(), a.end(), x) - a.begin());
                assert(first_at_least(a, x) == expected);
                assert(first_at_least_checked(a, x, nullptr) == expected);
            }
        }
    }
}

void test_wrong_searches() {
    std::vector<int> a = {2, 4, 6, 8, 10};
    assert(first_at_least(a, 10) == 4);
    assert(search_weak_invariant(a, 10) == 3);
    // La invariante débil sí se cumple al salir: todo lo que está a la izquierda es menor.
    for (int i = 0; i < 3; i++) assert(a[i] < 10);
    // Y aun así a[3] no es mayor o igual que 10.
    assert(a[3] < 10);
    assert(search_lo_is_mid({2, 4}, 9, 1000) == -1);
    assert(first_at_least({2, 4}, 9) == 2);
}

long long slow_power(long long b, long long e, long long m) {
    long long result = 1 % m;
    for (long long i = 0; i < e; i++) {
        result = result * (b % m) % m;
    }
    return result;
}

int floor_log2(long long e) {
    int result = 0;
    while (e > 1) {
        e /= 2;
        result++;
    }
    return result;
}

int bits_on(long long e) {
    int result = 0;
    for (; e > 0; e /= 2) {
        result += static_cast<int>(e % 2);
    }
    return result;
}

void test_power() {
    for (long long m : {1LL, 2LL, 7LL, 1000LL, 1000000007LL, 2147483648LL}) {
        for (long long b : {0LL, 1LL, 2LL, 3LL, 10LL, 2147483647LL}) {
            for (long long e = 0; e <= 300; e++) {
                assert(power_mod(b, e, m) == slow_power(b, e, m));
            }
        }
    }
    // Exactamente ⌊log e⌋ + 1 cuadrados, más un producto por cada bit 1 de e.
    for (long long e = 1; e <= 5000; e++) {
        long long multiplications = 0;
        power_mod(3, e, 1000, &multiplications);
        assert(multiplications == floor_log2(e) + 1 + bits_on(e));
        assert(multiplications <= 2 * (floor_log2(e) + 1));
    }
}

bool prefers(const std::vector<int>& list, int a, int b) {
    return std::find(list.begin(), list.end(), a) < std::find(list.begin(), list.end(), b);
}

// Elige al proponente libre al azar: el resultado no debe cambiar.
std::vector<int> gale_shapley_any_order(const Preferences& proposers, const Preferences& receivers,
                                        std::mt19937& gen) {
    int n = static_cast<int>(proposers.size());
    std::vector<int> next_choice(n, 0);
    std::vector<int> holder(n, -1);
    std::vector<int> free_proposers(n);
    std::iota(free_proposers.begin(), free_proposers.end(), 0);
    while (!free_proposers.empty()) {
        std::swap(free_proposers[gen() % free_proposers.size()], free_proposers.back());
        int p = free_proposers.back();
        free_proposers.pop_back();
        int r = proposers[p][next_choice[p]++];
        if (holder[r] == -1) {
            holder[r] = p;
        } else if (prefers(receivers[r], p, holder[r])) {
            free_proposers.push_back(holder[r]);
            holder[r] = p;
        } else {
            free_proposers.push_back(p);
        }
    }
    std::vector<int> partner(n);
    for (int r = 0; r < n; r++) {
        partner[holder[r]] = r;
    }
    return partner;
}

// Los teoremas, contra la enumeración de todos los matchings.
void test_theorems_by_brute_force() {
    std::mt19937 gen(7);
    for (int n = 1; n <= 6; n++) {
        for (int round = 0; round < 400; round++) {
            Preferences proposers = random_preferences(n, gen);
            Preferences receivers = random_preferences(n, gen);
            Matching result = gale_shapley(proposers, receivers);

            // Es un matching perfecto y estable.
            std::vector<bool> used(n, false);
            for (int r : result.partner) {
                assert(!used[r]);
                used[r] = true;
            }
            assert(!find_unstable_pair(result.partner, proposers, receivers));

            // Cota de propuestas, y la cota más fina del ejercicio.
            assert(result.proposals <= static_cast<long long>(n) * n);
            assert(result.proposals <= static_cast<long long>(n) * n - n + 1);

            // Cada proponente hace tantas propuestas como la posición de su pareja, contando desde 1.
            long long positions = 0;
            for (int p = 0; p < n; p++) {
                positions += 1 + (std::find(proposers[p].begin(), proposers[p].end(), result.partner[p]) - proposers[p].begin());
            }
            assert(result.proposals == positions);

            // Da lo mismo con la lista y en cualquier orden.
            long long steps = 0;
            assert(gale_shapley_scan(proposers, receivers, steps).partner == result.partner);
            assert(gale_shapley_any_order(proposers, receivers, gen) == result.partner);

            std::vector<std::vector<int>> stable = all_stable_matchings(proposers, receivers);
            assert(!stable.empty());
            assert(std::find(stable.begin(), stable.end(), result.partner) != stable.end());

            std::vector<int> holder(n);
            for (int p = 0; p < n; p++) {
                holder[result.partner[p]] = p;
            }
            for (const std::vector<int>& other : stable) {
                for (int p = 0; p < n; p++) {
                    // Ningún proponente tiene algo mejor en otro matching estable.
                    assert(other[p] == result.partner[p] || prefers(proposers[p], result.partner[p], other[p]));
                    // Ningún receptor tiene algo peor en otro matching estable.
                    int r = other[p];
                    assert(p == holder[r] || prefers(receivers[r], p, holder[r]));
                }
            }
        }
    }
}

void test_examples_of_the_notes() {
    // La idea de la primera oferta da un par inestable en el ejemplo.
    Preferences students = example_students();
    Preferences advisors = example_advisors();
    assert(find_unstable_pair(first_offer_matching(students), students, advisors).has_value());
    assert(gale_shapley(students, advisors).proposals == 9);

    // La instancia cruzada tiene dos matchings estables.
    Preferences crossed_t = crossed_students();
    Preferences crossed_a = crossed_advisors();
    assert(all_stable_matchings(crossed_t, crossed_a).size() == 2);
    assert((gale_shapley(crossed_t, crossed_a).partner == std::vector<int>{0, 1}));
    assert((gale_shapley(crossed_a, crossed_t).partner == std::vector<int>{1, 0}));

    // Con las listas iguales hay exactamente n(n + 1)/2 propuestas.
    for (int n : {1, 2, 3, 10, 57, 200}) {
        Matching result = gale_shapley(same_list_proposers(n), latest_wins_receivers(n));
        assert(result.proposals == static_cast<long long>(n) * (n + 1) / 2);
    }
}

}  // namespace

int main() {
    test_binary_search();
    test_wrong_searches();
    test_power();
    test_theorems_by_brute_force();
    test_examples_of_the_notes();
    std::cout << "test_examples: todo correcto\n";
}