// Gramática libre de contexto. El struct tiene los cuatro componentes de la definición
// G = (V, Σ, R, S), con los nombres del formato .cfg de code/formats.md.
// Además: leer y escribir ese formato, quitar las variables que no sirven, y las cadenas que
// genera una gramática hasta una longitud dada.
#ifndef CFG_H
#define CFG_H

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

// Una regla A → X1 X2 … Xk. Cada símbolo del lado derecho es el nombre de una variable o un
// terminal (una cadena de un solo carácter). La regla A → ε tiene el lado derecho vacío.
struct Rule {
    std::string head;
    std::vector<std::string> body;
    bool operator==(const Rule& other) const = default;
};

struct Cfg {
    std::vector<std::string> variables;  // V, en el orden del archivo
    std::vector<char> terminals;         // Σ
    std::vector<Rule> rules;             // R
    std::string start;                   // S ∈ V
};

inline bool is_variable(const Cfg& g, const std::string& symbol) {
    return std::find(g.variables.begin(), g.variables.end(), symbol) != g.variables.end();
}

inline bool is_terminal(const Cfg& g, const std::string& symbol) {
    return symbol.size() == 1 && std::find(g.terminals.begin(), g.terminals.end(), symbol[0]) != g.terminals.end();
}

// Lanza std::runtime_error si g no cumple la definición.
inline void check_cfg(const Cfg& g) {
    std::set<std::string> v(g.variables.begin(), g.variables.end());
    std::set<char> sigma(g.terminals.begin(), g.terminals.end());
    if (g.variables.empty()) {
        throw std::runtime_error("V no puede ser vacío");
    }
    if (v.size() != g.variables.size()) {
        throw std::runtime_error("hay una variable repetida en variables");
    }
    if (sigma.size() != g.terminals.size()) {
        throw std::runtime_error("hay un terminal repetido en terminals");
    }
    for (const std::string& name : g.variables) {
        if (name == "eps" || name == "->" || name == "|") {
            throw std::runtime_error("una variable no puede llamarse " + name);
        }
        if (name.size() == 1 && sigma.count(name[0]) > 0) {
            throw std::runtime_error(name + " es variable y terminal a la vez: V y Σ no comparten símbolos");
        }
    }
    if (sigma.count('|') > 0) {
        throw std::runtime_error("el terminal | se confunde con el separador de alternativas");
    }
    if (v.count(g.start) == 0) {
        throw std::runtime_error("la variable inicial " + g.start + " no está en variables");
    }
    for (const Rule& rule : g.rules) {
        if (v.count(rule.head) == 0) {
            throw std::runtime_error("regla de " + rule.head + ", que no está en variables");
        }
        for (const std::string& symbol : rule.body) {
            bool terminal = symbol.size() == 1 && sigma.count(symbol[0]) > 0;
            if (v.count(symbol) == 0 && !terminal) {
                throw std::runtime_error("en una regla de " + rule.head + ": " + symbol +
                                         " no es una variable ni un terminal");
            }
        }
    }
}

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

inline std::vector<std::string> cfg_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 Cfg read_cfg(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 = cfg_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;
    };

    Cfg g;
    g.variables = field("variables");
    for (const std::string& word : field("terminals")) {
        if (word.size() != 1 || word[0] == '#') {
            fail("un terminal es un solo carácter distinto de #: " + word);
        }
        g.terminals.push_back(word[0]);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1) {
        fail("start: lleva exactamente una variable");
    }
    g.start = start[0];
    if (!field("rules").empty()) {
        fail("después de rules: las reglas van una por línea");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        if (words.size() < 3 || words[1] != "->") {
            fail("una regla se escribe: variable -> alternativa | alternativa");
        }
        Rule rule;
        rule.head = words[0];
        // Cierra la alternativa que se venía leyendo. eps solo, o nada, es la alternativa vacía.
        auto close = [&g, &rule, &fail]() {
            if (rule.body.empty()) {
                fail("alternativa vacía: la cadena vacía se escribe eps");
            }
            if (rule.body.size() == 1 && rule.body[0] == "eps") {
                rule.body.clear();
            }
            g.rules.push_back(rule);
            rule.body.clear();
        };
        for (std::size_t i = 2; i < words.size(); i++) {
            if (words[i] == "|") {
                close();
            } else {
                rule.body.push_back(words[i]);
            }
        }
        close();
    }
    try {
        check_cfg(g);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(std::string("la gramática no es válida: ") + error.what());
    }
    return g;
}

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

