// La recursión del teorema de Savitch sobre un grafo explícito, comparada con BFS.
//
// can_yield(g, u, v, t) responde si hay un camino de u a v con a lo sumo t aristas, con t una
// potencia de 2. No marca nodos visitados: prueba cada nodo como punto medio y resuelve las
// dos mitades, una después de la otra, en el mismo espacio.
#ifndef SAVITCH_H
#define SAVITCH_H

#include <algorithm>
#include <queue>
#include <vector>

#include "graph.h"

struct SavitchStats {
    long long calls = 0;  // llamadas a can_yield: el tiempo
    int max_depth = 0;    // llamadas activas a la vez, como máximo: el espacio
};

inline bool has_edge(const Graph& g, int u, int v) {
    return std::find(g.edges[u].begin(), g.edges[u].end(), v) != g.edges[u].end();
}

inline bool can_yield(const Graph& g, int u, int v, long long t, int depth, SavitchStats& stats) {
    stats.calls++;
    stats.max_depth = std::max(stats.max_depth, depth);
    if (t == 1) {
        return u == v || has_edge(g, u, v);
    }
    int n = static_cast<int>(g.nodes.size());
    for (int middle = 0; middle < n; middle++) {
        // Las dos llamadas usan el mismo espacio: la segunda empieza cuando la primera terminó.
        if (can_yield(g, u, middle, t / 2, depth + 1, stats) && can_yield(g, middle, v, t / 2, depth + 1, stats)) {
            return true;
        }
    }
    return false;
}

// La menor potencia de 2 que es mayor o igual que n.
inline long long power_of_two_at_least(long long n) {
    long long t = 1;
    while (t < n) {
        t *= 2;
    }
    return t;
}

// Cuántos bits hacen falta para escribir un número entre 0 y n - 1.
inline int bits_for(long long n) {
    int bits = 1;
    while ((1LL << bits) < n) {
        bits++;
    }
    return bits;
}

struct BfsStats {
    long long steps = 0;  // aristas examinadas: el tiempo
    int max_queue = 0;    // nodos en la cola a la vez, como máximo
};

// ¿Hay un camino de u a v? Con la marca de visitados y la cola de siempre.
inline bool bfs_reaches(const Graph& g, int u, int v, BfsStats& stats) {
    std::vector<bool> visited(g.nodes.size(), false);
    std::queue<int> pending;
    visited[u] = true;
    pending.push(u);
    stats.max_queue = 1;
    while (!pending.empty()) {
        int x = pending.front();
        pending.pop();
        if (x == v) {
            return true;
        }
        for (int y : g.edges[x]) {
            stats.steps++;
            if (!visited[y]) {
                visited[y] = true;
                pending.push(y);
                stats.max_queue = std::max(stats.max_queue, static_cast<int>(pending.size()));
            }
        }
    }
    return false;
}

#endif
