// 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 "bst_map.h"

// Permite a las pruebas dañar un árbol, para ver si check_invariants lo nota.
struct BstMapTestAccess {
    template <typename Map>
    static auto* root(Map& map) { return map.root_; }
    template <typename Map>
    static void add_to_size(Map& map) { map.size_++; }
};

namespace {

using IntMap = BstMap<int, 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 std::vector<int>& keys) {
    IntMap map;
    for (int key : keys) {
        map.insert(key, key * 10);
    }
    return map;
}

// Claves en un orden que deja un árbol perfecto si se insertan en orden: la raíz primero.
void add_balanced(std::vector<int>& keys, int low, int high) {
    if (low > high) {
        return;
    }
    int middle = low + (high - low) / 2;
    keys.push_back(middle);
    add_balanced(keys, low, middle - 1);
    add_balanced(keys, middle + 1, high);
}

template <typename K, typename V>
void assert_same(const BstMap<K, V>& mine, const std::map<K, V>& model) {
    mine.check_invariants();
    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);
}

// ---- Sesión 1: insertar, buscar y recorrer ----

void test_new_is_empty() {
    IntMap map;
    map.check_invariants();
    assert(map.empty());
    assert(map.size() == 0);
    assert(map.height() == -1);
    assert(map.find(1) == nullptr);
    assert(map.in_order_keys().empty());
}

void test_insert_and_find() {
    IntMap map = make_map({5, 3, 8, 1, 4, 7});
    map.check_invariants();
    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);
    map.check_invariants();
}

void test_find_lets_edit_value() {
    IntMap map = make_map({2, 1, 3});
    *map.find(1) = 77;
    const IntMap& reader = map;
    assert(*reader.find(1) == 77);
    assert(reader.find(9) == nullptr);
}

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);
    map.check_invariants();
}

void test_in_order_is_sorted() {
    IntMap map = make_map({5, 3, 8, 1, 4, 7});
    assert((map.in_order_keys() == std::vector<int>{1, 3, 4, 5, 7, 8}));
}

void test_shape_follows_insertion_order() {
    IntMap map = make_map({5, 3, 8, 1, 4, 7});
    assert((map.pre_order_keys() == std::vector<int>{5, 3, 1, 4, 8, 7}));
    assert(map.height() == 2);
}

void test_sorted_keys_make_a_chain() {
    IntMap map;
    for (int i = 0; i < 500; i++) {
        map.insert(i, i);
        assert(map.height() == i);
    }
    map.check_invariants();
}

void test_comparisons_follow_height() {
    using Map = BstMap<LessOnly, int>;
    std::vector<int> keys;
    add_balanced(keys, 0, 1022);
    Map map;
    for (int key : keys) {
        map.insert(LessOnly{key}, key);
    }
    assert(map.height() == 9);
    // Bajar cuesta como máximo dos comparaciones por nivel, en find y en insert.
    for (int key : {0, 511, 1022, 300}) {
        LessOnly::comparisons = 0;
        assert(map.find(LessOnly{key}) != nullptr);
        assert(LessOnly::comparisons <= 20);
        LessOnly::comparisons = 0;
        assert(!map.insert(LessOnly{key}, 0));
        assert(LessOnly::comparisons <= 20);
    }
    LessOnly::comparisons = 0;
    assert(map.find(LessOnly{-1}) == nullptr);
    assert(LessOnly::comparisons <= 20);
}

void test_only_needs_less_than() {
    BstMap<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);
    map.check_invariants();
}

void test_strings_as_keys() {
    BstMap<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"}));
    map.check_invariants();
}

void test_no_objects_left_behind() {
    {
        BstMap<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);
    copy.check_invariants();
    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;
    assigned.check_invariants();
    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;
    map.check_invariants();
    assert(map.size() == 3);
    map = std::move(alias);
    map.check_invariants();
    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);
    target.check_invariants();
    source.check_invariants();
    assert(source.empty());
    source.insert(1, 1);
    assert(source.size() == 1);
    IntMap other;
    other = std::move(target);
    assert(other.size() == 3);
    other.check_invariants();
}

// Con un tope bajo de pila, un destructor recursivo se queda sin ella. test_lab.py pone el tope.
void test_destructor_without_recursion() {
    IntMap map;
    for (int i = 0; i < 6000; i++) {
        map.insert(i, i);
    }
    assert(map.height() == 5999);
}

// 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 test_broken_deep_order() {
    IntMap map = make_map({5, 3, 4});
    map.check_invariants();
    std::cout << "sano" << std::endl;
    // 7 es mayor que su padre 3, como debe ser, pero está a la izquierda del 5.
    BstMapTestAccess::root(map)->left->right->key = 7;
    map.check_invariants();
    std::_Exit(0);
}

