// Forma normal de Chomsky: la conversión en cuatro pasos y el algoritmo CYK.
// Cada paso es una función que recibe una gramática y devuelve otra que genera el mismo lenguaje.
#ifndef CHOMSKY_H
#define CHOMSKY_H

#include <algorithm>
#include <cstddef>
#include <map>
#include <ostream>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "cfg.h"

// Un nombre de variable que la gramática todavía no usa: base, base', base''…
inline std::string fresh_name(const Cfg& g, const std::string& base) {
    std::string name = base;
    while (is_variable(g, name) || is_terminal(g, name)) {
        name += "'";
    }
    return name;
}

// ------------------------------------------------------------
// ¿Está en forma normal de Chomsky?
// ------------------------------------------------------------

// Devuelve "" si toda regla es A → BC (con B y C variables distintas de la inicial), A → a,
// o S → ε con S la variable inicial. Si no, devuelve la primera regla que lo impide y por qué.
inline std::string why_not_chomsky(const Cfg& g) {
    for (const Rule& rule : g.rules) {
        std::string text = rule.head + " -> " + body_text(rule.body);
        if (rule.body.empty()) {
            if (rule.head != g.start) {
                return text + ": solo la variable inicial puede tener una regla ε";
            }
        } else if (rule.body.size() == 1) {
            if (is_variable(g, rule.body[0])) {
                return text + ": es una regla unitaria";
            }
        } else if (rule.body.size() == 2) {
            for (const std::string& symbol : rule.body) {
                if (!is_variable(g, symbol)) {
                    return text + ": en una regla de dos símbolos, los dos son variables";
                }
                if (symbol == g.start) {
                    return text + ": la variable inicial no aparece a la derecha";
                }
            }
        } else {
            return text + ": el lado derecho tiene más de dos símbolos";
        }
    }
    return "";
}

inline bool is_chomsky(const Cfg& g) {
    return why_not_chomsky(g).empty();
}

// ------------------------------------------------------------
// Paso 1: variable inicial nueva
// ------------------------------------------------------------

// Agrega S0 → S. Después de este paso la variable inicial no aparece en ningún lado derecho.
inline Cfg with_new_start(const Cfg& g) {
    Cfg result = g;
    result.start = fresh_name(g, g.start + "0");
    result.variables.insert(result.variables.begin(), result.start);
    result.rules.insert(result.rules.begin(), Rule{result.start, {g.start}});
    return result;
}

// ------------------------------------------------------------
// Paso 2: quitar las reglas ε
// ------------------------------------------------------------

// Las variables anulables: las que derivan ε. A es anulable si tiene una regla cuyo lado
// derecho son solo variables anulables (la regla A → ε es el caso de cero símbolos).
inline std::set<std::string> nullable_variables(const Cfg& g) {
    std::set<std::string> nullable;
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            bool all = true;
            for (const std::string& symbol : rule.body) {
                all = all && nullable.count(symbol) > 0;
            }
            if (all && nullable.insert(rule.head).second) {
                changed = true;
            }
        }
    }
    return nullable;
}

// Por cada regla A → X1…Xk, quedan todas las reglas que se obtienen borrando algunas
// apariciones de variables anulables, salvo la que borra todo. Si la variable inicial es
// anulable, conserva su regla ε.
inline Cfg without_epsilon_rules(const Cfg& g) {
    std::set<std::string> nullable = nullable_variables(g);
    Cfg result = g;
    result.rules.clear();
    for (const Rule& rule : g.rules) {
        std::vector<std::size_t> positions;  // las apariciones de variables anulables
        for (std::size_t i = 0; i < rule.body.size(); i++) {
            if (nullable.count(rule.body[i]) > 0) {
                positions.push_back(i);
            }
        }
        if (positions.size() > 20) {
            throw std::runtime_error("una regla tiene más de 20 variables anulables: saldrían más de un millón");
        }
        // Cada subconjunto de esas apariciones es una máscara de bits: el bit b dice si se borra positions[b].
        for (unsigned long mask = 0; mask < (1UL << positions.size()); mask++) {
            Rule shorter{rule.head, {}};
            for (std::size_t i = 0; i < rule.body.size(); i++) {
                auto where = std::find(positions.begin(), positions.end(), i);
                bool erased = where != positions.end() && ((mask >> (where - positions.begin())) & 1UL) != 0;
                if (!erased) {
                    shorter.body.push_back(rule.body[i]);
                }
            }
            if (!shorter.body.empty()) {
                add_rule(result, shorter);
            }
        }
    }
    if (nullable.count(g.start) > 0) {
        add_rule(result, Rule{g.start, {}});
    }
    return result;
}