// Escribe g en el formato .cfg, con las alternativas de cada variable en una sola línea.
inline void write_cfg(std::ostream& out, const Cfg& g) {
    out << "variables:";
    for (const std::string& name : g.variables) {
        out << ' ' << name;
    }
    out << "\nterminals:";
    for (char a : g.terminals) {
        out << ' ' << a;
    }
    out << "\nstart: " << g.start << "\nrules:\n";
    for (const std::string& name : g.variables) {
        bool first = true;
        for (const Rule& rule : g.rules) {
            if (rule.head != name) {
                continue;
            }
            out << (first ? name + " ->" : " |");
            first = false;
            if (rule.body.empty()) {
                out << " eps";
            }
            for (const std::string& symbol : rule.body) {
                out << ' ' << symbol;
            }
        }
        if (!first) {
            out << '\n';
        }
    }
}

// ------------------------------------------------------------
// Variables que no sirven
// ------------------------------------------------------------

// Las variables que generan alguna cadena de terminales. Se calculan marcando: una variable se
// marca cuando tiene una regla cuyo lado derecho solo tiene terminales y variables marcadas.
inline std::set<std::string> generating_variables(const Cfg& g) {
    std::set<std::string> v(g.variables.begin(), g.variables.end());
    std::set<std::string> marked;
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            if (marked.count(rule.head) > 0) {
                continue;
            }
            bool all = true;
            for (const std::string& symbol : rule.body) {
                if (v.count(symbol) > 0 && marked.count(symbol) == 0) {
                    all = false;
                    break;
                }
            }
            if (all) {
                marked.insert(rule.head);
                changed = true;
            }
        }
    }
    return marked;
}

// La misma gramática sin las variables que no generan nada y sin las que no se alcanzan desde
// la inicial. Genera el mismo lenguaje. La variable inicial se conserva siempre.
inline Cfg remove_useless(const Cfg& g) {
    std::set<std::string> v(g.variables.begin(), g.variables.end());
    std::set<std::string> generating = generating_variables(g);
    // Primero se quitan las reglas que usan una variable que no genera nada.
    std::vector<Rule> kept;
    for (const Rule& rule : g.rules) {
        bool ok = generating.count(rule.head) > 0;
        for (const std::string& symbol : rule.body) {
            if (v.count(symbol) > 0 && generating.count(symbol) == 0) {
                ok = false;
            }
        }
        if (ok) {
            kept.push_back(rule);
        }
    }
    // Después, las variables a las que no se llega desde la inicial con las reglas que quedan.
    std::set<std::string> reached = {g.start};
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : kept) {
            if (reached.count(rule.head) == 0) {
                continue;
            }
            for (const std::string& symbol : rule.body) {
                if (v.count(symbol) > 0 && reached.insert(symbol).second) {
                    changed = true;
                }
            }
        }
    }
    Cfg result;
    result.terminals = g.terminals;
    result.start = g.start;
    for (const std::string& name : g.variables) {
        if (reached.count(name) > 0) {
            result.variables.push_back(name);
        }
    }
    for (const Rule& rule : kept) {
        if (reached.count(rule.head) > 0) {
            result.rules.push_back(rule);
        }
    }
    return result;
}

// ------------------------------------------------------------
// Las cadenas que genera una gramática
// ------------------------------------------------------------

// Para cada variable A, el conjunto de las cadenas de terminales w con A ⇒* w y |w| ≤ n.
// Se calcula por punto fijo: se empieza con conjuntos vacíos y se aplican las reglas, A → X1 … Xk
// agrega a A las concatenaciones de una cadena de cada Xi, hasta que ningún conjunto crece.
// Termina porque hay una cantidad finita de cadenas de longitud a lo sumo n. Es correcto para
// cualquier gramática, también con reglas ε y con recursión por la izquierda.
inline std::map<std::string, std::set<std::string>> languages_up_to(const Cfg& g, std::size_t n) {
    std::set<std::string> v(g.variables.begin(), g.variables.end());
    std::map<std::string, std::set<std::string>> table;
    for (const std::string& name : g.variables) {
        table[name];
    }
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            std::set<std::string> partial = {""};
            for (const std::string& symbol : rule.body) {
                std::set<std::string> next;
                if (v.count(symbol) > 0) {
                    for (const std::string& left : partial) {
                        for (const std::string& right : table[symbol]) {
                            if (left.size() + right.size() <= n) {
                                next.insert(left + right);
                            }
                        }
                    }
                } else {
                    for (const std::string& left : partial) {
                        if (left.size() + 1 <= n) {
                            next.insert(left + symbol);
                        }
                    }
                }
                partial = next;
                if (partial.empty()) {
                    break;
                }
            }
            std::set<std::string>& target = table[rule.head];
            for (const std::string& w : partial) {
                if (target.insert(w).second) {
                    changed = true;
                }
            }
        }
    }
    return table;
}

// Las cadenas de L(G) de longitud a lo sumo n.
inline std::set<std::string> strings_up_to(const Cfg& g, std::size_t n) {
    return languages_up_to(g, n)[g.start];
}

#endif
