#include <iostream>
#include <stdexcept>
#include "binary_search_tree.h"
int main() {
    BinarySearchTree<int> tree;
    tree.remove(123987);
    try {
        tree.find_max();
    } catch (std::exception& e) {
        std::cerr << e.what() << "\n";
    }
    try {
        tree.find_min();
    } catch (std::exception& e) {
        std::cerr << e.what() << "\n";
    }
    int n = 120;
    while (n != 1) {
        tree.insert(n);
        if (n % 2 == 0)
            n = n / 2;
        else
            n = 3 * n + 1;
    }
    tree.insert(2);
    tree.remove(2);
    tree.remove(18);
    tree.print_tree(std::cout);
    std::cout << tree.find_max() << "\n";
    BinarySearchTree<int> tree2;
    tree2 = tree;
    tree.remove(6);
    std::cout << tree.root_data() << "\n";
    std::cout << "contains 9? " << std::boolalpha << tree.contains(9) << "\n";
    tree2.insert(9);
    std::cout << tree2.find_max() << "\n";
    std::cout << tree2.root_data() << "\n";
    tree2.remove(7);
    BinarySearchTree<int> tree3(tree);
    tree3 = tree3;
    tree3.~BinarySearchTree();
    tree3.print_tree();
}

#pragma once
#include <iostream>
#include <stdexcept>
template <typename T>
class BinarySearchTree {
    private:
        struct Node {
            T data;
            Node* left;
            Node* right;
            Node(const T& item)
            : data(item)
            , left(nullptr)
            , right(nullptr) {}
            Node(const T& item, Node* _left, Node* _right)
            : data(item)
            , left(_left)
            , right(_right) {}
        };
        Node* m_root;
        Node* copy(Node* node) const{
            if (node == nullptr)
                return nullptr;
            else
                return new Node(node->data, copy(node->left), copy(node->right));
        }
        Node* right_subtree_min(Node* root) const {
            if (root == nullptr)
                return nullptr;
            if (root->left == nullptr)
                return root;
            return right_subtree_min(root->left);
        }
        void remove(const T& item, Node* &root) {
            if (root == nullptr) {
                ;
            }
            if (item < root->data) {
                remove(item, root->left);
            } else if (item > root->data) {
                remove(item, root->right);
            } else if (root->left != nullptr && root->right != nullptr) {
                root->data = right_subtree_min(root->right)->data;
                remove(root->data, root->right);
            } else {
                Node* node_to_remove = root;
                root = root->left != nullptr ? root->left : root->right;
                delete node_to_remove;
            }
        }
        void display(Node* root, std::ostream& out, unsigned int counter = 0) const {
            if (m_root == nullptr) {
                out << "<empty>\n";
            } else if (root == nullptr) {
                out << "";
            } else {
                display(root->right, out, counter + 1);
                for (unsigned int i = 0; i < counter; i++) out << "  ";
                out << root->data << "\n";
                display(root->left, out, counter + 1);
            }
        }
    public:
        BinarySearchTree() : m_root(nullptr) {}
        BinarySearchTree(const BinarySearchTree& tree) : m_root(nullptr) {
            int n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n=0;
            n++;
            m_root = copy(tree.m_root);
        }
        ~BinarySearchTree() {
            make_empty(m_root);
        }
        BinarySearchTree& operator=(const BinarySearchTree& rhs) {
            if (&rhs == this)
                return *this;
            
            make_empty(m_root);
            m_root = copy(rhs.m_root);
            return *this;
        }
        bool contains(const T& item) const {
            Node* temp = m_root;
            while (temp != nullptr) {
                if (temp->data == item)
                    return true;
                else if (temp->data < item)
                    temp = temp->right;
                else
                    temp = temp->left;
            }
            return false;
        }
        
