#pragma once

#include <initializer_list>
#include <iostream>


template <typename T>
class Set {

public:

    struct Node {
        T value{};
        Node* left = nullptr;
        Node* right = nullptr;
        Node* parent = nullptr;
    };

    class Iterator {
    public:
        Iterator(Node* node) : node_(node) {}

        T& operator*() { // перегрузка оператора разыменования
            return node_->value;
        }

        Iterator operator++() { // перегрузка префиксной формы инкремента
            if (!node_) {
                throw std::runtime_error("Пустой контейнер");
            }
            if (node_->right) {
                node_ = node_->right;
                while (node_->left) {
                    node_ = node_->left;
                }
                return *this;
            }
            Node* temp = node_->parent;
            while (temp != nullptr && node_->value > temp->value) {
                temp = temp->parent;
            }
            node_ = temp;
            return *this;
        }

        Iterator operator++(int) { // перегрузка постфиксной формы инкремента
            return ++(*this);
        }

        Iterator operator--() { // перегрузка префиксной формы декремента
            if (!node_) {
                throw std::runtime_error("Пустой контейнер");
            }
            if (node_->left) {
                node_ = node_->left;
                while (node_->right) {
                    node_ = node_->right;
                }
                return *this;
            }
            Node* temp = node_->parent;
            while (temp != nullptr && node_->value < temp->value) {
                temp = temp->parent;
            }
            node_ = temp;
            return *this;
        }

        Iterator operator--(int) { // перегрузка постфиксной формы декремента
            return --(*this);
        }

        Iterator operator+(int n) {
            Iterator temp(node_);
            while (n) {
                temp++;
                n--;
            }
            return temp;
        }

        Iterator operator-(int n) {
            Iterator temp(node_);
            while (n) {
                temp--;
                n--;
            }
            return temp;
        }

        bool operator==(Iterator other) {
            return node_ == other.node_;
        }

        bool operator!=(Iterator other) {
            return node_ != other.node_;
        }

    private:
        Node* node_ = nullptr;
    };

    Iterator begin() {
        return Iterator(Min(root));
    }

    Iterator end() {
        return Iterator(nullptr);
    }

    Set() : size(0), root(nullptr) {}

    Set(const std::initializer_list<T>& list) : size(0), root(nullptr) {
        for (const auto& element : list) {
            Insert(element);
        }
    }

    Set(const Set& other) : size(other.size), root(Copy(other.root, nullptr)) {}

    Set(Set&& other) : size(other.size), root(other.root) {
        other.size = 0;
        other.root = nullptr;
    }

    Set& operator=(const Set& other) {
        if (this != &other) {
            Clear();
            size = other.size;
            root = Copy(other.root, nullptr);
        }
        return *this;
    }

    Set& operator=(Set&& other) {
        if (this != &other) {
            Clear();
            size = other.size;
            root = other.root;
            other.root = nullptr;
            other.size = 0;
        }
        return *this;
    }

    Node* Copy(Node* node, Node* parent) {
        if (node == nullptr) {
            return node;
        }
        Node* temp = new Node{ node->value, nullptr, nullptr, parent };
        temp->left = Copy(node->left, temp);
        temp->right = Copy(node->right, temp);
        return temp;
    }

    void Insert(const T& val) {
        if (root == nullptr) {
            root = new Node{ val, nullptr, nullptr, nullptr };
            size++;
            return;
        }
        Node* parent = nullptr;
        Node* node = root;
        while (node != nullptr && node->value != val) {
            parent = node;
            node = node->value > val ? node->left : node->right;
        }
        if (node == nullptr) {
            Node* temp = new Node{ val, nullptr, nullptr, parent };
            parent->value > val ? parent->left = temp : parent->right = temp;
            size++;
        }
    }

    void Erase(const T& val) {
        Node* parent = nullptr;
        Node* node = root;
        while (node != nullptr && node->value != val) {
            parent = node;
            node = node->value > val ? node->left : node->right;
        }
        if (node != nullptr) {
            if (node->left == nullptr && node->right == nullptr) {
                if (node == root) {
                    root = nullptr;
                }
                else {
                    node == parent->right ? parent->right = nullptr : parent->left = nullptr;
                }
                delete node;
            }
            else if (node->left == nullptr) {
                node->right->parent = node->parent;
                if (node == root) {
                    root = node->right;
                }
                else {
                    node == parent->right ? parent->right = node->right : parent->left = node->right;
                }
                delete node;
            }
            else if (node->right == nullptr) {
                node->left->parent = node->parent;
                if (node == root) {
                    root = node->left;
                }
                else {
                    node == parent->right ? parent->right = node->left : parent->left = node->left;
                }
                delete node;
            }
            else {
                Node* temp = Min(node->right);
                if (temp->right) {
                    temp->right->parent = temp->parent;
                }
                temp == temp->parent->right ? temp->parent->right = temp->right : temp->parent->left = temp->right;
                node->value = temp->value;
                delete temp;
            }
            size--;
        }
    }

    Node* Find(const T& val) {
        Node* node = root;
        while (node != nullptr && node->value != val) {
            node = node->value > val ? node->left : node->right;
        }
        return node;
    }

    int Count(const T& val) {
        return Find(val) == nullptr ? 0 : 1;
    }

    Node* Next(Node* node) {
        if (node) {
            if (node->right) {
                return Min(node->right);
            }
            Node* temp = node->parent;
            while (temp != nullptr && node->value > temp->value) {
                temp = temp->parent;
            }
            return temp;
        }
    }

    Node* Prev(Node* node) {
        if (node) {
            if (node->left) {
                return Max(node->left);
            }
            Node* temp = node->parent;
            while (temp != nullptr && node->value < temp->value) {
                temp = temp->parent;
            }
            return temp;
        }
    }


    Node* Begin() {
        return Min(root);
    }

    Node* End() {
        return Max(root);
    }

    Node* Min(Node* node) {
        if (node != nullptr)
            while (node->left != nullptr)
                node = node->left;
        return node;
    }

    Node* Max(Node* node) {
        if (node != nullptr)
            while (node->right != nullptr)
                node = node->right;
        return node;
    }

    void Print() {
        Print(root);
        std::cout << std::endl;
    }

    void Print(Node* node) {
        if (node != nullptr) {
            Print(node->left);
            std::cout << node->value << " ";
            Print(node->right);
        }
    }

    void Clear() {
        Clear(root);
        root = nullptr;
        size = 0;
    }

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

    int Size() {
        return size;
    }

    bool Compare(Node* a, Node* b) {
        if (a == nullptr && b == nullptr) {
            return true;
        }
        return (a != nullptr && b != nullptr) && (a->value == b->value) && Compare(a->left, b->left) && Compare(a->right, b->right);
    }

    bool operator==(const Set& other) {
        return Compare(root, other.root);
    }

    bool operator!=(const Set& other) {
        return !(*this == other);
    }

    ~Set() {
        Clear(root);
    }

private:
    int size = 0;
    Node* root = nullptr;
};