// Pruebas de lo que los apuntes afirman sobre cadenas y lenguajes (sesión A).
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <string>
#include <vector>

#include "languages.h"

static void test_sigma_star() {
    std::vector<char> binary = {'0', '1'};
    // Hay 2^n cadenas binarias de longitud n, y 2^(n+1) - 1 de longitud a lo sumo n.
    for (std::size_t n = 0; n <= 12; n++) {
        std::vector<std::string> words = all_strings(binary, n);
        assert(words.size() == (std::size_t{1} << (n + 1)) - 1);
        std::size_t exact = 0;
        for (const std::string& w : words) {
            exact += (w.size() == n);
        }
        assert(exact == std::size_t{1} << n);
    }
    // El orden: primero las más cortas, y cada cadena aparece una sola vez.
    std::vector<std::string> first = all_strings(binary, 3);
    std::vector<std::string> expected = {"", "0", "1", "00", "01", "10", "11", "000",
                                         "001", "010", "011", "100", "101", "110", "111"};
    assert(first == expected);
    // Con tres símbolos: 1 + 3 + 9 + 27 = 40.
    assert(all_strings({'a', 'b', 'c'}, 3).size() == 40);
}

static void test_concatenation() {
    std::vector<std::string> words = all_strings({'a', 'b'}, 4);
    for (const std::string& u : words) {
        assert(u + "" == u && "" + u == u);  // ε es el neutro
        for (const std::string& v : words) {
            assert((u + v).size() == u.size() + v.size());  // |uv| = |u| + |v|
        }
    }
    assert(std::string("ab") + "ba" != std::string("ba") + "ab");  // no es conmutativa
    for (const std::string& u : all_strings({'a', 'b'}, 2)) {
        for (const std::string& v : all_strings({'a', 'b'}, 2)) {
            for (const std::string& w : all_strings({'a', 'b'}, 2)) {
                assert((u + v) + w == u + (v + w));  // es asociativa
            }
        }
    }
}

static void test_parts() {
    // El ejemplo de los apuntes.
    std::string w = "abba";
    assert(prefixes(w) == (Language{"", "a", "ab", "abb", "abba"}));
    assert(suffixes(w) == (Language{"", "a", "ba", "bba", "abba"}));
    assert(substrings(w) == (Language{"", "a", "b", "ab", "bb", "ba", "abb", "bba", "abba"}));
    // Una cadena de longitud n tiene n + 1 prefijos y n + 1 sufijos; ε y w están entre ellos.
    // Todo prefijo y todo sufijo es una subcadena.
    for (const std::string& x : all_strings({'a', 'b'}, 7)) {
        Language p = prefixes(x);
        Language s = suffixes(x);
        Language sub = substrings(x);
        assert(p.size() == x.size() + 1 && s.size() == x.size() + 1);
        assert(p.count("") == 1 && p.count(x) == 1 && s.count("") == 1 && s.count(x) == 1);
        assert(unite(unite(p, s), sub) == sub);
        assert(sub.size() <= x.size() * (x.size() + 1) / 2 + 1);
    }
    // Con todos los símbolos distintos se alcanza el máximo: n(n + 1)/2 + 1.
    assert(substrings("abcd").size() == 11);
    assert(substrings("aaaa").size() == 5);
}

static void test_language_operations() {
    Language a = {"0", "01"};
    Language b = {"", "1", "01"};
    Language empty = {};
    Language only_eps = {""};

    // Los valores que imprime languages_demo y que los apuntes copian.
    assert(unite(a, b) == (Language{"", "0", "1", "01"}));
    assert(intersect(a, b) == (Language{"01"}));
    assert(concat(a, b) == (Language{"0", "01", "001", "011", "0101"}));
    assert(concat(b, a) == (Language{"0", "01", "10", "101", "010", "0101"}));
    assert(concat(a, b) != concat(b, a));
    assert(concat(a, b).size() == 5);  // menos de 2 × 3: 0·1 y 01·ε dan la misma cadena
    assert(power(a, 2) == (Language{"00", "001", "010", "0101"}));
    assert(star_up_to(a, 3) == (Language{"", "0", "00", "01", "000", "001", "010"}));
    assert(complement_up_to(a, {'0', '1'}, 2) == (Language{"", "1", "00", "10", "11"}));

    // ∅ y {ε} no son lo mismo.
    assert(empty.size() == 0 && only_eps.size() == 1 && empty != only_eps);
    assert(concat(empty, a) == empty && concat(a, empty) == empty);
    assert(concat(only_eps, a) == a && concat(a, only_eps) == a);
    assert(unite(empty, a) == a);
    assert(star_up_to(empty, 5) == only_eps);
    assert(star_up_to(only_eps, 5) == only_eps);
    assert(power(empty, 0) == only_eps && power(empty, 1) == empty);

    // A* es la unión de las potencias, tiene a ε, y (A*)* = A*.
    Language powers;
    for (int k = 0; k <= 6; k++) {
        for (const std::string& w : power(a, k)) {
            if (w.size() <= 6) {
                powers.insert(w);
            }
        }
    }
    Language star = star_up_to(a, 6);
    assert(star == powers);
    assert(star.count("") == 1);
    assert(star_up_to(star, 6) == star);
    // {0, 1}* son todas las cadenas binarias.
    assert(star_up_to({"0", "1"}, 6).size() == 127);

    // De Morgan, mirando las cadenas de longitud a lo sumo 4.
    std::vector<char> binary = {'0', '1'};
    Language left = complement_up_to(unite(a, b), binary, 4);
    Language right = intersect(complement_up_to(a, binary, 4), complement_up_to(b, binary, 4));
    assert(left == right);
}

int main() {
    test_sigma_star();
    test_concatenation();
    test_parts();
    test_language_operations();
    std::printf("test_languages: ok\n");
}
