// Pruebas públicas de los pasos 1 y 3. Se corre una por proceso: heap_tests nombre.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <cstring>
#include <functional>
#include <iostream>
#include <memory>
#include <queue>
#include <random>
#include <string>
#include <utility>
#include <vector>

#include "min_heap.h"
#include "top_k.h"

// Permite a las pruebas mirar y dañar el arreglo.
struct MinHeapTestAccess {
    template <typename Heap>
    static auto& items(Heap& heap) {
        return heap.items_;
    }
};

namespace {

using IntHeap = MinHeap<int>;

std::vector<int> items_of(IntHeap& heap) { return MinHeapTestAccess::items(heap); }

// Comparador que cuenta. El contador vive afuera porque el heap guarda su propia copia.
struct CountingLess {
    long* count;
    bool operator()(int a, int b) const {
        (*count)++;
        return a < b;
    }
};

// Valor sin operator<: si check_invariants lo necesitara, la prueba no compilaría.
struct NoOrder {
    int value = 0;
};
struct NoOrderLess {
    bool operator()(const NoOrder& a, const NoOrder& b) const { return a.value < b.value; }
};

// Cuenta sus copias: bajar y subir no deben copiar nada.
struct CountedCopies {
    int value = 0;
    inline static long copies = 0;
    explicit CountedCopies(int v) : value(v) {}
    CountedCopies(const CountedCopies& other) : value(other.value) { copies++; }
    CountedCopies(CountedCopies&& other) noexcept : value(other.value) {}
    CountedCopies& operator=(const CountedCopies& other) {
        value = other.value;
        copies++;
        return *this;
    }
    CountedCopies& operator=(CountedCopies&& other) noexcept {
        value = other.value;
        return *this;
    }
    bool operator<(const CountedCopies& other) const { return value < other.value; }
};

// Cuenta cuántos objetos viven a la vez.
struct Live {
    int value = 0;
    inline static long count = 0;
    inline static long peak = 0;
    explicit Live(int v) : value(v) { born(); }
    Live(const Live& other) : value(other.value) { born(); }
    Live& operator=(const Live& other) = default;
    ~Live() { count--; }
    static void born() {
        count++;
        peak = std::max(peak, count);
    }
};

void test_new_is_empty() {
    IntHeap heap;
    assert(heap.empty());
    assert(heap.size() == 0);
    heap.check_invariants();
}

void test_guide_example() {
    IntHeap heap;
    const std::vector<std::vector<int>> expected = {{5}, {3, 5}, {3, 5, 8}, {1, 3, 8, 5}, {1, 3, 8, 5, 4}};
    const std::vector<int> values = {5, 3, 8, 1, 4};
    for (std::size_t i = 0; i < values.size(); i++) {
        heap.push(values[i]);
        heap.check_invariants();
        assert(items_of(heap) == expected[i]);
        assert(heap.size() == i + 1);
    }
    assert(heap.top() == 1);
}

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

void test_pop_chooses_smaller_child() {
    // Si baja siempre por la izquierda, la raíz queda mal.
    IntHeap heap(std::vector<int>{1, 4, 2, 5, 6, 3});
    assert((items_of(heap) == std::vector<int>{1, 4, 2, 5, 6, 3}));
    heap.pop();
    assert(heap.top() == 2);
    heap.check_invariants();
}

void test_pops_in_order() {
    IntHeap heap;
    for (int value : {9, 2, 7, 2, 8, 1, 5, 9, 0}) {
        heap.push(value);
    }
    std::vector<int> out;
    while (!heap.empty()) {
        out.push_back(heap.top());
        heap.pop();
        heap.check_invariants();
    }
    assert((out == std::vector<int>{0, 1, 2, 2, 5, 7, 8, 9, 9}));
}

void test_one_element() {
    MinHeap<std::string> heap;
    heap.push("solo");
    assert(heap.top() == "solo");
    heap.pop();
    assert(heap.empty());
    heap.push("otra vez");
    assert(heap.top() == "otra vez");
}

void test_other_comparator() {
    MinHeap<int, std::greater<int>> heap;
    for (int value : {5, 3, 8, 1, 4}) {
        heap.push(value);
    }
    heap.check_invariants();
    assert(heap.top() == 8);
    heap.pop();
    assert(heap.top() == 5);
}

void test_comparator_with_capture() {
    std::vector<int> distance = {30, 10, 20};
    auto closer = [&distance](int a, int b) { return distance[a] < distance[b]; };
    MinHeap<int, decltype(closer)> heap(closer);
    heap.push(0);
    heap.push(1);
    heap.push(2);
    assert(heap.top() == 1);
    MinHeap<int, decltype(closer)> built(std::vector<int>{0, 1, 2}, closer);
    assert(built.top() == 1);
}

void test_only_uses_comparator() {
    MinHeap<NoOrder, NoOrderLess> heap;
    for (int value : {4, 1, 3}) {
        heap.push(NoOrder{value});
    }
    heap.check_invariants();
    assert(heap.top().value == 1);
    MinHeap<NoOrder, NoOrderLess> built(std::vector<NoOrder>{{3}, {2}, {1}});
    built.check_invariants();
    assert(built.top().value == 1);
}

void test_pairs_for_dijkstra() {
    // La semana 15 guarda (distancia, nodo). std::pair ya compara así.
    MinHeap<std::pair<long, int>> heap;
    heap.push({30, 1});
    heap.push({10, 2});
    heap.push({10, 1});
    assert((heap.top() == std::pair<long, int>{10, 1}));
    heap.pop();
    assert((heap.top() == std::pair<long, int>{10, 2}));
}

void test_no_copies_inside() {
    std::vector<CountedCopies> start;
    start.reserve(2000);
    for (int i = 2000; i > 0; i--) {
        start.emplace_back(i);
    }
    CountedCopies::copies = 0;
    MinHeap<CountedCopies> heap(std::move(start));
    for (int i = 0; i < 2000; i++) {
        heap.push(CountedCopies(i));
    }
    while (!heap.empty()) {
        heap.pop();
    }
    assert(CountedCopies::copies == 0);
}

void test_copy_is_independent() {
    IntHeap heap(std::vector<int>{3, 1, 2});
    IntHeap copy = heap;
    copy.pop();
    assert(heap.size() == 3);
    assert(heap.top() == 1);
    assert(copy.top() == 2);
}

void test_build_example() {
    IntHeap heap(std::vector<int>{5, 3, 8, 1, 4});
    assert((items_of(heap) == std::vector<int>{1, 3, 8, 5, 4}));
    IntHeap larger(std::vector<int>{9, 8, 7, 6, 5, 4, 3, 2, 1});
    assert((items_of(larger) == std::vector<int>{1, 2, 3, 6, 5, 4, 7, 8, 9}));
}

void test_build_small_sizes() {
    for (int n = 0; n <= 70; n++) {
        std::vector<int> values(n);
        for (int i = 0; i < n; i++) {
            values[i] = n - i;
        }
        IntHeap heap(values);
        assert(heap.size() == static_cast<std::size_t>(n));
        heap.check_invariants();
        for (int i = 1; i <= n; i++) {
            assert(heap.top() == i);
            heap.pop();
        }
        assert(heap.empty());
    }
}

void test_build_comparisons() {
    // De abajo hacia arriba son unas 2n. La biblioteca promete 3n. n push sobre esto, unas 15n.
    const int n = 1 << 16;
    std::vector<int> descending(n);
    for (int i = 0; i < n; i++) {
        descending[i] = n - i;
    }
    long count = 0;
    MinHeap<int, CountingLess> heap(descending, CountingLess{&count});
    assert(count <= 3L * n);
    heap.check_invariants();
}

void test_push_comparisons() {
    const int n = 1 << 14;
    const long log_n = 14;
    long count = 0;
    MinHeap<int, CountingLess> descending_heap{CountingLess{&count}};
    for (int value = n; value > 0; value--) {
        long before = count;
        descending_heap.push(value);
        assert(count - before <= log_n);
    }
    // Un valor mayor que el de su padre no sube: una sola comparación.
    count = 0;
    MinHeap<int, CountingLess> ascending_heap{CountingLess{&count}};
    for (int value = 0; value < n; value++) {
        ascending_heap.push(value);
    }
    assert(count <= n);
}

void test_pop_comparisons() {
    const int n = 1 << 14;
    const long log_n = 14;
    long count = 0;
    std::vector<int> values(n);
    std::mt19937 generator(13);
    for (int& value : values) {
        value = static_cast<int>(generator() % 1000000);
    }
    MinHeap<int, CountingLess> heap(values, CountingLess{&count});
    while (!heap.empty()) {
        long before = count;
        heap.pop();
        assert(count - before <= 2 * log_n);
    }
}

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 < 200000; step++) {
        if (reference.empty() || generator() % 5 < 3) {
            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());
        assert(heap.empty() == reference.empty());
        if (step % 5000 == 0) {
            heap.check_invariants();
        }
    }
    heap.check_invariants();
}

