// Pruebas de IntHeap y de heapsort: dirigidas y al azar, con semilla fija, contra la biblioteca.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <queue>
#include <random>
#include <utility>
#include <vector>

#include "heapsort.h"
#include "int_heap.h"

namespace {

void test_guide_example() {
    IntHeap heap;
    for (int value : {5, 3, 8, 1, 4}) {
        heap.push(value);
        heap.check_invariants();
    }
    assert((heap.items() == std::vector<int>{1, 3, 8, 5, 4}));
    heap.pop();
    assert((heap.items() == std::vector<int>{3, 4, 8, 5}));
}

void test_random_against_priority_queue() {
    std::mt19937 generator(13);
    IntHeap heap;
    std::priority_queue<int, std::vector<int>, std::greater<int>> reference;
    for (int step = 0; step < 100000; step++) {
        if (reference.empty() || generator() % 3 != 0) {
            int value = static_cast<int>(generator() % 1000);
            heap.push(value);
            reference.push(value);
        } else {
            assert(heap.top() == reference.top());
            heap.pop();
            reference.pop();
        }
        assert(heap.size() == reference.size());
        if (step % 1000 == 0) {
            heap.check_invariants();
        }
    }
}

void test_operation_bounds() {
    IntHeap heap;
    for (int value = 100000; value > 0; value--) {
        long before = heap.comparisons();
        heap.push(value);
        assert(heap.comparisons() - before <= static_cast<long>(std::log2(double(heap.size()))) + 1);
    }
    while (!heap.empty()) {
        long before = heap.comparisons();
        std::size_t size = heap.size();
        heap.pop();
        assert(heap.comparisons() - before <= 2 * (static_cast<long>(std::log2(double(size))) + 1));
    }
}

void test_build_bound() {
    for (int n = 0; n < 2000; n += 37) {
        std::vector<int> items(n);
        for (int i = 0; i < n; i++) {
            items[i] = n - i;
        }
        long comparisons = 0;
        build_max_heap(items, [&](int a, int b) {
            comparisons++;
            return a > b;
        });
        assert(comparisons <= 2L * n);
        for (int i = 1; i < n; i++) {
            assert(items[(i - 1) / 2] <= items[i]);
        }
    }
}

void test_heapsort_against_sort() {
    std::mt19937 generator(13);
    for (int round = 0; round < 300; round++) {
        std::vector<int> items(generator() % 300);
        for (int& item : items) {
            item = static_cast<int>(generator() % 50);
        }
        std::vector<int> expected = items;
        std::sort(expected.begin(), expected.end());
        heapsort(items, std::less<int>());
        assert(items == expected);
    }
}

void test_heapsort_small_sizes() {
    for (int n = 0; n < 8; n++) {
        std::vector<int> items(n);
        for (int i = 0; i < n; i++) {
            items[i] = n - i;
        }
        heapsort(items, std::less<int>());
        assert(std::is_sorted(items.begin(), items.end()));
    }
}

}  // namespace

int main() {
    test_guide_example();
    test_random_against_priority_queue();
    test_operation_bounds();
    test_build_bound();
    test_heapsort_against_sort();
    test_heapsort_small_sizes();
    std::cout << "todas las pruebas pasaron\n";
    return 0;
}