// Pruebas públicas del laboratorio. Se corre una por proceso: lab_tests nombre carpeta_de_datos.
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "graph.h"
#include "map_file.h"
#include "min_heap.h"
#include "routes.h"
#include "traversals.h"

namespace {

std::string data_dir;

std::string map_path(const std::string& name) { return data_dir + "/mapas/" + name + ".txt"; }

Graph hand_graph() {
    Graph graph(7);
    graph.add_edge(0, 1, 2);
    graph.add_edge(0, 2, 9);
    graph.add_edge(1, 3, 1);
    graph.add_edge(2, 3, 1);
    graph.add_edge(2, 4, 2);
    graph.add_edge(3, 5, 8);
    graph.add_edge(4, 5, 1);
    graph.add_edge(5, 6, 3);
    return graph;
}

// Un grafo al azar: a veces dirigido, a veces con pedazos separados, con empates y con pesos 0.
// Sin aristas repetidas.
Graph random_graph(std::mt19937& random) {
    int n = 1 + static_cast<int>(random() % 12);
    bool directed = random() % 2 == 0;
    int edges = static_cast<int>(random() % (2 * n + 1));
    int top_weight = 1 + static_cast<int>(random() % 12);
    Graph graph(n, directed);
    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.has_edge(u, v)) {
            graph.add_edge(u, v, static_cast<int>(random() % top_weight));
        }
    }
    return graph;
}

// Fuerza bruta: relajar todas las aristas, una y otra vez, hasta que nada cambie.
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;
}

// El padre de cada nodo tiene que explicar su distancia, con una arista que exista.
void check_parents(const Graph& graph, int source, const DijkstraResult& result) {
    assert(result.parent[source] == source);
    for (int v = 0; v < graph.node_count(); v++) {
        if (v == source) {
            continue;
        }
        if (result.distance[v] == UNREACHABLE) {
            assert(result.parent[v] == -1);
            continue;
        }
        int parent = result.parent[v];
        assert(parent != -1);
        bool explained = false;
        for (const Edge& edge : graph.neighbors(parent)) {
            if (edge.to == v && result.distance[parent] + edge.weight == result.distance[v]) {
                explained = true;
            }
        }
        assert(explained);
    }
}

using Search = DijkstraResult (*)(const Graph&, int);

void check_against_brute_force(Search search, int graphs) {
    std::mt19937 random(1500);
    for (int i = 0; i < graphs; i++) {
        Graph graph = random_graph(random);
        int source = static_cast<int>(random() % graph.node_count());
        DijkstraResult result = search(graph, source);
        assert(result.distance == brute_force(graph, source));
        check_parents(graph, source, result);
    }
}

// ---------- Antes de empezar: su heap ----------

void heap_from_week_13() {
    std::mt19937 random(13);
    MinHeap<HeapEntry> heap;
    std::vector<HeapEntry> expected;
    for (int i = 0; i < 500; i++) {
        HeapEntry entry{static_cast<Meters>(random() % 100), i};
        heap.push(entry);
        expected.push_back(entry);
    }
    heap.check_invariants();
    std::sort(expected.begin(), expected.end());
    for (const HeapEntry& entry : expected) {
        assert(!heap.empty());
        assert(heap.top() == entry);
        heap.pop();
    }
    assert(heap.empty());
}

// ---------- Paso 1: cargar el mapa ----------

void map_graph_small() {
    MapFile map;
    map.node_count = 4;
    map.points.resize(4);
    map.edges = {{0, 1, 70}, {1, 2, 30}, {2, 0, 500}};
    Graph graph = build_map_graph(map);
    assert(graph.check_invariants());
    assert(graph.node_count() == 4);
    assert(graph.edge_count() == 3);
    assert(!graph.directed());
    assert(graph.neighbors(3).empty());
    assert(graph.neighbors(1).size() == 2);
    for (const Edge& edge : graph.neighbors(1)) {
        assert((edge.to == 0 && edge.weight == 70) || (edge.to == 2 && edge.weight == 30));
    }
}

