// Pruebas de la construcción del producto y del complemento.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <stdexcept>
#include <string>
#include <vector>

#include "dfa.h"
#include "languages.h"

// ¿M1 y M2 aceptan las mismas cadenas de longitud a lo sumo max_len?
static bool same_up_to(const Dfa& m1, const Dfa& m2, std::size_t max_len) {
    for (const std::string& w : all_strings(m1.alphabet, max_len)) {
        if (accepts(m1, w) != accepts(m2, w)) {
            return false;
        }
    }
    return true;
}

static void test_product_of_notes() {
    Dfa even = load_dfa("machines/even_ones.dfa");
    Dfa ends = load_dfa("machines/ends_01.dfa");
    Dfa both = product(even, ends, Combine::Intersection);
    Dfa either = product(even, ends, Combine::Union);

    // 2 × 3 = 6 estados, y en este producto los 6 se alcanzan.
    assert(both.states.size() == 6 && either.states.size() == 6);
    assert(reachable(both).size() == 6);
    // La misma máquina con distinto F.
    assert(both.states == either.states && both.delta == either.delta && both.start == either.start);
    assert(both.start == "(par,q0)");
    assert(both.accept == (std::set<std::string>{"(par,q2)"}));
    assert(either.accept == (std::set<std::string>{"(par,q0)", "(par,q1)", "(par,q2)", "(impar,q2)"}));

    // El lema: δ*((p, q), w) = (δ1*(p, w), δ2*(q, w)), desde cualquier par.
    for (const std::string& p : even.states) {
        for (const std::string& q : ends.states) {
            for (const std::string& w : all_strings({'0', '1'}, 7)) {
                assert(delta_star(both, pair_name(p, q), w) ==
                       pair_name(delta_star(even, p, w), delta_star(ends, q, w)));
            }
        }
    }
    // Y lo que importa: reconoce la intersección y la unión.
    for (const std::string& w : all_strings({'0', '1'}, 12)) {
        assert(accepts(both, w) == (accepts(even, w) && accepts(ends, w)));
        assert(accepts(either, w) == (accepts(even, w) || accepts(ends, w)));
    }
    // La traza de los apuntes.
    assert(run(both, "1101") ==
           (std::vector<std::string>{"(par,q0)", "(impar,q0)", "(par,q0)", "(par,q1)", "(impar,q2)"}));
    assert(!accepts(both, "1101") && accepts(either, "1101"));
    assert(accepts(both, "1001") && accepts(both, "0101") && !accepts(both, "001"));
}

static void test_complement() {
    for (const char* path : {"machines/even_ones.dfa", "machines/ends_01.dfa", "machines/contains_101.dfa",
                             "machines/multiple_of_3.dfa", "machines/starts_with_1.dfa"}) {
        Dfa m = load_dfa(path);
        Dfa c = complement(m);
        assert(c.accept.size() + m.accept.size() == m.states.size());
        for (const std::string& w : all_strings({'0', '1'}, 12)) {
            assert(accepts(c, w) != accepts(m, w));
        }
        assert(complement(c).accept == m.accept);
    }
    // De Morgan con máquinas: A ∪ B es el complemento de (complemento de A) ∩ (complemento de B).
    Dfa a = load_dfa("machines/contains_101.dfa");
    Dfa b = load_dfa("machines/multiple_of_3.dfa");
    Dfa left = product(a, b, Combine::Union);
    Dfa right = complement(product(complement(a), complement(b), Combine::Intersection));
    assert(left.accept == right.accept);  // no solo el mismo lenguaje: el mismo F
    assert(same_up_to(left, right, 12));
}

// Cuántos estados del producto se alcanzan, en los ejemplos de los apuntes.
static void test_reachable() {
    Dfa even = load_dfa("machines/even_ones.dfa");
    Dfa ends = load_dfa("machines/ends_01.dfa");
    Dfa has = load_dfa("machines/contains_101.dfa");
    Dfa three = load_dfa("machines/multiple_of_3.dfa");

    // Una máquina consigo misma: solo se alcanzan los pares (q, q).
    Dfa twice = product(even, even, Combine::Intersection);
    assert(twice.states.size() == 4 && reachable(twice).size() == 2);
    assert(same_up_to(twice, even, 12));
    Dfa trimmed = remove_unreachable(twice);
    assert(trimmed.states.size() == 2 && same_up_to(trimmed, even, 12));

    // 3 × 4 = 12 estados, de los que se alcanzan 8.
    Dfa twelve = product(ends, has, Combine::Intersection);
    assert(twelve.states.size() == 12);
    assert(reachable(twelve).size() == 8);
    assert(same_up_to(remove_unreachable(twelve), twelve, 12));

    // Tres propiedades a la vez: el producto de un producto. 4 × 3 × 2 = 24.
    Dfa triple = product(product(has, three, Combine::Intersection), even, Combine::Intersection);
    assert(triple.states.size() == 24);
    assert(reachable(triple).size() == 24);
    for (const std::string& w : all_strings({'0', '1'}, 12)) {
        assert(accepts(triple, w) == (accepts(has, w) && accepts(three, w) && accepts(even, w)));
    }
}

static void test_alphabets() {
    Dfa even = load_dfa("machines/even_ones.dfa");
    Dfa turnstile = load_dfa("machines/turnstile.dfa");
    bool failed = false;
    try {
        product(even, turnstile, Combine::Union);
    } catch (const std::runtime_error&) {
        failed = true;
    }
    assert(failed);
}

int main() {
    test_product_of_notes();
    test_complement();
    test_reachable();
    test_alphabets();
    std::printf("test_product: ok\n");
}
