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

#include "avl_map.h"
#include "fibonacci_tree.h"

// Deja a las pruebas ver el árbol por dentro, rotar a mano y dañarlo.
struct AvlMapTestAccess {
    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); }
    template <typename Map, typename Node>
    static void update_height(Map&, Node* node) { Map::update_height(node); }
};

using Access = AvlMapTestAccess;

namespace {

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

// Clave que solo se puede comparar con <, y que cuenta las comparaciones.
struct LessOnly {
    int value = 0;
    inline static long comparisons = 0;
    bool operator<(const LessOnly& other) const {
        comparisons++;
        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;
}

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

// Revisa el árbol por su cuenta, sin usar check_invariants ni las alturas guardadas.
// Devuelve la altura real. Si check_heights, además exige alturas correctas y balance.
template <typename Node, typename K>
int verify_node(const Node* node, const K* low, const K* high, std::size_t& count, bool check_heights) {
    if (node == nullptr) {
        return -1;
    }
    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);
    int left = verify_node(node->left, low, &node->key, count, check_heights);
    int right = verify_node(node->right, &node->key, high, count, check_heights);
    int height = 1 + std::max(left, right);
    if (check_heights) {
        assert(node->height == height);
        assert(std::abs(left - right) <= 1);
    }
    return height;
}

// Para las pruebas del mapa de partida y de las rotaciones: orden, padres, raíz y tamaño.
template <typename K, typename V>
void verify_links(const AvlMap<K, V>& map) {
    const auto* root = Access::root(map);
    assert(root == nullptr || root->parent == nullptr);
    std::size_t count = 0;
    verify_node(root, static_cast<const K*>(nullptr), static_cast<const K*>(nullptr), count, false);
    assert(count == map.size());
}

// Todo lo anterior, más cada altura guardada y la condición AVL.
template <typename K, typename V>
void verify_avl(const AvlMap<K, V>& map) {
    const auto* root = Access::root(map);
    assert(root == nullptr || root->parent == nullptr);
    std::size_t count = 0;
    verify_node(root, static_cast<const K*>(nullptr), static_cast<const K*>(nullptr), count, true);
    assert(count == map.size());
}

template <typename K, typename V>
void assert_same_as_model(const AvlMap<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);
}

// Inserta las claves, que no provocan ninguna rotación, y comprueba que así fue.
IntMap make_without_rotations(const Keys& keys) {
    IntMap map = make_map(keys);
    assert(map.rotations() == 0);
    return map;
}

