// Autómata finito no determinista, con transiciones ε, en el formato .nfa de code/formats.md.
// Solo lo que hace falta esta semana: leerlo, y la construcción de subconjuntos de la semana 2,
// que es el paso 1 del algoritmo que decide A_NFA.
#ifndef NFA_H
#define NFA_H

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

#include "dfa.h"

const char EPS = '\0';  // la clave de las transiciones ε en delta

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

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);
    };
    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_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::set<std::string> q(n.states.begin(), n.states.end());
    std::set<char> sigma(n.alphabet.begin(), n.alphabet.end());
    std::vector<std::string> words;
    while (next_line(words)) {
        if (words.size() < 3) {
            fail("una transición se escribe: estado símbolo destino...");
        }
        char symbol = EPS;
        if (words[1] != "eps") {
            if (words[1].size() != 1 || sigma.count(words[1][0]) == 0) {
                fail("símbolo desconocido: " + words[1]);
            }
            symbol = words[1][0];
        }
        if (q.count(words[0]) == 0) {
            fail("estado desconocido: " + words[0]);
        }
        for (std::size_t i = 2; i < words.size(); i++) {
            if (q.count(words[i]) == 0) {
                fail("estado desconocido: " + words[i]);
            }
            n.delta[{words[0], symbol}].insert(words[i]);
        }
    }
    if (q.count(n.start) == 0) {
        fail("el estado inicial no está en states");
    }
    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());
    }
}

// Clausura ε: los estados a los que se llega desde el conjunto con cero o más transiciones ε.
inline std::set<std::string> eps_closure(const Nfa& n, std::set<std::string> current) {
    std::queue<std::string> pending;
    for (const std::string& q : current) {
        pending.push(q);
    }
    while (!pending.empty()) {
        std::string q = pending.front();
        pending.pop();
        auto it = n.delta.find({q, EPS});
        if (it == n.delta.end()) {
            continue;
        }
        for (const std::string& next : it->second) {
            if (current.insert(next).second) {
                pending.push(next);
            }
        }
    }
    return current;
}

// Un paso del conjunto de estados activos con el símbolo a, con su clausura ε.
inline std::set<std::string> move(const Nfa& n, const std::set<std::string>& current, char a) {
    std::set<std::string> next;
    for (const std::string& q : current) {
        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);
}

// El nombre del estado del DFA que corresponde a un conjunto de estados del NFA: {q0,q2}.
inline std::string set_name(const std::set<std::string>& subset) {
    std::string name = "{";
    for (const std::string& q : subset) {
        name += (name.size() > 1 ? "," : "") + q;
    }
    return name + "}";
}

// Construcción de subconjuntos. Con all_subsets = false genera solo los subconjuntos
// alcanzables desde la clausura ε de {q0}; con true, los 2^|Q|, como dice el teorema.
inline Dfa subset_construction(const Nfa& n, bool all_subsets = false) {
    Dfa d;
    d.alphabet = n.alphabet;
    std::set<std::string> first = eps_closure(n, {n.start});
    d.start = set_name(first);
    std::vector<std::set<std::string>> subsets;
    if (all_subsets) {
        if (n.states.size() > 20) {
            throw std::runtime_error("demasiados estados para generar todos los subconjuntos");
        }
        for (std::size_t mask = 0; mask < (std::size_t{1} << n.states.size()); mask++) {
            std::set<std::string> subset;
            for (std::size_t i = 0; i < n.states.size(); i++) {
                if ((mask >> i) & 1) {
                    subset.insert(n.states[i]);
                }
            }
            subsets.push_back(subset);
        }
    } else {
        std::set<std::set<std::string>> seen = {first};
        subsets.push_back(first);
        for (std::size_t i = 0; i < subsets.size(); i++) {
            for (char a : n.alphabet) {
                std::set<std::string> next = move(n, subsets[i], a);
                if (seen.insert(next).second) {
                    subsets.push_back(next);
                }
            }
        }
    }
    for (const std::set<std::string>& subset : subsets) {
        std::string name = set_name(subset);
        d.states.push_back(name);
        for (const std::string& q : subset) {
            if (n.accept.count(q) > 0) {
                d.accept.insert(name);
                break;
            }
        }
        for (char a : n.alphabet) {
            d.delta[{name, a}] = set_name(move(n, subset, a));
        }
    }
    check_dfa(d);
    return d;
}

#endif
