#ifndef __tree_HPP__
#define __tree_HPP__

#include "tree_node.h"

using namespace std;

template <Comparable T>
tree<T>::tree() noexcept
{
    this->_size = 0;
    this->head = nullptr;
}

template <Comparable T>
template<Comparable U>
requires Convertable<U, T>
tree<T>::tree(tree<U> &tree)
{
    this->_size = 0;
    this->head = nullptr;

    for (auto el:tree)
    {
        insert(el);
    }
}

template <Comparable T>
tree<T>::tree(tree<T> &tree)
{
    this->_size = 0;
    this->head = nullptr;

    for (auto el:tree)
    {
        insert(el);
    }
}

template <Comparable T>
tree<T>::tree(tree<T> &&tree) noexcept
{
    this->_size = tree.size();
    this->head = tree.head;
}

template <Comparable T>
template<Comparable U>
requires Convertable<U, T>
tree<T>::tree(const U &value)
{
    insert(value);
}


template <Comparable T>
template<input_iterator Iter>
tree<T>::tree(const Iter &begin, const Iter &end)
{
    for (auto iter = begin; iter != end; ++iter)
    {
        insert(*iter);
    }
}

template <Comparable T>
template<Comparable U>
requires Convertable<U, T>
tree<T>::tree(initializer_list<U> list)
{
    if (list.size() == 0)
    {
        tree();
        return;
    }

    for (auto &el:list)
    {
        insert(el);
    }
}

template <Comparable T>
template<Comparable U>
requires Convertable<U, T>
tree<T>::tree(const size_t &size, U const *arr)
{
    for (size_t i = 0; i < size; ++i)
    {
        insert(arr[i]);
    }
}

template <Comparable T>
template <Container C>
requires Convertable<typename C::value_type, T>
tree<T>::tree(const C &container)
{
    this->_size = container.size();
    for (auto iter:container)
        insert(iter);
}

template<Comparable T>
template <Container C>
requires Convertable<typename C::value_type, T>
tree<T> &tree<T>::operator = (const C &container)
{
    this->_size = 0;
    this->head = nullptr;
    for (auto iter:container)
    {
        insert(iter);
    }

    return *this;
}

template<Comparable T>
tree<T> &tree<T>::operator = (const tree<T> &tree)
{
    this->_size = 0;
    this->head = nullptr;

    for (auto iter:tree)
    {
        insert(iter);
    }

    return *this;
}

template<Comparable T>
template<Comparable U>
requires Convertable<U, T>
tree<T> &tree<T>::operator = (initializer_list<U> list)
{
    this->_size = 0;
    this->head = nullptr;

    for (auto &el:list)
    {
        insert(el);
    }

    return *this;
}

template <Comparable T>
tree<T> &tree<T>::operator = (tree<T> &&tree) noexcept
{
    this->_size = tree.size();
    this->head = tree.head;

    return *this;
}

template <Comparable T>
void tree<T>::set_size(int value) noexcept
{
    this->_size = value;
}

template <Comparable T>
void tree<T>::reset_size() noexcept
{
    this->_size = 0;
}

template <Comparable T>
size_t tree<T>::size() const noexcept
{
    return this->_size;
}

template <Comparable T>
void tree<T>::increment_size() noexcept
{
    this->_size++;
}

template <Comparable T>
void tree<T>::decrement_size() noexcept
{
    this->_size--;
}

template <Comparable T>
bool tree<T>::insert(shared_ptr<tree_node<T>> node)
{
    if (!head)
    {
        head = node;
    }
    else
    {
        shared_ptr<tree_node<T>> current = head;
        shared_ptr<tree_node<T>> parent;

        while (current)
        {
            parent = current;
            if (node->get() < current->get())
            {
                current = current->get_left();
            }
            else if (node->get() > current->get())
            {
                current = current->get_right();
            }
            else
            {
                return false;
            }
        }

        if (node->get() < parent->get())
        {
            parent->set_left(node);
        }
        else
        {
            parent->set_right(node);
        }
    }

    increment_size();

    return true;
}

