// Autómata finito no determinista, con transiciones ε. El struct tiene los cinco componentes
// de la definición N = (Q, Σ, δ, q0, F), con los nombres del formato .nfa de code/formats.md.
// Además: leer y escribir ese formato, la clausura ε y la simulación con el conjunto de
// estados activos.
#ifndef NFA_H
#define NFA_H

#include <cstddef>
#include <fstream>
#include <istream>
#include <map>
#include <ostream>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

// En δ, una transición ε se guarda con este carácter en el lugar del símbolo.
const char EPS = '\0';

using StateSet = std::set<std::string>;

struct Nfa {
    std::vector<std::string> states;                         // Q, en el orden del archivo
    std::vector<char> alphabet;                              // Σ
    std::map<std::pair<std::string, char>, StateSet> delta;  // δ : Q × (Σ ∪ {ε}) → P(Q)
    std::string start;                                       // q0
    StateSet accept;                                         // F ⊆ Q
};

// ------------------------------------------------------------
// Comprobar que la quíntupla es un NFA
// ------------------------------------------------------------

inline void check_nfa(const Nfa& n) {
    StateSet q(n.states.begin(), n.states.end());
    std::set<char> sigma(n.alphabet.begin(), n.alphabet.end());
    if (n.states.empty()) {
        throw std::runtime_error("Q no puede ser vacío");
    }
    if (q.size() != n.states.size()) {
        throw std::runtime_error("hay un estado repetido en states");
    }
    if (n.alphabet.empty()) {
        throw std::runtime_error("el alfabeto no puede ser vacío");
    }
    if (sigma.size() != n.alphabet.size()) {
        throw std::runtime_error("hay un símbolo repetido en alphabet");
    }
    if (q.count(n.start) == 0) {
        throw std::runtime_error("el estado inicial " + n.start + " no está en states");
    }
    for (const std::string& f : n.accept) {
        if (q.count(f) == 0) {
            throw std::runtime_error("el estado de aceptación " + f + " no está en states");
        }
    }
    for (const auto& [key, targets] : n.delta) {
        if (q.count(key.first) == 0) {
            throw std::runtime_error("transición desde " + key.first + ", que no está en states");
        }
        if (key.second != EPS && sigma.count(key.second) == 0) {
            throw std::runtime_error(std::string("transición con ") + key.second + ", que no está en alphabet");
        }
        for (const std::string& target : targets) {
            if (q.count(target) == 0) {
                throw std::runtime_error("transición hacia " + target + ", que no está en states");
            }
        }
    }
}

// ------------------------------------------------------------
// Leer y escribir el formato .nfa
// ------------------------------------------------------------

inline std::vector<std::string> split_nfa_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