void test_random_builds_and_strings() {
    std::mt19937 generator(13);
    for (int round = 0; round < 200; round++) {
        std::vector<std::string> values(generator() % 200);
        for (std::string& value : values) {
            value = std::to_string(generator() % 500);
        }
        MinHeap<std::string> heap(values);
        heap.check_invariants();
        std::sort(values.begin(), values.end());
        for (const std::string& value : values) {
            assert(heap.top() == value);
            heap.pop();
        }
        assert(heap.empty());
    }
}

// Cada una daña un heap sano. El programa debe imprimir "sano" y luego detenerse.
template <typename Damage>
void broken(Damage damage) {
    IntHeap heap(std::vector<int>{10, 20, 30, 40, 50, 60, 70, 80, 90, 100});
    heap.check_invariants();
    std::cout << "sano" << std::endl;
    damage(MinHeapTestAccess::items(heap));
    heap.check_invariants();
}

void test_broken_root() {
    broken([](std::vector<int>& items) { items[0] = 25; });
}

void test_broken_right_child() {
    broken([](std::vector<int>& items) { items[2] = 5; });
}

void test_broken_last_leaf() {
    broken([](std::vector<int>& items) { items.back() = 45; });
}

// ---- Paso 3 ----

void test_top_k_cases() {
    std::vector<int> values = {5, 1, 9, 3, 7, 9};
    auto greater = std::greater<int>();
    assert(top_k(values, 0, greater).empty());
    assert((top_k(values, 1, greater) == std::vector<int>{9}));
    assert((top_k(values, 3, greater) == std::vector<int>{9, 9, 7}));
    assert((top_k(values, 6, greater) == std::vector<int>{9, 9, 7, 5, 3, 1}));
    assert((top_k(values, 100, greater) == std::vector<int>{9, 9, 7, 5, 3, 1}));
    assert(top_k(std::vector<int>{}, 3, greater).empty());
    assert((top_k(values, 2, std::less<int>()) == std::vector<int>{1, 3}));
}

