// Pruebas de la sesión B sobre el no determinismo y los enumeradores.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <set>
#include <string>
#include <vector>

#include "ntm.h"
#include "tm.h"

static bool has_one(const std::string& w) {
    return w.find('1') != std::string::npos;
}

static bool is_zeros_ones(const std::string& w) {
    std::size_t n = w.size() / 2;
    return w.size() % 2 == 0 && w == std::string(n, '0') + std::string(n, '1');
}

// La máquina no determinista del capítulo: el recorrido por niveles acepta exactamente las
// cadenas con algún 1, en el nivel que dicen los apuntes. Seguir siempre la primera opción
// no termina si la cadena empieza con 0.
static void test_breadth_first() {
    Ntm m = load_ntm("machines/nondet_branch.tm");
    assert(m.delta.at({"q0", '0'}).size() == 2);
    for (const std::string& w : all_strings(m.alphabet, 9)) {
        Search search = breadth_first(m, w, 40);
        if (has_one(w)) {
            assert(search.outcome == Outcome::Accept);
            assert(search.depth == static_cast<long long>(w.find('1')) + 1);
        } else if (w.empty()) {
            assert(search.outcome == Outcome::Reject);  // una sola rama, que se detiene
        } else {
            assert(search.outcome == Outcome::Limit);  // hay una rama que no se detiene
        }
        Run first = first_branch(m, w, 5000);
        if (!w.empty() && w[0] == '0') {
            assert(first.outcome == Outcome::Limit && first.last.state == "q1");
        }
    }
    // El ejemplo de los apuntes.
    Search search = breadth_first(m, "001", 8);
    assert(search.outcome == Outcome::Accept && search.depth == 3 && search.visited == 9);
    assert(first_branch(m, "001", 1000000).outcome == Outcome::Limit);
    assert(breadth_first(m, "00", 5).outcome == Outcome::Limit);
}

// Una máquina determinista es un caso particular: el árbol es un solo camino, y el recorrido
// por niveles responde lo mismo que la ejecución, en el mismo número de pasos.
static void test_deterministic_as_ntm() {
    Ntm n = load_ntm("machines/zeros_ones.tm");
    Tm d = load_tm("machines/zeros_ones.tm");
    for (const std::string& w : all_strings(d.alphabet, 10)) {
        Search search = breadth_first(n, w, 1000);
        Run r = run(d, w, 1000);
        assert(search.outcome == r.outcome);
        assert((search.outcome == Outcome::Accept) == is_zeros_ones(w));
        assert(search.depth == r.steps);
    }
}

// El enumerador que se construye a partir de una máquina que reconoce: en la ronda i, i pasos
// con cada una de s1, …, si. Se comprueba con la máquina que no se detiene con las cadenas sin
// unos: aun así, toda cadena del lenguaje sale impresa, y ninguna que no esté.
static void test_enumerator() {
    Tm m = load_tm("machines/has_one_loops.tm");
    std::vector<std::string> strings = all_strings(m.alphabet, 6);  // s1, …, s127
    const std::size_t rounds = strings.size();
    std::set<std::string> printed;
    std::vector<std::size_t> first_round(strings.size(), 0);
    for (std::size_t i = 1; i <= rounds; i++) {
        for (std::size_t j = 0; j < i; j++) {
            if (run(m, strings[j], static_cast<long long>(i)).outcome == Outcome::Accept) {
                printed.insert(strings[j]);
                if (first_round[j] == 0) {
                    first_round[j] = i;
                }
            }
        }
        if (i == 8) {
            assert(printed == (std::set<std::string>{"1", "01", "10", "11"}));  // la salida de los apuntes
        }
    }
    for (std::size_t j = 0; j < strings.size(); j++) {
        const std::string& s = strings[j];
        assert((printed.count(s) > 0) == has_one(s));
        if (has_one(s)) {
            // s_j sale por primera vez en la ronda max(j, pasos que tarda M en aceptarla).
            std::size_t steps = s.find('1') + 1;
            assert(first_round[j] == std::max(j + 1, steps));
        }
    }
    // Ejecutar M con s1, después con s2… no sirve: con s1 = ε no se detiene.
    assert(run(m, strings[0], 1000000).outcome == Outcome::Limit);
}

int main() {
    test_breadth_first();
    test_deterministic_as_ntm();
    test_enumerator();
    std::printf("test_variants: ok\n");
}
