// ERROR A PROPÓSITO: BFS que marca un nodo al sacarlo de la cola, y no al meterlo.
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <queue>
#include <vector>

#include "../graph.h"

namespace {

struct Run {
    std::vector<int> distance;
    std::int64_t pushes;
};

// skip_marked agrega el arreglo más común: al sacar un nodo ya marcado, se ignora.
Run wrong_bfs(const Graph& graph, int source, bool skip_marked) {
    std::vector<bool> marked(graph.node_count(), false);
    std::vector<int> distance(graph.node_count(), -1);
    std::queue<int> pending;
    std::int64_t pushes = 1;
    distance[source] = 0;
    pending.push(source);
    while (!pending.empty()) {
        int u = pending.front();
        pending.pop();
        if (skip_marked && marked[u]) {
            continue;
        }
        marked[u] = true;  // demasiado tarde
        for (const Edge& edge : graph.neighbors(u)) {
            if (!marked[edge.to]) {
                distance[edge.to] = distance[u] + 1;
                pending.push(edge.to);
                pushes++;
            }
        }
    }
    return {distance, pushes};
}

// k rombos en fila: de cada cruce salen dos caminos que se juntan en el siguiente.
Graph diamonds(int k) {
    Graph graph(3 * k + 1);
    for (int i = 0; i < k; i++) {
        int top = 3 * i;
        graph.add_edge(top, top + 1);
        graph.add_edge(top, top + 2);
        graph.add_edge(top + 1, top + 3);
        graph.add_edge(top + 2, top + 3);
    }
    return graph;
}

}  // namespace

int main() {
    Graph triangle(3);
    triangle.add_edge(0, 1);
    triangle.add_edge(0, 2);
    triangle.add_edge(1, 2);
    std::cout << "triangulo, distancia de 0 a 2 (la verdadera es 1):\n";
    std::cout << "  marcando al sacar: " << wrong_bfs(triangle, 0, false).distance[2] << "\n";
    std::cout << "  e ignorando los ya marcados: " << wrong_bfs(triangle, 0, true).distance[2] << "\n";
    std::cout << "rombos  nodos  aristas  entradas a la cola  ignorando marcados\n";
    for (int k : {2, 4, 8, 12, 16}) {
        Graph graph = diamonds(k);
        std::cout << std::setw(6) << k << std::setw(7) << graph.node_count() << std::setw(9) << graph.edge_count()
                  << std::setw(20) << wrong_bfs(graph, 0, false).pushes << std::setw(20)
                  << wrong_bfs(graph, 0, true).pushes << "\n";
    }
    return 0;
}