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

#include "huffman.h"
#include "scheduling.h"
#include "shortest_paths.h"
#include "state_graph.h"
#include "toll_mistakes.h"

namespace {

int below(std::mt19937& rng, int limit) { return static_cast<int>(rng() % static_cast<unsigned>(limit)); }

// ---------- Retraso máximo ----------

void test_lateness_counterexamples() {
    std::vector<Job> a = {{1, 100}, {10, 10}};
    assert(brute_min_max_lateness(a) == 0);
    assert(max_lateness(a, order_by_duration(a)) == 1);
    assert(max_lateness(a, order_by_deadline(a)) == 0);
    std::vector<Job> b = {{1, 2}, {10, 10}};
    assert(brute_min_max_lateness(b) == 1);
    assert(max_lateness(b, order_by_slack(b)) == 9);
    assert(max_lateness(b, order_by_deadline(b)) == 1);
}

std::vector<Job> random_jobs(std::mt19937& rng, int n) {
    std::vector<Job> jobs;
    for (int i = 0; i < n; i++) {
        jobs.push_back({1 + below(rng, 6), below(rng, 16)});  // plazos en rango chico: muchos empates
    }
    return jobs;
}

void test_earliest_deadline_is_optimal() {
    std::mt19937 rng(501);
    for (int round = 0; round < 1500; round++) {
        std::vector<Job> jobs = random_jobs(rng, 1 + below(rng, 7));
        assert(max_lateness(jobs, order_by_deadline(jobs)) == brute_min_max_lateness(jobs));
    }
}

// Todos los horarios sin inversiones dan el mismo máximo, sea cual sea el orden dentro de un mismo plazo.
void test_no_inversion_schedules_agree() {
    std::mt19937 rng(502);
    for (int round = 0; round < 300; round++) {
        std::vector<Job> jobs = random_jobs(rng, 1 + below(rng, 7));
        std::vector<int> order(jobs.size());
        std::iota(order.begin(), order.end(), 0);
        long long expected = max_lateness(jobs, order_by_deadline(jobs));
        do {
            if (count_inversions(jobs, order) == 0) {
                assert(max_lateness(jobs, order) == expected);
            }
        } while (std::next_permutation(order.begin(), order.end()));
    }
}

// Cambiar un par adyacente invertido quita exactamente una inversión y no sube el máximo.
// Sin inversiones adyacentes no hay ninguna inversión.
void test_adjacent_swaps() {
    std::mt19937 rng(503);
    for (int round = 0; round < 2000; round++) {
        std::vector<Job> jobs = random_jobs(rng, 2 + below(rng, 7));
        std::vector<int> order(jobs.size());
        std::iota(order.begin(), order.end(), 0);
        std::shuffle(order.begin(), order.end(), rng);
        long long start = max_lateness(jobs, order);
        while (true) {
            std::size_t i = first_adjacent_inversion(jobs, order);
            if (i == order.size()) {
                assert(count_inversions(jobs, order) == 0);
                break;
            }
            int inversions = count_inversions(jobs, order);
            long long before = max_lateness(jobs, order);
            std::swap(order[i], order[i + 1]);
            assert(count_inversions(jobs, order) == inversions - 1);
            assert(max_lateness(jobs, order) <= before);
        }
        assert(max_lateness(jobs, order) <= start);
        assert(max_lateness(jobs, order) == max_lateness(jobs, order_by_deadline(jobs)));
    }
}

// El ejemplo de cinco tareas: D y E tienen el mismo plazo, y cualquier orden entre ellas da 3.
void test_lateness_example() {
    std::vector<Job> jobs = {{3, 5}, {2, 4}, {1, 7}, {4, 9}, {2, 9}};
    assert(max_lateness(jobs, {1, 0, 2, 3, 4}) == 3);
    assert(max_lateness(jobs, {1, 0, 2, 4, 3}) == 3);
    assert(brute_min_max_lateness(jobs) == 3);
    // Cambiar dos no vecinas puede subir el máximo, aunque estén invertidas.
    std::vector<Job> far = {{1, 5}, {1, 2}, {5, 4}};
    assert(max_lateness(far, {0, 1, 2}) == 3);
    assert(max_lateness(far, {2, 1, 0}) == 4);
}

// ---------- Huffman ----------

void test_huffman_counterexamples() {
    std::vector<long long> freq = {15, 7, 6, 6, 5};
    assert(brute_min_cost(freq) == 87);
    assert(code_cost(freq, top_down_split(freq)) == 89);
    assert(code_cost(freq, huffman(freq).depth) == 87);
    std::vector<long long> flat(8, 1);
    assert(code_cost(flat, chain_code(flat)) == 35);
    assert(code_cost(flat, huffman(flat).depth) == 24);
}

void test_review_question() {
    std::vector<long long> freq = {1, 1, 2, 3, 5, 8};
    HuffmanResult result = huffman(freq);
    assert(code_cost(freq, result.depth) == 45);
    assert(merges_total(result.merges) == 45);
    assert(brute_min_cost(freq) == 45);
    // Esta lista tiene empates de pesos, pero con ellos no se puede armar otro par: un solo árbol.
    assert(huffman_all_ties(freq).size() == 1);
}

void test_two_symbols() {
    std::vector<long long> freq = {3, 9};
    HuffmanResult result = huffman(freq);
    assert(result.depth == (std::vector<int>{1, 1}));
    assert(code_cost(freq, result.depth) == 12);
    assert(brute_min_cost(freq) == 12);
}

// Con empates de verdad hay árboles distintos, y todos cuestan lo mismo.
void test_ties_give_same_cost() {
    std::vector<long long> freq = {1, 1, 2, 2};
    std::set<std::vector<int>> trees = huffman_all_ties(freq);
    assert(trees.size() == 3);
    for (const std::vector<int>& depth : trees) {
        assert(code_cost(freq, depth) == 12);
    }
    assert(brute_min_cost(freq) == 12);
}

void test_huffman_is_optimal() {
    std::mt19937 rng(504);
    for (int round = 0; round < 400; round++) {
        int n = 2 + below(rng, 5);
        std::vector<long long> freq;
        for (int i = 0; i < n; i++) freq.push_back(1 + below(rng, 8));
        long long best = brute_min_cost(freq);
        HuffmanResult result = huffman(freq);
        assert(code_cost(freq, result.depth) == best);
        assert(merges_total(result.merges) == best);  // suma de uniones = suma de frecuencia por profundidad
        for (const std::vector<int>& depth : huffman_all_ties(freq)) {
            assert(code_cost(freq, depth) == best);   // cualquier forma de romper empates
        }
    }
}

// cost(T) = cost(T') + f(x) + f(y): para cada árbol T' del alfabeto reducido, con z = x + y al final,
// se arma T reemplazando la hoja z por x e y como hermanos, y se comparan los dos costos.
void test_cost_relation() {
    std::mt19937 rng(505);
    for (int round = 0; round < 200; round++) {
        int n = 3 + below(rng, 3);
        std::vector<long long> freq;
        for (int i = 0; i < n; i++) freq.push_back(1 + below(rng, 9));
        std::vector<long long> reduced(freq.begin() + 2, freq.end());
        reduced.push_back(freq[0] + freq[1]);
        auto visit = [&](const std::vector<int>& d) {
            std::vector<int> expanded(freq.size(), 0);
            for (std::size_t i = 2; i < freq.size(); i++) expanded[i] = d[i - 2];
            expanded[0] = expanded[1] = d[freq.size() - 2] + 1;
            assert(code_cost(freq, expanded) == code_cost(reduced, d) + freq[0] + freq[1]);
        };
        std::vector<std::vector<int>> groups;
        for (int i = 0; i < n - 1; i++) groups.push_back({i});
        std::vector<int> depth(static_cast<std::size_t>(n - 1), 0);
        all_full_trees(groups, depth, visit);
    }
}

// En un árbol óptimo, un símbolo más frecuente nunca está más hondo que uno menos frecuente.
void test_more_frequent_not_deeper() {
    std::mt19937 rng(506);
    for (int round = 0; round < 200; round++) {
        int n = 2 + below(rng, 4);
        std::vector<long long> freq;
        for (int i = 0; i < n; i++) freq.push_back(1 + below(rng, 6));
        long long best = brute_min_cost(freq);
        std::vector<std::vector<int>> groups;
        for (int i = 0; i < n; i++) groups.push_back({i});
        std::vector<int> depth(freq.size(), 0);
        auto visit = [&](const std::vector<int>& d) {
            if (code_cost(freq, d) != best) return;
            for (std::size_t i = 0; i < freq.size(); i++) {
                for (std::size_t j = 0; j < freq.size(); j++) {
                    if (freq[i] > freq[j]) assert(d[i] <= d[j]);
                }
            }
        };
        all_full_trees(groups, depth, visit);
    }
}

// ---------- Dijkstra ----------

Graph random_graph(std::mt19937& rng, int n, int arcs, int max_weight) {
    Graph graph(static_cast<std::size_t>(n));
    for (int i = 0; i < arcs; i++) {
        add_arc(graph, below(rng, n), below(rng, n), below(rng, max_weight + 1));  // incluye peso 0
    }
    return graph;
}

// Cada nodo, al fijarse, ya tiene su distancia de camino mínimo. Y un nodo se fija una sola vez.
void test_dijkstra_invariant() {
    std::mt19937 rng(507);
    for (int round = 0; round < 2000; round++) {
        int n = 1 + below(rng, 12);
        Graph graph = random_graph(rng, n, below(rng, 40), 9);
        std::vector<long long> truth = relax_until_stable(graph, 0);
        DijkstraResult result = dijkstra(graph, 0);
        std::vector<int> times(static_cast<std::size_t>(n), 0);
        long long previous = 0;
        for (const Pop& pop : result.pops) {
            assert(pop.distance >= previous);  // las distancias salen en orden creciente
            previous = pop.distance;
            if (pop.stale) continue;
            times[static_cast<std::size_t>(pop.node)]++;
            assert(pop.distance == truth[static_cast<std::size_t>(pop.node)]);
        }
        assert(result.distance == truth);
        for (int v = 0; v < n; v++) {
            // Se fijan exactamente los alcanzables.
            assert(times[static_cast<std::size_t>(v)] == (truth[static_cast<std::size_t>(v)] != UNREACHABLE ? 1 : 0));
        }
    }
}

void test_negative_edge() {
    Graph graph(4);
    add_arc(graph, 0, 1, 1);
    add_arc(graph, 0, 2, 4);
    add_arc(graph, 2, 1, -5);
    add_arc(graph, 1, 3, 2);
    std::vector<long long> truth = relax_until_stable(graph, 0);
    DijkstraResult result = dijkstra(graph, 0);
    assert(truth == (std::vector<long long>{0, -1, 4, 1}));
    assert(result.distance[3] == 3);
    assert(result.distance != truth);
}

void test_shifting_changes_winner() {
    Graph graph(4);
    add_arc(graph, 0, 1, 6);
    add_arc(graph, 0, 2, 9);
    add_arc(graph, 2, 1, 0);
    add_arc(graph, 1, 3, 7);
    DijkstraResult result = dijkstra(graph, 0);
    assert((path_to(result.parent, 0, 3) == std::vector<int>{0, 1, 3}));
    assert(result.distance[3] == 13);
}

// Dos ideas parecidas a Dijkstra fallan en sus contraejemplos.
void test_wrong_ideas() {
    Graph first(3);
    add_arc(first, 0, 1, 4);
    add_arc(first, 0, 2, 1);
    add_arc(first, 2, 1, 2);
    assert(fix_on_discovery(first, 0)[1] == 4);
    assert(dijkstra(first, 0).distance[1] == 3);
    Graph second(4);
    add_arc(second, 0, 1, 1);
    add_arc(second, 1, 3, 10);
    add_arc(second, 0, 2, 2);
    add_arc(second, 2, 3, 2);
    assert(cheapest_arc_walk(second, 0, 3) == 11);
    assert(dijkstra(second, 0).distance[3] == 4);
}

// El ejemplo de los apuntes: un arco de peso 0, un nodo sin llegada y dos entradas viejas.
void test_dijkstra_example() {
    Graph graph(6);
    add_arc(graph, 0, 1, 4);
    add_arc(graph, 0, 2, 1);
    add_arc(graph, 2, 1, 2);
    add_arc(graph, 2, 3, 7);
    add_arc(graph, 1, 3, 3);
    add_arc(graph, 3, 4, 0);
    add_arc(graph, 4, 2, 5);
    DijkstraResult result = dijkstra(graph, 0);
    assert(result.distance == (std::vector<long long>{0, 3, 1, 6, 6, UNREACHABLE}));
    int stale = 0;
    for (const Pop& pop : result.pops) stale += pop.stale ? 1 : 0;
    assert(stale == 2);
}

// ---------- Grafo de estados ----------

// Árbitro para el recorrido par: tabla por número de tramos, sin grafo de estados. Un recorrido
// mínimo no repite estado, así que basta mirar hasta 2n tramos.
long long even_walk_table(const Graph& graph, int source, int target) {
    std::size_t n = graph.size();
    std::vector<long long> now(n, UNREACHABLE);
    now[static_cast<std::size_t>(source)] = 0;
    long long best = now[static_cast<std::size_t>(target)];
    for (std::size_t steps = 1; steps <= 2 * n; steps++) {
        std::vector<long long> next(n, UNREACHABLE);
        for (std::size_t u = 0; u < n; u++) {
            if (now[u] == UNREACHABLE) continue;
            for (const Arc& arc : graph[u]) {
                std::size_t to = static_cast<std::size_t>(arc.to);
                next[to] = std::min(next[to], now[u] + arc.weight);
            }
        }
        now = next;
        if (steps % 2 == 0) best = std::min(best, now[static_cast<std::size_t>(target)]);
    }
    return best;
}

void test_even_walks() {
    std::mt19937 rng(508);
    for (int round = 0; round < 2000; round++) {
        int n = 1 + below(rng, 8);
        Graph graph = random_graph(rng, n, below(rng, 16), 9);
        int target = below(rng, n);
        WalkResult result = min_walk_multiple(graph, 0, target, 2);
        assert(result.distance == even_walk_table(graph, 0, target));
        if (result.distance != UNREACHABLE) {
            assert(result.walk.size() % 2 == 1);  // número par de tramos, impar de ciudades
        }
    }
}

// El ejemplo de los choferes: hace falta repetir una ciudad. Sin el triángulo no hay recorrido par.
void test_driver_example() {
    Graph line(6);
    for (auto [a, b, w] : std::vector<std::tuple<int, int, long long>>{{0, 1, 2}, {1, 2, 2}, {2, 3, 2}}) {
        add_arc(line, a, b, w);
        add_arc(line, b, a, w);
    }
    assert(dijkstra(line, 0).distance[3] == 6);
    assert(min_walk_multiple(line, 0, 3, 2).distance == UNREACHABLE);
    Graph graph = line;
    for (auto [a, b, w] : std::vector<std::tuple<int, int, long long>>{{1, 4, 1}, {4, 5, 1}, {5, 1, 1}}) {
        add_arc(graph, a, b, w);
        add_arc(graph, b, a, w);
    }
    WalkResult even = min_walk_multiple(graph, 0, 3, 2);
    assert(even.distance == 9);
    assert(even.walk.size() == 7);  // 6 tramos
    std::set<int> distinct(even.walk.begin(), even.walk.end());
    assert(distinct.size() < even.walk.size());
}

// El ejemplo de los peajes: la respuesta correcta y las dos formas equivocadas.
void test_toll_example() {
    const std::vector<Road> roads = {{0, 2, 2, false}, {2, 1, 3, false}, {0, 1, 1, true}, {1, 3, 1, true}};
    assert(with_one_distance_per_city(4, roads, 0, 3, 1) == NO_ROUTE);
    assert(with_global_counter(4, roads, 0, 3, 1) == NO_ROUTE);
    // Con dos peajes permitidos, la primera forma sí acierta: por eso una prueba suelta no la detecta.
    assert(with_one_distance_per_city(4, roads, 0, 3, 2) == 2);
}

// La cuenta del costo: V * c estados y E * c arcos a lo sumo.
void test_state_counts() {
    std::mt19937 rng(509);
    Graph graph = random_graph(rng, 50, 300, 20);
    for (int c : {1, 2, 3, 5}) {
        WalkResult result = min_walk_multiple(graph, 0, 1, c);
        assert(result.relaxations <= 300 * c);
        assert(result.pops <= 1 + 300 * c);  // una entrada por arco mirado, a lo sumo, y el origen
    }
}

}  // namespace

int main() {
    test_lateness_counterexamples();
    test_earliest_deadline_is_optimal();
    test_no_inversion_schedules_agree();
    test_adjacent_swaps();
    test_lateness_example();
    test_huffman_counterexamples();
    test_review_question();
    test_two_symbols();
    test_ties_give_same_cost();
    test_huffman_is_optimal();
    test_cost_relation();
    test_more_frequent_not_deeper();
    test_dijkstra_invariant();
    test_negative_edge();
    test_shifting_changes_winner();
    test_wrong_ideas();
    test_dijkstra_example();
    test_even_walks();
    test_driver_example();
    test_toll_example();
    test_state_counts();
    std::cout << "Todas las pruebas de la semana 5 pasaron.\n";
}