// 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, las cadenas que genera una gramática hasta una longitud,
// las derivaciones por la izquierda de una cadena y sus árboles de derivación.
// Las funciones que leen líneas siguen el esquema de code/week-01/dfa.h.
#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();
}

// ------------------------------------------------------------
// Comprobar que la cuádrupla es una gramática
// ------------------------------------------------------------

// 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) {
            if (!is_variable(g, symbol) && !is_terminal(g, symbol)) {
                throw std::runtime_error("en una regla de " + rule.head + " aparece " + symbol +
                                         ", que no es variable ni terminal");
            }
        }
    }
}

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

inline std::vector<std::string> split_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;
}

// Agrega la regla si no estaba. Las reglas forman un conjunto: repetir una no cambia nada.
inline void add_rule(Cfg& g, const Rule& rule) {
    if (std::find(g.rules.begin(), g.rules.end(), rule) == g.rules.end()) {
        g.rules.push_back(rule);
    }
}

// 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);
    };
    // 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_words(line);
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    // Un campo: "nombre: valor valor ...". Devuelve los valores.
    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& symbol : field("terminals")) {
        if (symbol.size() != 1 || symbol[0] == '#') {
            fail("un terminal es un solo carácter distinto de #: " + symbol);
        }
        g.terminals.push_back(symbol[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)) {
        // variable -> alternativa | alternativa …
        if (words.size() < 3 || words[1] != "->") {
            fail("una regla se escribe: variable -> símbolos | símbolos");
        }
        Rule rule;
        rule.head = words[0];
        bool has_eps = false;
        for (std::size_t i = 2; i <= words.size(); i++) {
            if (i < words.size() && words[i] != "|") {
                if (words[i] == "eps") {
                    has_eps = true;
                } else {
                    rule.body.push_back(words[i]);
                }
                continue;
            }
            // Terminó una alternativa.
            if (has_eps ? !rule.body.empty() : rule.body.empty()) {
                fail("una alternativa es una lista de símbolos, o eps sola");
            }
            add_rule(g, rule);
            rule.body.clear();
            has_eps = false;
        }
    }
    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());
    }
}

// El lado derecho de una regla, con los símbolos separados por espacios, como en el archivo.
inline std::string body_text(const std::vector<std::string>& body) {
    if (body.empty()) {
        return "eps";
    }
    std::string text;
    for (const std::string& symbol : body) {
        text += (text.empty() ? "" : " ") + symbol;
    }
    return text;
}

// Escribe g en el formato .cfg: lo que escribe se puede volver a leer con read_cfg.
// Las alternativas de una variable van en una sola línea, en el orden en que están en R.
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) {
        std::string line;
        for (const Rule& rule : g.rules) {
            if (rule.head == name) {
                line += (line.empty() ? name + " -> " : " | ") + body_text(rule.body);
            }
        }
        if (!line.empty()) {
            out << line << '\n';
        }
    }
}

// ------------------------------------------------------------
// Las cadenas que genera una gramática, hasta una longitud
// ------------------------------------------------------------

// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_length, las más cortas primero.
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_length) {
    std::vector<std::string> result = {""};
    std::size_t begin = 0;
    for (std::size_t length = 1; length <= max_length; length++) {
        std::size_t end = result.size();
        for (std::size_t i = begin; i < end; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        begin = end;
    }
    return result;
}

// Para cada variable A, el conjunto { w : A ⇒* w y |w| ≤ max_length }.
// Se calcula sin buscar derivaciones: se parte de conjuntos vacíos y se aplican las reglas
// (si A → X1…Xk y cada Xi genera wi, entonces A genera w1…wk) hasta que ningún conjunto crece.
// Como solo hay una cantidad finita de cadenas de longitud ≤ max_length, siempre termina,
// también con reglas ε y con reglas como S → SS.
inline std::map<std::string, std::set<std::string>> generated_by_variable(const Cfg& g, std::size_t max_length) {
    std::map<std::string, std::set<std::string>> language;
    for (const std::string& name : g.variables) {
        language[name];
    }
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            std::set<std::string> partial = {""};  // lo que generan los primeros símbolos del lado derecho
            for (const std::string& symbol : rule.body) {
                std::set<std::string> next;
                if (is_variable(g, symbol)) {
                    for (const std::string& left : partial) {
                        for (const std::string& right : language[symbol]) {
                            if (left.size() + right.size() <= max_length) {
                                next.insert(left + right);
                            }
                        }
                    }
                } else {
                    for (const std::string& left : partial) {
                        if (left.size() + 1 <= max_length) {
                            next.insert(left + symbol);
                        }
                    }
                }
                partial = next;
            }
            std::set<std::string>& target = language[rule.head];
            for (const std::string& w : partial) {
                if (target.insert(w).second) {
                    changed = true;
                }
            }
        }
    }
    return language;
}

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