// ---- 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.find(1) == nullptr);
    assert(map.in_order_keys().empty());
    assert(map.rotations() == 0);
    assert(map.repairs() == 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_in_order_is_sorted() {
    IntMap map = make_map({5, 3, 8, 1, 4, 7});
    assert((map.in_order_keys() == Keys{1, 3, 4, 5, 7, 8}));
}

void test_strings_as_keys() {
    AvlMap<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() {
    AvlMap<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.erase(LessOnly{2}));
    assert(map.find(LessOnly{2}) == nullptr);
    verify_links(map);
}

void test_no_objects_left_behind() {
    {
        AvlMap<int, Live> map;
        for (int i = 0; i < 100; i++) {
            map.insert((i * 37) % 101, Live(i));
        }
        assert(Live::count == 100);
        for (int i = 0; i < 100; i += 2) {
            assert(map.erase((i * 37) % 101));
        }
        assert(Live::count == 50);
    }
    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(copy.pre_order_keys() == original.pre_order_keys());
    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(assigned.pre_order_keys() == original.pre_order_keys());
}

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_erase_absent() {
    IntMap map = make_map({2, 1, 3});
    assert(!map.erase(9));
    assert(map.size() == 3);
    IntMap empty;
    assert(!empty.erase(1));
    verify_links(map);
}

// Esta no mira el balance: comprueba el mapa como mapa.
void test_random_against_map_links() {
    std::mt19937 random(20261110);
    IntMap mine;
    std::map<int, int> model;
    for (int step = 0; step < 4000; step++) {
        int key = static_cast<int>(random() % 200);
        int action = static_cast<int>(random() % 10);
        if (action < 5) {
            assert(mine.insert(key, step) == model.insert({key, step}).second);
        } else if (action < 9) {
            assert(mine.erase(key) == (model.erase(key) == 1));
        } 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());
        if (step % 20 == 0) {
            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;
    int sum = 0;
    for (auto [key, value] : map) {
        keys.push_back(key);
        sum += value;
    }
    assert((keys == Keys{5, 10, 15, 20, 25, 30, 35}));
    assert(sum == 1400);
    const IntMap& reader = map;
    int count = 0;
    for (const auto& entry : reader) {
        count += entry.key > 0 ? 1 : 0;
    }
    assert(count == 7);
}

// ---- Paso 1: altura y rotaciones ----
// Los árboles se arman en un orden que no provoca rotaciones, así que estas pruebas valen antes y
// después del paso 2. Tras rotar a mano, el árbol puede no ser AVL: no llamen a check_invariants.

void test_update_height_from_children() {
    IntMap map = make_without_rotations({4, 2, 6, 1});
    auto* one = Access::node(map, 1);
    auto* two = Access::node(map, 2);
    auto* six = Access::node(map, 6);
    auto* four = Access::node(map, 4);
    Access::update_height(map, one);
    assert(one->height == 0);
    Access::update_height(map, six);
    assert(six->height == 0);
    Access::update_height(map, two);
    assert(two->height == 1);
    Access::update_height(map, four);
    assert(four->height == 2);
    // Usa las alturas guardadas de los hijos: no baja a recalcular.
    one->height = 7;
    Access::update_height(map, two);
    assert(two->height == 8);
    one->height = 0;
    Access::update_height(map, two);
    assert(two->height == 1);
}

void test_rotate_right_at_root() {
    IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    auto* two = Access::node(map, 2);
    auto* raised = Access::rotate_right(map, Access::root(map));
    assert(raised == two);
    assert(Access::root(map) == two);
    assert(two->parent == nullptr);
    verify_links(map);
    assert((map.pre_order_keys() == Keys{2, 1, 4, 3, 6, 5, 7}));
}

void test_rotate_left_at_root() {
    IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    auto* six = Access::node(map, 6);
    auto* raised = Access::rotate_left(map, Access::root(map));
    assert(raised == six);
    assert(Access::root(map) == six);
    assert(six->parent == nullptr);
    verify_links(map);
    assert((map.pre_order_keys() == Keys{6, 4, 2, 1, 3, 5, 7}));
}

// El nodo que se rota es hijo izquierdo de alguien: hay que cambiar el enlace de ese padre.
void test_rotate_under_left_link() {
    IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    auto* four = Access::node(map, 4);
    Access::rotate_left(map, Access::node(map, 2));
    verify_links(map);
    assert(four->left == Access::node(map, 3));
    assert((map.pre_order_keys() == Keys{4, 3, 2, 1, 6, 5, 7}));
    Access::rotate_right(map, Access::node(map, 3));
    verify_links(map);
    assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 6, 5, 7}));
}

// Igual, por el enlace derecho.
void test_rotate_under_right_link() {
    IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    auto* four = Access::node(map, 4);
    Access::rotate_right(map, Access::node(map, 6));
    verify_links(map);
    assert(four->right == Access::node(map, 5));
    assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 5, 6, 7}));
    Access::rotate_left(map, Access::node(map, 5));
    verify_links(map);
    assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 6, 5, 7}));
}

