// Copia de RedBlackSet con un error a elección, para los programas de esta carpeta.
#ifndef BROKEN_RB_H
#define BROKEN_RB_H

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

enum class Bug { no_root_paint, new_node_black, single_on_zigzag, no_repaint_after_rotation };

template <Bug bug>
class BrokenRb {
    enum class Color { red, black };

    struct Node {
        int key;
        Node* left = nullptr;
        Node* right = nullptr;
        Color color = Color::red;
    };

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

    void insert(int key) {
        bool added = false;
        root_ = insert_at(root_, key, added);
        if (added) {
            size_++;
        }
        if (bug != Bug::no_root_paint) {
            root_->color = Color::black;
        }
    }

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

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

    void check_invariants() const {
        assert(!is_red(root_));
        std::size_t count = 0;
        check_node(root_, nullptr, nullptr, count);
        assert(count == size_);
    }

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

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

    Node* insert_at(Node* node, int key, bool& added) {
        if (node == nullptr) {
            added = true;
            Node* fresh = new Node{key};
            if (bug == Bug::new_node_black) {
                fresh->color = Color::black;
            }
            return fresh;
        }
        if (key < node->key) {
            node->left = insert_at(node->left, key, added);
        } else if (node->key < key) {
            node->right = insert_at(node->right, key, added);
        } else {
            return node;
        }
        return repair_from_grandparent(node);
    }

    static void recolor(Node* grandparent) {
        grandparent->color = Color::red;
        grandparent->left->color = Color::black;
        grandparent->right->color = Color::black;
    }

    static Node* paint_top(Node* top, Node* grandparent) {
        if (bug != Bug::no_repaint_after_rotation) {
            top->color = Color::black;
            grandparent->color = Color::red;
        }
        return top;
    }

    static Node* repair_from_grandparent(Node* grandparent) {
        Node* left = grandparent->left;
        Node* right = grandparent->right;
        if (is_red(left) && (is_red(left->left) || is_red(left->right))) {
            if (is_red(right)) {
                recolor(grandparent);
                return grandparent;
            }
            if (is_red(left->right) && bug != Bug::single_on_zigzag) {
                grandparent->left = rotate_left(left);
            }
            return paint_top(rotate_right(grandparent), grandparent);
        }
        if (is_red(right) && (is_red(right->left) || is_red(right->right))) {
            if (is_red(left)) {
                recolor(grandparent);
                return grandparent;
            }
            if (is_red(right->left) && bug != Bug::single_on_zigzag) {
                grandparent->right = rotate_right(right);
            }
            return paint_top(rotate_left(grandparent), grandparent);
        }
        return grandparent;
    }

    static void destroy(Node* node) {
        if (node != nullptr) {
            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->color == Color::red) {
            out << "r";
        }
        if (node->left != nullptr || node->right != nullptr) {
            out << "(";
            write_shape(node->left, out);
            out << ",";
            write_shape(node->right, out);
            out << ")";
        }
    }

    static int check_node(const Node* node, const int* low, const int* high, std::size_t& count) {
        if (node == nullptr) {
            return 0;
        }
        count++;
        assert(low == nullptr || *low < node->key);
        assert(high == nullptr || node->key < *high);
        if (is_red(node)) {
            assert(!is_red(node->left) && !is_red(node->right));
        }
        int left = check_node(node->left, low, &node->key, count);
        int right = check_node(node->right, &node->key, high, count);
        assert(left == right);
        return left + (is_red(node) ? 0 : 1);
    }

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

#endif