#ifndef __TREE_H__
#define __TREE_H__

#include <initializer_list>
#include <memory>
#include <chrono>
#include <optional>

#include "base_container.h"
#include "tree_node.h"
#include "errors.h"
#include "bst_iterator.hpp"
#include "reverse_bst_iterator.h"

using namespace std;

template <Comparable T>
class tree : public base_container
{
public:

    using value_type = T;
    using iterator = bst_iterator<T>;
    using const_iterator = bst_iterator<T>;
    using reverse_iterator = reverse_bst_iterator<T>;

    tree() noexcept;

    template<Comparable U>
    requires Convertable<U, T>
    explicit tree(tree<U> &tree);

    explicit tree(tree<T> &tree);

    tree(tree<T> &&tree) noexcept;

    template<Comparable U>
    requires Convertable<U, T>
    tree(initializer_list<U> list);

    template<Comparable U>
    requires Convertable<U, T>
    explicit tree(const U& value);

    template<input_iterator Iter>
    tree(const Iter &begin, const Iter &end);

    template<Comparable U>
    requires Convertable<U, T>
    tree(const size_t &size, U const *arr);

    template <Container C>
    requires Convertable<typename C::value_type, T>
    tree(const C &container);

    ~tree() = default;

    template <Container C>
    requires Convertable<typename C::value_type, T>
    tree<T> &operator = (const C &container);
    tree<T> &operator = (tree<T> &&tree) noexcept;
    tree<T> &operator = (const tree<T> &tree);

    template<Comparable U>
    requires Convertable<U, T>
    tree<T> &operator = (initializer_list<U> list);

    virtual bool is_empty() const noexcept;
    void clear();

    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> &merge(const tree<U> &tree) const;
    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> operator + (const tree<T> &tree) const;
    template<Comparable U>
    requires Convertable<U, T>
    tree<T> &operator += (const tree<T> &tree);

    template<Comparable U>
    requires Convertable<U, T>
    bool insert(const U& value);

    const optional<bst_iterator<T>> find(const T& value) const;
    bool delete_node(const T& value);
    bool delete_node(bst_iterator<T> &iter);

    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> union_trees(const tree<U> &other) const;
    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> operator | (const tree<U> &tree) const;
    tree<T> &operator |= (const tree<T> &tree);

    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> intersection_trees(const tree<U> &other) const;
    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> operator & (const tree<U> &tree) const;
    tree<T> &operator &= (const tree<T> &tree);

    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> difference_trees(const tree<U> &other) const;
    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> operator / (const tree<U> &tree) const;
    tree<T> &operator /= (const tree<T> &tree);

    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> symdifference_trees(const tree<U> &other) const;
    template<Comparable U>
    requires Convertable<T, Larger<T, U>> && Convertable<U, Larger<T, U>>
    tree<T> operator ^ (const tree<U> &tree) const;
    tree<T> &operator ^= (const tree<T> &tree);

    bool operator == (const tree<T> &tree) const noexcept;
    bool operator != (const tree<T> &tree) const noexcept;

    iterator begin() const noexcept;
    iterator end() const noexcept;
    reverse_iterator rbegin() const noexcept;
    reverse_iterator rend() const noexcept;

    virtual size_t size() const noexcept override;

protected:
    shared_ptr<tree_node<T>> get_head() const noexcept;

    void set_size(int value) noexcept;
    void reset_size() noexcept;
    void increment_size() noexcept;
    void decrement_size() noexcept;

    bool insert(shared_ptr<tree_node<T>> _node);

private:
    shared_ptr<tree_node<T>> head;
};

#include "tree.hpp"

#endif