/*
Реализовать класс Set.

Для класса Set реализовать методы:

insert (вставка элемента)
erase (удаление элемента)
min (принимает указатель на родителя и возвращает минимальный элемент в ветке)
max (принимает указатель на родителя и возвращает максимальный элемент в ветке)
find (возвращает указатель на элемент либо nullptr если его нет)
count (возвращает количество вхождений элемента в множество)
next (возвращает указатель на следующий элемент)
prev (возвращает указатель на предыдущий элемент)
begin (возвращает указатель на первый элемент)
end (возвращает указатель на последний элемент)
clear (очистка списка)
size (возвращает размер множества)
print (вывод элементов множества в консоль в порядке возпастания)
copy - для констр. и опер. копир (рекурсивная функция для копирования дерева)
compare - для операторов сравнения (принимает два указателя на узлы и рекурсивно сравнивает содержимое)
- переопределить операторы сравнения (==, !=)
- реализовать конструктор по умолчанию, деструктор
- реализовать конструктор копирования, копирующий оператор присваивания
- реализовать конструктор перемещения, перемещающий оператор присваивания
- сделать класс шаблонным
*/

#include <iostream>

using namespace std;

class Set {

public:

    struct Node {
        int value;
        Node* left;
        Node* right;
        Node* parent;
    };

    void insert(const int 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 = new Node{ val, nullptr, nullptr, parent };
            parent->value > val ? parent->left = node : parent->right = node;
            size_++;
        }
    }

    void erase(const int 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);
                node->value = temp->value;
                if (temp->right != nullptr) {
                    temp->right->parent = temp->parent;
                }
                temp == temp->parent->right ? temp->parent->right = temp->right : temp->parent->left = temp->right;
                delete temp;
            }
            size_--;
        }
    }

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

    Node* find(const int val) {
        Node* node = root_;
        while (node != nullptr && node->value != val) {
            node = node->value > val ? node->left : node->right;
        }
        return node;
    }

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

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

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

    void print() {
        print(root_);
        cout << endl;
    }

    void clear() {
        clear(root_);
        root_ = nullptr;
        size_ = 0;
    }

    int size() const {
        return size_;
    }

    Node* begin() {
        return min(root_);
    }

    Node* end() {
        return max(root_);
    }

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

    // вариант сравнения деревьев на случай разной топологии но одинакового размера
    bool compare(Node* a, Node* b) {
        if (a == nullptr && b == nullptr) {
            return true;
        }
        return  a->value == b->value && compare(next(a), next(b));
    }

private:

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

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

    Node* root_ = nullptr;
    int size_ = 0;
};


int main() {

   // раскомментировать для проверки
   /* setlocale(LC_ALL, "ru");

    Set<int> st{ 45,30,50,27,39,90,15,70,103 };

    st.print();
    cout << st.size() << endl;

    st.print();
    cout << st.size() << endl;

    Set<int> st2(st);

    st2.print();
    cout << st2.size() << endl;

    cout << (st == st2) << endl;

    st2.erase(45);
    st2.insert(45);

    st.print();
    st2.print();

    cout << (st == st2) << endl;

    auto node = st2.find(30);

    if (node != nullptr) {
        cout << node->value << endl;
    }

    Set<string> st3{ "один", "два", "три", "четыре" };

    st3.print();*/
}