// Mapa ordenado sobre un árbol rojinegro clásico, con puntero al padre.
// El mapa de búsqueda ya viene completo y funcionando, con un campo color en cada nodo.
// Ustedes completan lo marcado con Paso.
#ifndef RED_BLACK_MAP_H
#define RED_BLACK_MAP_H

#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

#include "not_implemented.h"

// Invariantes:
// - En cada nodo, todas las claves del subárbol izquierdo son menores que la suya, y todas las
//   del derecho son mayores. No hay claves repetidas.
// - Si x tiene hijo h, entonces h->parent == x. La raíz tiene padre nulo.
// - El árbol tiene exactamente size_ nodos, y root_ es nulo si y solo si size_ == 0.
// Y las cinco propiedades de un árbol rojinegro:
// 1. Cada nodo es rojo o negro.
// 2. La raíz es negra.
// 3. Las hojas nulas son negras: un puntero nulo cuenta como negro, sin ocupar memoria.
// 4. Un nodo rojo solo tiene hijos negros.
// 5. Todo camino desde un nodo hasta sus hojas nulas pasa por la misma cantidad de negros.
//
// K solo necesita operator<, y K y V se copian y se asignan. operator[] además pide V{}.
//
// Ownership: el mapa es owner de todos sus nodos. Los punteros de find, floor, ceiling, min_key y
// max_key, y los iteradores, siguen válidos al insertar: una rotación cambia enlaces y no mueve
// el contenido de ningún nodo. Este mapa no ofrece borrar.
template <typename K, typename V>
class RedBlackMap {
    enum class Color { red, black };

    struct Node {
        K key;
        V value;
        Node* parent = nullptr;
        Node* left = nullptr;
        Node* right = nullptr;
        Color color = Color::red;
    };

    friend struct RedBlackMapTestAccess;

public:
    // Lo que entrega un iterador. W es V, o const V si el mapa es const.
    template <typename W>
    struct Entry {
        const K& key;
        W& value;
    };

    template <typename W>
    class Iter {
    public:
        Entry<W> operator*() const { return {node_->key, node_->value}; }
        Iter& operator++() {
            node_ = successor(node_);
            return *this;
        }
        bool operator==(const Iter& other) const { return node_ == other.node_; }
        bool operator!=(const Iter& other) const { return node_ != other.node_; }

    private:
        friend class RedBlackMap;
        explicit Iter(Node* node) : node_(node) {}
        Node* node_;
    };

    using iterator = Iter<V>;
    using const_iterator = Iter<const V>;

    RedBlackMap() = default;

    // Postorden sin recursión ni memoria extra: el puntero al padre permite volver.
    ~RedBlackMap() {
        Node* node = root_;
        while (node != nullptr) {
            if (node->left != nullptr) {
                node = node->left;
            } else if (node->right != nullptr) {
                node = node->right;
            } else {
                Node* parent = node->parent;
                if (parent != nullptr) {
                    if (parent->left == node) {
                        parent->left = nullptr;
                    } else {
                        parent->right = nullptr;
                    }
                }
                delete node;
                node = parent;
            }
        }
    }

    // Delega en el constructor por defecto: si una copia lanza una excepción, el objeto ya
    // existe, así que corre el destructor y libera lo copiado hasta ahí.
    RedBlackMap(const RedBlackMap& other) : RedBlackMap() {
        copy_nodes_from(other);
    }

    RedBlackMap& operator=(const RedBlackMap& other) {
        RedBlackMap copy(other);
        swap(copy);
        return *this;
    }

    RedBlackMap(RedBlackMap&& other) noexcept
        : root_(std::exchange(other.root_, nullptr)),
          size_(std::exchange(other.size_, 0)),
          rotations_(std::exchange(other.rotations_, 0)),
          recolors_(std::exchange(other.recolors_, 0)) {}

    RedBlackMap& operator=(RedBlackMap&& other) noexcept {
        RedBlackMap moved(std::move(other));
        swap(moved);
        return *this;
    }

    void swap(RedBlackMap& other) noexcept {
        std::swap(root_, other.root_);
        std::swap(size_, other.size_);
        std::swap(rotations_, other.rotations_);
        std::swap(recolors_, other.recolors_);
    }

    std::size_t size() const { return size_; }
    bool empty() const { return size_ == 0; }

    // Rotaciones que hizo este mapa, y cuántas veces aplicó el caso del tío rojo.
    // Una copia empieza en cero, y un movimiento se las lleva.
    long rotations() const { return rotations_; }
    long recolors() const { return recolors_; }