        void insert(const T& item) {
            if (contains(item)) {
                ;
            } else {
                Node* new_node = new Node(item);
                if (m_root == nullptr) {
                    m_root = new_node;
                } else {
                    Node* temp = m_root;
                    while ((temp->left != nullptr && item < temp->data) || (temp->right != nullptr && item > temp->data)) {
                        if (item < temp->data)
                            temp = temp->left;
                        else if (item > temp->data)
                            temp = temp->right;
                    }
                    if (item > temp->data)
                        temp->right = new_node;
                    else 
                        temp->left = new_node;
                }
            }
        }
        void remove(const T& item) {
            if (!contains(item)) {
                ;
            } else {
                remove(item, m_root);
            }
        }
        const T& find_min() const {
            if (m_root == nullptr)
                throw std::invalid_argument("tree is empty");
            
            Node* temp = m_root;
            while (temp->left != nullptr) temp = temp->left;
            return temp->data;
        }
        const T& find_max() const {
            if (m_root == nullptr)
                throw std::invalid_argument("tree is empty");
            Node* temp = m_root;
            while (temp->right != nullptr) temp = temp->right;
            return temp->data;
        }
        void print_tree(std::ostream& out=std::cout) const {
            Node* temp = m_root;
            display(temp, out);
        }
        const T& root_data() const {
            return m_root->data;
        }
        void make_empty(Node* &node) {
            if (node != nullptr) {
                make_empty(node->left);
                make_empty(node->right);
                delete node;
            }
            node = nullptr;
        }
};

#include <iostream>
#include <stdexcept>
#include "avl_tree.h"
int main() {
    AVLTree<int> tree;
    tree.remove(12312);
    try {
        tree.find_max();
    }catch (std::exception& e) {
        std::cerr << e.what() << "\n";
    }
    try {
        tree.find_min();
    } catch (std::exception& e) {
        std::cerr << e.what() << "\n";
    }
    int n = 120;
    while (n != 1) {
        tree.insert(n);
        if (n % 2 == 0)
            n = n / 2;
        else
            n = 3 * n + 1;
    }
    tree.insert(2);
    tree.remove(2);
    tree.remove(18);
    tree.print_tree(std::cout);
    std::cout << tree.find_max() << "\n";
    AVLTree<int> tree2;
    tree2 = tree;
    tree.remove(6);
    std::cout << tree.root_data() << "\n";
    std::cout << "contains 9? " << std::boolalpha << tree.contains(9) << "\n";
    tree2.insert(9);
    std::cout << tree2.find_max() << "\n";
    std::cout << tree2.root_data() << "\n";
    tree2.remove(7);
    AVLTree<int> tree3(tree);
    tree3 = tree3;
    tree3.~AVLTree();
    tree3.print_tree();
}

