// Las dos construcciones que demuestran que las gramáticas libres de contexto y los autómatas
// de pila describen los mismos lenguajes:
//   cfg_to_pda     de una gramática a un PDA: la pila guarda lo que falta derivar
//   pda_to_cfg     de un PDA normalizado a una gramática: las variables A(p,q)
//   normalize_pda  lleva cualquier PDA a la forma que pda_to_cfg necesita
#ifndef CONVERT_H
#define CONVERT_H

#include <algorithm>
#include <cstddef>
#include <set>
#include <stdexcept>
#include <string>
#include <tuple>
#include <vector>

#include "cfg.h"
#include "pda.h"

// ------------------------------------------------------------
// De gramática a PDA
// ------------------------------------------------------------

// Construye un PDA que reconoce L(g). Tiene los estados q_start, q_begin, q_loop y q_accept,
// y los intermedios rN_J, que ponen en la pila el lado derecho de la regla número N, de
// derecha a izquierda, un símbolo por transición.
//   q_start --ε, ε → $--> q_begin --ε, ε → S--> q_loop
//   q_loop: para cada regla A → X1 … Xk, sacar A y poner X1 … Xk (X1 queda en la cima)
//   q_loop: para cada terminal a, leer a y sacar a
//   q_loop --ε, $ → ε--> q_accept
// Los símbolos de la pila son un solo carácter, así que las variables de g deben tener nombres
// de un carácter, y $ no puede ser un símbolo de g.
inline Pda cfg_to_pda(const Cfg& g) {
    check_cfg(g);
    Pda p;
    p.states = {"q_start", "q_begin", "q_loop", "q_accept"};
    p.alphabet = g.terminals;
    p.start = "q_start";
    p.accept = {"q_accept"};
    p.stack = g.terminals;
    for (const std::string& name : g.variables) {
        if (name.size() != 1) {
            throw std::runtime_error("la variable " + name + " debe tener un nombre de un solo carácter para ir en la pila");
        }
        p.stack.push_back(name[0]);
    }
    if (std::find(p.stack.begin(), p.stack.end(), '$') != p.stack.end()) {
        throw std::runtime_error("el símbolo $ marca el fondo de la pila: la gramática no puede usarlo");
    }
    p.stack.push_back('$');

    add_move(p, "q_start", EPS, EPS, "q_begin", '$');
    add_move(p, "q_begin", EPS, EPS, "q_loop", g.start[0]);
    for (std::size_t n = 0; n < g.rules.size(); n++) {
        const Rule& rule = g.rules[n];
        char head = rule.head[0];
        std::size_t k = rule.body.size();
        if (k == 0) {
            add_move(p, "q_loop", EPS, head, "q_loop", EPS);
            continue;
        }
        // Sacar A y poner Xk; después X(k-1), …, y al final X1, que vuelve a q_loop.
        std::string from = "q_loop";
        char pop = head;
        for (std::size_t j = k; j >= 1; j--) {
            std::string to = "q_loop";
            if (j > 1) {
                to = "r" + std::to_string(n + 1) + "_" + std::to_string(k - j + 1);
                p.states.push_back(to);
            }
            add_move(p, from, EPS, pop, to, rule.body[j - 1][0]);
            from = to;
            pop = EPS;
        }
    }
    for (char a : g.terminals) {
        add_move(p, "q_loop", a, a, "q_loop", EPS);
    }
    add_move(p, "q_loop", EPS, '$', "q_accept", EPS);
    check_pda(p);
    return p;
}

// ------------------------------------------------------------
// Normalizar un PDA
// ------------------------------------------------------------

// Las condiciones que se pueden comprobar mirando la descripción: un solo estado de aceptación,
// y cada transición saca un símbolo o pone un símbolo, pero no las dos cosas ni ninguna.
// La tercera condición, que la pila esté vacía al aceptar, depende de las ejecuciones.
inline bool has_normal_shape(const Pda& p) {
    if (p.accept.size() != 1) {
        return false;
    }
    for (const auto& [key, moves] : p.delta) {
        bool pops = std::get<2>(key) != EPS;
        for (const Move& move : moves) {
            bool pushes = move.push != EPS;
            if (pops == pushes) {
                return false;
            }
        }
    }
    return true;
}