// El subárbol del medio cambia de padre: es el enlace que más se olvida.
void test_rotate_moves_middle_subtree() {
    IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    auto* three = Access::node(map, 3);
    auto* four = Access::node(map, 4);
    Access::rotate_right(map, four);
    assert(four->left == three);
    assert(three->parent == four);
    IntMap other = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    auto* five = Access::node(other, 5);
    auto* other_four = Access::node(other, 4);
    Access::rotate_left(other, other_four);
    assert(other_four->right == five);
    assert(five->parent == other_four);
}

// Sin subárbol del medio: no hay padre que arreglar, y un acceso a él sería un error.
void test_rotate_without_middle_subtree() {
    IntMap left = make_without_rotations({4, 2, 6, 1});
    Access::rotate_right(left, Access::node(left, 2));
    verify_links(left);
    assert((left.pre_order_keys() == Keys{4, 1, 2, 6}));
    IntMap right = make_without_rotations({4, 2, 6, 7});
    Access::rotate_left(right, Access::node(right, 6));
    verify_links(right);
    assert((right.pre_order_keys() == Keys{4, 2, 7, 6}));
}

void test_rotate_keeps_in_order() {
    IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    Keys sorted = map.in_order_keys();
    for (int key : {4, 2, 6}) {
        Access::rotate_left(map, Access::node(map, key));
        verify_links(map);
        assert(map.in_order_keys() == sorted);
        // Tras subir su hijo derecho, key es hijo izquierdo de él: se puede deshacer.
        Access::rotate_right(map, Access::node(map, key)->parent);
        verify_links(map);
        assert(map.in_order_keys() == sorted);
        assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 6, 5, 7}));
    }
}

// Las rotaciones no tocan las alturas: la semana 12 las usa en un árbol sin ellas.
void test_rotate_leaves_heights_alone() {
    IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    int mark = 100;
    for (int key : {1, 2, 3, 4, 5, 6, 7}) {
        Access::node(map, key)->height = mark + key;
    }
    Access::rotate_left(map, Access::node(map, 4));
    Access::rotate_right(map, Access::node(map, 6));
    for (int key : {1, 2, 3, 4, 5, 6, 7}) {
        assert(Access::node(map, key)->height == mark + key);
    }
}

// Cada nodo sigue siendo el mismo, con su contenido: solo cambian los enlaces.
void test_rotate_keeps_nodes_in_place() {
    IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    int* value_of_four = map.find(4);
    int* value_of_six = map.find(6);
    Access::rotate_left(map, Access::node(map, 4));
    assert(map.find(4) == value_of_four);
    assert(map.find(6) == value_of_six);
    assert(*map.find(6) == 60);
}

void test_rotate_counts_rotations() {
    IntMap map = make_without_rotations({4, 2, 6, 1, 3, 5, 7});
    assert(map.repairs() == 0);
    Access::rotate_left(map, Access::node(map, 4));
    assert(map.rotations() == 1);
    Access::rotate_right(map, Access::node(map, 6));
    assert(map.rotations() == 2);
    assert(map.repairs() == 0);
}

// Muchas rotaciones seguidas sobre nodos elegidos al azar.
void test_rotate_random_nodes() {
    IntMap map;
    std::mt19937 random(99);
    for (int key : fibonacci_keys(8)) {
        map.insert(key, key);
    }
    Keys sorted = map.in_order_keys();
    assert(sorted.size() == 88);
    for (int i = 0; i < 2000; i++) {
        auto* node = Access::node(map, sorted[random() % sorted.size()]);
        if (random() % 2 == 0) {
            if (node->right != nullptr) {
                Access::rotate_left(map, node);
            }
        } else if (node->left != nullptr) {
            Access::rotate_right(map, node);
        }
        verify_links(map);
    }
    assert(map.in_order_keys() == sorted);
}

// ---- Paso 2: insertar con balance, y check_invariants ----

void test_check_accepts_healthy_trees() {
    IntMap empty;
    empty.check_invariants();
    IntMap map;
    for (int key = 0; key < 200; key++) {
        map.insert(key, key);
        map.check_invariants();
    }
}