// Lee una descripción completa, hasta el final de la entrada.
inline Nfa read_nfa(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    // Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
    auto next_line = [&in, &number](std::vector<std::string>& words) {
        std::string line;
        while (std::getline(in, line)) {
            number++;
            if (!line.empty() && line[0] == '#') {
                continue;
            }
            words = split_nfa_words(line);
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };

    Nfa n;
    n.states = field("states");
    for (const std::string& symbol : field("alphabet")) {
        if (symbol.size() != 1 || symbol[0] == '#') {
            fail("un símbolo es un solo carácter distinto de #: " + symbol);
        }
        n.alphabet.push_back(symbol[0]);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1) {
        fail("start: lleva exactamente un estado");
    }
    n.start = start[0];
    for (const std::string& state : field("accept")) {
        n.accept.insert(state);
    }
    if (!field("delta").empty()) {
        fail("después de delta: las transiciones van una por línea");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        // estado símbolo destino…  con eps en el lugar del símbolo para una transición ε
        if (words.size() < 3 || (words[1] != "eps" && words[1].size() != 1)) {
            fail("una transición se escribe: estado símbolo destino…");
        }
        char a = (words[1] == "eps") ? EPS : words[1][0];
        for (std::size_t i = 2; i < words.size(); i++) {
            n.delta[{words[0], a}].insert(words[i]);
        }
    }
    check_nfa(n);
    return n;
}

inline Nfa load_nfa(const std::string& path) {
    std::ifstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    try {
        return read_nfa(file);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(path + ": " + error.what());
    }
}

// Escribe n en el formato .nfa. Un par de estado y símbolo sin transiciones no lleva línea.
inline void write_nfa(std::ostream& out, const Nfa& n) {
    out << "states:";
    for (const std::string& state : n.states) {
        out << ' ' << state;
    }
    out << "\nalphabet:";
    for (char a : n.alphabet) {
        out << ' ' << a;
    }
    out << "\nstart: " << n.start << "\naccept:";
    for (const std::string& state : n.states) {
        if (n.accept.count(state) > 0) {
            out << ' ' << state;
        }
    }
    out << "\ndelta:\n";
    std::vector<char> labels = n.alphabet;
    labels.push_back(EPS);
    for (const std::string& state : n.states) {
        for (char a : labels) {
            auto it = n.delta.find({state, a});
            if (it == n.delta.end() || it->second.empty()) {
                continue;
            }
            out << state << ' ' << (a == EPS ? std::string("eps") : std::string(1, a));
            // Los destinos, en el orden de states.
            for (const std::string& target : n.states) {
                if (it->second.count(target) > 0) {
                    out << ' ' << target;
                }
            }
            out << '\n';
        }
    }
}

// ------------------------------------------------------------
// Ejecutar: el conjunto de estados activos
// ------------------------------------------------------------

// Clausura ε: los estados de s y todos los que se alcanzan desde ellos con transiciones ε.
// Es una búsqueda en el grafo de las transiciones ε.
inline StateSet eps_closure(const Nfa& n, const StateSet& s) {
    StateSet closure = s;
    std::vector<std::string> pending(s.begin(), s.end());
    while (!pending.empty()) {
        std::string q = pending.back();
        pending.pop_back();
        auto it = n.delta.find({q, EPS});
        if (it == n.delta.end()) {
            continue;
        }
        for (const std::string& target : it->second) {
            if (closure.insert(target).second) {
                pending.push_back(target);
            }
        }
    }
    return closure;
}

// Un paso: desde los estados de s, leer el símbolo a y después seguir las transiciones ε.
inline StateSet step(const Nfa& n, const StateSet& s, char a) {
    StateSet next;
    for (const std::string& q : s) {
        auto it = n.delta.find({q, a});
        if (it != n.delta.end()) {
            next.insert(it->second.begin(), it->second.end());
        }
    }
    return eps_closure(n, next);
}

// Los conjuntos de estados activos S0, S1, …, Sn: S0 es la clausura ε de {q0}, y S(i) es el
// conjunto de estados en los que el NFA puede estar después de leer los primeros i símbolos.
inline std::vector<StateSet> run(const Nfa& n, const std::string& w) {
    std::vector<StateSet> sets = {eps_closure(n, {n.start})};
    for (char a : w) {
        sets.push_back(step(n, sets.back(), a));
    }
    return sets;
}

// N acepta w si, después de leerla, algún estado activo es de aceptación.
inline bool accepts(const Nfa& n, const std::string& w) {
    StateSet active = eps_closure(n, {n.start});
    for (char a : w) {
        active = step(n, active, a);
    }
    for (const std::string& q : active) {
        if (n.accept.count(q) > 0) {
            return true;
        }
    }
    return false;
}

// Para imprimir un conjunto de estados en el orden de states: {q0, q3}.
inline std::string show_set(const Nfa& n, const StateSet& s) {
    std::string text = "{";
    for (const std::string& state : n.states) {
        if (s.count(state) > 0) {
            text += (text.size() > 1 ? ", " : "") + state;
        }
    }
    return text + "}";
}

#endif
