// Pruebas de Graph, MatrixGraph, los recorridos y CountingForest: casos dirigidos, y grafos al azar con
// semilla fija. La biblioteca estándar no trae grafos: la referencia es un cálculo por fuerza bruta.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <utility>
#include <vector>

#include "counting_forest.h"
#include "graph.h"
#include "matrix_graph.h"
#include "sample_graphs.h"
#include "traversals.h"

// Permite dañar un grafo, para ver si check_invariants lo nota.
struct GraphTestAccess {
    static std::vector<std::vector<Edge>>& lists(Graph& graph) { return graph.adjacency_; }
};

namespace {

Graph random_graph(int n, int edges, std::mt19937& rng, bool directed = false) {
    Graph graph(n, directed);
    std::set<std::pair<int, int>> seen;
    for (int i = 0; i < edges; i++) {
        int u = static_cast<int>(rng() % n);
        int v = static_cast<int>(rng() % n);
        if (!directed && u > v) {
            std::swap(u, v);
        }
        if (u != v && seen.insert({u, v}).second) {
            graph.add_edge(u, v);
        }
    }
    return graph;
}

std::vector<int> brute_distances(const Graph& graph, int source) {
    int n = graph.node_count();
    std::vector<int> distance(n, -1);
    distance[source] = 0;
    bool changed = true;
    while (changed) {
        changed = false;
        for (int u = 0; u < n; u++) {
            for (const Edge& edge : graph.neighbors(u)) {
                if (distance[u] != -1 && (distance[edge.to] == -1 || distance[u] + 1 < distance[edge.to])) {
                    distance[edge.to] = distance[u] + 1;
                    changed = true;
                }
            }
        }
    }
    return distance;
}

void test_graph_basics() {
    Graph graph = class_graph();
    assert(graph.node_count() == 7);
    assert(graph.edge_count() == 8);
    assert(graph.has_edge(5, 6) && graph.has_edge(6, 5));
    assert(!graph.has_edge(0, 6));
    assert(graph.check_invariants());
    Graph directed(3, true);
    directed.add_edge(0, 1, 7);
    assert(directed.has_edge(0, 1) && !directed.has_edge(1, 0));
    assert(directed.neighbors(0)[0].weight == 7);
    assert(directed.check_invariants());
}

void test_check_invariants_notices_damage() {
    Graph lost_pair = class_graph();
    GraphTestAccess::lists(lost_pair)[0].pop_back();
    assert(!lost_pair.check_invariants());
    Graph swapped = class_graph();
    GraphTestAccess::lists(swapped)[0][0].to = 6;
    assert(!swapped.check_invariants());
    Graph out_of_range = class_graph();
    GraphTestAccess::lists(out_of_range)[0][0].to = 7;
    assert(!out_of_range.check_invariants());
    Graph other_weight = class_graph();
    GraphTestAccess::lists(other_weight)[0][0].weight = 9;
    assert(!other_weight.check_invariants());
}

void test_matrix_agrees_with_lists() {
    std::mt19937 rng(14);
    Graph lists = random_graph(60, 200, rng);
    MatrixGraph matrix(60);
    for (int u = 0; u < 60; u++) {
        for (const Edge& edge : lists.neighbors(u)) {
            if (u < edge.to) {
                matrix.add_edge(u, edge.to);
            }
        }
    }
    assert(matrix.check_invariants());
    for (int u = 0; u < 60; u++) {
        for (int v = 0; v < 60; v++) {
            assert(matrix.has_edge(u, v) == lists.has_edge(u, v));
        }
    }
}

void test_bfs_by_hand() {
    BfsResult result = bfs(class_graph(), 0);
    assert((result.order == std::vector<int>{0, 1, 2, 3, 4, 5, 6}));
    assert((result.distance == std::vector<int>{0, 1, 1, 2, 2, 3, 4}));
    assert((path_to(result.parent, 6) == std::vector<int>{0, 1, 3, 5, 6}));
    Graph apart(3);
    apart.add_edge(0, 1);
    BfsResult partial = bfs(apart, 0);
    assert(partial.distance[2] == -1);
    assert(path_to(partial.parent, 2).empty());
    assert((path_to(partial.parent, 0) == std::vector<int>{0}));
}

void test_bfs_random() {
    std::mt19937 rng(14);
    for (int round = 0; round < 200; round++) {
        int n = 1 + static_cast<int>(rng() % 50);
        Graph graph = random_graph(n, static_cast<int>(rng() % (3 * n)), rng);
        int source = static_cast<int>(rng() % n);
        BfsResult result = bfs(graph, source);
        assert(result.distance == brute_distances(graph, source));
        for (std::size_t i = 0; i + 1 < result.order.size(); i++) {
            assert(result.distance[result.order[i]] <= result.distance[result.order[i + 1]]);
        }
        for (int v = 0; v < n; v++) {
            std::vector<int> path = path_to(result.parent, v);
            assert(static_cast<int>(path.size()) - 1 == result.distance[v] || (path.empty() && result.distance[v] == -1));
        }
    }
}

void test_dfs_versions_agree() {
    std::mt19937 rng(21);
    for (int round = 0; round < 200; round++) {
        int n = 1 + static_cast<int>(rng() % 50);
        Graph graph = random_graph(n, static_cast<int>(rng() % (3 * n)), rng);
        int source = static_cast<int>(rng() % n);
        std::vector<int> recursive = dfs_recursive(graph, source);
        assert(recursive == dfs_iterative(graph, source));
        std::vector<int> by_stack = stack_search(graph, source);
        std::vector<int> by_bfs = bfs(graph, source).order;
        std::sort(recursive.begin(), recursive.end());
        std::sort(by_stack.begin(), by_stack.end());
        std::sort(by_bfs.begin(), by_bfs.end());
        assert(recursive == by_stack);
        assert(recursive == by_bfs);
    }
}

void test_components_against_forest() {
    std::mt19937 rng(7);
    for (int round = 0; round < 200; round++) {
        int n = 1 + static_cast<int>(rng() % 60);
        Graph graph = random_graph(n, static_cast<int>(rng() % (2 * n)), rng);
        CountingForest forest(n, true, true);
        for (int u = 0; u < n; u++) {
            for (const Edge& edge : graph.neighbors(u)) {
                forest.unite(u, edge.to);
            }
        }
        std::vector<int> labels = component_labels(graph);
        assert(*std::max_element(labels.begin(), labels.end()) + 1 == forest.sets());
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                assert((labels[a] == labels[b]) == (forest.find(a) == forest.find(b)));
            }
        }
    }
}