void test_top_k_random() {
    std::mt19937 generator(13);
    for (int round = 0; round < 300; round++) {
        std::vector<int> values(generator() % 400);
        for (int& value : values) {
            value = static_cast<int>(generator() % 300);
        }
        std::size_t k = generator() % 450;
        std::vector<int> expected = values;
        std::sort(expected.begin(), expected.end(), std::greater<int>());
        expected.resize(std::min(k, expected.size()));
        assert(top_k(values, k, std::greater<int>()) == expected);
    }
}

void test_top_k_comparisons() {
    // Con valores crecientes, cada uno entra al heap. Ordenar todo usaría unas 17n.
    const int n = 100000;
    const std::size_t k = 8;
    std::vector<int> values(n);
    for (int i = 0; i < n; i++) {
        values[i] = i;
    }
    long count = 0;
    std::vector<int> result = top_k(values, k, [&count](int a, int b) {
        count++;
        return a > b;
    });
    assert(result.front() == n - 1);
    assert(result.size() == k);
    assert(count <= 10L * n);
}

void test_top_k_keeps_few_objects() {
    const int n = 20000;
    const std::size_t k = 10;
    std::vector<Live> values;
    values.reserve(n);
    for (int i = 0; i < n; i++) {
        values.emplace_back((i * 7919) % n);
    }
    Live::peak = Live::count;
    std::vector<Live> result = top_k(values, k, [](const Live& a, const Live& b) { return a.value > b.value; });
    assert(result.size() == k);
    assert(result[0].value == n - 1);
    // El heap, el resultado y algún temporal: de ninguna forma n copias.
    assert(Live::peak - n <= 3 * static_cast<long>(k) + 16);
}

struct Test {
    const char* name;
    void (*run)();
};

const Test tests[] = {
    {"new_is_empty", test_new_is_empty},
    {"guide_example", test_guide_example},
    {"pop_example", test_pop_example},
    {"pop_chooses_smaller_child", test_pop_chooses_smaller_child},
    {"pops_in_order", test_pops_in_order},
    {"one_element", test_one_element},
    {"other_comparator", test_other_comparator},
    {"comparator_with_capture", test_comparator_with_capture},
    {"only_uses_comparator", test_only_uses_comparator},
    {"pairs_for_dijkstra", test_pairs_for_dijkstra},
    {"no_copies_inside", test_no_copies_inside},
    {"copy_is_independent", test_copy_is_independent},
    {"build_example", test_build_example},
    {"build_small_sizes", test_build_small_sizes},
    {"build_comparisons", test_build_comparisons},
    {"push_comparisons", test_push_comparisons},
    {"pop_comparisons", test_pop_comparisons},
    {"random_against_priority_queue", test_random_against_priority_queue},
    {"random_builds_and_strings", test_random_builds_and_strings},
    {"broken_root", test_broken_root},
    {"broken_right_child", test_broken_right_child},
    {"broken_last_leaf", test_broken_last_leaf},
    {"top_k_cases", test_top_k_cases},
    {"top_k_random", test_top_k_random},
    {"top_k_comparisons", test_top_k_comparisons},
    {"top_k_keeps_few_objects", test_top_k_keeps_few_objects},
};

}  // namespace

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: heap_tests nombre\n";
        return 2;
    }
    for (const Test& test : tests) {
        if (std::strcmp(test.name, argv[1]) == 0) {
            test.run();
            return 0;
        }
    }
    std::cerr << "no existe la prueba " << argv[1] << "\n";
    return 2;
}