template <Comparable T>
const optional<bst_iterator<T>> tree<T>::find(const T& value) const
{
    shared_ptr<tree_node<T>> current = head;

    while (current)
    {
        if (value == current->get())
        {
            optional<bst_iterator<T>> result(current);
            return result;
        }
        else if (value < current->get())
        {
            current = current->get_left();
        }
        else
        {
            current = current->get_right();
        }
    }

    return nullopt;
}

template <Comparable T>
bool tree<T>::delete_node(const T& value)
{
    shared_ptr<tree_node<T>> current = head;
    shared_ptr<tree_node<T>> parent = nullptr;
    bool found = false;

    while (current && !found)
    {
        if (value == current->get())
        {
            found = true;
        }
        else if (value < current->get())
        {
            parent = current;
            current = current->get_left();
        }
        else
        {
            parent = current;
            current = current->get_right();
        }
    }

    if (!current)
    {
        return false;
    }

    if (!current->get_left() && !current->get_right())
    {
        if (!parent)
        {
            head = nullptr;
        }
        else if (current == parent->get_left())
        {
            parent->set_left(nullptr);
        }
        else
        {
            parent->set_right(nullptr);
        }
    }
    else if (!current->get_left() || !current->get_right())
    {
        shared_ptr<tree_node<T>> child = current->get_left() ? current->get_left() : current->get_right();

        if (!parent)
        {
            head = child;
        }
        else if (current == parent->get_left())
        {
            parent->set_left(child);
        }
        else
        {
            parent->set_right(child);
        }
    }
    else
    {
        shared_ptr<tree_node<T>> min_node = current->get_right();
        shared_ptr<tree_node<T>> min_parent = current;
        while (min_node->get_left())
        {
            min_parent = min_node;
            min_node = min_node->get_left();
        }
        current->set(min_node->get());
        if (min_node == min_parent->get_left())
        {
            min_parent->set_left(min_node->get_right());
        }
        else
        {
            min_parent->set_right(min_node->get_right());
        }
    }

    decrement_size();

    return true;
}

template <Comparable T>
bool tree<T>::delete_node(bst_iterator<T> &iter)
{
    return delete_node(*iter);
}

template <Comparable T>
template<Comparable U>
requires Convertable<U, T>
bool tree<T>::insert(const U& value)
{
    shared_ptr<tree_node<T>> node = nullptr;
    try
    {
        node = shared_ptr<tree_node<T>>(new tree_node<T>(value));
    }
    catch (bad_alloc &error)
    {
        auto timenow = chrono::system_clock::to_time_t(chrono::system_clock::now());
        throw memory_error(ctime(&timenow), __FILE__, typeid(tree).name(), __FUNCTION__);
    }

    return insert(node);
}

template <Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> tree<T>::union_trees(const tree<U> &other) const
{
    auto result = ::tree<Larger<T, U>>(*this);

    for (auto el:other)
    {
        result.insert(el);
    }

    return result;
}

template <Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> tree<T>::intersection_trees(const tree<U> &other) const
{
    auto result = ::tree<Larger<T, U>>(*this);
    for (bst_iterator<T> iter = begin(); iter != end(); ++iter)
    {
        T value = *iter;
        if (other.find(value).has_value())
        {
            result.insert(value);
        }
    }

    return result;
}

template <Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> tree<T>::difference_trees(const tree<U> &other) const
{
    auto result = ::tree<Larger<T, U>>(*this);
    for (bst_iterator<T> iter = begin(); iter != end(); ++iter)
    {
        T value = *iter;
        if(!other.find(value).has_value())
        {
            result.insert(value);
        }
    }

    return result;
}

template <Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> tree<T>::symdifference_trees(const tree<U> &other) const
{
    auto res1 = difference_trees(other);
    auto res2 = other.difference_trees(*this);
    auto res = res1.union_trees(res2);

    return res;
}

template <Comparable T>
bool tree<T>::is_empty(void) const noexcept
{
    return 0 == this->_size;
}

template <Comparable T>
void tree<T>::clear(void)
{
    while (head)
    {
        delete_node(head->get());
    }
}

