// Expresiones regulares. Una expresión es un árbol con un nodo por cada caso de la definición
// inductiva: ∅, ε, un símbolo, unión, concatenación y estrella.
// Además: el parser que lee una expresión escrita en una línea, y la escritura con los
// paréntesis justos.
//
// Cómo se escribe una expresión para estos programas:
//   - un símbolo es una letra o un dígito: a, b, 0, 1
//   - la unión es |, la concatenación no se escribe y la estrella es *
//   - ε se escribe % (o la propia letra ε) y ∅ se escribe @ (o el propio signo ∅)
//   - precedencia: primero la estrella, después la concatenación, al final la unión
//   - los paréntesis agrupan y los espacios se ignoran
#ifndef REGEX_H
#define REGEX_H

#include <cctype>
#include <cstddef>
#include <memory>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

enum class Kind { Empty, Epsilon, Symbol, Union, Concat, Star };

struct Regex;
// Un árbol no cambia después de construido, así que dos expresiones pueden compartir un subárbol.
using RegexPtr = std::shared_ptr<const Regex>;

struct Regex {
    Kind kind;
    char symbol;    // solo si kind == Symbol
    RegexPtr left;  // el único hijo de Star; el hijo izquierdo de Union y de Concat
    RegexPtr right;
};

// ------------------------------------------------------------
// Los seis casos de la definición
// ------------------------------------------------------------

inline RegexPtr empty_set() {
    return std::make_shared<const Regex>(Regex{Kind::Empty, '\0', nullptr, nullptr});
}

inline RegexPtr epsilon() {
    return std::make_shared<const Regex>(Regex{Kind::Epsilon, '\0', nullptr, nullptr});
}

inline RegexPtr symbol(char a) {
    return std::make_shared<const Regex>(Regex{Kind::Symbol, a, nullptr, nullptr});
}

inline RegexPtr make_union(const RegexPtr& r1, const RegexPtr& r2) {
    return std::make_shared<const Regex>(Regex{Kind::Union, '\0', r1, r2});
}

inline RegexPtr make_concat(const RegexPtr& r1, const RegexPtr& r2) {
    return std::make_shared<const Regex>(Regex{Kind::Concat, '\0', r1, r2});
}

inline RegexPtr make_star(const RegexPtr& r) {
    return std::make_shared<const Regex>(Regex{Kind::Star, '\0', r, nullptr});
}

// ------------------------------------------------------------
// Las mismas operaciones, aplicando las identidades de ∅ y de ε
// ------------------------------------------------------------

// R ∪ ∅ = ∅ ∪ R = R.
inline RegexPtr simple_union(const RegexPtr& r1, const RegexPtr& r2) {
    if (r1->kind == Kind::Empty) {
        return r2;
    }
    if (r2->kind == Kind::Empty) {
        return r1;
    }
    return make_union(r1, r2);
}

// R∅ = ∅R = ∅ y Rε = εR = R.
inline RegexPtr simple_concat(const RegexPtr& r1, const RegexPtr& r2) {
    if (r1->kind == Kind::Empty || r2->kind == Kind::Empty) {
        return empty_set();
    }
    if (r1->kind == Kind::Epsilon) {
        return r2;
    }
    if (r2->kind == Kind::Epsilon) {
        return r1;
    }
    return make_concat(r1, r2);
}

// ∅* = ε y ε* = ε.
inline RegexPtr simple_star(const RegexPtr& r) {
    if (r->kind == Kind::Empty || r->kind == Kind::Epsilon) {
        return epsilon();
    }
    return make_star(r);
}

// ------------------------------------------------------------
// Medidas
// ------------------------------------------------------------

// El tamaño de una expresión: cuántos nodos tiene su árbol.
inline std::size_t size(const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Union:
        case Kind::Concat:
            return 1 + size(r->left) + size(r->right);
        case Kind::Star:
            return 1 + size(r->left);
        default:
            return 1;
    }
}

// Cuántas hojas, uniones y estrellas tiene: de eso depende el tamaño del NFA de Thompson.
inline std::size_t count_without_concat(const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Union:
            return 1 + count_without_concat(r->left) + count_without_concat(r->right);
        case Kind::Concat:
            return count_without_concat(r->left) + count_without_concat(r->right);
        case Kind::Star:
            return 1 + count_without_concat(r->left);
        default:
            return 1;
    }
}

inline void collect_symbols(const RegexPtr& r, std::set<char>& symbols) {
    if (r->kind == Kind::Symbol) {
        symbols.insert(r->symbol);
    }
    if (r->left) {
        collect_symbols(r->left, symbols);
    }
    if (r->right) {
        collect_symbols(r->right, symbols);
    }
}

// Los símbolos que aparecen en la expresión, en orden.
inline std::vector<char> symbols_of(const RegexPtr& r) {
    std::set<char> symbols;
    collect_symbols(r, symbols);
    return std::vector<char>(symbols.begin(), symbols.end());
}

// ------------------------------------------------------------
// Escribir
// ------------------------------------------------------------

// Qué tan fuerte liga cada operación: la unión 1, la concatenación 2, la estrella 3.
// Las hojas no necesitan paréntesis nunca.
inline int precedence(Kind kind) {
    switch (kind) {
        case Kind::Union:
            return 1;
        case Kind::Concat:
            return 2;
        case Kind::Star:
            return 3;
        default:
            return 4;
    }
}

inline std::string to_string(const RegexPtr& r);

