// Sigue BFS paso a paso sobre el grafo de la clase: qué sale, qué se marca y cómo queda la cola.
#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

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

namespace {

std::string join(const std::vector<int>& nodes) {
    std::string text;
    for (int node : nodes) {
        text += (text.empty() ? "" : " ") + std::to_string(node);
    }
    return text;
}

}  // namespace

int main() {
    Graph graph = class_graph();
    std::vector<int> distance(graph.node_count(), -1);
    std::vector<int> waiting{0};
    std::size_t front = 0;
    distance[0] = 0;
    std::cout << "sale  marca     cola al terminar el paso\n";
    std::cout << "   -  0         " << join(waiting) << "\n";
    while (front < waiting.size()) {
        int u = waiting[front];
        front++;
        std::vector<int> newly_marked;
        for (const Edge& edge : graph.neighbors(u)) {
            if (distance[edge.to] == -1) {
                distance[edge.to] = distance[u] + 1;
                waiting.push_back(edge.to);
                newly_marked.push_back(edge.to);
            }
        }
        std::vector<int> queue_now(waiting.begin() + static_cast<std::ptrdiff_t>(front), waiting.end());
        std::cout << std::setw(4) << u << "  " << std::left << std::setw(10) << join(newly_marked)
                  << std::right << join(queue_now) << "\n";
    }

    BfsResult result = bfs(graph, 0);
    std::cout << "orden: ";
    print_nodes(result.order);
    std::cout << "distancia: ";
    print_nodes(result.distance);
    std::cout << "padre: ";
    print_nodes(result.parent);
    std::cout << "camino a 6: ";
    print_nodes(path_to(result.parent, 6));
    return 0;
}