// Pruebas de los ejemplos: Dijkstra contra un cálculo por fuerza bruta, y lo que dicen los apuntes.
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#include "graph.h"
#include "sample_graphs.h"
#include "shortest_paths.h"
#include "traversals.h"

namespace {

std::vector<Meters> brute_force(const Graph& graph, int source) {
    std::vector<Meters> distance(graph.node_count(), UNREACHABLE);
    distance[source] = 0;
    bool changed = true;
    while (changed) {
        changed = false;
        for (int u = 0; u < graph.node_count(); u++) {
            if (distance[u] == UNREACHABLE) {
                continue;
            }
            for (const Edge& edge : graph.neighbors(u)) {
                if (distance[u] + edge.weight < distance[edge.to]) {
                    distance[edge.to] = distance[u] + edge.weight;
                    changed = true;
                }
            }
        }
    }
    return distance;
}

void test_class_graph() {
    Graph graph = weighted_class_graph();
    assert(graph.check_invariants());
    DijkstraResult result = dijkstra(graph, 0);
    std::vector<Meters> expected{0, 2, 4, 3, 6, 7, 10};
    assert(result.distance == expected);
    assert(result.counts.settled == 7);
    assert(result.counts.pushes == 9);
    assert(result.counts.stale == 2);
    assert(result.counts.edges_read == 16);
    std::vector<int> route{0, 1, 3, 2, 4, 5, 6};
    assert(path_to(result.parent, 6) == route);
    assert(path_meters(graph, route) == 10);
    std::vector<int> fewest{0, 1, 3, 5, 6};
    assert(path_to(bfs(graph, 0).parent, 6) == fewest);
    assert(path_meters(graph, fewest) == 14);
}

// La corrida a mano de los apuntes.
void test_hand_run() {
    Graph graph(5);
    graph.add_edge(0, 1, 4);
    graph.add_edge(0, 2, 1);
    graph.add_edge(2, 1, 2);
    graph.add_edge(1, 3, 5);
    graph.add_edge(2, 3, 8);
    graph.add_edge(3, 4, 3);
    DijkstraResult result = dijkstra(graph, 0);
    std::vector<Meters> expected{0, 3, 1, 8, 11};
    assert(result.distance == expected);
    assert(result.counts.stale == 2);
    assert(result.counts.pushes == 7);
    std::vector<int> route{0, 2, 1, 3, 4};
    assert(path_to(result.parent, 4) == route);
}

void test_random_against_brute_force() {
    std::mt19937 random(150);
    for (int round = 0; round < 500; round++) {
        int n = 1 + static_cast<int>(random() % 12);
        Graph graph(n, random() % 2 == 0);
        int edges = static_cast<int>(random() % (2 * n + 1));
        for (int i = 0; i < edges; i++) {
            int u = static_cast<int>(random() % n);
            int v = static_cast<int>(random() % n);
            if (u != v) {
                graph.add_edge(u, v, static_cast<int>(random() % 10));
            }
        }
        int source = static_cast<int>(random() % n);
        DijkstraResult result = dijkstra(graph, source);
        assert(result.distance == brute_force(graph, source));
        assert(result.counts.pushes == result.counts.settled + result.counts.stale);
        std::size_t entries = 0;
        for (int u = 0; u < n; u++) {
            entries += graph.neighbors(u).size();
        }
        assert(result.counts.pushes <= entries + 1);
    }
}

void test_large_weights() {
    Graph graph(3);
    graph.add_edge(0, 1, 2000000000);
    graph.add_edge(1, 2, 2000000000);
    assert(dijkstra(graph, 0).distance[2] == 4000000000LL);
}

// Con todas las aristas de peso 1, las distancias son las de BFS.
void test_unit_weights_match_bfs() {
    std::mt19937 random(151);
    for (int round = 0; round < 200; round++) {
        int n = 2 + static_cast<int>(random() % 15);
        Graph graph(n);
        for (int i = 0; i < 2 * n; i++) {
            int u = static_cast<int>(random() % n);
            int v = static_cast<int>(random() % n);
            if (u != v) {
                graph.add_edge(u, v);
            }
        }
        DijkstraResult result = dijkstra(graph, 0);
        BfsResult levels = bfs(graph, 0);
        for (int v = 0; v < n; v++) {
            Meters expected = levels.distance[v] == -1 ? UNREACHABLE : levels.distance[v];
            assert(result.distance[v] == expected);
        }
    }
}

void test_negative_edge_gives_wrong_answer() {
    Graph graph = negative_edge_graph();
    assert(dijkstra(graph, 0).distance[3] == 3);
    assert(brute_force(graph, 0)[3] == 2);
}

}  // namespace

int main() {
    test_class_graph();
    test_hand_run();
    test_random_against_brute_force();
    test_large_weights();
    test_unit_weights_match_bfs();
    test_negative_edge_gives_wrong_answer();
    std::cout << "ok\n";
    return 0;
}