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

#include "digraph.h"
#include "mst.h"

namespace {

std::vector<Edge> class_graph() {
    return {{0, 1, 7}, {0, 3, 5}, {1, 2, 8}, {1, 3, 9}, {1, 4, 6}, {2, 4, 4},
            {3, 4, 15}, {3, 5, 10}, {4, 5, 12}, {4, 6, 11}, {5, 6, 13}};
}

int random_int(std::mt19937& rng, int low, int high) {
    return low + static_cast<int>(rng() % static_cast<unsigned>(high - low + 1));
}

// Grafo conexo al azar: un árbol más algunas aristas. max_weight chico produce empates.
std::vector<Edge> random_connected(std::mt19937& rng, int n, int extra, int max_weight) {
    std::vector<Edge> edges;
    for (int v = 1; v < n; v++) edges.push_back({random_int(rng, 0, v - 1), v, random_int(rng, 1, max_weight)});
    for (int i = 0; i < extra; i++) {
        int a = random_int(rng, 0, n - 1);
        int b = random_int(rng, 0, n - 1);
        if (a != b) edges.push_back({a, b, random_int(rng, 1, max_weight)});
    }
    return edges;
}

long long best_cost_brute(int n, const std::vector<Edge>& edges) {
    auto trees = all_minimum_trees(n, edges);
    long long cost = 0;
    for (int c : trees.at(0)) cost += edges[c].weight;
    return cost;
}

// El grafo de la clase: Kruskal, Prim y la fuerza bruta dan 43, y las ideas falsas no.
void test_class_graph() {
    std::vector<Edge> edges = class_graph();
    assert(total_weight(kruskal(7, edges)) == 43);
    for (int source = 0; source < 7; source++) {
        PrimResult p = prim(7, edges, source);
        assert(is_spanning_tree(7, p.tree));
        assert(total_weight(p.tree) == 43);
        assert(p.pushes <= static_cast<long long>(edges.size()));  // borrado perezoso: a lo sumo E entradas
    }
    assert(best_cost_brute(7, edges) == 43);
    assert(all_minimum_trees(7, edges).size() == 1);  // pesos distintos: uno solo

    assert(!is_spanning_tree(7, cheapest_edges_only(7, edges)));
    assert(count_components(7, cheapest_per_node(7, edges)) > 1);
    std::vector<Edge> paths = dijkstra(7, edges, 0).tree;
    assert(is_spanning_tree(7, paths));
    assert(total_weight(paths) > 43);
}

// Propiedad del corte con pesos distintos: la más barata de cualquier corte está en el único árbol mínimo.
void test_cut_property_distinct() {
    std::mt19937 rng(61);
    for (int round = 0; round < 200; round++) {
        int n = random_int(rng, 2, 6);
        std::vector<Edge> edges = random_connected(rng, n, random_int(rng, 0, 6), 1000);
        // Pesos distintos.
        for (int i = 0; i < static_cast<int>(edges.size()); i++) edges[i].weight = edges[i].weight * 100 + i;
        auto minimum = all_minimum_trees(n, edges);
        assert(minimum.size() == 1);
        for (int mask = 1; mask + 1 < (1 << n); mask++) {
            int cheapest = -1;
            for (int i = 0; i < static_cast<int>(edges.size()); i++) {
                bool crosses = ((mask >> edges[i].u) & 1) != ((mask >> edges[i].v) & 1);
                if (crosses && (cheapest == -1 || edges[i].weight < edges[cheapest].weight)) cheapest = i;
            }
            assert(cheapest != -1);
            assert(std::count(minimum[0].begin(), minimum[0].end(), cheapest) == 1);
        }
    }
}

// Versión con empates: si F está en un árbol mínimo, ningún lado de F cruza el corte y e es una de
// las más baratas que lo cruzan, entonces F más e está en algún árbol mínimo.
void test_cut_property_ties() {
    std::mt19937 rng(62);
    long long checked = 0;
    for (int round = 0; round < 120; round++) {
        int n = random_int(rng, 2, 6);
        std::vector<Edge> edges = random_connected(rng, n, random_int(rng, 0, 6), 3);
        auto minimum = all_minimum_trees(n, edges);
        std::vector<std::set<int>> tree_sets;
        for (const auto& tree : minimum) tree_sets.emplace_back(tree.begin(), tree.end());

        // F: un subconjunto al azar de un árbol mínimo al azar.
        for (int attempt = 0; attempt < 8; attempt++) {
            const auto& base = minimum[static_cast<std::size_t>(random_int(rng, 0, static_cast<int>(minimum.size()) - 1))];
            std::set<int> forest;
            for (int c : base) {
                if (rng() % 2 == 0) forest.insert(c);
            }
            for (int mask = 1; mask + 1 < (1 << n); mask++) {
                auto crosses = [&](int i) { return ((mask >> edges[i].u) & 1) != ((mask >> edges[i].v) & 1); };
                bool respected = std::none_of(forest.begin(), forest.end(), crosses);
                if (!respected) continue;
                int low = -1;
                for (int i = 0; i < static_cast<int>(edges.size()); i++) {
                    if (crosses(i) && (low == -1 || edges[i].weight < low)) low = edges[i].weight;
                }
                for (int i = 0; i < static_cast<int>(edges.size()); i++) {
                    if (!crosses(i) || edges[i].weight != low) continue;
                    bool found = false;
                    for (const std::set<int>& tree : tree_sets) {
                        if (tree.count(i) == 0) continue;
                        found = std::includes(tree.begin(), tree.end(), forest.begin(), forest.end());
                        if (found) break;
                    }
                    assert(found);
                    checked++;
                }
            }
        }
    }
    assert(checked > 0);
}

// El triángulo con tres pesos iguales: tres árboles mínimos, y ninguna arista está en todos.
void test_triangle_ties() {
    std::vector<Edge> triangle = {{0, 1, 1}, {0, 2, 1}, {1, 2, 1}};
    auto minimum = all_minimum_trees(3, triangle);
    assert(minimum.size() == 3);
    for (int edge = 0; edge < 3; edge++) {
        int contained = 0;
        for (const auto& tree : minimum) contained += static_cast<int>(std::count(tree.begin(), tree.end(), edge));
        assert(contained == 2);
    }
    assert(!is_spanning_tree(3, triangle));  // las tres juntas no son un árbol
}

// Kruskal y Prim contra la fuerza bruta, con muchos empates y con pesos negativos.
void test_mst_algorithms_random() {
    std::mt19937 rng(63);
    for (int round = 0; round < 600; round++) {
        int n = random_int(rng, 1, 7);
        std::vector<Edge> edges = random_connected(rng, n, random_int(rng, 0, 7), random_int(rng, 1, 5));
        if (round % 3 == 0) {
            for (Edge& e : edges) e.weight -= 3;
        }
        long long best = n == 1 ? 0 : best_cost_brute(n, edges);
        std::vector<Edge> k = kruskal(n, edges);
        assert(is_spanning_tree(n, k) || n == 1);
        assert(total_weight(k) == best);
        std::vector<Edge> shuffled = edges;
        std::shuffle(shuffled.begin(), shuffled.end(), rng);
        assert(total_weight(kruskal(n, shuffled)) == best);
        for (int source = 0; source < n; source++) {
            assert(total_weight(prim(n, edges, source).tree) == best);
        }
    }
}

// Sobre un grafo desconexo, Kruskal da un bosque, con un árbol por componente.
void test_forest() {
    std::vector<Edge> edges = {{0, 1, 3}, {1, 2, 1}, {0, 2, 2}, {3, 4, 5}};
    std::vector<Edge> forest = kruskal(6, edges);
    assert(forest.size() == 3);
    assert(total_weight(forest) == 8);
    assert(count_components(6, forest) == 3);
}

// Triángulo: el árbol mínimo no contiene el camino mínimo, y el árbol de caminos no es mínimo.
void test_mst_is_not_paths() {
    std::vector<Edge> triangle = {{0, 1, 2}, {1, 2, 2}, {0, 2, 3}};
    std::vector<Edge> mst = kruskal(3, triangle);
    assert(total_weight(mst) == 4);
    assert(dijkstra(3, mst, 0).dist[2] == 4);
    assert(dijkstra(3, triangle, 0).dist[2] == 3);
    assert(total_weight(dijkstra(3, triangle, 0).tree) == 5);
}

// Sumar una constante: el árbol mínimo es el mismo y el camino mínimo cambia.
void test_add_constant() {
    std::vector<Edge> square = {{0, 1, 1}, {1, 2, 1}, {0, 2, 3}, {2, 3, 2}, {1, 3, 4}};
    assert(dijkstra(4, square, 0).dist[2] == 2);
    std::vector<Edge> shifted = square;
    for (Edge& e : shifted) e.weight += 2;
    assert(dijkstra(4, shifted, 0).dist[2] == 5);  // ahora la directa, con costo 3 + 2
    assert(total_weight(kruskal(4, shifted)) == total_weight(kruskal(4, square)) + 3 * 2);

    std::mt19937 rng(64);
    for (int round = 0; round < 200; round++) {
        int n = random_int(rng, 2, 6);
        std::vector<Edge> edges = random_connected(rng, n, 5, 1000);
        for (int i = 0; i < static_cast<int>(edges.size()); i++) edges[i].weight = edges[i].weight * 100 + i;
        auto before = all_minimum_trees(n, edges);
        std::vector<Edge> moved = edges;
        int c = random_int(rng, 1, 500);
        for (Edge& e : moved) e.weight += c;
        assert(all_minimum_trees(n, moved) == before);
    }
}

// Agrupar: quitar las k - 1 más caras alcanza la mayor separación entre todas las particiones.
void test_clustering() {
    std::mt19937 rng(65);
    for (int round = 0; round < 300; round++) {
        int n = random_int(rng, 2, 7);
        std::vector<Edge> edges = random_connected(rng, n, random_int(rng, 0, 10), random_int(rng, 2, 9));
        for (int k = 2; k <= n; k++) {
            std::vector<int> group = max_spacing_groups(n, edges, k);
            assert(*std::max_element(group.begin(), group.end()) == k - 1);  // exactamente k grupos
            assert(spacing(edges, group) == best_spacing_brute(n, edges, k));
        }
    }
}

// Tipos de arista: el ejemplo de la clase, y las condiciones con tiempos.
void test_dfs_times() {
    Digraph g = {{1, 2, 3}, {2}, {0}, {2}, {3, 5}, {4}};
    std::vector<ClassifiedEdge> kinds;
    DfsTimes t = dfs_recursive(g, &kinds);
    assert((t.start == std::vector<int>{1, 2, 3, 6, 9, 10}));
    assert((t.finish == std::vector<int>{8, 5, 4, 7, 12, 11}));
    std::map<std::pair<int, int>, EdgeKind> found;
    for (const ClassifiedEdge& e : kinds) found[{e.u, e.v}] = e.kind;
    assert((found[{0, 1}] == EdgeKind::tree));
    assert((found[{0, 2}] == EdgeKind::forward));
    assert((found[{2, 0}] == EdgeKind::back));
    assert((found[{3, 2}] == EdgeKind::cross));
    assert((found[{4, 3}] == EdgeKind::cross));
    assert((found[{5, 4}] == EdgeKind::back));
}

Digraph random_digraph(std::mt19937& rng, int n, int m) {
    Digraph g(static_cast<std::size_t>(n));
    for (int i = 0; i < m; i++) {
        g[static_cast<std::size_t>(random_int(rng, 0, n - 1))].push_back(random_int(rng, 0, n - 1));
    }
    return g;
}

Digraph random_dag(std::mt19937& rng, int n, int m) {
    std::vector<int> label(static_cast<std::size_t>(n));
    for (int i = 0; i < n; i++) label[i] = i;
    std::shuffle(label.begin(), label.end(), rng);
    Digraph g(static_cast<std::size_t>(n));
    if (n < 2) return g;
    for (int i = 0; i < m; i++) {
        int a = random_int(rng, 0, n - 2);
        int b = random_int(rng, a + 1, n - 1);
        g[label[a]].push_back(label[b]);
    }
    return g;
}

// En grafos al azar: los intervalos se anidan o no se tocan, la pila explícita da los mismos
// tiempos, y hay arista hacia atrás si y solo si hay un ciclo.
void test_dfs_random() {
    std::mt19937 rng(66);
    for (int round = 0; round < 1500; round++) {
        int n = random_int(rng, 1, 9);
        Digraph g = random_digraph(rng, n, random_int(rng, 0, 2 * n));
        std::vector<ClassifiedEdge> kinds;
        DfsTimes t = dfs_recursive(g, &kinds);
        DfsTimes it = dfs_iterative(g);
        assert(t.start == it.start);
        assert(t.finish == it.finish);
        assert(t.finish_order == it.finish_order);

        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (u == v) continue;
                bool disjoint = t.finish[u] < t.start[v] || t.finish[v] < t.start[u];
                bool u_in_v = t.start[v] < t.start[u] && t.finish[u] < t.finish[v];
                bool v_in_u = t.start[u] < t.start[v] && t.finish[v] < t.finish[u];
                assert(disjoint || u_in_v || v_in_u);
            }
        }