void test_broken_repeated_key() {
    IntMap map = make_map({5, 8});
    map.check_invariants();
    std::cout << "sano" << std::endl;
    BstMapTestAccess::root(map)->right->key = 5;
    map.check_invariants();
    std::_Exit(0);
}

void test_broken_parent() {
    IntMap map = make_map({5, 3, 8, 4});
    map.check_invariants();
    std::cout << "sano" << std::endl;
    auto* root = BstMapTestAccess::root(map);
    root->left->right->parent = root;
    map.check_invariants();
    std::_Exit(0);
}

void test_broken_size() {
    IntMap map = make_map({5, 3, 8});
    map.check_invariants();
    std::cout << "sano" << std::endl;
    BstMapTestAccess::add_to_size(map);
    map.check_invariants();
    std::_Exit(0);
}

// ---- Sesión 1: borrar ----

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));
    map.check_invariants();
}

void test_erase_leaf() {
    IntMap map = make_map({5, 3, 8});
    assert(map.erase(3));
    map.check_invariants();
    assert((map.pre_order_keys() == std::vector<int>{5, 8}));
    assert(map.find(3) == nullptr);
    assert(map.size() == 2);
}

void test_erase_one_child() {
    IntMap left = make_map({5, 3, 1, 8});
    assert(left.erase(3));
    left.check_invariants();
    assert((left.pre_order_keys() == std::vector<int>{5, 1, 8}));
    IntMap right = make_map({5, 3, 4, 8});
    assert(right.erase(3));
    right.check_invariants();
    assert((right.pre_order_keys() == std::vector<int>{5, 4, 8}));
}

void test_erase_root_with_one_child() {
    IntMap map = make_map({5, 8, 9});
    assert(map.erase(5));
    map.check_invariants();
    assert((map.pre_order_keys() == std::vector<int>{8, 9}));
    assert(map.erase(8));
    assert(map.erase(9));
    map.check_invariants();
    assert(map.empty());
}

void test_erase_two_children_uses_successor() {
    IntMap map = make_map({5, 3, 8, 1, 4, 7});
    assert(map.erase(5));
    map.check_invariants();
    assert((map.pre_order_keys() == std::vector<int>{7, 3, 1, 4, 8}));
    assert(*map.find(7) == 70);
    assert(map.find(5) == nullptr);
}

void test_erase_successor_is_right_child() {
    IntMap map = make_map({5, 3, 8, 9});
    assert(map.erase(5));
    map.check_invariants();
    assert((map.pre_order_keys() == std::vector<int>{8, 3, 9}));
    assert(*map.find(8) == 80);
}

void test_erase_successor_with_right_child() {
    IntMap map = make_map({2, 1, 6, 4, 7, 5});
    assert(map.erase(2));
    map.check_invariants();
    assert((map.pre_order_keys() == std::vector<int>{4, 1, 6, 5, 7}));
    assert(*map.find(4) == 40);
    assert(*map.find(5) == 50);
}

void test_erase_releases_objects() {
    {
        BstMap<int, Live> map;
        for (int i = 0; i < 100; i++) {
            map.insert((i * 37) % 101, Live(i));
        }
        for (int i = 0; i < 100; i += 2) {
            assert(map.erase((i * 37) % 101));
            map.check_invariants();
        }
        assert(Live::count == 50);
    }
    assert(Live::count == 0);
}

void test_random_against_map() {
    std::mt19937 random(20261110);
    std::uniform_int_distribution<int> key_of(0, 199);
    std::uniform_int_distribution<int> action_of(0, 9);
    IntMap mine;
    std::map<int, int> model;
    for (int step = 0; step < 6000; step++) {
        int key = key_of(random);
        int action = action_of(random);
        if (action < 5) {
            auto [position, added] = model.insert({key, step});
            (void)position;
            assert(mine.insert(key, step) == added);
        } 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);
        }
        mine.check_invariants();
        assert(mine.size() == model.size());
        if (step % 50 == 0) {
            assert_same(mine, model);
        }
    }
    assert_same(mine, model);
}

void test_random_strings() {
    std::mt19937 random(11);
    std::uniform_int_distribution<int> letter(0, 5);
    auto word = [&] {
        std::string text;
        for (int i = 0; i < 3; i++) {
            text += static_cast<char>('a' + letter(random));
        }
        return text;
    };
    BstMap<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) {
            assert(mine.insert(key, word() + "valor largo para el heap") == model.insert({key, ""}).second);
            model[key] = *mine.find(key);
        } else {
            assert(mine.erase(key) == (model.erase(key) == 1));
        }
        mine.check_invariants();
    }
    assert_same(mine, model);
}

