// Autómata finito no determinista generalizado (GNFA): las flechas llevan expresiones
// regulares en lugar de símbolos. Sirve para convertir un DFA en una expresión regular
// eliminando sus estados de uno en uno.
#ifndef GNFA_H
#define GNFA_H

#include <map>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "dfa.h"
#include "regex.h"

struct Gnfa {
    std::vector<std::string> states;                                 // Q, con start y accept
    std::string start;                                               // no le entra ninguna flecha
    std::string accept;                                              // no le sale ninguna flecha
    std::map<std::pair<std::string, std::string>, RegexPtr> arrow;   // la expresión de i a j
};

// La expresión de la flecha de i a j. Una flecha que no está dibujada lleva ∅.
inline RegexPtr label(const Gnfa& g, const std::string& i, const std::string& j) {
    auto it = g.arrow.find({i, j});
    return it == g.arrow.end() ? empty_set() : it->second;
}

// Un nombre que no esté usado: base, o base con apóstrofos.
inline std::string fresh_name(const std::set<std::string>& used, std::string base) {
    while (used.count(base) > 0) {
        base += "'";
    }
    return base;
}

// Normalizar: un estado inicial nuevo con una flecha ε al inicial del DFA, y un único estado
// de aceptación nuevo al que llega una flecha ε desde cada estado de aceptación del DFA.
// Las flechas del DFA entre dos mismos estados se juntan en una sola, con la unión de sus
// símbolos.
inline Gnfa to_gnfa(const Dfa& m) {
    std::set<std::string> used(m.states.begin(), m.states.end());
    Gnfa g;
    g.start = fresh_name(used, "ini");
    used.insert(g.start);
    g.accept = fresh_name(used, "fin");
    g.states.push_back(g.start);
    g.states.insert(g.states.end(), m.states.begin(), m.states.end());
    g.states.push_back(g.accept);
    g.arrow[{g.start, m.start}] = epsilon();
    for (const std::string& q : m.states) {
        if (m.accept.count(q) > 0) {
            g.arrow[{q, g.accept}] = epsilon();
        }
        for (char a : m.alphabet) {
            const std::string& target = step(m, q, a);
            g.arrow[{q, target}] = simple_union(label(g, q, target), symbol(a));
        }
    }
    return g;
}

// Eliminar el estado k. Para cada pareja (i, j) de los estados que quedan, la flecha nueva es
//     R(i, j) ∪ R(i, k) R(k, k)* R(k, j)
// Las operaciones aplican las identidades de ∅ y de ε, para no arrastrar términos vacíos.
inline Gnfa eliminate(const Gnfa& g, const std::string& k) {
    if (k == g.start || k == g.accept) {
        throw std::runtime_error("no se elimina el estado inicial ni el de aceptación");
    }
    Gnfa result;
    result.start = g.start;
    result.accept = g.accept;
    for (const std::string& q : g.states) {
        if (q != k) {
            result.states.push_back(q);
        }
    }
    if (result.states.size() == g.states.size()) {
        throw std::runtime_error("el estado " + k + " no está en el autómata");
    }
    RegexPtr loop = simple_star(label(g, k, k));
    for (const std::string& i : result.states) {
        if (i == g.accept) {
            continue;  // del estado de aceptación no sale nada
        }
        for (const std::string& j : result.states) {
            if (j == g.start) {
                continue;  // al estado inicial no entra nada
            }
            RegexPtr through = simple_concat(simple_concat(label(g, i, k), loop), label(g, k, j));
            RegexPtr merged = simple_union(label(g, i, j), through);
            if (merged->kind != Kind::Empty) {
                result.arrow[{i, j}] = merged;
            }
        }
    }
    return result;
}

// De DFA a expresión regular, eliminando los estados en el orden dado.
// El orden debe nombrar cada estado del DFA exactamente una vez.
inline RegexPtr to_regex(const Dfa& m, const std::vector<std::string>& order) {
    std::set<std::string> named(order.begin(), order.end());
    std::set<std::string> all(m.states.begin(), m.states.end());
    if (order.size() != m.states.size() || named != all) {
        throw std::runtime_error("el orden debe nombrar cada estado una vez");
    }
    Gnfa g = to_gnfa(m);
    for (const std::string& k : order) {
        g = eliminate(g, k);
    }
    return label(g, g.start, g.accept);
}

#endif