void map_graph_real() {
    MapFile map = read_map_file(map_path("miraflores"));
    Graph graph = build_map_graph(map);
    assert(graph.check_invariants());
    assert(graph.node_count() == 2242);
    assert(graph.edge_count() == 3474);
    std::size_t entries = 0;
    for (int u = 0; u < graph.node_count(); u++) {
        entries += graph.neighbors(u).size();
    }
    assert(entries == 2 * 3474);
    for (const MapEdge& edge : map.edges) {
        bool found = false;
        for (const Edge& entry : graph.neighbors(edge.u)) {
            found = found || (entry.to == edge.v && entry.weight == edge.meters);
        }
        assert(found);
    }
}

// ---------- Paso 2: Dijkstra y la ruta ----------

void dijkstra_hand_case() {
    Graph graph = hand_graph();
    DijkstraResult result = dijkstra(graph, 0);
    std::vector<Meters> expected{0, 2, 4, 3, 6, 7, 10};
    assert(result.distance == expected);
    std::vector<int> parents{0, 0, 3, 1, 2, 4, 5};
    assert(result.parent == parents);
    assert(result.counts.settled == 7);
    assert(result.counts.pushes == 9);
    assert(result.counts.stale == 2);
    assert(result.counts.edges_read == 16);
}

void dijkstra_random_against_brute_force() { check_against_brute_force(dijkstra, 400); }

void dijkstra_unreachable() {
    Graph graph(5);
    graph.add_edge(0, 1, 4);
    graph.add_edge(2, 3, 1);
    DijkstraResult result = dijkstra(graph, 0);
    assert(result.distance[1] == 4);
    assert(result.distance[2] == UNREACHABLE);
    assert(result.distance[4] == UNREACHABLE);
    assert(result.parent[3] == -1);
    assert(result.counts.settled == 2);
    assert(route_to(result.parent, 3).empty());
}

void dijkstra_large_weights() {
    Graph graph(4);
    graph.add_edge(0, 1, 2000000000);
    graph.add_edge(1, 2, 2000000000);
    graph.add_edge(2, 3, 2000000000);
    DijkstraResult result = dijkstra(graph, 0);
    assert(result.distance[3] == 6000000000LL);
}

void dijkstra_counts_on_real_map() {
    Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
    DijkstraResult result = dijkstra(graph, 0);
    assert(result.counts.settled == 2242);
    assert(result.counts.edges_read == 2 * 3474);  // cada lista se lee una sola vez
    assert(result.counts.pushes <= 2 * 3474 + 1);
    assert(result.counts.pushes == result.counts.settled + result.counts.stale);  // toda entrada sale
    assert(result.counts.stale > 0);
}

// Muchos orígenes: un heap con las claves cambiando por dentro falla en muy pocos.
void dijkstra_many_sources_on_real_map() {
    Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
    for (int source = 0; source < 300; source++) {
        DijkstraResult result = dijkstra(graph, source);
        assert(result.distance == brute_force(graph, source));
    }
}

void route_on_hand_case() {
    Graph graph = hand_graph();
    DijkstraResult result = dijkstra(graph, 0);
    std::vector<int> route{0, 1, 3, 2, 4, 5, 6};
    assert(route_to(result.parent, 6) == route);
    std::vector<int> alone{0};
    assert(route_to(result.parent, 0) == alone);
}

void route_on_real_map() {
    Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
    DijkstraResult result = dijkstra(graph, 1839);
    assert(result.distance[1883] == 1512);
    std::vector<int> route = route_to(result.parent, 1883);
    assert(route.front() == 1839 && route.back() == 1883);
    Meters total = 0;
    for (std::size_t i = 1; i < route.size(); i++) {
        Meters best = UNREACHABLE;
        for (const Edge& edge : graph.neighbors(route[i - 1])) {
            if (edge.to == route[i]) {
                best = edge.weight;
            }
        }
        assert(best != UNREACHABLE);
        total += best;
    }
    assert(total == 1512);
}

// ---------- Paso 3: BFS frente a Dijkstra ----------