// Escribe r como operando de una operación de precedencia level: con paréntesis solo si r
// liga más débil que ella.
inline std::string operand(const RegexPtr& r, int level) {
    std::string text = to_string(r);
    return precedence(r->kind) < level ? "(" + text + ")" : text;
}

// La expresión con los paréntesis justos. La unión y la concatenación son asociativas, así
// que (R1|R2)|R3 y R1|(R2|R3) se escriben igual: R1|R2|R3.
inline std::string to_string(const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Empty:
            return "∅";
        case Kind::Epsilon:
            return "ε";
        case Kind::Symbol:
            return std::string(1, r->symbol);
        case Kind::Union:
            return operand(r->left, 1) + "|" + operand(r->right, 1);
        case Kind::Concat:
            return operand(r->left, 2) + operand(r->right, 2);
        case Kind::Star:
            // Una estrella sobre otra estrella lleva paréntesis para que se lea: (a*)*.
            return (r->left->kind == Kind::Star ? "(" + to_string(r->left) + ")" : operand(r->left, 3)) + "*";
    }
    return "";
}

// La expresión con todos los paréntesis, un par por cada operación: muestra el árbol sin
// depender de la precedencia.
inline std::string to_string_full(const RegexPtr& r) {
    switch (r->kind) {
        case Kind::Union:
            return "(" + to_string_full(r->left) + "|" + to_string_full(r->right) + ")";
        case Kind::Concat:
            return "(" + to_string_full(r->left) + to_string_full(r->right) + ")";
        case Kind::Star:
            return "(" + to_string_full(r->left) + "*)";
        default:
            return to_string(r);
    }
}

inline void tree_lines(const RegexPtr& r, const std::string& indent, std::string& out) {
    switch (r->kind) {
        case Kind::Union:
            out += indent + "unión\n";
            break;
        case Kind::Concat:
            out += indent + "concatenación\n";
            break;
        case Kind::Star:
            out += indent + "estrella\n";
            break;
        default:
            out += indent + to_string(r) + "\n";
            break;
    }
    if (r->left) {
        tree_lines(r->left, indent + "    ", out);
    }
    if (r->right) {
        tree_lines(r->right, indent + "    ", out);
    }
}

// El árbol, un nodo por línea, con los hijos debajo y más adentro.
inline std::string tree(const RegexPtr& r) {
    std::string out;
    tree_lines(r, "", out);
    return out;
}

// ------------------------------------------------------------
// Leer: un parser recursivo, con una función por nivel de precedencia
// ------------------------------------------------------------
//
//   unión         →  concatenación ( '|' concatenación )*
//   concatenación →  estrella estrella*
//   estrella      →  átomo '*'*
//   átomo         →  símbolo  |  ε  |  ∅  |  '(' unión ')'

struct RegexParser {
    std::string text;
    std::size_t pos = 0;

    [[noreturn]] void fail(const std::string& message) const {
        throw std::runtime_error("posición " + std::to_string(pos + 1) + ": " + message);
    }

    void skip_spaces() {
        while (pos < text.size() && text[pos] == ' ') {
            pos++;
        }
    }

    // ¿Sigue el texto s en la posición actual? Si sigue, lo consume.
    bool take(const std::string& s) {
        skip_spaces();
        if (text.compare(pos, s.size(), s) == 0) {
            pos += s.size();
            return true;
        }
        return false;
    }

    // ¿Empieza un átomo en la posición actual? Sirve para saber si la concatenación sigue.
    bool atom_ahead() {
        skip_spaces();
        if (pos >= text.size()) {
            return false;
        }
        unsigned char c = static_cast<unsigned char>(text[pos]);
        return std::isalnum(c) != 0 || c == '(' || c == '%' || c == '@' || text.compare(pos, 2, "ε") == 0 ||
               text.compare(pos, 3, "∅") == 0;
    }

    RegexPtr parse_atom() {
        if (take("(")) {
            RegexPtr inside = parse_union();
            if (!take(")")) {
                fail("falta cerrar un paréntesis");
            }
            return inside;
        }
        if (take("%") || take("ε")) {
            return epsilon();
        }
        if (take("@") || take("∅")) {
            return empty_set();
        }
        skip_spaces();
        if (pos < text.size() && std::isalnum(static_cast<unsigned char>(text[pos])) != 0) {
            return symbol(text[pos++]);
        }
        if (pos >= text.size()) {
            fail("la expresión termina donde se esperaba un símbolo o un paréntesis");
        }
        fail(std::string("se esperaba un símbolo o un paréntesis, y hay ") + text[pos]);
    }

    RegexPtr parse_star() {
        RegexPtr r = parse_atom();
        while (take("*")) {
            r = make_star(r);
        }
        return r;
    }

    RegexPtr parse_concat() {
        RegexPtr r = parse_star();
        while (atom_ahead()) {
            RegexPtr next = parse_star();
            r = make_concat(r, next);
        }
        return r;
    }

    RegexPtr parse_union() {
        RegexPtr r = parse_concat();
        while (take("|")) {
            RegexPtr next = parse_concat();
            r = make_union(r, next);
        }
        return r;
    }
};

// Lee una expresión completa. Lanza std::runtime_error si no está bien formada.
inline RegexPtr parse_regex(const std::string& text) {
    RegexParser parser{text};
    RegexPtr r = parser.parse_union();
    parser.skip_spaces();
    if (parser.pos != text.size()) {
        parser.fail(std::string("sobra ") + text[parser.pos]);
    }
    return r;
}

#endif