// Un grafo no dirigido sin ciclos es un bosque: exactamente V - C aristas.
void test_undirected_cycles_random() {
    std::mt19937 rng(9);
    for (int round = 0; round < 300; round++) {
        int n = 1 + static_cast<int>(rng() % 30);
        Graph graph = random_graph(n, static_cast<int>(rng() % (n + 2)), rng);
        std::vector<int> labels = component_labels(graph);
        int components = *std::max_element(labels.begin(), labels.end()) + 1;
        bool is_forest = static_cast<int>(graph.edge_count()) == n - components;
        assert(has_cycle_undirected(graph) == !is_forest);
    }
}

// Un grafo dirigido no tiene ciclos si y solo si se puede vaciar quitando nodos sin entradas.
void test_directed_cycles_random() {
    std::mt19937 rng(11);
    for (int round = 0; round < 300; round++) {
        int n = 1 + static_cast<int>(rng() % 20);
        Graph graph = random_graph(n, static_cast<int>(rng() % (2 * n)), rng, true);
        std::vector<int> incoming(n, 0);
        for (int u = 0; u < n; u++) {
            for (const Edge& edge : graph.neighbors(u)) {
                incoming[edge.to]++;
            }
        }
        std::vector<int> ready;
        for (int u = 0; u < n; u++) {
            if (incoming[u] == 0) {
                ready.push_back(u);
            }
        }
        int removed = 0;
        while (!ready.empty()) {
            int u = ready.back();
            ready.pop_back();
            removed++;
            for (const Edge& edge : graph.neighbors(u)) {
                if (--incoming[edge.to] == 0) {
                    ready.push_back(edge.to);
                }
            }
        }
        assert(has_cycle_directed(graph) == (removed != n));
    }
}

void test_forest_variants_agree() {
    for (bool by_rank : {false, true}) {
        for (bool compress : {false, true}) {
            std::mt19937 rng(5);
            int n = 200;
            CountingForest forest(n, by_rank, compress);
            std::vector<int> label(n);
            for (int i = 0; i < n; i++) {
                label[i] = i;
            }
            int sets = n;
            for (int step = 0; step < 2000; step++) {
                int a = static_cast<int>(rng() % n);
                int b = static_cast<int>(rng() % n);
                if (step % 2 == 0) {
                    bool different = label[a] != label[b];
                    assert(forest.unite(a, b) == different);
                    if (different) {
                        int from = label[a];
                        std::replace(label.begin(), label.end(), from, label[b]);
                        sets--;
                    }
                } else {
                    assert((forest.find(a) == forest.find(b)) == (label[a] == label[b]));
                }
                assert(forest.sets() == sets);
                assert(forest.check_invariants());
            }
        }
    }
}

// Con rango y sin compresión, el rango de una raíz es la altura, y no pasa de log2 n.
void test_rank_bounds_height() {
    std::mt19937 rng(6);
    int n = 4096;
    CountingForest forest(n, true, false);
    for (int step = 0; step < 3 * n; step++) {
        forest.unite(static_cast<int>(rng() % n), static_cast<int>(rng() % n));
    }
    assert(forest.height() <= 12);
    for (int x = 0; x < n; x++) {
        if (forest.parents()[x] == x) {
            int tallest = 0;
            for (int y = 0; y < n; y++) {
                if (forest.find(y) == x) {
                    tallest = std::max(tallest, forest.depth(y));
                }
            }
            assert(tallest == forest.ranks()[x]);
        }
    }
}

// Con compresión, el rango de una raíz queda como cota: puede ser mayor que la altura.
void test_compression_leaves_rank_as_bound() {
    CountingForest forest(8, true, true);
    for (auto [a, b] : std::vector<std::pair<int, int>>{{0, 1}, {2, 3}, {0, 2}, {4, 5}, {6, 7}, {4, 6}, {0, 4}}) {
        forest.unite(a, b);
    }
    assert(forest.height() == 3);
    assert(forest.ranks()[0] == 3);
    for (int x = 0; x < 8; x++) {
        forest.find(x);
    }
    assert(forest.height() == 1);
    assert(forest.ranks()[0] == 3);
    assert(forest.shape(0) == "0(1,2,3,4,5,6,7)");
}

}  // namespace

int main() {
    test_graph_basics();
    test_check_invariants_notices_damage();
    test_matrix_agrees_with_lists();
    test_bfs_by_hand();
    test_bfs_random();
    test_dfs_versions_agree();
    test_components_against_forest();
    test_undirected_cycles_random();
    test_directed_cycles_random();
    test_forest_variants_agree();
    test_rank_bounds_height();
    test_compression_leaves_rank_as_bound();
    std::cout << "todas las pruebas pasaron\n";
    return 0;
}