void route_meters_hand_case() {
    Graph graph = hand_graph();
    std::vector<int> route{0, 1, 3, 5, 6};
    assert(route_meters(graph, route) == 14);
    assert(route_meters(graph, {3}) == 0);
    assert(route_meters(graph, {}) == 0);
    assert(route_meters(graph, {6, 5, 4}) == 4);  // no dirigido: también de vuelta
}

void routes_against_bfs() {
    Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
    std::mt19937 random(15);
    int fewer_meters = 0;
    int more_edges = 0;
    for (int i = 0; i < 40; i++) {
        int source = static_cast<int>(random() % graph.node_count());
        int target = static_cast<int>(random() % graph.node_count());
        DijkstraResult result = dijkstra(graph, source);
        std::vector<int> best = route_to(result.parent, target);
        std::vector<int> fewest = path_to(bfs(graph, source).parent, target);
        assert(route_meters(graph, best) == result.distance[target]);
        assert(result.distance[target] <= route_meters(graph, fewest));
        assert(fewest.size() <= best.size());
        fewer_meters += result.distance[target] < route_meters(graph, fewest) ? 1 : 0;
        more_edges += fewest.size() < best.size() ? 1 : 0;
    }
    assert(fewer_meters > 0 && more_edges > 0);
}

// ---------- Paso 4: detenerse al sacar el destino ----------

// Dijkstra saca a los nodos de menor a mayor distancia: hasta target salen todos los que están
// más cerca, nunca uno que esté más lejos, y los empatados dependen del orden.
void check_stop(const Graph& graph, int source, int target) {
    std::vector<Meters> truth = brute_force(graph, source);
    DijkstraResult result = dijkstra_to(graph, source, target);
    assert(result.distance[target] == truth[target]);
    std::size_t closer = 0;
    std::size_t up_to_target = 0;
    for (Meters d : truth) {
        if (d == UNREACHABLE) {
            continue;
        }
        if (truth[target] == UNREACHABLE) {
            closer++;
            up_to_target++;
            continue;
        }
        closer += d < truth[target] ? 1 : 0;
        up_to_target += d <= truth[target] ? 1 : 0;
    }
    if (truth[target] == UNREACHABLE) {
        assert(result.counts.settled == closer);
    } else {
        assert(closer + 1 <= result.counts.settled);
        assert(result.counts.settled <= up_to_target);
    }
    if (truth[target] != UNREACHABLE) {
        std::vector<int> route = route_to(result.parent, target);
        assert(route.front() == source && route.back() == target);
        assert(route_meters(graph, route) == truth[target]);
    }
}

void stop_tiny_case() {
    Graph graph(3);
    graph.add_edge(0, 2, 5);
    graph.add_edge(0, 1, 1);
    graph.add_edge(1, 2, 1);
    DijkstraResult result = dijkstra_to(graph, 0, 2);
    assert(result.distance[2] == 2);
    assert(result.counts.settled == 3);
}

void stop_hand_case() {
    Graph graph = hand_graph();
    DijkstraResult result = dijkstra_to(graph, 0, 5);
    assert(result.distance[5] == 7);
    assert(result.counts.settled == 6);  // 0, 1, 3, 2, 4 y 5: el 6 no sale
    assert(result.counts.edges_read == 12);  // no lee la lista de target
    assert(result.parent[5] == 4);
    result = dijkstra_to(graph, 0, 0);
    assert(result.distance[0] == 0);
    assert(result.counts.settled == 1);
    assert(result.counts.edges_read == 0);
}

void stop_random_against_brute_force() {
    std::mt19937 random(1504);
    for (int i = 0; i < 400; i++) {
        Graph graph = random_graph(random);
        int source = static_cast<int>(random() % graph.node_count());
        int target = static_cast<int>(random() % graph.node_count());
        check_stop(graph, source, target);
    }
}

void stop_saves_nodes_on_real_map() {
    Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
    DijkstraResult whole = dijkstra(graph, 1839);
    check_stop(graph, 1839, 1883);
    DijkstraResult near = dijkstra_to(graph, 1839, 1883);
    assert(near.counts.settled < whole.counts.settled);
    assert(near.counts.edges_read < whole.counts.edges_read);
}