#pragma once
#include <iostream>
#include <stdexcept>
template <typename T>
class AVLTree {
    private:
        struct Node {
            T data;
            Node* left;
            Node* right;
            int height;
            Node(const T& item)
            : data(item)
            , left(nullptr)
            , right(nullptr)
            , height(0) {}
            Node(const T& item, Node* _left, Node* _right, int _height=0)
            : data(item)
            , left(_left)
            , right(_right)
            , height(_height) {}
        };
        Node* m_root;
        void balance(Node* &node) {
            if (node == nullptr) {
                return;
            }
            if (height(node->left) - height(node->right) > 1) {
                if (height(node->left->left) >= height(node->left->right))
                    lc_rotate(node);
                else
                    dlc_rotate(node);
            } else if (height(node->right) - height(node->left) > 1) {
                if (height(node->right->right) >= height(node->right->left))
                    rc_rotate(node);
                else
                    drc_rotate(node);
            }
            node->height = std::max(height(node->left), height(node->right)) + 1;
        }
        Node* copy(Node* node) const {
            if (node == nullptr)
                return nullptr;
            else
                return new Node(node->data, copy(node->left), copy(node->right), node->height);
        }
        void display(Node* root, std::ostream& out, unsigned int counter = 0) const {
            if (m_root == nullptr) {
                out << "<empty>\n";
            } else if (root == nullptr) {
                out << "";
            } else {
                display(root->right, out, counter + 1);
                for (unsigned int i = 0; i < counter; i++) out << "  ";
                out << root->data << "\n";
                display(root->left, out, counter + 1);
            }
        }
        void dlc_rotate(Node* &node) {
            rc_rotate(node->left);
            lc_rotate(node);
        }
        void drc_rotate(Node* &node) {
            lc_rotate(node->right);
            rc_rotate(node);
        }
        void insert(const T& item, Node* &node) {
            if (node == nullptr) {
                node = new Node(item, nullptr, nullptr);
            } else if (item < node->data) {
                insert(item, node->left);
            } else if (item > node->data) {
                insert(item, node->right);
            }
            balance(node);
        }
        int height(Node* node) const {
            return node == nullptr ? -1 : node->height;
        }
        void lc_rotate(Node* &node) {
            Node* left_child = node->left;
            node->left = left_child->right;
            left_child->right = node;
            node->height = std::max(height(node->left), height(node->right)) + 1;
            left_child->height = std::max(height(left_child->left), node->height) + 1;
            node = left_child;
        }
        void rc_rotate(Node* &node) {
            Node* right_child = node->right;
            node->right = right_child->left;
            right_child->left = node;
            node->height = std::max(height(node->left), height(node->right)) + 1;
            right_child->height = std::max(height(right_child->right), node->height) + 1;
            node = right_child;
        }
        T& right_subtree_min(Node* root) const {
            while (root->left != nullptr) root = root->left;
            return root->data;
        }
        void remove(const T& item, Node* &root) {
            if (root == nullptr) {
                return;
            }
            if (item < root->data) {
                remove(item, root->left);
            } else if (item > root->data) {
                remove(item, root->right);
            } else if (root->left != nullptr && root->right != nullptr) {
                root->data = right_subtree_min(root->right);
                remove(root->data, root->right);
            } else {
                Node* node_to_remove = root;
                root = root->left != nullptr ? root->left : root->right;
                delete node_to_remove;
            }
            balance(root);
        }
    public:
        AVLTree() : m_root(nullptr) {}
        AVLTree(const AVLTree& tree) : m_root(nullptr) {
            m_root = copy(tree.m_root);
        }
        ~AVLTree() {
            make_empty(m_root);
        }
        AVLTree& operator=(const AVLTree& rhs) {
            if (&rhs == this)
                return *this;
            
            make_empty(m_root);
            m_root = copy(rhs.m_root);
            return *this;
        }
        bool contains(const T& item) const {
            Node* temp = m_root;
            while (temp != nullptr) {
                if (temp->data == item)
                    return true;
                else if (temp->data < item)
                    temp = temp->right;
                else
                    temp = temp->left;
            }
            return false;
        }
        
        void insert(const T& item) {
            if (contains(item)) {
                ;
            } else {
                insert(item, m_root);
            }
        }
        void remove(const T& item) {
            if (!contains(item)) {
                ;
            } else {
                remove(item, m_root);
            }
        }
        const T& find_min() const {
            if (m_root == nullptr)
                throw std::invalid_argument("tree is empty");
            
            Node* temp = m_root;
            while (temp->left != nullptr) temp = temp->left;
            return temp->data;
        }
        const T& find_max() const {
            if (m_root == nullptr)
                throw std::invalid_argument("tree is empty");
            Node* temp = m_root;
            while (temp->right != nullptr) temp = temp->right;
            return temp->data;
        }
        void print_tree(std::ostream& out=std::cout) const {
            Node* temp = m_root;
            display(temp, out);
        }
        const T& root_data() const {
            return m_root->data;
        }
        void make_empty(Node* &node) {
            if (node != nullptr) {
                make_empty(node->left);
                make_empty(node->right);
                delete node;
            }
            node = nullptr;
        }
};

all: bst avl
clean: 
	rm -f *.gcov *.gcda *.gcno a.out
	
compile_test: clean binary_search_tree.h avl_tree.h compile_test.cpp
	g++ -std=c++17 -Wall -Wextra -Weffc++ -pedantic-errors -g compile_test.cpp
bst: clean binary_search_tree.h binary_search_tree_tests.cpp
	g++ -std=c++17 -Wall -Wextra -Weffc++ -pedantic-errors -g --coverage binary_search_tree_tests.cpp && ./a.out && gcov -mr binary_search_tree_tests.cpp
avl: clean avl_tree.h avl_tree_tests.cpp
	g++ -std=c++17 -Wall -Wextra -Weffc++ -pedantic-errors -g --coverage avl_tree_tests.cpp && ./a.out && gcov -mr avl_tree_tests.cpp
build_a_tree: clean binary_search_tree.h avl_tree.h build_a_tree.cpp
	g++ -std=c++17 -Wall -Wextra -Weffc++ -pedantic-errors -g build_a_tree.cpp && ./a.out