// Pruebas del simulador: el formato .tm con varias líneas por par, los lenguajes de las
// máquinas de machines/ y las ejecuciones que citan los apuntes.
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

#include "ntm.h"

// Todas las cadenas binarias de longitud a lo sumo max_length.
static std::vector<std::string> binary_strings(std::size_t max_length) {
    std::vector<std::string> all = {""};
    for (std::size_t first = 0; first < all.size(); first++) {
        if (all[first].size() < max_length) {
            all.push_back(all[first] + "0");
            all.push_back(all[first] + "1");
        }
    }
    return all;
}

static bool accepts(const Ntm& n, const std::string& w, std::size_t steps) {
    bool by_levels = !accepting_branch(n, w, steps, steps + w.size() + 1).empty();
    bool by_branches = accepts_within(n, start_config(n, w), steps, steps + w.size() + 1);
    assert(by_levels == by_branches);  // las dos búsquedas coinciden
    return by_levels;
}

static bool throws(const std::string& path) {
    try {
        read_ntm_file(path);
    } catch (const std::runtime_error&) {
        return true;
    }
    return false;
}

int main() {
    Ntm eleven = read_ntm_file("machines/contains_11.tm");
    Ntm back = read_ntm_file("machines/contains_01_back.tm");
    Ntm left = read_ntm_file("machines/left_end_accept.tm");
    Ntm loop = read_ntm_file("machines/loop.tm");
    Ntm zeros = read_ntm_file("machines/zeros_ones.tm");

    // El formato: dos líneas para (q0, 1) en contains_11.
    assert(moves(eleven, "q0", '1').size() == 2);
    assert(moves(eleven, "q0", '0').size() == 1);
    assert(moves(eleven, "q1", '0').empty());  // sin línea: esa rama rechaza
    assert(!is_deterministic(eleven) && !is_deterministic(back));
    assert(is_deterministic(left) && is_deterministic(loop) && is_deterministic(zeros));

    // Los lenguajes, con todas las cadenas de longitud a lo sumo 8.
    std::size_t count = 0;
    for (const std::string& w : binary_strings(8)) {
        count++;
        std::size_t zeros_count = 0;
        while (zeros_count < w.size() && w[zeros_count] == '0') {
            zeros_count++;
        }
        bool is_0n1n = w == std::string(zeros_count, '0') + std::string(zeros_count, '1');
        assert(accepts(eleven, w, w.size() + 1) == (w.find("11") != std::string::npos));
        assert(accepts(back, w, w.size() + 2) == (w.find("01") != std::string::npos));
        assert(accepts(left, w, 2) == (!w.empty() && w[0] == '0'));
        assert(!accepts(loop, w, 12));
        if (w.size() <= 6) {
            assert(accepts(zeros, w, 60) == is_0n1n);
        }
    }
    assert(count == 511);

    // contains_11 acepta en |w| + 1 pasos o menos; con menos pasos de los necesarios, no.
    assert(accepts(eleven, "011", 3) && !accepts(eleven, "011", 2));
    // La rama de los apuntes con 0110.
    std::vector<Config> branch = accepting_branch(eleven, "0110", 10, 10);
    std::vector<std::string> shown;
    for (const Config& c : branch) {
        shown.push_back(show_config(c));
    }
    assert((shown == std::vector<std::string>{"q0 0110", "0 q0 110", "01 q1 10", "011 q_accept 0"}));

    // L en la primera celda deja el cabezal donde está.
    Config first = start_config(left, "01");
    std::vector<Config> next = successors(left, first);
    assert(next.size() == 1 && next[0].head == 0 && next[0].state == "q1" && next[0].tape == "X1");
    // Una configuración que ya se detuvo no tiene siguiente.
    assert(successors(eleven, {"q_accept", "0", 0}).empty());
    assert(successors(eleven, {"q_reject", "0", 0}).empty());
    // La cadena vacía: la cinta tiene al menos la celda que lee el cabezal.
    assert(show_config(start_config(eleven, "")) == "q0 _");

    // Las tres descripciones de errors/ no se aceptan.
    assert(throws("errors/moves_after_accept.tm"));
    assert(throws("errors/no_blank.tm"));
    assert(throws("errors/stay_move.tm"));

    std::cout << "test_ntm: ok (5 máquinas, " << count << " cadenas)\n";
    return 0;
}
