// La codificación importa: el tiempo se mide contra la longitud de la entrada, y un número
// escrito en binario ocupa muy poco. Tres tablas con conteos de operaciones.
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "search.h"

static std::string binary(unsigned long long x) {
    std::string text;
    do {
        text.insert(text.begin(), static_cast<char>('0' + x % 2));
        x /= 2;
    } while (x > 0);
    return text;
}

int main() {
    std::cout << "Un número x, en binario y en unario\n";
    std::cout << "        x   en binario             bits   símbolos en unario\n";
    for (unsigned long long x : {5ULL, 12ULL, 100ULL, 1000ULL, 1000000ULL}) {
        std::string b = binary(x);
        std::cout << std::setw(9) << x << "   " << std::left << std::setw(22) << b << std::right << std::setw(5)
                  << b.size() << std::setw(21) << x << '\n';
    }

    std::cout << "\n¿Es primo x? Divisiones de prueba hasta la raíz, con el mayor primo de b bits\n";
    std::cout << " b                  x    divisiones\n";
    for (int b = 8; b <= 40; b += 8) {
        unsigned long long x = (1ULL << b) - 1;
        long long divisions = 0;
        while (!trial_division(x, &divisions)) {
            x--;
        }
        std::cout << std::setw(2) << b << std::setw(19) << x << std::setw(14) << divisions << '\n';
    }

    std::cout << "\nSUBSET-SUM con la tabla de Algoritmos: 10 números de b bits, objetivo la mitad de la suma\n";
    std::cout << " b   bits de la entrada   casillas de la tabla\n";
    for (int b = 4; b <= 16; b += 4) {
        // Diez números fijos de b bits exactos: 2^(b-1) + (i mod 8) · 2^(b-4), para i = 0..9.
        std::vector<long long> numbers;
        long long sum = 0;
        long long input_bits = 0;
        for (int i = 0; i < 10; i++) {
            long long x = (1LL << (b - 1)) + (i % 8) * (1LL << (b - 4));
            numbers.push_back(x);
            sum += x;
            input_bits += bit_length(static_cast<unsigned long long>(x));
        }
        long long target = sum / 2;
        input_bits += bit_length(static_cast<unsigned long long>(target));
        long long cells = 0;
        subset_sum_table(numbers, target, &cells);
        std::cout << std::setw(2) << b << std::setw(21) << input_bits << std::setw(23) << cells << '\n';
    }
}
