// Máquina de Turing no determinista: δ(q, a) es un conjunto de acciones, y la máquina acepta
// si alguna de sus ejecuciones llega a q_accept. Se escribe en el mismo formato .tm, con
// varias líneas para el mismo par de estado y símbolo.
//
// Aquí está la simulación determinista: recorrer el árbol de ejecuciones por niveles.
#ifndef NTM_H
#define NTM_H

#include <cstddef>
#include <fstream>
#include <map>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "tm.h"

struct Ntm {
    std::vector<std::string> states;                                    // Q
    std::vector<char> alphabet;                                         // Σ
    std::vector<char> tape;                                             // Γ
    std::map<std::pair<std::string, char>, std::vector<Action>> delta;  // δ : Q' × Γ → P(Q × Γ × {L, R})
    std::string start;                                                  // q0
    std::string accept;                                                 // q_accept
    std::string reject;                                                 // q_reject
};

inline Ntm load_ntm(const std::string& path) {
    std::ifstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    try {
        Description d = read_description(file);
        Ntm m;
        m.states = d.states;
        m.alphabet = d.alphabet;
        m.tape = d.tape;
        m.start = d.start;
        m.accept = d.accept;
        m.reject = d.reject;
        for (const Rule& rule : d.rules) {
            m.delta[{rule.state, rule.read}].push_back(rule.action);  // en el orden del archivo
        }
        return m;
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(path + ": " + error.what());
    }
}

// Las opciones de la máquina en una configuración. Sin ninguna línea, la única es ir a q_reject.
inline std::vector<Action> choices(const Ntm& m, const Config& c) {
    auto it = m.delta.find({c.state, scanned(c)});
    if (it == m.delta.end()) {
        return {{m.reject, scanned(c), 'R'}};
    }
    return it->second;
}

// Los hijos de una configuración en el árbol de ejecuciones. Una configuración final no tiene.
inline std::vector<Config> successors(const Ntm& m, const Config& c) {
    std::vector<Config> result;
    if (c.state == m.accept || c.state == m.reject) {
        return result;
    }
    for (const Action& action : choices(m, c)) {
        Config next = c;
        apply(next, action);
        result.push_back(next);
    }
    return result;
}

struct Search {
    Outcome outcome = Outcome::Limit;
    long long depth = 0;    // el nivel al que llegó
    long long visited = 0;  // cuántas configuraciones sacó de la cola
};

// Recorre el árbol por niveles: el nivel d tiene las configuraciones a las que se llega con d
// pasos. Acepta en cuanto encuentra una con q_accept. Rechaza si un nivel queda vacío, porque
// entonces todas las ramas se detuvieron sin aceptar. Si pasa de max_depth, no se sabe.
inline Search breadth_first(const Ntm& m, const std::string& w, long long max_depth) {
    Search result;
    std::vector<Config> level = {{m.start, w, 0}};
    for (long long depth = 0; depth <= max_depth; depth++) {
        result.depth = depth;
        std::vector<Config> next_level;
        for (const Config& c : level) {
            result.visited++;
            if (c.state == m.accept) {
                result.outcome = Outcome::Accept;
                return result;
            }
            for (const Config& child : successors(m, c)) {
                next_level.push_back(child);
            }
        }
        if (next_level.empty()) {
            result.outcome = Outcome::Reject;
            return result;
        }
        level = next_level;
    }
    return result;
}

// Lo que haría un recorrido en profundidad antes de retroceder por primera vez: seguir
// siempre la primera opción. Si esa rama no se detiene, el recorrido no vuelve nunca.
inline Run first_branch(const Ntm& m, const std::string& w, long long limit) {
    Run result;
    result.last = {m.start, w, 0};
    while (result.last.state != m.accept && result.last.state != m.reject && result.steps < limit) {
        apply(result.last, choices(m, result.last).front());
        result.steps++;
    }
    if (result.last.state == m.accept) {
        result.outcome = Outcome::Accept;
    } else if (result.last.state == m.reject) {
        result.outcome = Outcome::Reject;
    }
    return result;
}

#endif
