// Cadenas y lenguajes finitos, para comprobar con ejemplos pequeños las definiciones de la
// sesión A. Una cadena es un std::string y un lenguaje finito es un std::set<std::string>.
// Un lenguaje infinito no cabe en un set: de la estrella y del complemento solo se calcula la
// parte con cadenas de longitud acotada.
#ifndef LANGUAGES_H
#define LANGUAGES_H

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

using Language = std::set<std::string>;

// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_len, primero las más cortas
// y, entre las de igual longitud, en el orden del alfabeto.
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_len) {
    std::vector<std::string> result = {""};
    std::size_t first = 0;  // dónde empiezan las cadenas de la longitud anterior
    for (std::size_t len = 1; len <= max_len; len++) {
        std::size_t last = result.size();
        for (std::size_t i = first; i < last; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        first = last;
    }
    return result;
}

inline Language prefixes(const std::string& w) {
    Language result;
    for (std::size_t len = 0; len <= w.size(); len++) {
        result.insert(w.substr(0, len));
    }
    return result;
}

inline Language suffixes(const std::string& w) {
    Language result;
    for (std::size_t from = 0; from <= w.size(); from++) {
        result.insert(w.substr(from));
    }
    return result;
}

inline Language substrings(const std::string& w) {
    Language result;
    for (std::size_t from = 0; from <= w.size(); from++) {
        for (std::size_t len = 0; from + len <= w.size(); len++) {
            result.insert(w.substr(from, len));
        }
    }
    return result;
}

inline Language unite(const Language& a, const Language& b) {
    Language result = a;
    result.insert(b.begin(), b.end());
    return result;
}

inline Language intersect(const Language& a, const Language& b) {
    Language result;
    for (const std::string& w : a) {
        if (b.count(w) > 0) {
            result.insert(w);
        }
    }
    return result;
}

// AB = { uv : u ∈ A, v ∈ B }
inline Language concat(const Language& a, const Language& b) {
    Language result;
    for (const std::string& u : a) {
        for (const std::string& v : b) {
            result.insert(u + v);
        }
    }
    return result;
}

// A^0 = {ε} y A^(k+1) = A^k A
inline Language power(const Language& a, int k) {
    Language result = {""};
    for (int i = 0; i < k; i++) {
        result = concat(result, a);
    }
    return result;
}

// Las cadenas de A* con longitud a lo sumo max_len.
inline Language star_up_to(const Language& a, std::size_t max_len) {
    Language result = {""};
    std::vector<std::string> pending = {""};
    while (!pending.empty()) {
        std::string u = pending.back();
        pending.pop_back();
        for (const std::string& v : a) {
            std::string w = u + v;
            if (w.size() <= max_len && result.insert(w).second) {
                pending.push_back(w);
            }
        }
    }
    return result;
}

// Las cadenas del complemento de A, respecto de Σ*, con longitud a lo sumo max_len.
inline Language complement_up_to(const Language& a, const std::vector<char>& alphabet, std::size_t max_len) {
    Language result;
    for (const std::string& w : all_strings(alphabet, max_len)) {
        if (a.count(w) == 0) {
            result.insert(w);
        }
    }
    return result;
}

// Para imprimir: la cadena vacía se muestra como ε.
inline std::string show(const std::string& w) {
    return w.empty() ? "ε" : w;
}

// Un lenguaje finito, con las cadenas más cortas primero. El lenguaje sin cadenas se muestra como ∅.
inline std::string show(const Language& a) {
    std::vector<std::string> words(a.begin(), a.end());
    std::stable_sort(words.begin(), words.end(),
                     [](const std::string& x, const std::string& y) { return x.size() < y.size(); });
    if (a.empty()) {
        return "∅";
    }
    std::string text = "{";
    for (std::size_t i = 0; i < words.size(); i++) {
        text += (i > 0 ? ", " : "") + show(words[i]);
    }
    return text + "}";
}

#endif
