// Mapa ordenado sobre un árbol binario de búsqueda. Completen cada método marcado con not_implemented.
// La copia, el movimiento, height y pre_order_keys ya vienen hechos.
#ifndef BST_MAP_H
#define BST_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.
//
// 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. Al borrar una clave con dos hijos, el nodo
// del sucesor desaparece y su contenido pasa a otro nodo: dejan de valer los que señalaban al
// sucesor y al nodo borrado. Tras un borrado, no los usen.
template <typename K, typename V>
class BstMap {
    struct Node {
        K key;
        V value;
        Node* parent = nullptr;
        Node* left = nullptr;
        Node* right = nullptr;
    };

    friend struct BstMapTestAccess;

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}; }
        // Paso 3: avanza al sucesor.
        Iter& operator++() { not_implemented("Iter::operator++"); }
        bool operator==(const Iter& other) const { return node_ == other.node_; }
        bool operator!=(const Iter& other) const { return node_ != other.node_; }

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

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

    BstMap() = default;

    // Paso 1: libera todos los nodos en postorden, sin recursión: baje hasta una hoja, bórrela
    // y vuelva por parent, cortando antes el enlace del padre. La prueba corre con poca pila.
    ~BstMap() { not_implemented("~BstMap"); }

    // 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í.
    BstMap(const BstMap& other) : BstMap() {
        copy_nodes_from(other);
    }

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

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

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

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

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

    // Paso 1. Como std::map::insert: si la clave ya estaba, no cambia su valor y devuelve false.
    // Con un ciclo, sin recursión: la prueba del destructor arma una cadena con poca pila.
    bool insert(const K&, const V&) { not_implemented("insert"); }

    // Paso 1. Como en std::map: si la clave no está, la inserta con V{}.
    V& operator[](const K&) { not_implemented("operator[]"); }

    // Paso 1. Puntero al valor; nulo si la clave no está.
    V* find(const K&) { not_implemented("find"); }
    const V* find(const K&) const { not_implemented("find const"); }

    // Paso 2. Devuelve false si la clave no estaba.
    bool erase(const K&) { not_implemented("erase"); }

    // Paso 3. Punteros a la clave menor y a la mayor; nulos si está vacío.
    const K* min_key() const { not_implemented("min_key"); }
    const K* max_key() const { not_implemented("max_key"); }

    // Paso 3. Puntero a la mayor clave <= key; nulo si no hay.
    const K* floor(const K&) const { not_implemented("floor"); }

    // Paso 3. Puntero a la menor clave >= key; nulo si no hay.
    const K* ceiling(const K&) const { not_implemented("ceiling"); }

    // Paso 3. Los pares con clave en [low, high), en orden. Debe costar O(altura + cantidad de pares).
    std::vector<std::pair<K, V>> range(const K&, const K&) const { not_implemented("range"); }

    // Paso 3. end es el iterador con nodo nulo.
    iterator begin() { not_implemented("begin"); }
    iterator end() { not_implemented("end"); }
    const_iterator begin() const { not_implemented("begin const"); }
    const_iterator end() const { not_implemented("end const"); }

    // Paso 1. Las claves en orden.
    std::vector<K> in_order_keys() const { not_implemented("in_order_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;
    }

    // Paso 1. Con assert, comprueba todas las invariantes de arriba. Puede ser recursiva: las
    // pruebas la usan en árboles pequeños. Mirar solo a los hijos directos no alcanza.
    void check_invariants() const { not_implemented("check_invariants"); }

private:
    // Sugeridas: estas funciones privadas evitan repetir código, y las semanas 11 y 12 las usarán.
    // Pueden agregar otras.

    // El nodo con la menor clave de este subárbol. node no es nulo.
    static Node* min_node(Node*) { not_implemented("min_node"); }

    // El nodo que sigue en el orden de las claves; nulo si es el último.
    static Node* successor(Node*) { not_implemented("successor"); }

    // El nodo con esa clave; nulo si no está.
    Node* find_node(const K&) const { not_implemented("find_node"); }

    // El nodo con esa clave, y si se acaba de crear. Lo usan insert y operator[]. Con un ciclo.
    std::pair<Node*, bool> insert_node(const K&, const V&) { not_implemented("insert_node"); }

    // En el lugar de old_child, que es hijo de parent (o la raíz), pone a child, que puede ser
    // nulo. Actualiza el enlace de parent, o root_, y el padre de child.
    void replace_child(Node*, Node*, Node*) { not_implemented("replace_child"); }

    // Quita node, y devuelve el padre del nodo que salió de verdad del árbol.
    Node* remove_node(Node*) { not_implemented("remove_node"); }

    // 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_.
    // Copia el nodo con todos sus campos, 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;
    }

    void copy_nodes_from(const BstMap& 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;
};

#endif