void test_case_left_left() {
    IntMap map = make_map({30, 20, 10});
    verify_avl(map);
    assert((map.pre_order_keys() == Keys{20, 10, 30}));
    assert(map.rotations() == 1);
    assert(map.repairs() == 1);
}

void test_case_right_right() {
    IntMap map = make_map({10, 20, 30});
    verify_avl(map);
    assert((map.pre_order_keys() == Keys{20, 10, 30}));
    assert(map.rotations() == 1);
    assert(map.repairs() == 1);
}

void test_case_left_right() {
    IntMap map = make_map({30, 10, 20});
    verify_avl(map);
    assert((map.pre_order_keys() == Keys{20, 10, 30}));
    assert(map.rotations() == 2);
    assert(map.repairs() == 1);
}

void test_case_right_left() {
    IntMap map = make_map({10, 30, 20});
    verify_avl(map);
    assert((map.pre_order_keys() == Keys{20, 10, 30}));
    assert(map.rotations() == 2);
    assert(map.repairs() == 1);
}

void test_one_to_seven() {
    IntMap map = make_map({1, 2, 3, 4, 5, 6, 7});
    verify_avl(map);
    assert((map.pre_order_keys() == Keys{4, 2, 1, 3, 6, 5, 7}));
    assert(map.rotations() == 4);
    assert(map.repairs() == 4);
    assert(map.height() == 2);
}

// La rotación doble con subárboles de verdad: los dos hijos del nodo que sube cambian de padre.
void test_double_rotation_moves_subtrees() {
    IntMap left_right = make_map({50, 20, 70, 10, 30, 25});
    verify_avl(left_right);
    assert((left_right.pre_order_keys() == Keys{30, 20, 10, 25, 50, 70}));
    IntMap also = make_map({50, 20, 70, 10, 30, 35});
    verify_avl(also);
    assert((also.pre_order_keys() == Keys{30, 20, 10, 50, 35, 70}));
    IntMap right_left = make_map({50, 20, 80, 70, 90, 75});
    verify_avl(right_left);
    assert((right_left.pre_order_keys() == Keys{70, 50, 20, 80, 75, 90}));
    IntMap mirrored = make_map({50, 20, 80, 70, 90, 65});
    verify_avl(mirrored);
    assert((mirrored.pre_order_keys() == Keys{70, 50, 20, 65, 80, 90}));
}

// La reparación ocurre abajo: la raíz no cambia, y su enlace debe apuntar al nodo que subió.
void test_repair_below_the_root() {
    IntMap map = make_map({10, 5, 20, 30, 40});
    verify_avl(map);
    assert((map.pre_order_keys() == Keys{10, 5, 30, 20, 40}));
    IntMap other = make_map({10, 20, 5, 3, 1});
    verify_avl(other);
    assert((other.pre_order_keys() == Keys{10, 3, 1, 5, 20}));
}

void test_sorted_height_is_floor_log2() {
    IntMap up;
    IntMap down;
    for (int i = 1; i <= 3000; i++) {
        up.insert(i, i);
        down.insert(-i, i);
        assert(up.height() == floor_log2(i));
        assert(down.height() == floor_log2(i));
    }
    verify_avl(up);
    verify_avl(down);
}

// operator[] también inserta, así que también debe balancear.
void test_subscript_balances() {
    IntMap map;
    for (int i = 0; i < 1023; i++) {
        map[i] = i;
    }
    verify_avl(map);
    assert(map.height() == 9);
    assert(map[500] == 500);
}

// La referencia que entrega operator[] sigue valiendo aunque esa inserción haya rotado.
void test_subscript_reference_after_rotation() {
    IntMap map;
    map[1] = 10;
    map[2] = 20;
    int& value = map[3];
    assert(map.rotations() == 1);
    value = 30;
    assert(*map.find(3) == 30);
}