// Un PDA que reconoce el mismo lenguaje que p y cumple las tres condiciones:
//   1. tiene un solo estado de aceptación, n_accept;
//   2. cuando llega a n_accept la pila está vacía;
//   3. cada transición saca un símbolo o pone un símbolo, y no las dos cosas ni ninguna.
// Agrega un estado inicial que pone una marca de fondo nueva, un estado n_drain que vacía la
// pila después de un estado de aceptación de p, y un estado intermedio por cada transición que
// se parte en dos.
inline Pda normalize_pda(const Pda& p) {
    check_pda(p);
    std::set<std::string> used(p.states.begin(), p.states.end());
    auto fresh_state = [&used](std::string name) {
        while (used.count(name) > 0) {
            name += "'";
        }
        used.insert(name);
        return name;
    };
    std::set<char> gamma(p.stack.begin(), p.stack.end());
    auto fresh_symbol = [&gamma]() {
        for (char c : std::string("@%&!?~^=+*<>")) {
            if (gamma.insert(c).second) {
                return c;
            }
        }
        throw std::runtime_error("no queda un carácter libre para un símbolo nuevo de la pila");
    };

    Pda result;
    std::string start = fresh_state("n_start");
    std::string drain = fresh_state("n_drain");
    std::string accept = fresh_state("n_accept");
    char bottom = fresh_symbol();  // la marca de fondo nueva
    char filler = fresh_symbol();  // el símbolo que se pone y se saca donde p no tocaba la pila
    result.states = p.states;
    result.states.insert(result.states.begin(), start);
    result.states.push_back(drain);
    result.states.push_back(accept);
    result.alphabet = p.alphabet;
    result.stack = p.stack;
    result.stack.push_back(bottom);
    result.stack.push_back(filler);
    result.start = start;
    result.accept = {accept};

    // Las transiciones antes de partirlas: (desde, lee, saca, hacia, pone).
    std::vector<std::tuple<std::string, char, char, std::string, char>> raw;
    raw.push_back({start, EPS, EPS, p.start, bottom});
    for (const std::string& state : p.states) {
        for (const auto& [key, moves] : p.delta) {
            if (std::get<0>(key) != state) {
                continue;
            }
            for (const Move& move : moves) {
                raw.push_back({state, std::get<1>(key), std::get<2>(key), move.target, move.push});
            }
        }
        if (p.accept.count(state) > 0) {
            raw.push_back({state, EPS, EPS, drain, EPS});
        }
    }
    for (char c : p.stack) {
        raw.push_back({drain, EPS, c, drain, EPS});
    }
    raw.push_back({drain, EPS, bottom, accept, EPS});

    std::size_t counter = 0;
    for (const auto& [from, read, pop, to, push] : raw) {
        if ((pop == EPS) != (push == EPS)) {
            add_move(result, from, read, pop, to, push);
            continue;
        }
        std::string middle = fresh_state("n" + std::to_string(++counter));
        result.states.insert(result.states.end() - 2, middle);
        if (pop != EPS) {
            // Saca y pone: primero saca, después pone.
            add_move(result, from, read, pop, middle, EPS);
            add_move(result, middle, EPS, EPS, to, push);
        } else {
            // Ni saca ni pone: pone el símbolo de relleno y lo saca enseguida.
            add_move(result, from, read, EPS, middle, filler);
            add_move(result, middle, EPS, filler, to, EPS);
        }
    }
    check_pda(result);
    return result;
}

// ------------------------------------------------------------
// De PDA a gramática
// ------------------------------------------------------------

inline std::string pair_variable(const std::string& p, const std::string& q) {
    return "A(" + p + "," + q + ")";
}

// Construye la gramática de las variables A(p,q): A(p,q) genera las cadenas que llevan al
// autómata del estado p con la pila vacía al estado q con la pila vacía.
//   A(p,p) → ε                       para cada estado p
//   A(p,q) → A(p,r) A(r,q)           para cada terna de estados p, q, r
//   A(p,q) → a A(r,s) b              si (r, u) ∈ δ(p, a, ε) y (q, ε) ∈ δ(s, b, u): el mismo
//                                    símbolo u se pone al principio y se saca al final
// La variable inicial es A(q0, q_accept). El autómata debe estar normalizado: las condiciones
// 1 y 3 se comprueban aquí; la 2 (pila vacía al aceptar) la garantiza quien llama.
inline Cfg pda_to_cfg(const Pda& p) {
    check_pda(p);
    if (!has_normal_shape(p)) {
        throw std::runtime_error("el PDA no está normalizado: pasarlo antes por normalize_pda");
    }
    Cfg g;
    g.terminals = p.alphabet;
    g.start = pair_variable(p.start, *p.accept.begin());
    for (const std::string& a : p.states) {
        for (const std::string& b : p.states) {
            g.variables.push_back(pair_variable(a, b));
        }
    }
    auto add_rule = [&g](const Rule& rule) {
        if (std::find(g.rules.begin(), g.rules.end(), rule) == g.rules.end()) {
            g.rules.push_back(rule);
        }
    };
    // Las transiciones que ponen y las que sacan, agrupadas por el símbolo de la pila.
    for (const auto& [push_key, push_moves] : p.delta) {
        if (std::get<2>(push_key) != EPS) {
            continue;
        }
        const std::string& from = std::get<0>(push_key);
        char a = std::get<1>(push_key);
        for (const Move& push_move : push_moves) {
            for (const auto& [pop_key, pop_moves] : p.delta) {
                if (std::get<2>(pop_key) != push_move.push) {
                    continue;
                }
                const std::string& before = std::get<0>(pop_key);
                char b = std::get<1>(pop_key);
                for (const Move& pop_move : pop_moves) {
                    Rule rule;
                    rule.head = pair_variable(from, pop_move.target);
                    if (a != EPS) {
                        rule.body.push_back(std::string(1, a));
                    }
                    rule.body.push_back(pair_variable(push_move.target, before));
                    if (b != EPS) {
                        rule.body.push_back(std::string(1, b));
                    }
                    add_rule(rule);
                }
            }
        }
    }
    for (const std::string& a : p.states) {
        for (const std::string& b : p.states) {
            for (const std::string& r : p.states) {
                g.rules.push_back({pair_variable(a, b), {pair_variable(a, r), pair_variable(r, b)}});
            }
        }
    }
    for (const std::string& a : p.states) {
        g.rules.push_back({pair_variable(a, a), {}});
    }
    check_cfg(g);
    return g;
}

#endif