// Las mismas cadenas, de la más corta a la más larga.
inline std::vector<std::string> shortest_first(const std::set<std::string>& language) {
    std::vector<std::string> words(language.begin(), language.end());
    std::stable_sort(words.begin(), words.end(),
                     [](const std::string& a, const std::string& b) { return a.size() < b.size(); });
    return words;
}

// La longitud de la cadena más corta que genera cada variable. Una variable que no genera
// ninguna cadena queda con el valor NO_STRING.
inline constexpr std::size_t NO_STRING = static_cast<std::size_t>(-1);

inline std::map<std::string, std::size_t> shortest_lengths(const Cfg& g) {
    std::map<std::string, std::size_t> shortest;
    for (const std::string& name : g.variables) {
        shortest[name] = NO_STRING;
    }
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            std::size_t total = 0;
            bool possible = true;
            for (const std::string& symbol : rule.body) {
                if (!is_variable(g, symbol)) {
                    total += 1;
                } else if (shortest[symbol] == NO_STRING) {
                    possible = false;
                    break;
                } else {
                    total += shortest[symbol];
                }
            }
            if (possible && total < shortest[rule.head]) {
                shortest[rule.head] = total;
                changed = true;
            }
        }
    }
    return shortest;
}

// ------------------------------------------------------------
// Derivaciones por la izquierda
// ------------------------------------------------------------

// Una derivación por la izquierda queda determinada por la lista de reglas que usa, en orden:
// cada paso reemplaza la variable que está más a la izquierda. Se guardan las posiciones en g.rules.
using Derivation = std::vector<std::size_t>;

struct DerivationSearch {
    std::vector<Derivation> found;  // las derivaciones por la izquierda de w que se encontraron
    bool complete = true;           // false si la búsqueda se cortó por alguno de los dos topes
    long explored = 0;              // pasos de derivación que se probaron
};

// Busca todas las derivaciones por la izquierda de w, probando reglas con backtracking.
// Abandona un camino cuando lo ya derivado no puede terminar en w: los terminales que quedaron
// a la izquierda de la primera variable no son un prefijo de w, o lo que falta derivar ya no
// cabe en |w| símbolos. Con reglas ε o unitarias la búsqueda puede no terminar: por eso se
// corta a los max_steps pasos de cada derivación y al encontrar max_found derivaciones.
inline DerivationSearch leftmost_derivations(const Cfg& g, const std::string& w, std::size_t max_steps,
                                             std::size_t max_found = 1000) {
    DerivationSearch search;
    std::map<std::string, std::size_t> shortest = shortest_lengths(g);
    std::vector<std::string> form = {g.start};
    Derivation used;

    auto visit = [&](auto&& self) -> void {
        if (search.found.size() >= max_found) {
            search.complete = false;
            return;
        }
        // Los terminales antes de la primera variable deben coincidir con w.
        std::size_t first = 0;
        while (first < form.size() && !is_variable(g, form[first])) {
            if (first >= w.size() || form[first][0] != w[first]) {
                return;
            }
            first++;
        }
        if (first == form.size()) {
            if (form.size() == w.size()) {
                search.found.push_back(used);
            }
            return;
        }
        // Lo más corto que puede generar la forma no debe pasar de |w|.
        std::size_t least = 0;
        for (const std::string& symbol : form) {
            std::size_t add = is_variable(g, symbol) ? shortest[symbol] : 1;
            if (add == NO_STRING || least + add > w.size()) {
                return;
            }
            least += add;
        }
        if (used.size() >= max_steps) {
            search.complete = false;
            return;
        }
        std::string variable = form[first];
        for (std::size_t r = 0; r < g.rules.size(); r++) {
            if (g.rules[r].head != variable) {
                continue;
            }
            const std::vector<std::string>& body = g.rules[r].body;
            search.explored++;
            form.erase(form.begin() + static_cast<std::ptrdiff_t>(first));
            form.insert(form.begin() + static_cast<std::ptrdiff_t>(first), body.begin(), body.end());
            used.push_back(r);
            self(self);
            used.pop_back();
            form.erase(form.begin() + static_cast<std::ptrdiff_t>(first),
                       form.begin() + static_cast<std::ptrdiff_t>(first + body.size()));
            form.insert(form.begin() + static_cast<std::ptrdiff_t>(first), variable);
        }
    };
    visit(visit);
    return search;
}