// ------------------------------------------------------------
// Paso 3: quitar las reglas unitarias
// ------------------------------------------------------------

inline bool is_unit(const Cfg& g, const Rule& rule) {
    return rule.body.size() == 1 && is_variable(g, rule.body[0]);
}

// Los pares (A, B) tales que A ⇒* B usando solo reglas unitarias. Incluye los pares (A, A).
inline std::set<std::pair<std::string, std::string>> unit_pairs(const Cfg& g) {
    std::set<std::pair<std::string, std::string>> pairs;
    for (const std::string& name : g.variables) {
        pairs.insert({name, name});
    }
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            if (!is_unit(g, rule)) {
                continue;
            }
            // Si A llega a rule.head, también llega a rule.body[0].
            for (const std::string& a : g.variables) {
                if (pairs.count({a, rule.head}) > 0 && pairs.insert({a, rule.body[0]}).second) {
                    changed = true;
                }
            }
        }
    }
    return pairs;
}

// Por cada par (A, B) y cada regla B → u que no es unitaria, queda la regla A → u.
inline Cfg without_unit_rules(const Cfg& g) {
    std::set<std::pair<std::string, std::string>> pairs = unit_pairs(g);
    Cfg result = g;
    result.rules.clear();
    for (const std::string& a : g.variables) {
        for (const std::string& b : g.variables) {
            if (pairs.count({a, b}) == 0) {
                continue;
            }
            for (const Rule& rule : g.rules) {
                if (rule.head == b && !is_unit(g, rule)) {
                    add_rule(result, Rule{a, rule.body});
                }
            }
        }
    }
    return result;
}

// ------------------------------------------------------------
// Paso 4: partir las reglas largas y sacar los terminales de las reglas de dos símbolos
// ------------------------------------------------------------

// A → X1 X2 … Xk con k ≥ 3 se cambia por A → X1 A_1, A_1 → X2 A_2, …, A_(k−2) → X(k−1) Xk.
// Después, en cada regla de dos símbolos, un terminal a se cambia por una variable U_a con
// la única regla U_a → a.
inline Cfg with_short_rules(const Cfg& g) {
    Cfg result = g;
    result.rules.clear();
    std::map<std::string, int> pieces;  // cuántas variables nuevas lleva cada variable original
    for (const Rule& rule : g.rules) {
        if (rule.body.size() <= 2) {
            add_rule(result, rule);
            continue;
        }
        std::string head = rule.head;
        for (std::size_t i = 0; i + 2 < rule.body.size(); i++) {
            pieces[rule.head]++;
            std::string piece = fresh_name(result, rule.head + "_" + std::to_string(pieces[rule.head]));
            result.variables.push_back(piece);
            add_rule(result, Rule{head, {rule.body[i], piece}});
            head = piece;
        }
        add_rule(result, Rule{head, {rule.body[rule.body.size() - 2], rule.body[rule.body.size() - 1]}});
    }
    std::map<std::string, std::string> variable_of;  // terminal → su variable U_a
    for (Rule& rule : result.rules) {
        if (rule.body.size() != 2) {
            continue;
        }
        for (std::string& symbol : rule.body) {
            if (is_variable(result, symbol)) {
                continue;
            }
            if (variable_of.count(symbol) == 0) {
                variable_of[symbol] = fresh_name(result, "U_" + symbol);
                result.variables.push_back(variable_of[symbol]);
            }
            symbol = variable_of[symbol];
        }
    }
    for (char a : g.terminals) {
        std::string terminal(1, a);
        if (variable_of.count(terminal) > 0) {
            result.rules.push_back(Rule{variable_of[terminal], {terminal}});
        }
    }
    // Al cambiar terminales por variables, dos reglas distintas pueden haber quedado iguales.
    Cfg clean = result;
    clean.rules.clear();
    for (const Rule& rule : result.rules) {
        add_rule(clean, rule);
    }
    return clean;
}

