// Pruebas de las cadenas distinguibles, de la cota 2^k y del autómata de las clases.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <optional>
#include <string>
#include <vector>

#include "dfa.h"
#include "distinguish.h"
#include "minimize.h"
#include "pumping.h"
#include "streaming.h"

// ¿El k-ésimo símbolo desde el final de w es 1? Mirando la cadena completa.
static bool kth_from_end_is_one(const std::string& w, std::size_t k) {
    return w.size() >= k && w[w.size() - k] == '1';
}

// { 0^n 1^n } en tres líneas: 0^i y 0^j se distinguen con 1^i.
static void test_zeros_ones() {
    for (std::size_t i = 0; i < 20; i++) {
        for (std::size_t j = 0; j < 20; j++) {
            std::string x(i, '0'), y(j, '0'), z(i, '1');
            assert(in_zeros_ones(x + z));
            assert(in_zeros_ones(y + z) == (i == j));
        }
    }
}

// La deuda de la semana 2: las 2^k cadenas de longitud k son distinguibles dos a dos.
static void test_last_k() {
    for (int k = 1; k <= 6; k++) {
        std::size_t width = static_cast<std::size_t>(k);
        Dfa m = last_k_dfa(k);
        assert(m.states.size() == (std::size_t{1} << k));
        // El autómata reconoce el lenguaje.
        for (const std::string& w : all_strings({'0', '1'}, 10)) {
            assert(accepts(m, w) == kth_from_end_is_one(w, width));
        }
        std::vector<std::string> strings;
        for (const std::string& w : all_strings({'0', '1'}, width)) {
            if (w.size() == width) {
                strings.push_back(w);
            }
        }
        assert(strings.size() == (std::size_t{1} << k));
        // El sufijo de los apuntes: si x e y difieren en la posición i (desde 1), z = 0^(i-1).
        for (const std::string& x : strings) {
            for (const std::string& y : strings) {
                for (std::size_t i = 1; i <= width; i++) {
                    if (x[i - 1] == y[i - 1]) {
                        continue;
                    }
                    std::string z(i - 1, '0');
                    assert(kth_from_end_is_one(x + z, width) == (x[i - 1] == '1'));
                    assert(kth_from_end_is_one(y + z, width) == (y[i - 1] == '1'));
                    assert(separates(m, x, y, z));
                }
            }
        }
        assert(pairwise_distinguishable(m, strings));
        // Y entonces ningún estado sobra: el mínimo tiene 2^k.
        assert(minimize(m).states.size() == (std::size_t{1} << k));
    }
    // El archivo de machines/ es el autómata de k = 3, y la tabla de los apuntes.
    Dfa three = load_dfa("machines/last_3.dfa");
    assert(isomorphic(three, last_k_dfa(3)));
    assert(*distinguishing_suffix(three, "000", "001") == "00");
    assert(*distinguishing_suffix(three, "000", "010") == "0");
    assert(*distinguishing_suffix(three, "011", "100") == "");
    assert(*distinguishing_suffix(three, "110", "111") == "00");
}

// La fuerza bruta y el recorrido de pares de estados dan lo mismo.
static void test_brute_force() {
    for (const char* path : {"machines/ends_01.dfa", "machines/contains_101.dfa", "machines/multiple_of_3.dfa",
                             "machines/ends_01_seven.dfa", "machines/contains_1001.dfa",
                             "machines/count_attempt.dfa", "machines/last_3.dfa"}) {
        Dfa m = load_dfa(path);
        std::vector<std::string> strings = all_strings(m.alphabet, 3);
        for (const std::string& x : strings) {
            for (const std::string& y : strings) {
                std::size_t tried = 0;
                std::optional<std::string> brute = brute_distinguishing_suffix(m, x, y, m.states.size() - 1, tried);
                std::optional<std::string> fast = distinguishing_suffix(m, x, y);
                assert(brute.has_value() == fast.has_value());
                if (brute) {
                    assert(brute->size() == fast->size());  // los dos son de longitud mínima
                    assert(separates(m, x, y, *brute) && separates(m, x, y, *fast));
                }
                // Dos cadenas que llegan al mismo estado no se pueden distinguir.
                if (delta_star(m, m.start, x) == delta_star(m, m.start, y)) {
                    assert(!fast);
                }
            }
        }
    }
    // Las salidas copiadas en los apuntes.
    Dfa m = load_dfa("machines/contains_1001.dfa");
    std::size_t tried = 0;
    assert(!brute_distinguishing_suffix(m, "", "0", 7, tried) && tried == 255);
    assert(*brute_distinguishing_suffix(m, "", "1", 7, tried) == "001" && tried == 9);
    Dfa three = load_dfa("machines/last_3.dfa");
    assert(*brute_distinguishing_suffix(three, "011", "001", 7, tried) == "0" && tried == 2);
}

