// Backtracking frente a simulación del NFA, con el caso malo: (a|a)*b contra a^n.
// La cadena no tiene ninguna b, así que la respuesta siempre es "rechaza".
// Cuenta las llamadas del backtracking y mide el tiempo de las dos búsquedas.
// Se compila con -O2 y sin sanitizers: make bench.
#include <chrono>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

#include "backtrack.h"
#include "nfa.h"
#include "regex.h"
#include "thompson.h"

static double seconds_since(std::chrono::steady_clock::time_point start) {
    return std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
}

int main() {
    RegexPtr r = parse_regex("(a|a)*b");
    Nfa n = thompson(r);
    std::printf("expresión: (a|a)*b    cadena: a^n    NFA de Thompson: %zu estados\n\n", n.states.size());
    std::printf("      n   backtracking: llamadas   backtracking: tiempo   NFA: tiempo\n");
    std::vector<std::size_t> lengths = {5, 10, 15, 20, 25};
    for (std::size_t length : lengths) {
        std::string w(length, 'a');
        long long calls = 0;
        auto t0 = std::chrono::steady_clock::now();
        bool by_backtracking = backtrack_accepts(r, w, &calls);
        double backtracking_time = seconds_since(t0);
        auto t1 = std::chrono::steady_clock::now();
        bool by_nfa = accepts(n, w);
        double nfa_time = seconds_since(t1);
        if (by_backtracking || by_nfa) {
            std::printf("error: alguna de las dos búsquedas aceptó\n");
            return 1;
        }
        std::printf("%7zu   %22lld   %18.4f s   %9.4f s\n", length, calls, backtracking_time, nfa_time);
    }
    // Solo el NFA: con estas longitudes el backtracking no termina.
    for (std::size_t length : {1000, 100000}) {
        std::string w(length, 'a');
        auto t1 = std::chrono::steady_clock::now();
        bool by_nfa = accepts(n, w);
        double nfa_time = seconds_since(t1);
        if (by_nfa) {
            std::printf("error: el NFA aceptó\n");
            return 1;
        }
        std::printf("%7zu   %22s   %20s   %9.4f s\n", length, "-", "-", nfa_time);
    }
}