void test_repeated_key_changes_nothing() {
    IntMap map = make_map({1, 2, 3, 4, 5});
    long rotations = map.rotations();
    Keys shape = map.pre_order_keys();
    for (int key = 1; key <= 5; key++) {
        assert(!map.insert(key, 0));
    }
    assert(map.rotations() == rotations);
    assert(map.pre_order_keys() == shape);
    verify_avl(map);
}

// Basta una reparación por inserción, y una reparación son 1 o 2 rotaciones.
void test_one_repair_per_insert() {
    std::mt19937 random(2026);
    IntMap map;
    for (int i = 0; i < 20000; i++) {
        long repairs = map.repairs();
        long rotations = map.rotations();
        map.insert(static_cast<int>(random() % 1000000), i);
        assert(map.repairs() - repairs <= 1);
        assert(map.rotations() - rotations <= 2);
        assert((map.repairs() == repairs) == (map.rotations() == rotations));
    }
    verify_avl(map);
    assert(map.repairs() > 1000);
}

// Insertado por niveles, un árbol de Fibonacci no necesita ninguna rotación. Reparar de más se nota.
void test_fibonacci_needs_no_rotation() {
    for (int h = 0; h <= 12; h++) {
        std::vector<int> keys = fibonacci_keys(h);
        assert(static_cast<long>(keys.size()) == min_avl_nodes(h));
        IntMap map;
        for (int key : keys) {
            map.insert(key, key);
        }
        verify_avl(map);
        assert(map.height() == h);
        assert(map.rotations() == 0);
    }
}

void test_pointers_survive_rotations() {
    IntMap map;
    map.insert(1, 10);
    int* value = map.find(1);
    auto it = map.begin();
    for (int key = 2; key <= 100; key++) {
        map.insert(key, key * 10);
    }
    assert(map.rotations() > 0);
    assert(map.find(1) == value);
    assert(*value == 10);
    ++it;
    assert((*it).key == 2);
}

void test_iterate_after_rotations() {
    IntMap map;
    for (int key = 500; key >= 1; key--) {
        map.insert(key, key);
    }
    int expected = 1;
    for (auto [key, value] : map) {
        assert(key == expected);
        assert(value == expected);
        expected++;
    }
    assert(expected == 501);
}

void test_comparisons_follow_height() {
    AvlMap<LessOnly, int> map;
    for (int key = 0; key < 1023; key++) {
        map.insert(LessOnly{key}, key);
    }
    assert(map.height() == 9);
    for (int key : {0, 511, 1022, 300}) {
        LessOnly::comparisons = 0;
        assert(map.find(LessOnly{key}) != nullptr);
        assert(LessOnly::comparisons <= 20);
    }
}

void test_random_inserts_against_map() {
    std::mt19937 random(7);
    IntMap mine;
    std::map<int, int> model;
    for (int step = 0; step < 3000; step++) {
        int key = static_cast<int>(random() % 5000);
        assert(mine.insert(key, step) == model.insert({key, step}).second);
        verify_avl(mine);
        mine.check_invariants();
    }
    assert_same_as_model(mine, model);
}

// Cada una de estas daña un árbol sano. check_invariants debe detener el programa.
// test_lab.py exige ver "sano" y luego un fallo, así que no pasan sin check_invariants.
// Si no se detiene, se sale sin destruir: el fallo no debe venir del destructor sobre un árbol roto.
void healthy(const IntMap& map) {
    map.check_invariants();
    std::cout << "sano" << std::endl;
}

void test_broken_deep_order() {
    IntMap map = make_map({5, 3, 8, 4});
    healthy(map);
    // 7 es mayor que su padre 3, como debe ser, pero está a la izquierda del 5.
    Access::root(map)->left->right->key = 7;
    map.check_invariants();
    std::_Exit(0);
}

