#pragma once
#include <algorithm>

///////////////////////
//// BINARY TREES ////
//////////////////////

template<typename T>
struct TreeNode {
    T n;
    TreeNode<T>* left;
    TreeNode<T>* right;

    ~TreeNode() {
        std::cout << left << " " << right << std::endl;
        delete left;
        delete right;
    }
};

template<typename T, typename = decltype(std::declval<T>() < std::declval<T>()), typename = decltype(std::declval<T>() == std::declval<T>())>
class BinTree {
    public:
        TreeNode<T>* root;
        BinTree() = default;

        ~BinTree() { delete root; }

        // finding
        T* find(T n) {
            TreeNode<T>* result = find(n, root);
            return result == nullptr ? nullptr : &(result->n);
        }

        // deleting
        void operator-= (T n) {
            TreeNode<T>* node_ptr = find(n, root);
            if (node_ptr) {del(node_ptr);}
        }

        //inserting
        bool operator+= (T n) {
            return insert(n, root);
        }

        bool contains(T n) {
            return find(n) != nullptr;
        }

        int size(TreeNode<T>* current) {
            return (!current) ? 0 : 1 + size(current->left) + size(current->right);
        }

        int size() {
            return size(root);
        }

        int get_degree(T n) {
            return get_degree(n, root, 0);
        }

    private:
        TreeNode<T>* find(T n, TreeNode<T>* start) {
            if (start == nullptr || n == start->n) {
                return start;
            }
            if (n < start->n) {
                return find(n, start->left);
            } else {
                return find(n, start->right);
            }
        }

        // returns the minimum node of a subtree
        TreeNode<T>* find_min(TreeNode<T>* current) {
            while (current->left != nullptr) { current = current->left;}
            return current;
        }

        // returns the parent of the child arg
        TreeNode<T>* find_parent(TreeNode<T>* child, TreeNode<T>* current) {
            if (current == nullptr) {
                return nullptr;
            }
            if (current->left == child || current->right == child) {
                return current;
            } else {
                TreeNode<T>* result_left = find_parent(child, current->left);
                if (result_left != nullptr) {
                    return result_left;
                } else {
                    return find_parent(child, current->right);
                }
            }
        }

        // delete a node (or to get technical a value) from the tree
        void del(TreeNode<T>*& to_delete) {
            if (to_delete->right != nullptr) {
                // RIGHT = NODE
                TreeNode<T>* min = find_min(to_delete->right);
                TreeNode<T>* min_parent = find_parent(min, to_delete);

                // reassign the pointers around min
                if (min->right != nullptr) {
                    min_parent->left = min->right;
                }

                // copy the value at min to to_delete
                to_delete->n = std::move(min->n);

                // delete the min node
                if (min_parent->left == min) {
                    min_parent->left = nullptr;
                } else {
                    min_parent->right = nullptr;
                }
                min->left = nullptr;
                min->right = nullptr;
                delete min;

            } else if (to_delete->left != nullptr) {
                // LEFT = NODE, RIGHT = NULLPTR
                // let left child take over the to_delete node
                TreeNode<T>* left_child = to_delete->left;
                to_delete->n = std::move(left_child->n);
                to_delete->left = left_child->left;
                to_delete->right = left_child->right;

                // delete the left_child node
                left_child->left = nullptr;
                left_child->right = nullptr;
                delete left_child;
            } else {
                // LEFT = NULLPTR, RIGHT = NULLPTR
                // no children, so just delete
                if (to_delete == root) {
                    root = nullptr;
                    delete to_delete;
                    return;
                }
                TreeNode<T>* parent = find_parent(to_delete, root);
                if (parent->left == to_delete) {
                    parent->left = nullptr;
                } else {
                    parent->right = nullptr;
                }
                delete to_delete;
            }
        }

        bool insert(const T to_insert, TreeNode<T>*& current) {
            if (current == nullptr) {
                current = new TreeNode<T> {to_insert, nullptr, nullptr };
                return true;
            }

            if (current->n == to_insert) {
                return false;
            }

            if (current->n > to_insert) {
                return insert(to_insert, current->left);
            }

            return insert(to_insert, current->right);

        }

        int get_degree(const T& n, TreeNode<T>* current, int current_degree) {
            if (current->n == n) {
                return current_degree;
            }

            int result_left = -1;
            int result_right = -1;
            if (current->left != nullptr) {
                result_left = get_degree(n, current->left, current_degree + 1);
            }
            if (current->right != nullptr) {
                result_right = get_degree(n, current->right, current_degree + 1);
            }
            return std::max(result_left, result_right);
        }
};

///////////////////////
/////// GRAPHS ///////
//////////////////////

template<typename T>
struct Node {
    int id;
    T data;
};

template<typename T>
struct Edge {
    Node<T>* node_a;
    Node<T>* node_b;
    int weight;
};

template<typename T>
class Graph {
    public:
        // Public fields
        Node<T>* nodes;
        Edge<T>* edges;
        const int max_nodes;
        const int max_edges;

        // Constructor
        Graph<T>(int max_nodes_arg, int max_edges_arg):
            nodes {new Node<T>[max_nodes_arg]},
            edges {new Edge<T>[max_edges_arg]},
            max_nodes{max_nodes_arg},
            max_edges{max_edges_arg}{};

        // Destructor
        ~Graph() {
            delete[] edges;
            delete[] nodes;
            std::cout << "graph destroyed.\n";
        }

        // Adding a Node (with +=)
        void operator+=(Node<T> node) {
            if (current_amount_nodes < max_nodes) {
                insert(node);
                current_amount_nodes++;
            } else {
                throw std::out_of_range("maximum amount of nodes reached");
            }
        }
        int get_amount_nodes() {return current_amount_nodes;}
        int get_amount_edges() {return current_amount_edges;}
        void inc_amount_edges() {current_amount_edges++;}
    private:
        int current_amount_nodes = 0;
        int current_amount_edges = 0;

        /**
         *@
        */
        void insert(Node<T> const& toInsert) {
            int i = 0;
            while (i < (max_nodes - 1) && nodes[i].id > toInsert.id) {
                i++;
            }

            for(int j = i; j < get_amount_nodes(); j++) {
                nodes[j + 1] = nodes[j];
            }
            nodes[i] = toInsert;
        }
};

template<typename T>
void add_edge(Graph<T>& graph, Node<T>* node_a, Node<T>* node_b, int weight) {
    auto i = graph.get_amount_edges(); // next position to write to
    if (i < graph.max_edges) {
        graph.edges[i] = Edge<T>{ node_a, node_b, weight };
        graph.inc_amount_edges();
    } else {
        throw std::out_of_range("maximum amount of edges reached");
    }
}