// Árbol binario de búsqueda sin valores: el conjunto de claves de los apuntes.
// El laboratorio construye un mapa con valores y con puntero al padre.
#ifndef BST_SET_H
#define BST_SET_H

#include <cassert>
#include <cstddef>
#include <sstream>
#include <string>
#include <vector>

// Invariantes:
// - En cada nodo, todas las claves del subárbol izquierdo son menores que la suya,
//   y todas las del derecho son mayores. Por eso no hay claves repetidas.
// - El árbol tiene exactamente size_ nodos, y root_ es nulo si y solo si size_ == 0.
//
// K solo necesita operator<: a y b son la misma clave si ni a < b ni b < a.
template <typename K>
class BstSet {
    struct Node {
        K key;
        Node* left = nullptr;
        Node* right = nullptr;
    };

public:
    BstSet() = default;

    // Sin recursión: un árbol degenerado no agota la pila.
    ~BstSet() {
        std::vector<Node*> pending;
        if (root_ != nullptr) {
            pending.push_back(root_);
        }
        while (!pending.empty()) {
            Node* node = pending.back();
            pending.pop_back();
            if (node->left != nullptr) {
                pending.push_back(node->left);
            }
            if (node->right != nullptr) {
                pending.push_back(node->right);
            }
            delete node;
        }
    }

    // Este conjunto es para estudiar las operaciones: no se copia ni se mueve.
    BstSet(const BstSet&) = delete;
    BstSet& operator=(const BstSet&) = delete;

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

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

    // Devuelve false si la clave ya estaba.
    bool insert(const K& key) {
        Node** link = &root_;
        while (*link != nullptr) {
            if (key < (*link)->key) {
                link = &(*link)->left;
            } else if ((*link)->key < key) {
                link = &(*link)->right;
            } else {
                return false;
            }
        }
        *link = new Node{key};
        size_++;
        return true;
    }

    // Devuelve false si la clave no estaba.
    bool erase(const K& key) {
        Node** link = &root_;
        while (*link != nullptr) {
            if (key < (*link)->key) {
                link = &(*link)->left;
            } else if ((*link)->key < key) {
                link = &(*link)->right;
            } else {
                break;
            }
        }
        if (*link == nullptr) {
            return false;
        }
        Node* node = *link;
        if (node->left != nullptr && node->right != nullptr) {
            // Dos hijos: el sucesor es el mínimo del subárbol derecho.
            Node** next_link = &node->right;
            while ((*next_link)->left != nullptr) {
                next_link = &(*next_link)->left;
            }
            node->key = (*next_link)->key;
            // Ahora el que se quita es el nodo del sucesor, que no tiene hijo izquierdo.
            link = next_link;
            node = *link;
        }
        *link = node->left != nullptr ? node->left : node->right;
        delete node;
        size_--;
        return true;
    }

    // Puntero a la clave menor; nulo si está vacío.
    const K* min() const {
        const Node* node = root_;
        if (node == nullptr) {
            return nullptr;
        }
        while (node->left != nullptr) {
            node = node->left;
        }
        return &node->key;
    }

    // Puntero a la clave mayor; nulo si está vacío.
    const K* max() const {
        const Node* node = root_;
        if (node == nullptr) {
            return nullptr;
        }
        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;
    }

    // Las claves de [low, high), en orden.
    std::vector<K> range(const K& low, const K& high) const {
        std::vector<K> keys;
        collect_range(root_, low, high, keys);
        return keys;
    }

    std::vector<K> in_order() const {
        std::vector<K> keys;
        walk_in(root_, keys);
        return keys;
    }

    std::vector<K> pre_order() const {
        std::vector<K> keys;
        walk_pre(root_, keys);
        return keys;
    }

    std::vector<K> post_order() const {
        std::vector<K> keys;
        walk_post(root_, keys);
        return keys;
    }

    // Altura: aristas del camino más largo desde la raíz. Vacío: -1. Un solo nodo: 0.
    // Va nivel por nivel, sin recursión.
    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;
    }

    // Suma de las profundidades de todos los nodos: la raíz tiene profundidad 0.
    long total_depth() const {
        long total = 0;
        long depth = 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) {
                total += depth;
                if (node->left != nullptr) {
                    next.push_back(node->left);
                }
                if (node->right != nullptr) {
                    next.push_back(node->right);
                }
            }
            level = std::move(next);
            depth++;
        }
        return total;
    }

    // La forma del árbol en una línea: clave(izquierdo,derecho), con _ si falta un hijo.
    std::string shape() const {
        std::ostringstream out;
        write_shape(root_, out);
        return out.str();
    }

    // Comprueba con límites: mirar solo a los hijos directos no alcanza.
    // Es recursiva: su profundidad es la altura del árbol.
    void check_invariants() const {
        assert(count_checked(root_, nullptr, nullptr) == size_);
        assert((root_ == nullptr) == (size_ == 0));
    }

private:
    static void walk_in(const Node* node, std::vector<K>& keys) {
        if (node == nullptr) {
            return;
        }
        walk_in(node->left, keys);
        keys.push_back(node->key);
        walk_in(node->right, keys);
    }

    static void walk_pre(const Node* node, std::vector<K>& keys) {
        if (node == nullptr) {
            return;
        }
        keys.push_back(node->key);
        walk_pre(node->left, keys);
        walk_pre(node->right, keys);
    }

    static void walk_post(const Node* node, std::vector<K>& keys) {
        if (node == nullptr) {
            return;
        }
        walk_post(node->left, keys);
        walk_post(node->right, keys);
        keys.push_back(node->key);
    }

    static void collect_range(const Node* node, const K& low, const K& high, std::vector<K>& keys) {
        if (node == nullptr) {
            return;
        }
        if (low < node->key) {
            collect_range(node->left, low, high, keys);
        }
        if (!(node->key < low) && node->key < high) {
            keys.push_back(node->key);
        }
        if (node->key < high) {
            collect_range(node->right, low, high, keys);
        }
    }

    static void write_shape(const Node* node, std::ostringstream& out) {
        if (node == nullptr) {
            out << "_";
            return;
        }
        out << node->key;
        if (node->left != nullptr || node->right != nullptr) {
            out << "(";
            write_shape(node->left, out);
            out << ",";
            write_shape(node->right, out);
            out << ")";
        }
    }

    // Cuenta los nodos, y exige que cada clave quede entre low y high (nulo: sin límite).
    static std::size_t count_checked(const Node* node, const K* low, const K* high) {
        if (node == nullptr) {
            return 0;
        }
        assert(low == nullptr || *low < node->key);
        assert(high == nullptr || node->key < *high);
        return 1 + count_checked(node->left, low, &node->key)
                 + count_checked(node->right, &node->key, high);
    }

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

#endif