// Las formas por las que pasa una derivación por la izquierda: S, …, w. Cada forma es una
// lista de símbolos.
inline std::vector<std::vector<std::string>> sentential_forms(const Cfg& g, const Derivation& derivation) {
    std::vector<std::vector<std::string>> forms = {{g.start}};
    for (std::size_t r : derivation) {
        std::vector<std::string> form = forms.back();
        std::size_t first = 0;
        while (first < form.size() && !is_variable(g, form[first])) {
            first++;
        }
        if (first == form.size() || form[first] != g.rules[r].head) {
            throw std::runtime_error("la lista de reglas no es una derivación por la izquierda");
        }
        form.erase(form.begin() + static_cast<std::ptrdiff_t>(first));
        form.insert(form.begin() + static_cast<std::ptrdiff_t>(first), g.rules[r].body.begin(),
                    g.rules[r].body.end());
        forms.push_back(form);
    }
    return forms;
}

// Una forma como texto. Si todas las variables son de una letra, los símbolos van pegados
// (aSb); si no, separados por espacios. La forma sin símbolos es ε.
inline std::string form_text(const Cfg& g, const std::vector<std::string>& form) {
    if (form.empty()) {
        return "ε";
    }
    bool spaced = false;
    for (const std::string& name : g.variables) {
        spaced = spaced || name.size() > 1;
    }
    std::string text;
    for (const std::string& symbol : form) {
        text += ((spaced && !text.empty()) ? " " : "") + symbol;
    }
    return text;
}

// ------------------------------------------------------------
// Árboles de derivación
// ------------------------------------------------------------

// Un nodo lleva una variable y tiene un hijo por cada símbolo de la regla que se le aplicó.
// Una hoja lleva un terminal o ε.
struct Tree {
    std::string symbol;
    std::vector<Tree> children;
};

// El árbol de una derivación por la izquierda. Los pasos de la derivación recorren el árbol
// en preorden: primero el nodo, después sus hijos de izquierda a derecha.
inline Tree tree_of(const Cfg& g, const Derivation& derivation) {
    std::size_t next = 0;
    auto build = [&](auto&& self, const std::string& symbol) -> Tree {
        Tree node{symbol, {}};
        if (!is_variable(g, symbol)) {
            return node;
        }
        if (next >= derivation.size() || g.rules[derivation[next]].head != symbol) {
            throw std::runtime_error("la lista de reglas no es una derivación por la izquierda");
        }
        const Rule& rule = g.rules[derivation[next]];
        next++;
        if (rule.body.empty()) {
            node.children.push_back(Tree{"ε", {}});
        }
        for (const std::string& child : rule.body) {
            node.children.push_back(self(self, child));
        }
        return node;
    };
    Tree root = build(build, g.start);
    if (next != derivation.size()) {
        throw std::runtime_error("sobran pasos en la derivación");
    }
    return root;
}

// Las hojas del árbol, de izquierda a derecha: la cadena que el árbol deriva.
inline std::string yield_of(const Tree& tree) {
    if (tree.children.empty()) {
        return tree.symbol == "ε" ? "" : tree.symbol;
    }
    std::string text;
    for (const Tree& child : tree.children) {
        text += yield_of(child);
    }
    return text;
}

// Cuántos nodos del árbol llevan una variable: es la cantidad de pasos de sus derivaciones.
inline std::size_t count_inner(const Tree& tree) {
    if (tree.children.empty()) {
        return 0;
    }
    std::size_t total = 1;
    for (const Tree& child : tree.children) {
        total += count_inner(child);
    }
    return total;
}

// El árbol es un árbol de derivación de g: en cada nodo interno hay una variable, y sus hijos
// son el lado derecho de alguna regla de esa variable.
inline bool is_parse_tree(const Cfg& g, const Tree& tree) {
    if (tree.children.empty()) {
        return tree.symbol == "ε" || is_terminal(g, tree.symbol);
    }
    Rule rule{tree.symbol, {}};
    for (const Tree& child : tree.children) {
        if (child.symbol != "ε" || !child.children.empty()) {
            rule.body.push_back(child.symbol);
        } else if (tree.children.size() != 1) {
            return false;
        }
        if (!is_parse_tree(g, child)) {
            return false;
        }
    }
    return std::find(g.rules.begin(), g.rules.end(), rule) != g.rules.end();
}

// Dibuja el árbol con una línea por nodo.
inline void print_tree(std::ostream& out, const Tree& tree, const std::string& indent = "",
                       const std::string& prefix = "") {
    out << prefix << tree.symbol << '\n';
    for (std::size_t i = 0; i < tree.children.size(); i++) {
        bool last = (i + 1 == tree.children.size());
        print_tree(out, tree.children[i], indent + (last ? "    " : "│   "), indent + (last ? "└── " : "├── "));
    }
}

// El árbol en una línea: [A hijo hijo …], y una hoja es su símbolo. Es el formato del laboratorio.
inline std::string bracket_text(const Tree& tree) {
    if (tree.children.empty()) {
        return tree.symbol == "ε" ? "eps" : tree.symbol;
    }
    std::string text = "[" + tree.symbol;
    for (const Tree& child : tree.children) {
        text += " " + bracket_text(child);
    }
    return text + "]";
}

#endif
