// Pruebas del buscador con backtracking (sesión B): responde lo mismo que la simulación del
// NFA, termina con estrellas anidadas, y con (a|a)*b contra a^n hace 10·2^n − 4 llamadas.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

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

static std::size_t test_agrees_with_nfa() {
    std::vector<std::string> expressions = {
        "(0|1)*1", "((0|1)(0|1))*", "0*10*10*", "(1|01*0)*", "(0|10)*(%|1)", "(01)*|(10)*",
        "(0*)*1",  "(0|%)*1",       "(0*1*)*",  "@",         "%",            "(0|@)1",
        "(%|0)*",  "((0|1)*)*",
    };
    std::vector<std::string> words = all_strings({'0', '1'}, 8);
    for (const std::string& text : expressions) {
        RegexPtr r = parse_regex(text);
        Nfa n = thompson(r, {'0', '1'});
        for (const std::string& w : words) {
            assert(backtrack_accepts(r, w) == accepts(n, w));
        }
    }
    return expressions.size();
}

static void test_bad_case() {
    RegexPtr r = parse_regex("(a|a)*b");
    long long calls = 0;
    assert(backtrack_accepts(r, "aab", &calls) && calls == 12);
    assert(!backtrack_accepts(r, "aaa", &calls) && calls == 76);
    long long power = 1;
    for (std::size_t n = 0; n <= 14; n++) {
        assert(!backtrack_accepts(r, std::string(n, 'a'), &calls));
        assert(calls == 10 * power - 4);
        power *= 2;
    }
    // Con la b al final, la primera rama que prueba ya acierta: las llamadas son lineales.
    for (std::size_t n = 0; n <= 14; n++) {
        assert(backtrack_accepts(r, std::string(n, 'a') + "b", &calls));
        assert(calls == static_cast<long long>(3 * n + 6));
    }
}

int main() {
    std::size_t expressions = test_agrees_with_nfa();
    test_bad_case();
    std::printf("test_backtrack: ok (%zu expresiones, 511 cadenas cada una)\n", expressions);
}
