// Pruebas de lo que los apuntes afirman sobre la codificación: la longitud en binario, las
// divisiones de prueba y la tabla de SUBSET-SUM.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <optional>
#include <random>
#include <vector>

#include "search.h"

static void test_bit_length() {
    assert(bit_length(0) == 1);
    assert(bit_length(1) == 1);
    assert(bit_length(5) == 3);
    assert(bit_length(12) == 4);
    assert(bit_length(100) == 7);
    assert(bit_length(1000) == 10);
    assert(bit_length(1000000) == 20);
    // 2^b − 1 es el mayor número de b bits, y 2^b ya necesita b + 1.
    for (int b = 1; b <= 62; b++) {
        assert(bit_length((1ULL << b) - 1) == b);
        assert(bit_length(1ULL << b) == b + 1);
    }
}

static void test_trial_division() {
    struct Row {
        unsigned long long prime;
        long long divisions;
    };
    // La tabla de los apuntes: el mayor primo de b bits para b = 8, 16, 24, 32.
    std::vector<Row> table = {{251, 14}, {65521, 254}, {16777213, 4094}, {4294967291ULL, 65534}};
    for (const Row& row : table) {
        long long divisions = 0;
        assert(trial_division(row.prime, &divisions));
        assert(divisions == row.divisions);
        // Es el mayor: los que siguen hasta la potencia de dos son compuestos.
        unsigned long long x = row.prime + 1;
        while ((x & (x - 1)) != 0) {
            assert(!trial_division(x, &divisions));
            x++;
        }
    }
    long long divisions = 0;
    assert(!trial_division(0, &divisions) && !trial_division(1, &divisions));
    assert(trial_division(2, &divisions) && divisions == 0);
    assert(!trial_division(8633, &divisions));
    assert(trial_division(8641, &divisions));
    // Un compuesto con un factor pequeño se descubre enseguida: el costo alto es el de los primos.
    assert(!trial_division(4294967292ULL, &divisions) && divisions == 1);
}

// La tabla decide lo mismo que la búsqueda exhaustiva, y calcula n · (objetivo + 1) casillas.
static void test_table_agrees_with_search() {
    std::mt19937 random(12);
    for (int round = 0; round < 300; round++) {
        std::size_t n = 1 + random() % 8;
        std::vector<long long> numbers;
        for (std::size_t i = 0; i < n; i++) {
            numbers.push_back(1 + static_cast<long long>(random() % 20));
        }
        long long target = static_cast<long long>(random() % 60);
        long long tried = 0, cells = 0;
        std::optional<std::vector<int>> found = search_subset_sum(numbers, target, &tried);
        bool by_table = subset_sum_table(numbers, target, &cells);
        assert(found.has_value() == by_table);
        assert(cells == static_cast<long long>(n) * (target + 1));
        if (!found) {
            assert(tried == (1LL << n));
        }
    }
    // Los cuatro renglones de la tabla de los apuntes.
    std::vector<long long> expected = {550, 8730, 139530, 2232330};
    for (int b = 4; b <= 16; b += 4) {
        std::vector<long long> numbers;
        long long sum = 0;
        for (int i = 0; i < 10; i++) {
            long long x = (1LL << (b - 1)) + (i % 8) * (1LL << (b - 4));
            assert(bit_length(static_cast<unsigned long long>(x)) == b);
            numbers.push_back(x);
            sum += x;
        }
        long long cells = 0;
        subset_sum_table(numbers, sum / 2, &cells);
        assert(cells == expected[static_cast<std::size_t>(b / 4 - 1)]);
    }
}

int main() {
    test_bit_length();
    test_trial_division();
    test_table_agrees_with_search();
    std::printf("test_encoding: ok\n");
}
