// Pruebas de los ordenamientos de la clase: casos dirigidos y al azar, contra la biblioteca.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <random>
#include <vector>

#include "inputs.h"
#include "int_sorts.h"

namespace {

void check_all_sorts(const std::vector<int>& input) {
    std::vector<int> expected = input;
    std::sort(expected.begin(), expected.end());
    long long comparisons = 0;

    std::vector<int> items = input;
    merge_sort_ints(items, comparisons);
    assert(items == expected);

    items = input;
    quick_sort_first_ints(items, comparisons);
    assert(items == expected);

    items = input;
    quick_sort_random_ints(items, 1, comparisons);
    assert(items == expected);

    items = input;
    quick_sort_three_ints(items, 1, comparisons);
    assert(items == expected);
}

void test_small_cases() {
    check_all_sorts({});
    check_all_sorts({1});
    check_all_sorts({2, 1});
    check_all_sorts({1, 1, 1});
    check_all_sorts({3, 1, 2, 3, 1, 2});
}

void test_random_inputs() {
    std::mt19937 rng(2026);
    for (int round = 0; round < 300; round++) {
        std::size_t n = rng() % 200;
        check_all_sorts(repeated_input(n, 1 + static_cast<int>(rng() % 50), rng()));
    }
}

void test_exact_counts() {
    // Con el primero como pivote, cada partición saca un solo elemento.
    for (std::size_t n : {10, 100, 1000}) {
        long long expected = static_cast<long long>(n * (n - 1) / 2);
        long long comparisons = 0;
        std::vector<int> items = sorted_input(n);
        quick_sort_first_ints(items, comparisons);
        assert(comparisons == expected);
        comparisons = 0;
        items = std::vector<int>(n, 7);
        quick_sort_first_ints(items, comparisons);
        assert(comparisons == expected);
    }
    // Mergesort con n = 2^k: como mucho n log2 n comparaciones.
    for (int k = 1; k <= 14; k++) {
        std::size_t n = std::size_t{1} << k;
        long long comparisons = 0;
        std::vector<int> items = random_input(n, 7);
        merge_sort_ints(items, comparisons);
        assert(comparisons <= static_cast<long long>(n) * k);
    }
    // La partición en tres con todos iguales: una pasada, dos comparaciones por elemento.
    long long comparisons = 0;
    std::vector<int> items(1000, 7);
    quick_sort_three_ints(items, 1, comparisons);
    assert(comparisons == 2000);
}

void test_lower_bound() {
    std::mt19937 rng(2026);
    for (int round = 0; round < 2000; round++) {
        std::size_t n = rng() % 64;
        std::vector<int> items = repeated_input(n, 1 + static_cast<int>(n), rng());
        std::sort(items.begin(), items.end());
        for (int x = -1; x <= static_cast<int>(n) + 1; x++) {
            long long probes = 0;
            std::size_t found = lower_bound_index(items, x, probes);
            std::size_t expected = static_cast<std::size_t>(std::lower_bound(items.begin(), items.end(), x) - items.begin());
            assert(found == expected);
            // Se revisan a lo sumo piso(log2 n) + 1 elementos.
            long long limit = 0;
            for (std::size_t size = n; size > 0; size /= 2) {
                limit++;
            }
            assert(probes <= limit);
        }
    }
}

}  // namespace

int main() {
    test_small_cases();
    test_random_inputs();
    test_exact_counts();
    test_lower_bound();
    std::cout << "ok\n";
    return 0;
}