// Pruebas de AvlSet y de los árboles de Fibonacci: dirigidas, exhaustivas y al azar, contra std::set.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <random>
#include <set>
#include <string>
#include <vector>

#include "avl_set.h"
#include "fibonacci_tree.h"
#include "plain_tree.h"

namespace {

int floor_log2(long n) {
    int result = 0;
    while (n > 1) {
        n /= 2;
        result++;
    }
    return result;
}

AvlSet<int>* build(AvlSet<int>& tree, const std::vector<int>& keys) {
    for (int key : keys) {
        tree.insert(key);
        tree.check_invariants();
    }
    return &tree;
}

void test_four_cases() {
    struct Case {
        std::vector<int> keys;
        const char* kind;
        long rotations;
    };
    const Case cases[] = {
        {{30, 20, 10}, "izquierda-izquierda", 1},
        {{10, 20, 30}, "derecha-derecha", 1},
        {{30, 10, 20}, "izquierda-derecha", 2},
        {{10, 30, 20}, "derecha-izquierda", 2},
    };
    for (const Case& one : cases) {
        AvlSet<int> tree;
        build(tree, one.keys);
        assert(tree.shape() == "20(10,30)");
        assert(tree.rotations() == one.rotations);
        assert(tree.last_repairs().size() == 1);
        assert(tree.last_repairs()[0].kind == one.kind);
    }
}

void test_one_to_seven_is_perfect() {
    AvlSet<int> tree;
    build(tree, {1, 2, 3, 4, 5, 6, 7});
    assert(tree.shape() == "4(2(1,3),6(5,7))");
    assert(tree.rotations() == 4);
}

// La recurrencia, contra Fibonacci y contra el árbol de verdad.
void test_fibonacci_trees() {
    long a = 1;
    long b = 2;
    for (int h = 0; h <= 20; h++) {
        assert(min_avl_nodes(h) == b - 1);
        long next = a + b;
        a = b;
        b = next;
        std::vector<int> keys = fibonacci_keys(h);
        assert(static_cast<long>(keys.size()) == min_avl_nodes(h));
        AvlSet<int> tree;
        for (int key : keys) {
            tree.insert(key);
        }
        tree.check_invariants();
        assert(tree.rotations() == 0);
        assert(tree.height() == h);
    }
    assert(min_avl_nodes(4) == 12);
}

// Con claves ordenadas: altura exacta y rotaciones exactas, para muchos n.
void test_sorted_insertions_are_exact() {
    AvlSet<int> up;
    AvlSet<int> down;
    for (int n = 1; n <= 5000; n++) {
        up.insert(n);
        down.insert(-n);
        assert(up.height() == floor_log2(n));
        assert(down.height() == floor_log2(n));
        assert(up.rotations() == n - floor_log2(n) - 1);
        assert(down.rotations() == n - floor_log2(n) - 1);
    }
    up.check_invariants();
    down.check_invariants();
}

// Todos los órdenes de 8 claves: una reparación por inserción, y todos los borrados posibles.
void test_every_order_of_eight_keys() {
    std::vector<int> keys(8);
    std::iota(keys.begin(), keys.end(), 1);
    do {
        AvlSet<int> tree;
        for (int key : keys) {
            long before = tree.rotations();
            tree.insert(key);
            assert(tree.last_repairs().size() <= 1);
            assert(tree.rotations() - before <= 2);
        }
        assert(tree.height() <= 3);
        std::vector<int> sorted = tree.in_order();
        assert(std::is_sorted(sorted.begin(), sorted.end()));
    } while (std::next_permutation(keys.begin(), keys.end()));
}

void test_erase_cases() {
    {
        AvlSet<int> tree;
        build(tree, {4, 2, 5, 1, 3});
        tree.erase(5);
        tree.check_invariants();
        assert(tree.shape() == "2(1,4(3,_))");
        assert(tree.last_repairs().size() == 1);
        assert(tree.last_repairs()[0].kind == "izquierda-izquierda");
        assert(tree.rotations() == 1);
    }
    {
        AvlSet<int> tree;
        build(tree, {5, 2, 10, 1, 8, 12, 7, 13});
        assert(tree.rotations() == 0);
        tree.erase(1);
        tree.check_invariants();
        assert(tree.shape() == "10(5(2,8(7,_)),12(_,13))");
    }
    {
        AvlSet<int> tree;
        build(tree, {5, 3, 8, 2, 4, 9, 1});
        tree.erase(5);
        tree.check_invariants();
        assert(tree.shape() == "3(2(1,_),8(4,9))");
    }
    {
        AvlSet<int> tree;
        build(tree, {2, 1});
        assert(!tree.erase(9));
        assert(tree.erase(2));
        assert(tree.erase(1));
        tree.check_invariants();
        assert(tree.empty());
        assert(tree.height() == -1);
    }
}

// La cascada: en un árbol de Fibonacci, borrar la clave mayor repara h / 2 veces.
void test_erase_cascade() {
    for (int h = 1; h <= 20; h++) {
        std::vector<int> keys = fibonacci_keys(h);
        AvlSet<int> tree;
        for (int key : keys) {
            tree.insert(key);
        }
        tree.erase(static_cast<int>(keys.size()));
        tree.check_invariants();
        assert(static_cast<int>(tree.last_repairs().size()) == h / 2);
        assert(tree.height() == h - 1);
    }
}

void test_random_against_std_set() {
    std::mt19937 random(20261111);
    AvlSet<int> mine;
    std::set<int> model;
    for (int step = 0; step < 20000; step++) {
        int key = static_cast<int>(random() % 500);
        int height = mine.height();
        if (random() % 2 == 0) {
            assert(mine.insert(key) == model.insert(key).second);
            assert(mine.last_repairs().size() <= 1);
        } else {
            assert(mine.erase(key) == (model.erase(key) == 1));
            assert(static_cast<int>(mine.last_repairs().size()) <= height / 2);
        }
        mine.check_invariants();
        assert(mine.size() == model.size());
        assert(mine.contains(key) == (model.count(key) == 1));
    }
    std::vector<int> expected(model.begin(), model.end());
    assert(mine.in_order() == expected);
}

void test_strings() {
    std::mt19937 random(3);
    AvlSet<std::string> mine;
    std::set<std::string> model;
    for (int step = 0; step < 3000; step++) {
        std::string key;
        for (int i = 0; i < 3; i++) {
            key += static_cast<char>('a' + random() % 6);
        }
        if (step % 3 == 2) {
            assert(mine.erase(key) == (model.erase(key) == 1));
        } else {
            assert(mine.insert(key) == model.insert(key).second);
        }
        mine.check_invariants();
    }
    std::vector<std::string> expected(model.begin(), model.end());
    assert(mine.in_order() == expected);
}

void test_plain_tree_measures() {
    PlainTree<int> tree;
    for (int key = 0; key < 100; key++) {
        tree.insert(key);
    }
    assert(tree.height() == 99);
    assert(tree.height_and_depth().second == 99 * 100 / 2);
    assert(tree.contains(50));
    assert(!tree.contains(100));
    assert(!tree.insert(50));
}

}  // namespace

int main() {
    test_four_cases();
    test_one_to_seven_is_perfect();
    test_fibonacci_trees();
    test_sorted_insertions_are_exact();
    test_every_order_of_eight_keys();
    test_erase_cases();
    test_erase_cascade();
    test_random_against_std_set();
    test_strings();
    test_plain_tree_measures();
    std::cout << "ok\n";
    return 0;
}