// Los cuatro pasos, en el orden correcto.
inline Cfg to_chomsky(const Cfg& g) {
    return with_short_rules(without_unit_rules(without_epsilon_rules(with_new_start(g))));
}

// ------------------------------------------------------------
// CYK
// ------------------------------------------------------------

struct CykTable {
    std::size_t n = 0;
    // cell[i][j], con 0 ≤ i ≤ j < n: las variables que generan la subcadena w[i..j].
    std::vector<std::vector<std::set<std::string>>> cell;
    long checks = 0;  // cuántas veces se probó una regla A → BC con un punto de corte
};

// Llena la tabla por longitudes crecientes de subcadena. g debe estar en forma normal de Chomsky.
inline CykTable cyk(const Cfg& g, const std::string& w) {
    std::string why = why_not_chomsky(g);
    if (!why.empty()) {
        throw std::runtime_error("CYK necesita una gramática en forma normal de Chomsky. " + why);
    }
    CykTable table;
    table.n = w.size();
    std::size_t n = w.size();
    table.cell.assign(n, std::vector<std::set<std::string>>(n));
    // Longitud 1: las reglas A → a.
    for (std::size_t i = 0; i < n; i++) {
        for (const Rule& rule : g.rules) {
            if (rule.body.size() == 1 && rule.body[0] == std::string(1, w[i])) {
                table.cell[i][i].insert(rule.head);
            }
        }
    }
    // Longitud ≥ 2: las reglas A → BC, con B para w[i..k] y C para w[k+1..j].
    for (std::size_t length = 2; length <= n; length++) {
        for (std::size_t i = 0; i + length <= n; i++) {
            std::size_t j = i + length - 1;
            for (std::size_t k = i; k < j; k++) {
                for (const Rule& rule : g.rules) {
                    if (rule.body.size() != 2) {
                        continue;
                    }
                    table.checks++;
                    if (table.cell[i][k].count(rule.body[0]) > 0 && table.cell[k + 1][j].count(rule.body[1]) > 0) {
                        table.cell[i][j].insert(rule.head);
                    }
                }
            }
        }
    }
    return table;
}

// ¿w ∈ L(G)? La cadena vacía se decide aparte: solo la regla S → ε la genera.
inline bool cyk_accepts(const Cfg& g, const CykTable& table) {
    if (table.n == 0) {
        return std::find(g.rules.begin(), g.rules.end(), Rule{g.start, {}}) != g.rules.end();
    }
    return table.cell[0][table.n - 1].count(g.start) > 0;
}

inline bool cyk_accepts(const Cfg& g, const std::string& w) {
    return cyk_accepts(g, cyk(g, w));
}

// Un árbol de derivación de w[i..j] con raíz A. Requiere que A esté en cell[i][j].
// Vuelve a buscar una regla y un punto de corte que justifiquen esa entrada de la tabla, y
// se queda con los primeros que encuentra: si hay varios árboles, devuelve uno.
inline Tree cyk_subtree(const Cfg& g, const CykTable& table, const std::string& w, const std::string& a,
                        std::size_t i, std::size_t j) {
    if (i == j) {
        return Tree{a, {Tree{std::string(1, w[i]), {}}}};
    }
    for (std::size_t k = i; k < j; k++) {
        for (const Rule& rule : g.rules) {
            if (rule.head == a && rule.body.size() == 2 && table.cell[i][k].count(rule.body[0]) > 0 &&
                table.cell[k + 1][j].count(rule.body[1]) > 0) {
                Tree left = cyk_subtree(g, table, w, rule.body[0], i, k);
                Tree right = cyk_subtree(g, table, w, rule.body[1], k + 1, j);
                return Tree{a, {left, right}};
            }
        }
    }
    throw std::runtime_error(a + " no está en esa celda de la tabla");
}

// Un árbol de derivación de w. Requiere que la gramática genere w.
inline Tree cyk_tree(const Cfg& g, const CykTable& table, const std::string& w) {
    if (!cyk_accepts(g, table)) {
        throw std::runtime_error("la gramática no genera la cadena");
    }
    if (w.empty()) {
        return Tree{g.start, {Tree{"ε", {}}}};
    }
    return cyk_subtree(g, table, w, g.start, 0, w.size() - 1);
}

