// Un grafo real: las calles alrededor de Miraflores. Tamaño, memoria, y BFS frente a DFS.
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

#include "map_file.h"
#include "traversals.h"

namespace {

std::int64_t path_meters(const Graph& graph, const std::vector<int>& path) {
    std::int64_t meters = 0;
    for (std::size_t i = 0; i + 1 < path.size(); i++) {
        for (const Edge& edge : graph.neighbors(path[i])) {
            if (edge.to == path[i + 1]) {
                meters += edge.weight;
                break;
            }
        }
    }
    return meters;
}

// Camino de DFS: la pila de marcos en el momento de llegar al destino. Es igual a dfs_iterative.
std::vector<int> dfs_path(const Graph& graph, int source, int target, int& marked_count) {
    std::vector<bool> marked(graph.node_count(), false);
    std::vector<std::pair<int, std::size_t>> stack;
    marked[source] = true;
    marked_count = 1;
    stack.push_back({source, 0});
    while (!stack.empty() && stack.back().first != target) {
        auto& [u, next] = stack.back();
        const std::vector<Edge>& list = graph.neighbors(u);
        if (next == list.size()) {
            stack.pop_back();
            continue;
        }
        int v = list[next].to;
        next++;
        if (!marked[v]) {
            marked[v] = true;
            marked_count++;
            stack.push_back({v, 0});
        }
    }
    std::vector<int> path;
    for (const auto& frame : stack) {
        path.push_back(frame.first);
    }
    return path;
}

}  // namespace

int main(int argc, char* argv[]) {
    if (argc != 4) {
        std::cerr << "uso: map_tour mapa origen destino\n";
        return 1;
    }
    Graph graph = read_map(argv[1]);
    int source = std::stoi(argv[2]);
    int target = std::stoi(argv[3]);
    std::int64_t v = graph.node_count();
    std::int64_t e = static_cast<std::int64_t>(graph.edge_count());

    std::size_t largest = 0;
    for (int u = 0; u < v; u++) {
        largest = std::max(largest, graph.neighbors(u).size());
    }
    std::cout << "nodos: " << v << ", aristas: " << e << "\n";
    std::cout << "grado medio: " << 2.0 * static_cast<double>(e) / static_cast<double>(v) << ", grado maximo: " << largest << "\n";
    std::cout << "aristas sobre las posibles: " << 100.0 * static_cast<double>(e) / (static_cast<double>(v) * (v - 1) / 2) << " %\n";
    std::cout << "matriz de un byte por celda: " << v * v << " bytes\n";
    std::cout << "listas: " << list_bytes(graph) << " bytes\n";

    std::vector<int> labels = component_labels(graph);
    std::cout << "componentes: " << *std::max_element(labels.begin(), labels.end()) + 1 << "\n";

    BfsResult result = bfs(graph, source);
    std::vector<int> by_bfs = path_to(result.parent, target);
    int dfs_marked = 0;
    std::vector<int> by_dfs = dfs_path(graph, source, target, dfs_marked);
    // BFS saca los nodos en el orden en que los marcó: este es el conteo al marcar el destino.
    int bfs_marked = 0;
    for (int u : result.order) {
        bfs_marked++;
        if (u == target) {
            break;
        }
    }
    std::cout << "de " << source << " a " << target << ":\n";
    std::cout << "BFS: " << by_bfs.size() - 1 << " aristas, " << path_meters(graph, by_bfs)
              << " metros, nodos marcados: " << bfs_marked << "\n";
    std::cout << "DFS: " << by_dfs.size() - 1 << " aristas, " << path_meters(graph, by_dfs)
              << " metros, nodos marcados: " << dfs_marked << "\n";
    return 0;
}