// Dijkstra paso a paso sobre el grafo de la clase, desde el nodo 0.
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

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

namespace {

// El heap en orden de salida: una copia que se vacía. No es el orden del arreglo interno.
std::string heap_text(MinFirstQueue heap) {
    std::ostringstream text;
    while (!heap.empty()) {
        text << "(" << heap.top().first << "," << heap.top().second << ") ";
        heap.pop();
    }
    return text.str();
}

std::string distances_text(const std::vector<Meters>& distance) {
    std::ostringstream text;
    for (std::size_t v = 0; v < distance.size(); v++) {
        text << (v == 0 ? "" : " ");
        if (distance[v] == UNREACHABLE) {
            text << "-";
        } else {
            text << distance[v];
        }
    }
    return text.str();
}

}  // namespace

int main() {
    Graph graph = weighted_class_graph();
    int n = graph.node_count();
    std::vector<Meters> distance(n, UNREACHABLE);
    std::vector<int> parent(n, -1);
    std::vector<bool> settled(n, false);
    MinFirstQueue heap;
    distance[0] = 0;
    parent[0] = 0;
    heap.push({0, 0});
    std::cout << std::left << std::setw(9) << "sale" << std::setw(11) << "relaja" << std::setw(16) << "distancias"
              << "heap\n";
    std::cout << std::setw(9) << "-" << std::setw(11) << "-" << std::setw(16) << distances_text(distance)
              << heap_text(heap) << "\n";
    while (!heap.empty()) {
        auto [d, u] = heap.top();
        heap.pop();
        std::ostringstream popped;
        popped << "(" << d << "," << u << ")";
        if (settled[u]) {
            std::cout << std::setw(9) << popped.str() << std::setw(11) << "vieja" << std::setw(16)
                      << distances_text(distance) << heap_text(heap) << "\n";
            continue;
        }
        settled[u] = true;
        std::ostringstream relaxed;
        for (const Edge& edge : graph.neighbors(u)) {
            if (d + edge.weight < distance[edge.to]) {
                distance[edge.to] = d + edge.weight;
                parent[edge.to] = u;
                heap.push({distance[edge.to], edge.to});
                relaxed << edge.to << " ";
            }
        }
        std::cout << std::setw(9) << popped.str() << std::setw(11) << relaxed.str() << std::setw(16)
                  << distances_text(distance) << heap_text(heap) << "\n";
    }
    std::cout << "ruta de Dijkstra a 6: ";
    std::vector<int> route = path_to(parent, 6);
    print_nodes(route);
    std::cout << "  aristas: " << route.size() - 1 << ", metros: " << path_meters(graph, route) << "\n";
    std::vector<int> fewest = path_to(bfs(graph, 0).parent, 6);
    std::cout << "ruta de BFS a 6: ";
    print_nodes(fewest);
    std::cout << "  aristas: " << fewest.size() - 1 << ", metros: " << path_meters(graph, fewest) << "\n";
    return 0;
}