// Un AVL de enteros con un error a propósito, elegido por el parámetro del template.
// Compárenlo con ../avl_set.h: cada error está marcado con su nombre.
#ifndef BROKEN_AVL_H
#define BROKEN_AVL_H

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <sstream>
#include <string>

enum class Bug { no_height_update, parent_before_child, single_on_zigzag, stop_after_first_repair };

template <Bug bug>
class BrokenAvl {
    struct Node {
        int key;
        Node* left = nullptr;
        Node* right = nullptr;
        int height = 0;
    };

public:
    BrokenAvl() = default;
    ~BrokenAvl() { destroy(root_); }
    BrokenAvl(const BrokenAvl&) = delete;
    BrokenAvl& operator=(const BrokenAvl&) = delete;

    void insert(int key) {
        repaired_ = false;
        root_ = insert_at(root_, key);
    }

    void erase(int key) {
        repaired_ = false;
        root_ = erase_at(root_, key);
    }

    // La altura de verdad, y no la guardada: baja por todo el árbol.
    int real_height() const { return real_height_of(root_); }
    int stored_height() const { return height_of(root_); }

    std::string shape() const {
        std::ostringstream out;
        write_shape(root_, out);
        return out.str();
    }

    void check_invariants() const { check(root_); }

private:
    static int height_of(const Node* node) { return node != nullptr ? node->height : -1; }
    static int balance_of(const Node* node) { return height_of(node->left) - height_of(node->right); }
    static void update_height(Node* node) {
        node->height = 1 + std::max(height_of(node->left), height_of(node->right));
    }

    static Node* rotate_left(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        y->left = x;
        return y;
    }

    static Node* rotate_right(Node* x) {
        Node* y = x->left;
        x->left = y->right;
        y->right = x;
        return y;
    }

    // Actualiza las alturas de los dos nodos de una rotación: el que bajó y el que subió.
    static void after_rotation(Node* lowered, Node* raised) {
        if constexpr (bug == Bug::no_height_update) {
            // Error: se rota y no se actualiza ninguna altura.
            (void)lowered;
            (void)raised;
        } else if constexpr (bug == Bug::parent_before_child) {
            // Error: el que subió es ahora el padre, y se calcula con la altura vieja de su hijo.
            update_height(raised);
            update_height(lowered);
        } else {
            update_height(lowered);
            update_height(raised);
        }
    }

    Node* rebalance(Node* x) {
        update_height(x);
        int balance = balance_of(x);
        if (std::abs(balance) <= 1) {
            return x;
        }
        if constexpr (bug == Bug::stop_after_first_repair) {
            // Error: "basta una reparación" vale al insertar, y no al borrar.
            if (repaired_) {
                return x;
            }
        }
        repaired_ = true;
        if (balance > 1) {
            if constexpr (bug != Bug::single_on_zigzag) {
                if (balance_of(x->left) < 0) {
                    Node* y = x->left;
                    x->left = rotate_left(y);
                    after_rotation(y, x->left);
                }
            }
            Node* top = rotate_right(x);
            after_rotation(x, top);
            return top;
        }
        if constexpr (bug != Bug::single_on_zigzag) {
            if (balance_of(x->right) > 0) {
                Node* y = x->right;
                x->right = rotate_right(y);
                after_rotation(y, x->right);
            }
        }
        Node* top = rotate_left(x);
        after_rotation(x, top);
        return top;
    }

    Node* insert_at(Node* node, int key) {
        if (node == nullptr) {
            return new Node{key};
        }
        if (key < node->key) {
            node->left = insert_at(node->left, key);
        } else if (node->key < key) {
            node->right = insert_at(node->right, key);
        } else {
            return node;
        }
        return rebalance(node);
    }

    Node* erase_at(Node* node, int key) {
        if (node == nullptr) {
            return nullptr;
        }
        if (key < node->key) {
            node->left = erase_at(node->left, key);
        } else if (node->key < key) {
            node->right = erase_at(node->right, key);
        } else {
            if (node->left == nullptr || node->right == nullptr) {
                Node* child = node->left != nullptr ? node->left : node->right;
                delete node;
                return child;
            }
            const Node* next = node->right;
            while (next->left != nullptr) {
                next = next->left;
            }
            node->key = next->key;
            node->right = erase_at(node->right, node->key);
        }
        return rebalance(node);
    }

    static int real_height_of(const Node* node) {
        if (node == nullptr) {
            return -1;
        }
        return 1 + std::max(real_height_of(node->left), real_height_of(node->right));
    }

    static void destroy(Node* node) {
        if (node == nullptr) {
            return;
        }
        destroy(node->left);
        destroy(node->right);
        delete node;
    }

    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 << ")";
        }
    }

    // Vuelve a calcular cada altura desde los hijos, y la compara con la guardada.
    static int check(const Node* node) {
        if (node == nullptr) {
            return -1;
        }
        int left = check(node->left);
        int right = check(node->right);
        assert(node->height == 1 + std::max(left, right));
        assert(std::abs(left - right) <= 1);
        return node->height;
    }

    Node* root_ = nullptr;
    bool repaired_ = false;
};

#endif