// Pruebas de BstSet: casos dirigidos, y operaciones al azar con semilla fija contra std::set.
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#include "bst_set.h"
#include "counted_key.h"

namespace {

void test_review_questions() {
    BstSet<int> tree;
    for (int key : {5, 3, 8, 1, 4, 7}) {
        assert(tree.insert(key));
    }
    assert(tree.shape() == "5(3(1,4),8(7,_))");
    assert((tree.in_order() == std::vector<int>{1, 3, 4, 5, 7, 8}));
    assert((tree.pre_order() == std::vector<int>{5, 3, 1, 4, 8, 7}));
    assert((tree.post_order() == std::vector<int>{1, 4, 3, 7, 8, 5}));
    assert(tree.height() == 2);
    assert(tree.erase(5));
    assert(tree.shape() == "7(3(1,4),8)");
    tree.check_invariants();
}

// Insertar en preorden repite la forma: cada nodo llega antes que sus descendientes.
void test_pre_order_rebuilds_shape() {
    BstSet<int> tree;
    for (int key : {50, 30, 70, 20, 40, 60, 80, 35, 65, 90}) {
        tree.insert(key);
    }
    BstSet<int> copy;
    for (int key : tree.pre_order()) {
        copy.insert(key);
    }
    assert(copy.shape() == tree.shape());
}

void test_empty_tree() {
    BstSet<int> tree;
    tree.check_invariants();
    assert(tree.height() == -1);
    assert(tree.min() == nullptr);
    assert(tree.max() == nullptr);
    assert(tree.floor(1) == nullptr);
    assert(tree.range(0, 10).empty());
    assert(!tree.erase(1));
    assert(tree.shape() == "_");
}

void test_repeated_insert() {
    BstSet<int> tree;
    assert(tree.insert(1));
    assert(!tree.insert(1));
    assert(tree.size() == 1);
}

void test_floor() {
    BstSet<int> tree;
    for (int key : {20, 10, 30, 5, 15}) {
        tree.insert(key);
    }
    assert(tree.floor(4) == nullptr);
    assert(*tree.floor(5) == 5);
    assert(*tree.floor(14) == 10);
    assert(*tree.floor(29) == 20);
    assert(*tree.floor(100) == 30);
}

void test_range_is_half_open() {
    BstSet<int> tree;
    for (int key : {20, 10, 30, 5, 15}) {
        tree.insert(key);
    }
    assert((tree.range(10, 30) == std::vector<int>{10, 15, 20}));
    assert(tree.range(30, 10).empty());
    assert(tree.range(11, 12).empty());
}

void test_sorted_insert_is_a_chain() {
    BstSet<CountedKey> tree;
    const int n = 1000;
    for (int key = 0; key < n; key++) {
        tree.insert(CountedKey{key});
    }
    assert(tree.height() == n - 1);
    // Bajar hasta el final de la cadena hace dos comparaciones por nodo.
    assert(CountedKey::comparisons == static_cast<long>(n) * (n - 1));
    assert(tree.total_depth() == static_cast<long>(n) * (n - 1) / 2);
}

void test_random_against_set() {
    std::mt19937 random(20261110);
    std::uniform_int_distribution<int> key_of(0, 299);
    std::uniform_int_distribution<int> action_of(0, 9);
    BstSet<int> mine;
    std::set<int> model;
    for (int step = 0; step < 20000; step++) {
        int key = key_of(random);
        int action = action_of(random);
        if (action < 5) {
            assert(mine.insert(key) == model.insert(key).second);
        } else if (action < 9) {
            assert(mine.erase(key) == (model.erase(key) == 1));
        } else {
            assert(mine.contains(key) == (model.count(key) == 1));
            auto after = model.upper_bound(key);
            const int* floor = mine.floor(key);
            assert((floor == nullptr) == (after == model.begin()));
            assert(floor == nullptr || *floor == *std::prev(after));
        }
        mine.check_invariants();
        assert(mine.size() == model.size());
        if (step % 200 == 0) {
            std::vector<int> expected(model.begin(), model.end());
            assert(mine.in_order() == expected);
            auto low = model.lower_bound(100);
            auto high = model.lower_bound(200);
            assert(mine.range(100, 200) == std::vector<int>(low, high));
            assert(model.empty() || (*mine.min() == *model.begin() && *mine.max() == *model.rbegin()));
        }
    }
}

}  // namespace

int main() {
    test_review_questions();
    test_pre_order_rebuilds_shape();
    test_empty_tree();
    test_repeated_insert();
    test_floor();
    test_range_is_half_open();
    test_sorted_insert_is_a_chain();
    test_random_against_set();
    std::cout << "ok\n";
    return 0;
}