void test_broken_parent() {
    IntMap map = make_map({5, 3, 8, 4});
    healthy(map);
    auto* root = Access::root(map);
    root->left->right->parent = root;
    map.check_invariants();
    std::_Exit(0);
}

void test_broken_size() {
    IntMap map = make_map({5, 3, 8});
    healthy(map);
    Access::add_to_size(map);
    map.check_invariants();
    std::_Exit(0);
}

// La altura guardada de una hoja está mal.
void test_broken_stale_leaf_height() {
    IntMap map = make_map({5, 3, 8, 4});
    healthy(map);
    Access::node(map, 8)->height = 1;
    map.check_invariants();
    std::_Exit(0);
}

// La altura de un nodo interno está mal, y sin embargo la diferencia con su hermano es válida.
void test_broken_stale_inner_height() {
    IntMap map = make_map({5, 3, 8, 1, 4, 7, 9});
    healthy(map);
    Access::node(map, 3)->height = 0;
    map.check_invariants();
    std::_Exit(0);
}

// Solo la altura de la raíz está mal: nadie por encima la usa para notar el error.
void test_broken_root_height() {
    IntMap map = make_map({5, 3, 8});
    healthy(map);
    Access::root(map)->height = 5;
    map.check_invariants();
    std::_Exit(0);
}

// Todas las alturas son correctas y el árbol está desbalanceado: rompe solo la condición AVL.
void test_broken_real_imbalance() {
    IntMap map = make_map({2, 1, 4, 3, 5});
    healthy(map);
    // Queda 2(1,3(_,4(_,5))): el 3 y la raíz tienen balance -2. Se ponen bien todas las alturas.
    Access::rotate_right(map, Access::node(map, 4));
    for (int key : {5, 4, 3, 1, 2}) {
        Access::update_height(map, Access::node(map, key));
    }
    map.check_invariants();
    std::_Exit(0);
}

// ---- Paso 3: borrar con balance ----

void test_erase_needs_single_rotation() {
    IntMap right = make_map({5, 3, 7, 8});
    assert(right.erase(3));
    verify_avl(right);
    assert((right.pre_order_keys() == Keys{7, 5, 8}));
    IntMap left = make_map({5, 3, 7, 2});
    assert(left.erase(7));
    verify_avl(left);
    assert((left.pre_order_keys() == Keys{3, 2, 5}));
    assert(left.repairs() == 1);
}

void test_erase_needs_double_rotation() {
    IntMap right_left = make_map({5, 2, 8, 7});
    assert(right_left.erase(2));
    verify_avl(right_left);
    assert((right_left.pre_order_keys() == Keys{7, 5, 8}));
    assert(right_left.rotations() == 2);
    IntMap left_right = make_map({5, 2, 7, 3});
    assert(left_right.erase(7));
    verify_avl(left_right);
    assert((left_right.pre_order_keys() == Keys{3, 2, 5}));
    assert(left_right.rotations() == 2);
}

// El hijo pesado tiene balance 0, que solo pasa al borrar: va la rotación simple.
void test_erase_heavy_child_with_zero_balance() {
    IntMap left = make_without_rotations({4, 2, 5, 1, 3});
    assert(left.erase(5));
    verify_avl(left);
    assert((left.pre_order_keys() == Keys{2, 1, 4, 3}));
    assert(left.rotations() == 1);
    IntMap right = make_without_rotations({2, 1, 4, 3, 5});
    assert(right.erase(1));
    verify_avl(right);
    assert((right.pre_order_keys() == Keys{4, 2, 3, 5}));
    assert(right.rotations() == 1);
}

// Igual, con nietos de alturas distintas: aquí una rotación doble deja el árbol desbalanceado.
void test_erase_zero_balance_uneven_grandchildren() {
    IntMap right = make_without_rotations({5, 2, 10, 1, 8, 12, 7, 13});
    assert(right.erase(1));
    verify_avl(right);
    assert((right.pre_order_keys() == Keys{10, 5, 2, 8, 7, 12, 13}));
    IntMap left = make_without_rotations({9, 5, 12, 2, 6, 13, 1, 7});
    assert(left.erase(13));
    verify_avl(left);
    assert((left.pre_order_keys() == Keys{5, 2, 1, 9, 6, 7, 12}));
}