        bool has_back = false;
        for (const ClassifiedEdge& e : kinds) {
            has_back = has_back || e.kind == EdgeKind::back;
            switch (e.kind) {
                case EdgeKind::back:
                    assert(t.start[e.v] <= t.start[e.u] && t.finish[e.u] <= t.finish[e.v]);
                    break;
                case EdgeKind::tree:
                case EdgeKind::forward:
                    assert(t.start[e.u] < t.start[e.v] && t.finish[e.v] < t.finish[e.u]);
                    break;
                case EdgeKind::cross:
                    assert(t.finish[e.v] < t.start[e.u]);
                    break;
            }
        }
        auto reach = reach_matrix(g);
        bool has_cycle = false;
        for (int v = 0; v < n; v++) has_cycle = has_cycle || reach[v][v];
        assert(has_back == has_cycle);
    }
}

// En un DAG, toda arista u -> v tiene fin[v] < fin[u], y el orden decreciente de fin es topológico.
void test_topological() {
    std::mt19937 rng(67);
    for (int round = 0; round < 1000; round++) {
        int n = random_int(rng, 1, 10);
        Digraph g = random_dag(rng, n, random_int(rng, 0, 3 * n));
        DfsTimes t = dfs_recursive(g);
        for (int u = 0; u < n; u++) {
            for (int v : g[u]) assert(t.finish[v] < t.finish[u]);
        }
        assert(is_topological(g, reverse_finish_order(g)));
    }
    // Con un ciclo, el orden existe como lista, pero no es topológico.
    Digraph cycle = {{1}, {2}, {0, 3}, {}};
    assert(!is_topological(cycle, reverse_finish_order(cycle)));
}