// ---------- Paso 5: otras dos colas ----------

void priority_queue_random_against_brute_force() { check_against_brute_force(dijkstra_priority_queue, 400); }

void priority_queue_same_counts() {
    Graph graph = hand_graph();
    DijkstraResult result = dijkstra_priority_queue(graph, 0);
    assert(result.counts.settled == 7);
    assert(result.counts.pushes == 9);
    assert(result.counts.stale == 2);
    Graph real = build_map_graph(read_map_file(map_path("miraflores")));
    DijkstraResult own = dijkstra(real, 0);
    DijkstraResult library = dijkstra_priority_queue(real, 0);
    assert(own.distance == library.distance);
    assert(own.counts.pushes == library.counts.pushes);
    assert(own.counts.stale == library.counts.stale);
}

void array_random_against_brute_force() { check_against_brute_force(dijkstra_array, 400); }

void array_disconnected() {
    Graph graph(6);
    graph.add_edge(0, 1, 4);
    graph.add_edge(2, 3, 1);
    DijkstraResult result = dijkstra_array(graph, 0);
    assert(result.distance[1] == 4);
    assert(result.distance[2] == UNREACHABLE);
    assert(result.parent[2] == -1);
    assert(result.counts.settled == 2);
}

void array_reads_the_whole_array() {
    Graph graph = hand_graph();
    DijkstraResult result = dijkstra_array(graph, 0);
    assert(result.counts.settled == 7);
    assert(result.counts.pushes == 0);
    assert(result.counts.edges_read == 16);
    assert(result.counts.scanned >= 7 * 7 && result.counts.scanned <= 8 * 7);
    Graph real = build_map_graph(read_map_file(map_path("miraflores")));
    DijkstraResult whole = dijkstra_array(real, 0);
    std::size_t v = 2242;
    assert(whole.distance == dijkstra(real, 0).distance);
    assert(whole.counts.scanned >= v * v && whole.counts.scanned <= (v + 1) * v);
}

struct Case {
    const char* name;
    void (*run)();
};

const Case CASES[] = {
    {"heap_from_week_13", heap_from_week_13},
    {"map_graph_small", map_graph_small},
    {"map_graph_real", map_graph_real},
    {"dijkstra_hand_case", dijkstra_hand_case},
    {"dijkstra_random_against_brute_force", dijkstra_random_against_brute_force},
    {"dijkstra_unreachable", dijkstra_unreachable},
    {"dijkstra_large_weights", dijkstra_large_weights},
    {"dijkstra_counts_on_real_map", dijkstra_counts_on_real_map},
    {"dijkstra_many_sources_on_real_map", dijkstra_many_sources_on_real_map},
    {"route_on_hand_case", route_on_hand_case},
    {"route_on_real_map", route_on_real_map},
    {"route_meters_hand_case", route_meters_hand_case},
    {"routes_against_bfs", routes_against_bfs},
    {"stop_tiny_case", stop_tiny_case},
    {"stop_hand_case", stop_hand_case},
    {"stop_random_against_brute_force", stop_random_against_brute_force},
    {"stop_saves_nodes_on_real_map", stop_saves_nodes_on_real_map},
    {"priority_queue_random_against_brute_force", priority_queue_random_against_brute_force},
    {"priority_queue_same_counts", priority_queue_same_counts},
    {"array_random_against_brute_force", array_random_against_brute_force},
    {"array_disconnected", array_disconnected},
    {"array_reads_the_whole_array", array_reads_the_whole_array},
};

}  // namespace

int main(int argc, char* argv[]) {
    if (argc == 3) {
        data_dir = argv[2];
        for (const Case& test : CASES) {
            if (std::strcmp(test.name, argv[1]) == 0) {
                test.run();
                return 0;
            }
        }
    }
    std::cerr << "uso: lab_tests nombre carpeta_de_datos\n";
    return 2;
}