// Myhill-Nerode: el autómata de las clases es el DFA mínimo, salvo los nombres.
static void test_nerode() {
    for (const char* path : {"machines/ends_01.dfa", "machines/contains_101.dfa", "machines/multiple_of_3.dfa",
                             "machines/ends_01_seven.dfa", "machines/contains_1001.dfa",
                             "machines/count_attempt.dfa", "machines/last_3.dfa",
                             "machines/multiple_of_3_mod6.dfa"}) {
        Dfa m = load_dfa(path);
        Classes classes = nerode_classes(m);
        Dfa by_classes = nerode_dfa(m);
        assert(by_classes.states.size() == classes.representatives.size());
        // Los representantes son distinguibles dos a dos, y toda cadena cae en una clase.
        assert(pairwise_distinguishable(m, classes.representatives));
        for (const std::string& w : all_strings(m.alphabet, 7)) {
            std::optional<std::string> r = class_of(m, classes, w);
            assert(r.has_value());
            // δ*([ε], w) = [w]
            assert(delta_star(by_classes, by_classes.start, w) == class_name(*r));
            assert(accepts(by_classes, w) == accepts(m, w));
        }
        assert(isomorphic(by_classes, minimize(m)));
    }
    Dfa seven = load_dfa("machines/ends_01_seven.dfa");
    assert(nerode_classes(seven).representatives == (std::vector<std::string>{"", "0", "01"}));
    assert(isomorphic(nerode_dfa(seven), load_dfa("machines/ends_01.dfa")));
}

// Streaming: el registro de k bits responde lo mismo que el DFA de 2^k estados, y sus 2^k
// contenidos posibles son exactamente los estados.
static void test_streaming() {
    for (int k = 1; k <= 6; k++) {
        Dfa m = last_k_dfa(k);
        for (const std::string& w : all_strings({'0', '1'}, 10)) {
            Window window;
            window.k = k;
            Balance balance;
            for (char a : w) {
                window.read(a);
                balance.read(a);
            }
            assert(window.answer() == accepts(m, w));
            assert(balance.answer() == in_equal(w));
            // El contenido del registro, escrito con k dígitos, es el nombre del estado.
            std::string name(static_cast<std::size_t>(k), '0');
            for (int i = 0; i < k; i++) {
                if ((window.bits >> (k - 1 - i)) & 1u) {
                    name[static_cast<std::size_t>(i)] = '1';
                }
            }
            assert(name == delta_star(m, m.start, w));
        }
    }
    // Con entradas de longitud a lo sumo n, las cadenas 0^0, ..., 0^(n/2) son distinguibles
    // dos a dos con sufijos que no pasan de la longitud n: 0^i 1^i mide 2i ≤ n.
    std::size_t n = 20;
    for (std::size_t i = 0; i <= n / 2; i++) {
        for (std::size_t j = 0; j < i; j++) {
            std::string z(j, '1');  // el sufijo es el del más corto de los dos
            assert(std::string(i, '0').size() + z.size() <= n);
            assert(in_equal(std::string(j, '0') + z) && !in_equal(std::string(i, '0') + z));
        }
    }
}

int main() {
    test_zeros_ones();
    test_last_k();
    test_brute_force();
    test_nerode();
    test_streaming();
    std::printf("test_distinguish: ok\n");
}
