// Pruebas públicas del laboratorio. Se corre una por proceso: map_tests nombre.
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#include "measure.h"
#include "rb_set.h"
#include "red_black_map.h"

// Deja a las pruebas ver el árbol por dentro, armarlo a mano, rotar y dañarlo.
struct RedBlackMapTestAccess {
    template <typename Map>
    static auto* root(Map& map) { return map.root_; }
    template <typename Map>
    static const auto* root(const Map& map) { return map.root_; }
    template <typename Map>
    static void add_to_size(Map& map) { map.size_++; }
    template <typename Map, typename K>
    static auto* node(Map& map, const K& key) { return map.find_node(key); }
    template <typename Map, typename Node>
    static auto* rotate_left(Map& map, Node* node) { return map.rotate_left(node); }
    template <typename Map, typename Node>
    static auto* rotate_right(Map& map, Node* node) { return map.rotate_right(node); }

    // Lee un árbol en una línea: clave(izquierdo,derecho), con _ si falta un hijo y r si es rojo.
    template <typename K, typename V>
    static void build(RedBlackMap<K, V>& map, const std::string& text) {
        std::size_t position = 0;
        map.root_ = parse<K, V>(map, text, position, nullptr);
        assert(position == text.size());
    }

    template <typename K, typename V>
    static std::string shape(const RedBlackMap<K, V>& map) {
        std::ostringstream out;
        write<K, V>(map.root_, out);
        return out.str();
    }

    template <typename K, typename V, typename Node>
    static void paint_red(Node* node) { node->color = RedBlackMap<K, V>::Color::red; }

    template <typename K, typename V, typename Node>
    static void paint_black(Node* node) { node->color = RedBlackMap<K, V>::Color::black; }

    // Un color que no es ninguno de los dos.
    template <typename K, typename V, typename Node>
    static void paint_invalid(Node* node) { node->color = static_cast<typename RedBlackMap<K, V>::Color>(2); }

    template <typename K, typename V, typename Node>
    static bool is_red(const Node* node) { return node != nullptr && node->color == RedBlackMap<K, V>::Color::red; }

private:
    template <typename K, typename V>
    static typename RedBlackMap<K, V>::Node* parse(RedBlackMap<K, V>& map, const std::string& text, std::size_t& position,
                                                   typename RedBlackMap<K, V>::Node* parent) {
        if (text[position] == '_') {
            position++;
            return nullptr;
        }
        int key = 0;
        while (position < text.size() && text[position] >= '0' && text[position] <= '9') {
            key = key * 10 + (text[position] - '0');
            position++;
        }
        using Map = RedBlackMap<K, V>;
        auto* node = new typename Map::Node{key, key * 10, parent};
        node->color = Map::Color::black;
        if (position < text.size() && text[position] == 'r') {
            node->color = Map::Color::red;
            position++;
        }
        map.size_++;
        if (position < text.size() && text[position] == '(') {
            position++;
            node->left = parse<K, V>(map, text, position, node);
            assert(text[position] == ',');
            position++;
            node->right = parse<K, V>(map, text, position, node);
            assert(text[position] == ')');
            position++;
        }
        return node;
    }

    template <typename K, typename V>
    static void write(const typename RedBlackMap<K, V>::Node* node, std::ostringstream& out) {
        if (node == nullptr) {
            out << "_";
            return;
        }
        out << node->key;
        if (node->color == RedBlackMap<K, V>::Color::red) {
            out << "r";
        }
        if (node->left != nullptr || node->right != nullptr) {
            out << "(";
            write<K, V>(node->left, out);
            out << ",";
            write<K, V>(node->right, out);
            out << ")";
        }
    }
};

using Access = RedBlackMapTestAccess;