    // Como std::map::insert: si la clave ya estaba, no cambia su valor y devuelve false.
    bool insert(const K& key, const V& value) {
        return insert_node(key, value).second;
    }

    // Como en std::map: si la clave no está, la inserta con V{}.
    V& operator[](const K& key) {
        return insert_node(key, V{}).first->value;
    }

    V* find(const K& key) {
        Node* node = find_node(key);
        return node != nullptr ? &node->value : nullptr;
    }

    const V* find(const K& key) const {
        const Node* node = find_node(key);
        return node != nullptr ? &node->value : nullptr;
    }

    const K* min_key() const {
        return root_ != nullptr ? &min_node(root_)->key : nullptr;
    }

    const K* max_key() const {
        if (root_ == nullptr) {
            return nullptr;
        }
        const Node* node = root_;
        while (node->right != nullptr) {
            node = node->right;
        }
        return &node->key;
    }

    // Puntero a la mayor clave <= key; nulo si no hay.
    const K* floor(const K& key) const {
        const Node* node = root_;
        const K* candidate = nullptr;
        while (node != nullptr) {
            if (key < node->key) {
                node = node->left;
            } else if (node->key < key) {
                candidate = &node->key;
                node = node->right;
            } else {
                return &node->key;
            }
        }
        return candidate;
    }

    // Puntero a la menor clave >= key; nulo si no hay.
    const K* ceiling(const K& key) const {
        const Node* node = ceiling_node(key);
        return node != nullptr ? &node->key : nullptr;
    }

    // Los pares con clave en [low, high), en orden. Cuesta O(altura + cantidad de pares).
    std::vector<std::pair<K, V>> range(const K& low, const K& high) const {
        std::vector<std::pair<K, V>> pairs;
        for (Node* node = ceiling_node(low); node != nullptr && node->key < high; node = successor(node)) {
            pairs.emplace_back(node->key, node->value);
        }
        return pairs;
    }

    iterator begin() { return iterator(root_ != nullptr ? min_node(root_) : nullptr); }
    iterator end() { return iterator(nullptr); }
    const_iterator begin() const { return const_iterator(root_ != nullptr ? min_node(root_) : nullptr); }
    const_iterator end() const { return const_iterator(nullptr); }

    // Las claves en orden.
    std::vector<K> in_order_keys() const {
        std::vector<K> keys;
        keys.reserve(size_);
        if (root_ != nullptr) {
            for (Node* node = min_node(root_); node != nullptr; node = successor(node)) {
                keys.push_back(node->key);
            }
        }
        return keys;
    }

    // Las claves en preorden, que fijan la forma del árbol. Con pila propia, sin recursión.
    std::vector<K> pre_order_keys() const {
        std::vector<K> keys;
        keys.reserve(size_);
        std::vector<const Node*> pending;
        if (root_ != nullptr) {
            pending.push_back(root_);
        }
        while (!pending.empty()) {
            const Node* node = pending.back();
            pending.pop_back();
            keys.push_back(node->key);
            if (node->right != nullptr) {
                pending.push_back(node->right);
            }
            if (node->left != nullptr) {
                pending.push_back(node->left);
            }
        }
        return keys;
    }

    // Altura: aristas del camino más largo desde la raíz. Vacío: -1. Un solo nodo: 0.
    int height() const {
        int levels = 0;
        std::vector<const Node*> level;
        if (root_ != nullptr) {
            level.push_back(root_);
        }
        while (!level.empty()) {
            std::vector<const Node*> next;
            for (const Node* node : level) {
                if (node->left != nullptr) {
                    next.push_back(node->left);
                }
                if (node->right != nullptr) {
                    next.push_back(node->right);
                }
            }
            level = std::move(next);
            levels++;
        }
        return levels - 1;
    }

    // Cuántos negros hay en un camino desde la raíz hasta una hoja nula. La hoja nula no se cuenta.
    int black_height() const {
        int blacks = 0;
        for (const Node* node = root_; node != nullptr; node = node->left) {
            blacks += is_red(node) ? 0 : 1;
        }
        return blacks;
    }

    // Paso 2. Comprueba con assert las cinco propiedades, el orden de todo el árbol, los padres y el
    // tamaño. Recursiva, con una función auxiliar privada: se usa en las pruebas, no en el mapa.
    void check_invariants() const { not_implemented("check_invariants"); }

private:
    static Node* min_node(Node* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }

    // El nodo que sigue en el orden de las claves; nulo si es el último.
    static Node* successor(Node* node) {
        if (node->right != nullptr) {
            return min_node(node->right);
        }
        Node* parent = node->parent;
        while (parent != nullptr && parent->right == node) {
            node = parent;
            parent = parent->parent;
        }
        return parent;
    }

    Node* find_node(const K& key) const {
        Node* node = root_;
        while (node != nullptr) {
            if (key < node->key) {
                node = node->left;
            } else if (node->key < key) {
                node = node->right;
            } else {
                return node;
            }
        }
        return nullptr;
    }

    // El nodo con la menor clave >= key; nulo si no hay.
    Node* ceiling_node(const K& key) const {
        Node* node = root_;
        Node* candidate = nullptr;
        while (node != nullptr) {
            if (node->key < key) {
                node = node->right;
            } else if (key < node->key) {
                candidate = node;
                node = node->left;
            } else {
                return node;
            }
        }
        return candidate;
    }

    // El nodo con esa clave, y si se acaba de crear.
    std::pair<Node*, bool> insert_node(const K& key, const V& value) {
        Node* parent = nullptr;
        Node* node = root_;
        bool go_left = false;
        while (node != nullptr) {
            parent = node;
            if (key < node->key) {
                go_left = true;
                node = node->left;
            } else if (node->key < key) {
                go_left = false;
                node = node->right;
            } else {
                return {node, false};
            }
        }
        Node* fresh = new Node{key, value, parent};
        if (parent == nullptr) {
            root_ = fresh;
        } else if (go_left) {
            parent->left = fresh;
        } else {
            parent->right = fresh;
        }
        size_++;
        // Paso 3: aquí, y no en insert, para que operator[] también repare.
        return {fresh, true};
    }

    // En el lugar de old_child, que es hijo de parent (o la raíz), pone a child, que puede ser nulo.
    void replace_child(Node* parent, Node* old_child, Node* child) {
        if (parent == nullptr) {
            root_ = child;
        } else if (parent->left == old_child) {
            parent->left = child;
        } else {
            parent->right = child;
        }
        if (child != nullptr) {
            child->parent = parent;
        }
    }

    // ---- Lo propio del árbol rojinegro ----

    static bool is_red(const Node* node) { return node != nullptr && node->color == Color::red; }

    // Paso 1. Copien sus rotate_left y rotate_right de la semana 11, sin cambiar nada.
    // Suben al hijo que corresponde, y lo devuelven. Arreglan los enlaces, los padres y root_
    // (replace_child ayuda), y suman 1 a rotations_. No tocan los colores.
    Node* rotate_left(Node*) { not_implemented("rotate_left"); }
    Node* rotate_right(Node*) { not_implemented("rotate_right"); }

    // Paso 3. Repara desde z, que es rojo: pseudocódigo reparar_insercion de los apuntes. Al terminar,
    // pinta la raíz de negro. Un tío nulo cuenta como negro, y is_red ya lo resuelve. Cada vez que
    // aplique el caso del tío rojo, suma 1 a recolors_.
    void fix_insert(Node*) { not_implemented("fix_insert"); }

    // ---- Lo que viene de la semana 10 ----

    // Copia el nodo con todos sus campos, también color, sin sus enlaces.
    static Node* clone_node(const Node* from, Node* parent) {
        Node* copy = new Node(*from);
        copy->parent = parent;
        copy->left = nullptr;
        copy->right = nullptr;
        return copy;
    }

    // Copia la forma de other en preorden, sin recursión: baja por los hijos que faltan y
    // vuelve con el puntero al padre. El árbol a medias queda siempre colgado de root_.
    void copy_nodes_from(const RedBlackMap& other) {
        if (other.root_ == nullptr) {
            return;
        }
        const Node* from = other.root_;
        root_ = clone_node(from, nullptr);
        Node* to = root_;
        while (true) {
            if (from->left != nullptr && to->left == nullptr) {
                from = from->left;
                to->left = clone_node(from, to);
                to = to->left;
            } else if (from->right != nullptr && to->right == nullptr) {
                from = from->right;
                to->right = clone_node(from, to);
                to = to->right;
            } else if (to->parent != nullptr) {
                from = from->parent;
                to = to->parent;
            } else {
                break;
            }
        }
        size_ = other.size_;
    }

    Node* root_ = nullptr;
    std::size_t size_ = 0;
    long rotations_ = 0;
    long recolors_ = 0;
};

#endif