// Un buscador con backtracking: recorre el árbol de la expresión y prueba las alternativas
// una por una. Cuando una falla, vuelve atrás y prueba la siguiente.
// Es correcto, y con algunas expresiones tarda un tiempo exponencial en la longitud de la
// cadena: está aquí para compararlo con la simulación del NFA.
#ifndef BACKTRACK_H
#define BACKTRACK_H

#include <cstddef>
#include <functional>
#include <string>

#include "regex.h"

struct Backtracker {
    std::string w;
    long long calls = 0;  // cuántas veces se llamó a match

    // ¿Se puede leer con r un tramo de w que empieza en pos, de modo que lo que sigue (rest)
    // acepte desde donde r terminó?
    bool match(const RegexPtr& r, std::size_t pos, const std::function<bool(std::size_t)>& rest) {
        calls++;
        switch (r->kind) {
            case Kind::Empty:
                return false;
            case Kind::Epsilon:
                return rest(pos);
            case Kind::Symbol:
                return pos < w.size() && w[pos] == r->symbol && rest(pos + 1);
            case Kind::Union:
                // Primero la alternativa izquierda; si falla, la derecha.
                return match(r->left, pos, rest) || match(r->right, pos, rest);
            case Kind::Concat:
                return match(r->left, pos, [&](std::size_t middle) { return match(r->right, middle, rest); });
            case Kind::Star:
                // Primero intenta una vuelta más y, si falla, sale de la estrella. Una vuelta
                // que no avanza no se cuenta: sin esa condición, (a*)* no terminaría.
                return match(r->left, pos,
                             [&](std::size_t middle) { return middle > pos && match(r, middle, rest); }) ||
                       rest(pos);
        }
        return false;
    }
};

// ¿Describe r la cadena w completa? Devuelve además cuántas llamadas hizo.
inline bool backtrack_accepts(const RegexPtr& r, const std::string& w, long long* calls = nullptr) {
    Backtracker search{w};
    bool found = search.match(r, 0, [&](std::size_t end) { return end == w.size(); });
    if (calls != nullptr) {
        *calls = search.calls;
    }
    return found;
}

#endif