// La reparación debe empezar donde salió de verdad el nodo: el padre del sucesor.
void test_erase_two_children_repairs_from_successor() {
    IntMap map = make_map({5, 3, 8, 2, 4, 9, 1});
    assert(map.erase(5));
    verify_avl(map);
    assert((map.pre_order_keys() == Keys{3, 2, 1, 8, 4, 9}));
    assert(*map.find(8) == 80);
    assert(map.find(5) == nullptr);
    IntMap deep = make_map({8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15, 16});
    assert(deep.erase(8));
    verify_avl(deep);
    assert(*deep.find(9) == 90);
    assert(deep.size() == 15);
}

void test_erase_until_empty() {
    IntMap map = make_map({1, 2, 3, 4, 5, 6, 7, 8, 9});
    for (int key = 9; key >= 1; key--) {
        int top = map.pre_order_keys().front();
        assert(map.erase(top));
        verify_avl(map);
        map.check_invariants();
        assert(map.find(top) == nullptr);
    }
    assert(map.empty());
    assert(map.height() == -1);
    map.insert(1, 1);
    verify_avl(map);
}

// Al borrar puede hacer falta reparar en todos los antepasados. No basta una, como al insertar.
void test_erase_can_repair_many_levels() {
    for (int h = 2; h <= 16; h++) {
        std::vector<int> keys = fibonacci_keys(h);
        IntMap map;
        for (int key : keys) {
            map.insert(key, key);
        }
        assert(map.rotations() == 0);
        assert(map.erase(static_cast<int>(keys.size())));
        verify_avl(map);
        assert(map.repairs() == h / 2);
        assert(map.height() == h - 1);
    }
}

// Con el árbol ya sano no se repara nada más, y nunca se pasa de h / 2 reparaciones.
void test_erase_repairs_are_bounded() {
    std::mt19937 random(31);
    IntMap map;
    Keys keys;
    for (int key = 0; key < 3000; key++) {
        keys.push_back(key);
    }
    std::shuffle(keys.begin(), keys.end(), random);
    for (int key : keys) {
        map.insert(key, key);
    }
    std::shuffle(keys.begin(), keys.end(), random);
    for (int key : keys) {
        int height = map.height();
        long repairs = map.repairs();
        assert(map.erase(key));
        long done = map.repairs() - repairs;
        assert(done <= height / 2);
        if (key % 50 == 0) {
            verify_avl(map);
        }
    }
    assert(map.empty());
}

void test_random_against_map_with_balance() {
    std::mt19937 random(20261111);
    IntMap mine;
    std::map<int, int> model;
    for (int step = 0; step < 6000; step++) {
        int key = static_cast<int>(random() % 200);
        int action = static_cast<int>(random() % 10);
        if (action < 5) {
            assert(mine.insert(key, step) == model.insert({key, step}).second);
        } else if (action < 9) {
            assert(mine.erase(key) == (model.erase(key) == 1));
        } else {
            const int* found = mine.find(key);
            auto position = model.find(key);
            assert((found != nullptr) == (position != model.end()));
            assert(found == nullptr || *found == position->second);
        }
        verify_avl(mine);
        mine.check_invariants();
        assert(mine.size() == model.size());
        if (step % 50 == 0) {
            assert_same_as_model(mine, model);
        }
    }
    assert_same_as_model(mine, model);
}