void test_copy_after_random_operations() {
    std::mt19937 random(5);
    std::uniform_int_distribution<int> key_of(0, 99);
    IntMap mine;
    for (int step = 0; step < 1000; step++) {
        int key = key_of(random);
        if (step % 3 == 0) {
            mine.erase(key);
        } else {
            mine.insert(key, key);
        }
    }
    IntMap copy(mine);
    copy.check_invariants();
    assert(copy.pre_order_keys() == mine.pre_order_keys());
}

// ---- Sesión 2: consultas ordenadas ----

void test_min_max() {
    IntMap map;
    assert(map.min_key() == nullptr);
    assert(map.max_key() == nullptr);
    map = make_map({5, 3, 8, 1, 4, 7});
    assert(*map.min_key() == 1);
    assert(*map.max_key() == 8);
}

void test_floor_ceiling_cases() {
    IntMap map = make_map({20, 10, 30, 5, 15, 25, 35});
    assert(map.floor(4) == nullptr);
    assert(*map.floor(5) == 5);
    assert(*map.floor(14) == 10);
    assert(*map.floor(26) == 25);
    assert(*map.floor(99) == 35);
    assert(map.ceiling(36) == nullptr);
    assert(*map.ceiling(35) == 35);
    assert(*map.ceiling(16) == 20);
    assert(*map.ceiling(11) == 15);
    assert(*map.ceiling(-1) == 5);
    IntMap empty;
    assert(empty.floor(1) == nullptr);
    assert(empty.ceiling(1) == nullptr);
}

// Con std::map, techo es lower_bound, y piso es el anterior a upper_bound.
void test_floor_ceiling_random() {
    std::mt19937 random(77);
    std::uniform_int_distribution<int> key_of(0, 999);
    IntMap mine;
    std::map<int, int> model;
    for (int i = 0; i < 300; i++) {
        int key = key_of(random);
        mine.insert(key, key);
        model.insert({key, key});
    }
    for (int key = -1; key <= 1000; key++) {
        auto at_or_after = model.lower_bound(key);
        const int* ceiling = mine.ceiling(key);
        assert((ceiling == nullptr) == (at_or_after == model.end()));
        assert(ceiling == nullptr || *ceiling == at_or_after->first);
        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)->first);
    }
}

void test_range_is_half_open() {
    IntMap map = make_map({5, 3, 8, 1, 4, 7});
    auto pairs = map.range(3, 7);
    assert((pairs == std::vector<std::pair<int, int>>{{3, 30}, {4, 40}, {5, 50}}));
    assert(map.range(6, 7).empty());
    assert(map.range(7, 3).empty());
    assert(map.range(4, 4).empty());
    assert(map.range(0, 100).size() == 6);
    IntMap empty;
    assert(empty.range(0, 100).empty());
}

void test_range_random() {
    std::mt19937 random(123);
    std::uniform_int_distribution<int> key_of(0, 500);
    IntMap mine;
    std::map<int, int> model;
    for (int i = 0; i < 200; i++) {
        int key = key_of(random);
        mine.insert(key, i);
        model.insert({key, i});
    }
    for (int i = 0; i < 500; i++) {
        int low = key_of(random);
        int high = key_of(random);
        std::vector<std::pair<int, int>> expected;
        if (low <= high) {
            for (auto it = model.lower_bound(low); it != model.lower_bound(high); ++it) {
                expected.push_back(*it);
            }
        }
        assert(mine.range(low, high) == expected);
    }
}

void test_range_does_not_walk_everything() {
    using Map = BstMap<LessOnly, int>;
    std::vector<int> keys;
    add_balanced(keys, 0, 4094);
    Map map;
    for (int key : keys) {
        map.insert(LessOnly{key}, key);
    }
    LessOnly::comparisons = 0;
    auto pairs = map.range(LessOnly{1000}, LessOnly{1005});
    assert(pairs.size() == 5);
    // Altura 11: un recorrido completo haría al menos 4095 comparaciones.
    assert(LessOnly::comparisons <= 100);
}

void test_iterator_in_order() {
    IntMap map = make_map({5, 3, 8, 1, 4, 7});
    std::vector<int> keys;
    std::vector<int> values;
    for (auto [key, value] : map) {
        keys.push_back(key);
        values.push_back(value);
    }
    assert((keys == std::vector<int>{1, 3, 4, 5, 7, 8}));
    assert((values == std::vector<int>{10, 30, 40, 50, 70, 80}));
}

void test_iterator_edits_value() {
    IntMap map = make_map({2, 1, 3});
    for (auto [key, value] : map) {
        value = key + 1;
    }
    assert(*map.find(1) == 2);
    assert(*map.find(3) == 4);
}