template<Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> &tree<T>::merge(const tree<U> &tree) const
{
    auto result = ::tree<Larger<T, U>>(*this);
    bool insert_code = true;
    for (auto el:tree)
    {
        insert_code = result.insert(el);
        if (!insert_code)
        {
            auto timenow = chrono::system_clock::to_time_t(chrono::system_clock::now());
            throw merge_error(ctime(&timenow), __FILE__, typeid(tree).name(), __FUNCTION__);
        }
    }

    return result;
}

template<Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> tree<T>::operator + (const tree<T> &tree) const
{
    return merge(tree);
}

template<Comparable T>
template<Comparable U>
requires Convertable<U, T>
tree<T> &tree<T>::operator += (const tree<T> &tree)
{
    bool insert_code = true;
    for (auto el:tree)
    {
        insert_code = insert(el);
        if (!insert_code)
        {
            auto timenow = chrono::system_clock::to_time_t(chrono::system_clock::now());
            throw merge_error(ctime(&timenow), __FILE__, typeid(tree).name(), __FUNCTION__);
        }
    }

    return *this;
}

template <Comparable T>
bst_iterator<T> tree<T>::begin() const noexcept
{
    return bst_iterator<T>(head);
}

template <Comparable T>
bst_iterator<T> tree<T>::end() const noexcept
{
    return bst_iterator<T>(nullptr);
}

template <Comparable T>
reverse_bst_iterator<T> tree<T>::rbegin() const noexcept
{
    return reverse_bst_iterator<T>(head);
}

template <Comparable T>
reverse_bst_iterator<T> tree<T>::rend() const noexcept
{
    return reverse_bst_iterator<T>(nullptr);
}

template <Comparable T>
bool tree<T>::operator == (const tree<T> &tree) const noexcept
{
    bool result = true;
    auto iter1 = begin();
    auto iter2 = tree.begin();
    for (; result && iter1 != end() && iter2 != tree.end(); ++iter1, ++iter2)
    {
        if (iter1 == end() || iter2 == tree.end())
            result = false;

        if (*iter1 != *iter2)
            result =  false;
    }

    return result;
}

template <Comparable T>
bool tree<T>::operator != (const tree<T> &tree) const noexcept
{
    return !(*this == tree);
}

template <Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> tree<T>::operator | (const tree<U> &tree) const
{
    return union_trees(tree);
}

template <Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> tree<T>::operator / (const tree<U> &tree) const
{
    return difference_trees(tree);
}

template <Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> tree<T>::operator ^ (const tree<U> &tree) const
{
    return symdifference_trees(tree);
}

template <Comparable T>
template<Comparable U>
requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
tree<T> tree<T>::operator & (const tree<U> &tree) const
{
    return intersection_trees(tree);
}

// template <Comparable T>
// tree<T> tree<T>::operator + (const tree<T> &tree) const noexcept
// {
//     return merge(tree);
// }

// template <Comparable T>
// tree<T> &tree<T>::operator += (const tree<T> &tree) noexcept
// {
//     *this = merge(tree);
//     return *this;
// }

template <Comparable T>
tree<T> &tree<T>::operator |= (const tree<T> &tree)
{
    *this = union_trees(tree);
    return *this;
}

template <Comparable T>
tree<T> &tree<T>::operator /= (const tree<T> &tree)
{
    *this = difference_trees(tree);
    return *this;
}

template <Comparable T>
tree<T> &tree<T>::operator ^= (const tree<T> &tree)
{
    *this = symdifference_trees(tree);
    return *this;
}

template <Comparable T>
tree<T> &tree<T>::operator &= (const tree<T> &tree)
{
    *this = intersection_trees(tree);
    return *this;
}

template <Comparable T>
shared_ptr<tree_node<T>> tree<T>::get_head(void) const noexcept
{
    return this->head;
}

template <Comparable T>
ostream& operator <<(ostream& os, const tree<T>& tree)
{
    for (auto it:tree)
    {
        os << it << " ";
    }
    os << endl;

    return os;
}

#endif