namespace {

using IntMap = RedBlackMap<int, int>;
using Keys = std::vector<int>;

// Clave que solo se puede comparar con <.
struct LessOnly {
    int value = 0;
    bool operator<(const LessOnly& other) const { return value < other.value; }
};

// Valor que cuenta cuántos objetos viven: una copia olvidada se nota aquí.
struct Live {
    int value = 0;
    inline static long count = 0;
    Live() { count++; }
    explicit Live(int v) : value(v) { count++; }
    Live(const Live& other) : value(other.value) { count++; }
    Live& operator=(const Live& other) = default;
    ~Live() { count--; }
};

IntMap make_map(const Keys& keys) {
    IntMap map;
    for (int key : keys) {
        map.insert(key, key * 10);
    }
    return map;
}

// Un árbol armado a mano, con esa forma y esos colores. No pasa por insert.
IntMap tree_of(const std::string& text) {
    IntMap map;
    Access::build(map, text);
    return map;
}

std::string shape_of(const IntMap& map) { return Access::shape(map); }

// Revisa el árbol por su cuenta, sin usar check_invariants. Devuelve los negros hasta una hoja nula.
template <typename K, typename V, typename Node>
int verify_node(const Node* node, const K* low, const K* high, std::size_t& count) {
    if (node == nullptr) {
        return 0;
    }
    count++;
    assert(low == nullptr || *low < node->key);
    assert(high == nullptr || node->key < *high);
    assert(node->left == nullptr || node->left->parent == node);
    assert(node->right == nullptr || node->right->parent == node);
    bool red = Access::is_red<K, V>(node);
    if (red) {
        assert((!Access::is_red<K, V>(node->left)));
        assert((!Access::is_red<K, V>(node->right)));
    }
    int left = verify_node<K, V>(node->left, low, &node->key, count);
    int right = verify_node<K, V>(node->right, &node->key, high, count);
    assert(left == right);
    return left + (red ? 0 : 1);
}

// Solo orden, padres, raíz y tamaño: para el mapa de partida, cuyos colores no significan nada.
template <typename K, typename V, typename Node>
void verify_links_node(const Node* node, const K* low, const K* high, std::size_t& count) {
    if (node == nullptr) {
        return;
    }
    count++;
    assert(low == nullptr || *low < node->key);
    assert(high == nullptr || node->key < *high);
    assert(node->left == nullptr || node->left->parent == node);
    assert(node->right == nullptr || node->right->parent == node);
    verify_links_node<K, V>(node->left, low, &node->key, count);
    verify_links_node<K, V>(node->right, &node->key, high, count);
}

template <typename K, typename V>
void verify_links(const RedBlackMap<K, V>& map) {
    const auto* root = Access::root(map);
    assert(root == nullptr || root->parent == nullptr);
    assert((root == nullptr) == (map.size() == 0));
    std::size_t count = 0;
    verify_links_node<K, V>(root, static_cast<const K*>(nullptr), static_cast<const K*>(nullptr), count);
    assert(count == map.size());
}

// Las cinco propiedades, el orden, los padres, y que la altura respete la cota.
template <typename K, typename V>
void verify_rb(const RedBlackMap<K, V>& map) {
    const auto* root = Access::root(map);
    assert(root == nullptr || root->parent == nullptr);
    assert((root == nullptr) == (map.size() == 0));
    assert((!Access::is_red<K, V>(root)));
    std::size_t count = 0;
    int blacks = verify_node<K, V>(root, static_cast<const K*>(nullptr), static_cast<const K*>(nullptr), count);
    assert(count == map.size());
    assert(blacks == map.black_height());
    assert(map.height() + 1 <= 2 * blacks);
    assert(blacks >= 31 || (std::size_t{1} << blacks) - 1 <= map.size());
}

template <typename K, typename V>
void assert_same_as_model(const RedBlackMap<K, V>& mine, const std::map<K, V>& model) {
    assert(mine.size() == model.size());
    std::vector<K> keys;
    for (const auto& [key, value] : model) {
        keys.push_back(key);
        const V* found = mine.find(key);
        assert(found != nullptr);
        assert(*found == value);
    }
    assert(mine.in_order_keys() == keys);
}

void expect_shapes(const Keys& keys, const std::string& shape, long rotations, long recolors) {
    IntMap map = make_map(keys);
    verify_rb(map);
    map.check_invariants();
    assert(shape_of(map) == shape);
    assert(map.rotations() == rotations);
    assert(map.recolors() == recolors);
}

// ---- El mapa de partida: pasan desde el inicio, y deben seguir pasando al final ----

void test_new_is_empty() {
    IntMap map;
    verify_links(map);
    assert(map.empty());
    assert(map.height() == -1);
    assert(map.black_height() == 0);
    assert(map.find(1) == nullptr);
    assert(map.in_order_keys().empty());
    assert(map.rotations() == 0);
    assert(map.recolors() == 0);
}

void test_insert_and_find() {
    IntMap map = make_map({5, 3, 8, 1, 4, 7});
    verify_links(map);
    assert(map.size() == 6);
    for (int key : {1, 3, 4, 5, 7, 8}) {
        assert(map.find(key) != nullptr);
        assert(*map.find(key) == key * 10);
    }
    for (int key : {0, 2, 6, 9}) {
        assert(map.find(key) == nullptr);
    }
}

void test_insert_does_not_overwrite() {
    IntMap map;
    assert(map.insert(1, 100));
    assert(!map.insert(1, 200));
    assert(*map.find(1) == 100);
    assert(map.size() == 1);
}

void test_subscript_operator() {
    IntMap map;
    map[4] = 40;
    map[2]++;
    map[2]++;
    assert(map.size() == 2);
    assert(map[4] == 40);
    assert(map[2] == 2);
    assert(map.size() == 2);
    verify_links(map);
}

void test_strings_as_keys() {
    RedBlackMap<std::string, int> map;
    map.insert("pera", 1);
    map.insert("ananá", 2);
    map.insert("zapote", 3);
    map["ñame"] = 4;
    // Orden de bytes: la ñ, que empieza con 0xC3, va después de la z.
    assert((map.in_order_keys() == std::vector<std::string>{"ananá", "pera", "zapote", "ñame"}));
    verify_links(map);
}

void test_only_needs_less_than() {
    RedBlackMap<LessOnly, std::string> map;
    map.insert(LessOnly{2}, "dos");
    map.insert(LessOnly{1}, "uno");
    assert(!map.insert(LessOnly{2}, "otro"));
    assert(*map.find(LessOnly{2}) == "dos");
    assert(map.size() == 2);
    verify_links(map);
}

void test_no_objects_left_behind() {
    {
        RedBlackMap<int, Live> map;
        for (int i = 0; i < 100; i++) {
            map.insert((i * 37) % 101, Live(i));
        }
        assert(Live::count == 100);
    }
    assert(Live::count == 0);
}

void test_copy_is_independent() {
    IntMap original = make_map({5, 3, 8, 1, 4, 7});
    IntMap copy(original);
    verify_links(copy);
    assert(shape_of(copy) == shape_of(original));
    copy.insert(9, 90);
    *copy.find(5) = 0;
    assert(original.find(9) == nullptr);
    assert(*original.find(5) == 50);
    IntMap assigned;
    assigned.insert(100, 100);
    assigned = original;
    verify_links(assigned);
    assert(assigned.find(100) == nullptr);
    assert(shape_of(assigned) == shape_of(original));
}

void test_self_assignment() {
    IntMap map = make_map({2, 1, 3});
    IntMap& alias = map;
    map = alias;
    verify_links(map);
    assert(map.size() == 3);
    map = std::move(alias);
    verify_links(map);
    assert(map.size() == 3);
}

void test_move_leaves_empty_and_usable() {
    IntMap source = make_map({2, 1, 3});
    IntMap target(std::move(source));
    assert(target.size() == 3);
    verify_links(target);
    verify_links(source);
    assert(source.empty());
    source.insert(1, 1);
    assert(source.size() == 1);
    IntMap other;
    other = std::move(target);
    assert(other.size() == 3);
    verify_links(other);
}

void test_random_against_map_links() {
    std::mt19937 random(20261117);
    IntMap mine;
    std::map<int, int> model;
    for (int step = 0; step < 4000; step++) {
        int key = static_cast<int>(random() % 500);
        if (random() % 10 < 7) {
            assert(mine.insert(key, step) == model.insert({key, step}).second);
        } else {
            const int* found = mine.find(key);
            auto position = model.find(key);
            assert((found != nullptr) == (position != model.end()));
            assert(found == nullptr || *found == position->second);
        }
        assert(mine.size() == model.size());
    }
    verify_links(mine);
    assert_same_as_model(mine, model);
}

void test_queries_still_work() {
    IntMap map = make_map({20, 10, 30, 5, 15, 25, 35});
    assert(*map.min_key() == 5);
    assert(*map.max_key() == 35);
    assert(map.floor(4) == nullptr);
    assert(*map.floor(14) == 10);
    assert(*map.ceiling(16) == 20);
    assert(map.ceiling(36) == nullptr);
    auto pairs = map.range(10, 25);
    assert((pairs == std::vector<std::pair<int, int>>{{10, 100}, {15, 150}, {20, 200}}));
    Keys keys;
    for (auto [key, value] : map) {
        assert(value == key * 10);
        keys.push_back(key);
    }
    assert((keys == Keys{5, 10, 15, 20, 25, 30, 35}));
}

// ---- Paso 1: las rotaciones de la semana 11. Los árboles se arman a mano ----

void test_rotate_right_at_root() {
    IntMap map = tree_of("40(20(10,30),60)");
    auto* node = Access::node(map, 40);
    auto* top = Access::rotate_right(map, node);
    assert(top->key == 20);
    assert(Access::root(map) == top);
    assert(top->parent == nullptr);
    assert(shape_of(map) == "20(10,40(30,60))");
    verify_links(map);
}

void test_rotate_left_at_root() {
    IntMap map = tree_of("20(10,40(30,60))");
    auto* top = Access::rotate_left(map, Access::node(map, 20));
    assert(top->key == 40);
    assert(Access::root(map) == top);
    assert(top->parent == nullptr);
    assert(shape_of(map) == "40(20(10,30),60)");
    verify_links(map);
}

void test_rotate_under_left_link() {
    IntMap map = tree_of("50(30(20,40),70)");
    auto* top = Access::rotate_right(map, Access::node(map, 30));
    assert(top->key == 20);
    assert(shape_of(map) == "50(20(_,30(_,40)),70)");
    assert(Access::node(map, 50)->left == top);
    verify_links(map);
}

void test_rotate_under_right_link() {
    IntMap map = tree_of("50(30,70(60,80))");
    auto* top = Access::rotate_left(map, Access::node(map, 70));
    assert(top->key == 80);
    assert(shape_of(map) == "50(30,80(70(60,_),_))");
    assert(Access::node(map, 50)->right == top);
    verify_links(map);
}

// El subárbol del medio se muda: su padre tiene que cambiar.
void test_rotate_moves_middle_subtree() {
    IntMap map = tree_of("40(20(10,30),60)");
    auto* middle = Access::node(map, 30);
    auto* x = Access::node(map, 40);
    Access::rotate_right(map, x);
    assert(middle->parent == x);
    assert(x->left == middle);
    Access::rotate_left(map, Access::node(map, 20));
    assert(middle->parent == Access::node(map, 20));
}

void test_rotate_without_middle_subtree() {
    IntMap map = tree_of("3(2(1,_),_)");
    Access::rotate_right(map, Access::node(map, 3));
    assert(shape_of(map) == "2(1,3)");
    verify_links(map);
    IntMap other = tree_of("1(_,2(_,3))");
    Access::rotate_left(other, Access::node(other, 1));
    assert(shape_of(other) == "2(1,3)");
    verify_links(other);
}

// Las rotaciones no tocan los colores: cada nodo se queda con el suyo.
void test_rotate_leaves_colors_alone() {
    IntMap map = tree_of("40(20r(10,30),60)");
    Access::rotate_right(map, Access::node(map, 40));
    assert(shape_of(map) == "20r(10,40(30,60))");
    Access::rotate_left(map, Access::node(map, 20));
    assert(shape_of(map) == "40(20r(10,30),60)");
    assert(map.recolors() == 0);
}

void test_rotate_keeps_nodes_in_place() {
    IntMap map = tree_of("40(20(10,30),60)");
    auto* x = Access::node(map, 40);
    auto* y = Access::node(map, 20);
    const int* value = map.find(20);
    Access::rotate_right(map, x);
    assert(x->key == 40);
    assert(y->key == 20);
    assert(Access::node(map, 40) == x);
    assert(map.find(20) == value);
}

void test_rotate_counts_rotations() {
    IntMap map = tree_of("40(20(10,30),60)");
    Access::rotate_right(map, Access::node(map, 40));
    assert(map.rotations() == 1);
    Access::rotate_left(map, Access::node(map, 20));
    assert(map.rotations() == 2);
}

void test_rotate_random_nodes() {
    std::mt19937 random(20261118);
    IntMap map = tree_of("8(4(2(1,3),6(5,7)),12(10(9,11),14(13,15)))");
    Keys order = map.in_order_keys();
    long done = 0;
    for (int step = 0; step < 3000; step++) {
        auto* node = Access::node(map, static_cast<int>(1 + random() % 15));
        if (random() % 2 == 0 && node->right != nullptr) {
            Access::rotate_left(map, node);
            done++;
        } else if (node->left != nullptr) {
            Access::rotate_right(map, node);
            done++;
        }
        verify_links(map);
        assert(map.in_order_keys() == order);
    }
    assert(map.rotations() == done);
}

// ---- Paso 2: check_invariants, con árboles armados a mano ----

void test_check_accepts_healthy_trees() {
    for (const char* text : {"10", "10(5r,_)", "10(_,20r)", "10(5r,20r)", "10(5,20)", "20(10(_,15r),30(25r,_))",
                             "20(10(5r,15r),30)", "8(4r(2(1r,3r),6(5r,7r)),12(10r,14r))",
                             "7(2r(1,5(4r,_)),11r(8,14(_,15r)))"}) {
        IntMap map = tree_of(text);
        map.check_invariants();
    }
    IntMap empty;
    empty.check_invariants();
}

// Los árboles que hay que detectar. Antes se revisa uno sano, para que un check_invariants
// que siempre falle no pase estas pruebas.
void expect_rejected(const std::string& text) {
    IntMap healthy = tree_of("20(10(_,15r),30(25r,_))");
    healthy.check_invariants();
    std::cout << "sano" << std::endl;
    IntMap broken = tree_of(text);
    broken.check_invariants();
}

// Propiedad 1: ni rojo ni negro.
void test_broken_invalid_color() {
    IntMap healthy = tree_of("20(10,30)");
    healthy.check_invariants();
    std::cout << "sano" << std::endl;
    Access::paint_invalid<int, int>(Access::node(healthy, 10));
    healthy.check_invariants();
}

// Propiedad 2: raíz roja, y nada más está mal.
void test_broken_red_root_alone() { expect_rejected("5r"); }
void test_broken_red_root_with_children() { expect_rejected("5r(3,8)"); }

// Propiedad 4: un rojo con hijo rojo. La cantidad de negros es igual en todos los caminos.
void test_broken_red_red_left() { expect_rejected("10(5r(3r,_),15r)"); }
void test_broken_red_red_right() { expect_rejected("10(5r(_,7r),15r)"); }
void test_broken_red_red_deep() { expect_rejected("20(10(5r,15r(12r,_)),30(25r,35r))"); }

// Propiedad 5: distinta cantidad de negros, sin ningún rojo con hijo rojo.
void test_broken_blacks_at_root() { expect_rejected("10(5,15r)"); }
void test_broken_blacks_missing_child() { expect_rejected("10(5,_)"); }
// El camino de más a la izquierda y el de más a la derecha cuentan lo mismo: la diferencia
// está adentro, y solo se ve revisando cada nodo.
void test_broken_blacks_inner_left() { expect_rejected("20(10(5,15r),30(25,35))"); }
void test_broken_blacks_inner_right() { expect_rejected("20(10(5,15),30(25r,35))"); }
void test_broken_blacks_inner_deep() { expect_rejected("40(20(10(5,15),30(25,35)),60(50(45,55r),70(65,75)))"); }

// El orden.
void test_broken_order_child() { expect_rejected("10(15,5)"); }
void test_broken_order_deep_left() { expect_rejected("20(10(5,25),30(22,35))"); }
void test_broken_order_deep_right() { expect_rejected("20(10(5,15),30(18,35))"); }

// Los enlaces y el tamaño.
void test_broken_parent_of_child() {
    IntMap map = tree_of("20(10(5,15),30(25,35))");
    map.check_invariants();
    std::cout << "sano" << std::endl;
    auto* node = Access::node(map, 15);
    auto* parent = node->parent;
    node->parent = Access::node(map, 30);
    map.check_invariants();
    // Si no lo notó: se repara el enlace, para que el destructor no sea quien falle.
    node->parent = parent;
}

void test_broken_parent_of_root() {
    IntMap map = tree_of("20(10,30)");
    map.check_invariants();
    std::cout << "sano" << std::endl;
    Access::root(map)->parent = Access::node(map, 10);
    map.check_invariants();
    // Si no lo notó: se repara el enlace, para que el destructor no sea quien falle.
    Access::root(map)->parent = nullptr;
}

void test_broken_size() {
    IntMap map = tree_of("20(10,30)");
    map.check_invariants();
    std::cout << "sano" << std::endl;
    Access::add_to_size(map);
    map.check_invariants();
}

// ---- Paso 3: la inserción ----

void test_first_key_is_black() { expect_shapes({10}, "10", 0, 0); }

void test_parent_black_needs_nothing() {
    expect_shapes({10, 5}, "10(5r,_)", 0, 0);
    expect_shapes({10, 20}, "10(_,20r)", 0, 0);
    expect_shapes({10, 5, 20}, "10(5r,20r)", 0, 0);
}

void test_uncle_red_recolors() {
    expect_shapes({20, 10, 30, 5}, "20(10(5r,_),30)", 0, 1);
    expect_shapes({20, 10, 30, 15}, "20(10(_,15r),30)", 0, 1);
    expect_shapes({20, 10, 30, 25}, "20(10,30(25r,_))", 0, 1);
    expect_shapes({20, 10, 30, 35}, "20(10,30(_,35r))", 0, 1);
}

// Tío nulo: cuenta como negro.
void test_line_rotates_once() {
    expect_shapes({30, 20, 10}, "20(10r,30r)", 1, 0);
    expect_shapes({10, 20, 30}, "20(10r,30r)", 1, 0);
}

void test_zigzag_rotates_twice() {
    expect_shapes({30, 10, 20}, "20(10r,30r)", 2, 0);
    expect_shapes({10, 30, 20}, "20(10r,30r)", 2, 0);
}

void test_review_question() {
    expect_shapes({10, 20, 30}, "20(10r,30r)", 1, 0);
    expect_shapes({10, 20, 30, 15}, "20(10(_,15r),30)", 1, 1);
    expect_shapes({10, 20, 30, 15, 25}, "20(10(_,15r),30(25r,_))", 1, 1);
}

// El problema sube, y arriba encuentra un tío negro de verdad, que no es nulo.
void test_recolor_then_rotate_above() {
    expect_shapes({11, 2, 14, 1, 7, 15, 5, 8}, "11(2r(1,7(5r,8r)),14(_,15r))", 0, 2);
    expect_shapes({11, 2, 14, 1, 7, 15, 5, 8, 4}, "7(2r(1,5(4r,_)),11r(8,14(_,15r)))", 2, 3);
}

void test_root_stays_black() {
    IntMap map;
    for (int key = 0; key < 200; key++) {
        map.insert(key, key);
        assert((!Access::is_red<int, int>(Access::root(map))));
    }
    verify_rb(map);
}

void test_subscript_repairs() {
    IntMap map;
    for (int key = 0; key < 200; key++) {
        map[key] = key;
        verify_rb(map);
    }
    assert(map.rotations() > 0);
    assert(map.height() <= 13);
}

void test_subscript_reference_after_rotation() {
    IntMap map;
    map[1] = 1;
    map[2] = 2;
    int& value = map[3];
    value = 33;
    assert(*map.find(3) == 33);
    verify_rb(map);
}

void test_repeated_key_changes_nothing() {
    IntMap map = make_map({20, 10, 30, 5});
    std::string before = shape_of(map);
    long rotations = map.rotations();
    long recolors = map.recolors();
    for (int key : {20, 10, 30, 5}) {
        assert(!map.insert(key, 0));
        map[key];
    }
    assert(shape_of(map) == before);
    assert(map.rotations() == rotations);
    assert(map.recolors() == recolors);
    assert(*map.find(5) == 50);
}

void test_at_most_two_rotations_in_every_order() {
    for (int n = 1; n <= 7; n++) {
        Keys keys(n);
        std::iota(keys.begin(), keys.end(), 1);
        do {
            IntMap map;
            for (int key : keys) {
                long before = map.rotations();
                map.insert(key, key);
                assert(map.rotations() - before <= 2);
            }
            verify_rb(map);
        } while (std::next_permutation(keys.begin(), keys.end()));
    }
}

// Todos los órdenes de hasta 7 claves dan la forma y las cuentas del árbol de los apuntes.
void test_same_as_notes_tree_in_every_order() {
    for (int n = 1; n <= 7; n++) {
        Keys keys(n);
        std::iota(keys.begin(), keys.end(), 1);
        do {
            IntMap map;
            RedBlackSet<int> notes;
            for (int key : keys) {
                map.insert(key, key);
                notes.insert(key);
            }
            assert(shape_of(map) == notes.shape());
            assert(map.rotations() == notes.rotations());
            assert(map.recolors() == notes.recolors());
        } while (std::next_permutation(keys.begin(), keys.end()));
    }
}

void test_same_as_notes_tree_with_many_keys() {
    Keys keys(4000);
    std::iota(keys.begin(), keys.end(), 0);
    std::mt19937 random(20261119);
    std::shuffle(keys.begin(), keys.end(), random);
    IntMap map;
    RedBlackSet<int> notes;
    for (std::size_t i = 0; i < keys.size(); i++) {
        map.insert(keys[i], keys[i]);
        notes.insert(keys[i]);
        if (i % 100 == 0) {
            assert(shape_of(map) == notes.shape());
        }
    }
    assert(shape_of(map) == notes.shape());
    assert(map.rotations() == notes.rotations());
    assert(map.recolors() == notes.recolors());
    assert(map.height() == notes.height());
}

void test_sorted_keys_in_both_directions() {
    for (int n : {1000, 4000}) {
        IntMap up;
        IntMap down;
        for (int key = 0; key < n; key++) {
            up.insert(key, key);
            down.insert(n - key, key);
        }
        verify_rb(up);
        verify_rb(down);
        assert(up.height() == down.height());
        assert(up.rotations() == down.rotations());
        assert(up.recolors() == down.recolors());
    }
    assert(make_map({1, 2, 3, 4, 5, 6, 7, 8}).height() == 3);
}

void test_pointers_survive_rotations() {
    IntMap map;
    std::vector<const int*> values;
    for (int key = 0; key < 500; key++) {
        map.insert(key, key * 10);
        values.push_back(map.find(key));
    }
    assert(map.rotations() > 400);
    for (int key = 0; key < 500; key++) {
        assert(map.find(key) == values[key]);
        assert(*values[key] == key * 10);
    }
}

void test_iterate_after_rotations() {
    IntMap map;
    for (int key = 99; key >= 0; key--) {
        map.insert(key, key);
    }
    int next = 0;
    for (auto [key, value] : map) {
        assert(key == next);
        assert(value == next);
        next++;
    }
    assert(next == 100);
}

void test_copy_keeps_colors() {
    IntMap original = make_map({10, 20, 30, 15, 25});
    IntMap copy(original);
    assert(shape_of(copy) == "20(10(_,15r),30(25r,_))");
    verify_rb(copy);
    copy.insert(26, 0);
    verify_rb(copy);
    assert(shape_of(original) == "20(10(_,15r),30(25r,_))");
    verify_rb(original);
}

void test_random_inserts_against_map() {
    std::mt19937 random(20261120);
    IntMap mine;
    std::map<int, int> model;
    for (int step = 0; step < 5000; step++) {
        int key = static_cast<int>(random() % 3000);
        int action = static_cast<int>(random() % 10);
        if (action < 6) {
            assert(mine.insert(key, step) == model.insert({key, step}).second);
        } else if (action < 8) {
            mine[key] = step;
            model[key] = step;
        } else {
            const int* found = mine.find(key);
            auto position = model.find(key);
            assert((found != nullptr) == (position != model.end()));
            assert(found == nullptr || *found == position->second);
        }
        assert(mine.size() == model.size());
        mine.check_invariants();
        verify_rb(mine);
    }
    assert_same_as_model(mine, model);
}

void test_random_strings() {
    std::mt19937 random(20261121);
    RedBlackMap<std::string, int> mine;
    std::map<std::string, int> model;
    for (int step = 0; step < 2000; step++) {
        std::string key = "clave" + std::to_string(random() % 800);
        assert(mine.insert(key, step) == model.insert({key, step}).second);
        if (step % 10 == 0) {
            mine.check_invariants();
            verify_rb(mine);
        }
    }
    assert_same_as_model(mine, model);
}

// ---- Paso 5: lo que mide ----

// Mapa falso: cuenta lo que le piden, sin tiempos.
struct CountingMap {
    inline static long created = 0;
    inline static long inserted = 0;
    inline static long looked_up = 0;
    CountingMap() { created++; }
    bool insert(int, int) {
        inserted++;
        return true;
    }
    const int* find(int key) const {
        looked_up++;
        static const int value = 1;
        return key % 2 == 0 ? &value : nullptr;
    }
    std::size_t size() const { return 0; }
};

void test_time_inserts_builds_a_new_map_each_time() {
    Keys keys(100);
    std::iota(keys.begin(), keys.end(), 0);
    double seconds = time_inserts<CountingMap>(keys, 3);
    assert(seconds >= 0);
    assert(CountingMap::created == 3);
    assert(CountingMap::inserted == 300);
    assert(CountingMap::looked_up == 0);
}

void test_time_finds_looks_up_every_key() {
    Keys keys(100);
    std::iota(keys.begin(), keys.end(), 0);
    CountingMap map;
    double seconds = time_finds(map, keys, 5);
    assert(seconds >= 0);
    assert(CountingMap::created == 1);
    assert(CountingMap::inserted == 0);
    assert(CountingMap::looked_up == 500);
}

void test_measure_works_with_the_real_maps() {
    Keys keys(1000);
    std::iota(keys.begin(), keys.end(), 0);
    assert((time_inserts<std::map<int, int>>(keys, 1) >= 0));
    assert(time_inserts<IntMap>(keys, 1) >= 0);
    std::map<int, int> standard;
    IntMap mine;
    for (int key : keys) {
        put(standard, key);
        put(mine, key);
    }
    assert(has(standard, 5) && !has(standard, 5000));
    assert(has(mine, 5) && !has(mine, 5000));
    assert(time_finds(standard, keys, 1) >= 0);
    assert(time_finds(mine, keys, 1) >= 0);
}

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

#define TEST(name) {#name, test_##name}

const Test tests[] = {
    TEST(new_is_empty), TEST(insert_and_find), TEST(insert_does_not_overwrite), TEST(subscript_operator),
    TEST(strings_as_keys), TEST(only_needs_less_than), TEST(no_objects_left_behind), TEST(copy_is_independent),
    TEST(self_assignment), TEST(move_leaves_empty_and_usable), TEST(random_against_map_links), TEST(queries_still_work),
    TEST(rotate_right_at_root), TEST(rotate_left_at_root), TEST(rotate_under_left_link), TEST(rotate_under_right_link),
    TEST(rotate_moves_middle_subtree), TEST(rotate_without_middle_subtree), TEST(rotate_leaves_colors_alone),
    TEST(rotate_keeps_nodes_in_place), TEST(rotate_counts_rotations), TEST(rotate_random_nodes),
    TEST(check_accepts_healthy_trees), TEST(broken_invalid_color), TEST(broken_red_root_alone),
    TEST(broken_red_root_with_children), TEST(broken_red_red_left), TEST(broken_red_red_right), TEST(broken_red_red_deep),
    TEST(broken_blacks_at_root), TEST(broken_blacks_missing_child), TEST(broken_blacks_inner_left),
    TEST(broken_blacks_inner_right), TEST(broken_blacks_inner_deep), TEST(broken_order_child), TEST(broken_order_deep_left),
    TEST(broken_order_deep_right), TEST(broken_parent_of_child), TEST(broken_parent_of_root), TEST(broken_size),
    TEST(first_key_is_black), TEST(parent_black_needs_nothing), TEST(uncle_red_recolors), TEST(line_rotates_once),
    TEST(zigzag_rotates_twice), TEST(review_question), TEST(recolor_then_rotate_above), TEST(root_stays_black),
    TEST(subscript_repairs), TEST(subscript_reference_after_rotation), TEST(repeated_key_changes_nothing),
    TEST(at_most_two_rotations_in_every_order), TEST(same_as_notes_tree_in_every_order),
    TEST(same_as_notes_tree_with_many_keys), TEST(sorted_keys_in_both_directions), TEST(pointers_survive_rotations),
    TEST(iterate_after_rotations), TEST(copy_keeps_colors), TEST(random_inserts_against_map), TEST(random_strings),
    TEST(time_inserts_builds_a_new_map_each_time), TEST(time_finds_looks_up_every_key),
    TEST(measure_works_with_the_real_maps),
};

}  // namespace

int main(int argc, char** argv) {
    if (argc != 2) {
        std::cerr << "uso: map_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;
}