// Imprime la tabla: la fila i y la columna j tienen las variables que generan w[i..j].
inline void print_cyk_table(std::ostream& out, const Cfg& g, const CykTable& table, const std::string& w) {
    std::size_t n = table.n;
    std::vector<std::vector<std::string>> text(n, std::vector<std::string>(n));
    std::size_t width = 5;
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t j = i; j < n; j++) {
            // Las variables en el orden de la gramática, no en orden alfabético.
            for (const std::string& name : g.variables) {
                if (table.cell[i][j].count(name) > 0) {
                    text[i][j] += (text[i][j].empty() ? "" : ",") + name;
                }
            }
            text[i][j] = text[i][j].empty() ? "∅" : "{" + text[i][j] + "}";
            // El símbolo ∅ ocupa tres bytes y una sola columna.
            std::size_t shown = text[i][j] == "∅" ? 1 : text[i][j].size();
            width = std::max(width, shown + 2);
        }
    }
    auto padded = [width](const std::string& s, std::size_t shown) { return s + std::string(width - shown, ' '); };
    // Cada línea se arma completa y se le quitan los espacios del final.
    auto emit = [&out](std::string line) {
        while (!line.empty() && line.back() == ' ') {
            line.pop_back();
        }
        out << line << '\n';
    };
    std::string line = "       ";
    for (std::size_t j = 0; j < n; j++) {
        std::string header = "j=" + std::to_string(j) + " " + w[j];
        line += padded(header, header.size());
    }
    emit(line);
    for (std::size_t i = 0; i < n; i++) {
        std::string number = std::to_string(i);
        line = "i=" + number + std::string(number.size() < 3 ? 3 - number.size() : 0, ' ') + w[i] + " ";
        for (std::size_t j = 0; j < n; j++) {
            if (j < i) {
                line += padded("", 0);
            } else {
                line += padded(text[i][j], text[i][j] == "∅" ? 1 : text[i][j].size());
            }
        }
        emit(line);
    }
}

// Cuántos árboles de derivación tiene w con raíz en la variable inicial. Es la misma tabla,
// con un número por variable en lugar de un sí o no: los árboles de A para w[i..j] son, sumando
// sobre las reglas A → BC y los cortes k, (árboles de B para w[i..k]) × (árboles de C para w[k+1..j]).
// El resultado se satura en MANY_TREES para no pasarse del tipo.
inline constexpr unsigned long long MANY_TREES = 1000000000000000000ULL;

inline unsigned long long count_trees(const Cfg& g, const std::string& w) {
    std::string why = why_not_chomsky(g);
    if (!why.empty()) {
        throw std::runtime_error("CYK necesita una gramática en forma normal de Chomsky. " + why);
    }
    std::size_t n = w.size();
    if (n == 0) {
        return cyk_accepts(g, w) ? 1 : 0;
    }
    std::vector<std::vector<std::map<std::string, unsigned long long>>> count(
        n, std::vector<std::map<std::string, unsigned long long>>(n));
    for (std::size_t i = 0; i < n; i++) {
        for (const Rule& rule : g.rules) {
            if (rule.body.size() == 1 && rule.body[0] == std::string(1, w[i])) {
                count[i][i][rule.head] = 1;
            }
        }
    }
    for (std::size_t length = 2; length <= n; length++) {
        for (std::size_t i = 0; i + length <= n; i++) {
            std::size_t j = i + length - 1;
            for (std::size_t k = i; k < j; k++) {
                for (const Rule& rule : g.rules) {
                    if (rule.body.size() != 2) {
                        continue;
                    }
                    auto left = count[i][k].find(rule.body[0]);
                    auto right = count[k + 1][j].find(rule.body[1]);
                    if (left == count[i][k].end() || right == count[k + 1][j].end()) {
                        continue;
                    }
                    unsigned long long& total = count[i][j][rule.head];
                    // left->second y right->second son a lo sumo 10^18, y su producto puede no caber.
                    if (left->second > MANY_TREES / right->second) {
                        total = MANY_TREES;
                    } else {
                        total = std::min(MANY_TREES, total + left->second * right->second);
                    }
                }
            }
        }
    }
    auto top = count[0][n - 1].find(g.start);
    return top == count[0][n - 1].end() ? 0 : top->second;
}

#endif