void test_const_iterator() {
    const IntMap map = make_map({2, 1, 3});
    int sum = 0;
    for (const auto& entry : map) {
        sum += entry.key + entry.value;
    }
    assert(sum == 66);
    auto entry = *map.begin();
    static_assert(std::is_const_v<std::remove_reference_t<decltype(entry.value)>>);
}

void test_iterator_of_empty_map() {
    IntMap map;
    assert(map.begin() == map.end());
    assert(!(map.begin() != map.end()));
}

// El iterador solo guarda su nodo, así que una inserción no lo invalida, igual que en std::map.
void test_iterator_survives_insert() {
    IntMap map = make_map({10, 20, 30});
    auto it = map.begin();
    assert((*it).key == 10);
    map.insert(15, 150);
    map.insert(5, 50);
    ++it;
    assert((*it).key == 15);
}

void test_iterator_random() {
    std::mt19937 random(9);
    std::uniform_int_distribution<int> key_of(0, 2000);
    IntMap mine;
    std::map<int, int> model;
    for (int i = 0; i < 1000; i++) {
        int key = key_of(random);
        if (i % 4 == 3) {
            mine.erase(key);
            model.erase(key);
        } else {
            mine.insert(key, i);
            model.insert({key, i});
        }
    }
    auto expected = model.begin();
    for (auto [key, value] : mine) {
        assert(expected != model.end());
        assert(key == expected->first);
        assert(value == expected->second);
        ++expected;
    }
    assert(expected == model.end());
}

// Recorrer una cadena no debe hacer recursión ni volver a bajar desde la raíz cada vez.
void test_iterate_chain_comparisons() {
    BstMap<LessOnly, int> map;
    for (int i = 0; i < 2000; i++) {
        map.insert(LessOnly{i}, i);
    }
    LessOnly::comparisons = 0;
    long sum = 0;
    for (auto [key, value] : map) {
        (void)key;
        sum += value;
    }
    assert(sum == 1999L * 2000 / 2);
    assert(LessOnly::comparisons == 0);
}

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

const Test tests[] = {
    {"new_is_empty", test_new_is_empty},
    {"insert_and_find", test_insert_and_find},
    {"insert_does_not_overwrite", test_insert_does_not_overwrite},
    {"find_lets_edit_value", test_find_lets_edit_value},
    {"subscript_operator", test_subscript_operator},
    {"in_order_is_sorted", test_in_order_is_sorted},
    {"shape_follows_insertion_order", test_shape_follows_insertion_order},
    {"sorted_keys_make_a_chain", test_sorted_keys_make_a_chain},
    {"comparisons_follow_height", test_comparisons_follow_height},
    {"only_needs_less_than", test_only_needs_less_than},
    {"strings_as_keys", test_strings_as_keys},
    {"no_objects_left_behind", test_no_objects_left_behind},
    {"copy_is_independent", test_copy_is_independent},
    {"self_assignment", test_self_assignment},
    {"move_leaves_empty_and_usable", test_move_leaves_empty_and_usable},
    {"destructor_without_recursion", test_destructor_without_recursion},
    {"broken_deep_order", test_broken_deep_order},
    {"broken_repeated_key", test_broken_repeated_key},
    {"broken_parent", test_broken_parent},
    {"broken_size", test_broken_size},
    {"erase_absent", test_erase_absent},
    {"erase_leaf", test_erase_leaf},
    {"erase_one_child", test_erase_one_child},
    {"erase_root_with_one_child", test_erase_root_with_one_child},
    {"erase_two_children_uses_successor", test_erase_two_children_uses_successor},
    {"erase_successor_is_right_child", test_erase_successor_is_right_child},
    {"erase_successor_with_right_child", test_erase_successor_with_right_child},
    {"erase_releases_objects", test_erase_releases_objects},
    {"random_against_map", test_random_against_map},
    {"random_strings", test_random_strings},
    {"copy_after_random_operations", test_copy_after_random_operations},
    {"min_max", test_min_max},
    {"floor_ceiling_cases", test_floor_ceiling_cases},
    {"floor_ceiling_random", test_floor_ceiling_random},
    {"range_is_half_open", test_range_is_half_open},
    {"range_random", test_range_random},
    {"range_does_not_walk_everything", test_range_does_not_walk_everything},
    {"iterator_in_order", test_iterator_in_order},
    {"iterator_edits_value", test_iterator_edits_value},
    {"const_iterator", test_const_iterator},
    {"iterator_of_empty_map", test_iterator_of_empty_map},
    {"iterator_survives_insert", test_iterator_survives_insert},
    {"iterator_random", test_iterator_random},
    {"iterate_chain_comparisons", test_iterate_chain_comparisons},
};

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