// La recursión de Savitch frente a BFS, con números.
//
//     savitch_demo                      la tabla con los caminos de 4, 8, 16 y 32 nodos
//     savitch_demo archivo.graph nodo   ¿se llega del nodo de partida a ese nodo?
//
// En el camino v0 → v1 → … → v(n-1) se pregunta si de v0 se llega a v(n-1).
// Lo que guarda cada algoritmo se cuenta en bits, con ⌈log2 n⌉ bits por nodo:
//   Savitch: por cada llamada activa, tres nodos (origen, destino y punto medio) y el exponente de t.
//   BFS: un bit de visitado por nodo, más los nodos de la cola.
#include <cstdio>
#include <iostream>
#include <stdexcept>
#include <string>

#include "savitch.h"

static Graph path_graph(int n) {
    Graph g;
    for (int i = 0; i < n; i++) {
        g.nodes.push_back("v" + std::to_string(i));
        g.edges.emplace_back();
        if (i > 0) {
            g.edges[i - 1].push_back(i);
        }
    }
    g.start = 0;
    return g;
}

static long long savitch_bits(long long n, long long t, int depth) {
    int exponent_bits = bits_for(bits_for(t) + 1);
    return static_cast<long long>(depth) * (3 * bits_for(n) + exponent_bits);
}

static void compare(const Graph& g, int target, bool header) {
    long long n = static_cast<long long>(g.nodes.size());
    long long t = power_of_two_at_least(n);
    SavitchStats savitch;
    bool by_savitch = can_yield(g, g.start, target, t, 1, savitch);
    BfsStats bfs;
    bool by_bfs = bfs_reaches(g, g.start, target, bfs);
    if (by_savitch != by_bfs) {
        throw std::runtime_error("las dos respuestas no coinciden");
    }
    if (header) {
        std::printf("   n     t   llega   Savitch: llamadas  activas  bits   BFS: aristas  cola  bits\n");
    }
    std::printf("%4lld  %4lld   %-5s   %17lld  %7d  %4lld   %12lld  %4d  %4lld\n", n, t, by_bfs ? "sí" : "no",
                savitch.calls, savitch.max_depth, savitch_bits(n, t, savitch.max_depth), bfs.steps, bfs.max_queue,
                n + static_cast<long long>(bfs.max_queue) * bits_for(n));
}

int main(int argc, char** argv) {
    try {
        if (argc == 3) {
            Graph g = load_graph(argv[1]);
            compare(g, node_index(g, argv[2]), true);
            return 0;
        }
        bool header = true;
        for (int n : {4, 8, 16, 32}) {
            compare(path_graph(n), n - 1, header);
            header = false;
        }
    } catch (const std::runtime_error& e) {
        std::cerr << "error: " << e.what() << '\n';
        return 1;
    }
    return 0;
}