// El atajo de meter todos los vecinos no da los tiempos de fin.
void test_stack_shortcut() {
    Digraph small = {{1, 2}, {2}, {}};
    std::vector<int> shortcut = stack_shortcut_order(small);
    assert((shortcut == std::vector<int>{0, 2, 1}));
    std::vector<int> back(shortcut.rbegin(), shortcut.rend());
    assert(!is_topological(small, shortcut));
    assert(!is_topological(small, back));
    assert(is_topological(small, reverse_finish_order(small)));
}

// Kosaraju-Sharir contra la definición, y en orden de sumidero a fuente.
void test_kosaraju() {
    std::mt19937 rng(68);
    int wrong_without_reversing = 0;
    for (int round = 0; round < 3000; round++) {
        int n = random_int(rng, 1, 9);
        Digraph g = random_digraph(rng, n, random_int(rng, 0, 2 * n));
        std::vector<int> comp = strong_components(g);
        assert(same_partition(comp, components_brute(g)));
        for (int u = 0; u < n; u++) {
            for (int v : g[u]) assert(comp[v] <= comp[u]);  // toda arista va a una componente ya hallada
        }
        // El mismo resultado sobre el grafo invertido, porque las componentes son las mismas.
        assert(same_partition(strong_components(reversed(g)), comp));
        // Lema: si hay arista de C a D en el original, en el invertido fin(D) > fin(C).
        DfsTimes t = dfs_recursive(reversed(g));
        std::map<int, int> top_finish;
        for (int v = 0; v < n; v++) top_finish[comp[v]] = std::max(top_finish[comp[v]], t.finish[v]);
        for (int u = 0; u < n; u++) {
            for (int v : g[u]) {
                if (comp[u] != comp[v]) assert(top_finish[comp[v]] > top_finish[comp[u]]);
            }
        }
        if (!same_partition(components_without_reversing(g), comp)) wrong_without_reversing++;
    }
    assert(wrong_without_reversing > 0);

    // El ejemplo de la clase.
    Digraph g = make_digraph(8, {{0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 4}, {4, 5}, {5, 3}, {6, 5}, {6, 7}, {7, 6}});
    assert(same_partition(strong_components(g), {0, 0, 0, 1, 1, 1, 2, 2}));
    assert(!same_partition(components_without_reversing(g), {0, 0, 0, 1, 1, 1, 2, 2}));
}

// Con pila explícita se puede recorrer un camino que agotaría la pila de llamadas.
void test_deep_iterative() {
    int n = 300000;
    Digraph path(static_cast<std::size_t>(n));
    for (int i = 0; i + 1 < n; i++) path[i].push_back(i + 1);
    DfsTimes t = dfs_iterative(path);
    assert(t.finish[0] == 2 * n);
    assert(t.finish[n - 1] == n + 1);
    std::vector<int> comp = strong_components(path);
    assert(comp[0] == n - 1);
}

}  // namespace

int main() {
    test_class_graph();
    test_cut_property_distinct();
    test_cut_property_ties();
    test_triangle_ties();
    test_mst_algorithms_random();
    test_forest();
    test_mst_is_not_paths();
    test_add_constant();
    test_clustering();
    test_dfs_times();
    test_dfs_random();
    test_topological();
    test_stack_shortcut();
    test_kosaraju();
    test_deep_iterative();
    std::cout << "Todas las pruebas de la semana 6 pasaron.\n";
}