void test_random_strings_with_balance() {
    std::mt19937 random(11);
    auto word = [&] {
        std::string text;
        for (int i = 0; i < 3; i++) {
            text += static_cast<char>('a' + random() % 6);
        }
        return text;
    };
    AvlMap<std::string, std::string> mine;
    std::map<std::string, std::string> model;
    for (int step = 0; step < 3000; step++) {
        std::string key = word();
        if (step % 3 != 2) {
            std::string value = word() + "valor largo para el heap";
            assert(mine.insert(key, value) == model.insert({key, value}).second);
        } else {
            assert(mine.erase(key) == (model.erase(key) == 1));
        }
        verify_avl(mine);
    }
    assert_same_as_model(mine, model);
}

// La copia lleva las alturas: copiar un nodo copia todos sus campos.
void test_copy_keeps_heights() {
    std::mt19937 random(5);
    IntMap mine;
    for (int step = 0; step < 1000; step++) {
        int key = static_cast<int>(random() % 100);
        if (step % 3 == 0) {
            mine.erase(key);
        } else {
            mine.insert(key, key);
        }
    }
    IntMap copy(mine);
    verify_avl(copy);
    copy.check_invariants();
    assert(copy.pre_order_keys() == mine.pre_order_keys());
    for (int key = 100; key < 300; key++) {
        copy.insert(key, key);
        verify_avl(copy);
    }
    verify_avl(mine);
}

// La forma exacta tras una serie de operaciones: sucesor al borrar, y rotación simple con balance 0.
// La esperada sale del AvlSet de los apuntes, que es otra implementación.
void test_exact_shape_after_script() {
    std::mt19937 random(424242);
    IntMap map;
    for (int step = 0; step < 300; step++) {
        int key = static_cast<int>(random() % 64);
        if (random() % 3 == 0) {
            map.erase(key);
        } else {
            map.insert(key, key);
        }
    }
    verify_avl(map);
    Keys expected{38, 23, 11, 3, 1, 0, 2, 7, 8, 17, 13, 12, 16, 19, 18, 20, 22, 28, 25, 24, 27, 31, 30, 35, 36, 48, 43, 40, 39, 41, 46, 44, 45, 47, 56, 52, 50, 49, 51, 55, 53, 60, 58, 62, 61, 63};
    assert(map.pre_order_keys() == expected);
}

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(in_order_is_sorted), 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(erase_absent),
    TEST(random_against_map_links), TEST(queries_still_work),
    TEST(update_height_from_children), 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_keeps_in_order), TEST(rotate_leaves_heights_alone),
    TEST(rotate_keeps_nodes_in_place), TEST(rotate_counts_rotations), TEST(rotate_random_nodes),
    TEST(check_accepts_healthy_trees), TEST(case_left_left), TEST(case_right_right), TEST(case_left_right),
    TEST(case_right_left), TEST(one_to_seven), TEST(double_rotation_moves_subtrees), TEST(repair_below_the_root),
    TEST(sorted_height_is_floor_log2), TEST(subscript_balances), TEST(subscript_reference_after_rotation),
    TEST(repeated_key_changes_nothing), TEST(one_repair_per_insert), TEST(fibonacci_needs_no_rotation),
    TEST(pointers_survive_rotations), TEST(iterate_after_rotations), TEST(comparisons_follow_height),
    TEST(random_inserts_against_map), TEST(broken_deep_order), TEST(broken_parent), TEST(broken_size),
    TEST(broken_stale_leaf_height), TEST(broken_stale_inner_height), TEST(broken_root_height),
    TEST(broken_real_imbalance),
    TEST(erase_needs_single_rotation), TEST(erase_needs_double_rotation), TEST(erase_heavy_child_with_zero_balance),
    TEST(erase_zero_balance_uneven_grandchildren), TEST(erase_two_children_repairs_from_successor),
    TEST(erase_until_empty), TEST(erase_can_repair_many_levels), TEST(erase_repairs_are_bounded),
    TEST(random_against_map_with_balance), TEST(random_strings_with_balance), TEST(copy_keeps_heights),
    TEST(exact_shape_after_script),
};

}  // 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;
}