// Pruebas de la recursión de Savitch sobre grafos: responde lo mismo que BFS y su profundidad
// es log2 t + 1.
#include <cassert>
#include <cstdio>
#include <queue>
#include <random>
#include <string>
#include <vector>

#include "savitch.h"

// La distancia de u a v en aristas, o -1 si no se llega.
static int distance(const Graph& g, int u, int v) {
    std::vector<int> dist(g.nodes.size(), -1);
    std::queue<int> pending;
    dist[u] = 0;
    pending.push(u);
    while (!pending.empty()) {
        int x = pending.front();
        pending.pop();
        for (int y : g.edges[x]) {
            if (dist[y] == -1) {
                dist[y] = dist[x] + 1;
                pending.push(y);
            }
        }
    }
    return dist[v];
}

int main() {
    assert(power_of_two_at_least(1) == 1 && power_of_two_at_least(5) == 8 && power_of_two_at_least(8) == 8);
    assert(bits_for(2) == 1 && bits_for(8) == 3 && bits_for(9) == 4 && bits_for(1024) == 10);

    // El grafo de PATH de los apuntes.
    Graph routes = load_graph("machines/two_routes.graph");
    int s = node_index(routes, "s");
    int t = node_index(routes, "t");
    SavitchStats stats;
    assert(can_yield(routes, s, t, 8, 1, stats));
    assert(stats.max_depth == 4);  // t = 8, 4, 2, 1
    SavitchStats back;
    assert(!can_yield(routes, t, s, 8, 1, back));
    assert(distance(routes, s, t) == 4);
    SavitchStats short_stats;
    assert(!can_yield(routes, s, t, 2, 1, short_stats));  // con 2 aristas no alcanza
    assert(can_yield(routes, s, t, 4, 1, short_stats));

    // can_yield(u, v, t) es verdadero exactamente cuando la distancia de u a v es a lo sumo t.
    std::mt19937 rng(8);
    int checked = 0;
    for (int k = 0; k < 300; k++) {
        int n = 1 + static_cast<int>(rng() % 7);
        Graph g;
        for (int i = 0; i < n; i++) {
            g.nodes.push_back("n" + std::to_string(i));
            g.edges.emplace_back();
        }
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (rng() % 100 < 25) {
                    g.edges[u].push_back(v);
                }
            }
        }
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                int d = distance(g, u, v);
                for (long long steps = 1; steps <= 8; steps *= 2) {
                    SavitchStats st;
                    bool expected = d != -1 && d <= steps;
                    assert(can_yield(g, u, v, steps, 1, st) == expected);
                    int levels = 1;
                    for (long long x = steps; x > 1; x /= 2) {
                        levels++;
                    }
                    assert(st.max_depth <= levels);
                    checked++;
                }
                BfsStats bfs;
                assert(bfs_reaches(g, u, v, bfs) == (d != -1));
            }
        }
    }
    std::printf("test_savitch: el grafo de la clase y %d consultas en grafos al azar\n", checked);
    return 0;
}
