// Pruebas de RedBlackSet y de Tree234: casos dirigidos, todos los órdenes y al azar.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <numeric>
#include <random>
#include <set>
#include <string>
#include <vector>

#include "rb_set.h"
#include "tree_234.h"

namespace {

std::string shape_after(const std::vector<int>& keys) {
    RedBlackSet<int> tree;
    for (int key : keys) {
        tree.insert(key);
        tree.check_invariants();
    }
    return tree.shape();
}

void test_directed_shapes() {
    assert(shape_after({10}) == "10");
    assert(shape_after({10, 5}) == "10(5r,_)");
    assert(shape_after({10, 20}) == "10(_,20r)");
    assert(shape_after({30, 20, 10}) == "20(10r,30r)");
    assert(shape_after({10, 20, 30}) == "20(10r,30r)");
    assert(shape_after({30, 10, 20}) == "20(10r,30r)");
    assert(shape_after({10, 30, 20}) == "20(10r,30r)");
    assert(shape_after({10, 20, 30, 15, 25}) == "20(10(_,15r),30(25r,_))");
    assert(shape_after({11, 2, 14, 1, 7, 15, 5, 8, 4}) == "7(2r(1,5(4r,_)),11r(8,14(_,15r)))");
}

void test_repeated_key_changes_nothing() {
    RedBlackSet<int> tree;
    for (int key : {5, 3, 8}) {
        assert(tree.insert(key));
    }
    std::string before = tree.shape();
    assert(!tree.insert(3));
    assert(tree.shape() == before);
    assert(tree.size() == 3);
}

void test_review_question_steps() {
    RedBlackSet<int> tree;
    tree.insert(10);
    assert(tree.last_steps().size() == 1);
    tree.insert(20);
    assert(tree.last_steps().empty());
    tree.insert(30);
    assert(tree.last_steps().size() == 1);
    assert(tree.last_steps()[0].kind == "tio negro, en linea: una rotacion");
    tree.insert(15);
    assert(tree.last_steps().size() == 2);
    assert(tree.last_steps()[0].kind == "tio rojo: recolorear");
    assert(tree.last_steps()[1].kind == "raiz roja: pintar de negro");
    tree.insert(25);
    assert(tree.last_steps().empty());
    assert(tree.collapsed() == "[20]([10 15],[25 30])");
    assert(tree.left_leaning_groups() == 1);
    assert(tree.right_leaning_groups() == 1);
}

// Todos los órdenes: invariantes, cotas, y como máximo 2 rotaciones por inserción.
void test_every_order() {
    for (int n = 1; n <= 8; n++) {
        std::vector<int> keys(n);
        std::iota(keys.begin(), keys.end(), 1);
        do {
            RedBlackSet<int> tree;
            Tree234<int> model;
            for (int key : keys) {
                long before = tree.rotations();
                tree.insert(key);
                model.insert(key);
                tree.check_invariants();
                model.check_invariants();
                assert(tree.rotations() - before <= 2);
                assert(tree.collapsed() == model.shape());
                assert(tree.recolors() == model.splits());
                assert(tree.black_height() == model.levels());
            }
            assert(tree.height() + 1 <= 2 * tree.black_height());
            assert(static_cast<long>(tree.size()) >= (1L << tree.black_height()) - 1);
            assert(tree.height() <= 2 * std::log2(n + 1.0) - 1);
        } while (std::next_permutation(keys.begin(), keys.end()));
    }
}

void test_tree_234_policies_keep_their_invariants() {
    std::mt19937 random(121);
    std::vector<int> keys(3000);
    std::iota(keys.begin(), keys.end(), 0);
    std::shuffle(keys.begin(), keys.end(), random);
    for (SplitPolicy policy : {SplitPolicy::old_middle, SplitPolicy::fixed_second, SplitPolicy::top_down}) {
        Tree234<int> tree(policy);
        std::set<int> model;
        for (int key : keys) {
            assert(tree.insert(key));
            assert(!tree.insert(key));
            model.insert(key);
            if (key % 100 == 0) {
                tree.check_invariants();
            }
        }
        tree.check_invariants();
        assert(tree.size() == model.size());
        for (int key : keys) {
            assert(tree.contains(key));
        }
        assert(!tree.contains(-1));
    }
}

void test_random_against_std_set() {
    std::mt19937 random(122);
    RedBlackSet<int> tree;
    std::set<int> model;
    for (int step = 0; step < 20000; step++) {
        int key = static_cast<int>(random() % 5000);
        if (step % 3 != 2) {
            assert(tree.insert(key) == model.insert(key).second);
        } else {
            assert(tree.contains(key) == (model.count(key) == 1));
        }
        assert(tree.size() == model.size());
        if (step % 10 == 0) {
            tree.check_invariants();
        }
    }
    std::vector<int> expected(model.begin(), model.end());
    assert(tree.in_order() == expected);
}

void test_strings_only_need_less_than() {
    RedBlackSet<std::string> tree;
    for (const char* word : {"pera", "ananá", "zapote", "ñame", "kiwi"}) {
        tree.insert(word);
        tree.check_invariants();
    }
    assert((tree.in_order() == std::vector<std::string>{"ananá", "kiwi", "pera", "zapote", "ñame"}));
}

// Crecientes y decrecientes son espejos: la misma altura y las mismas cuentas.
void test_sorted_orders_are_mirrors() {
    for (int n : {1, 2, 3, 10, 100, 5000}) {
        RedBlackSet<int> up;
        RedBlackSet<int> down;
        for (int key = 0; key < n; key++) {
            up.insert(key);
            down.insert(n - key);
        }
        up.check_invariants();
        down.check_invariants();
        assert(up.height() == down.height());
        assert(up.rotations() == down.rotations());
        assert(up.recolors() == down.recolors());
        assert(up.total_depth() == down.total_depth());
    }
}

}  // namespace

int main() {
    test_directed_shapes();
    test_repeated_key_changes_nothing();
    test_review_question_steps();
    test_every_order();
    test_tree_234_policies_keep_their_invariants();
    test_random_against_std_set();
    test_strings_only_need_less_than();
    test_sorted_orders_are_mirrors();
    std::cout << "ok\n";
    return 0;
}