#pragma once
    #include <cassert>
    #include <numeric>
    #include <functional>
    #include <limits>
    #include <vector>
    #include <algorithm>
    #include <avltree.hpp>

    template <class T>
    AVLTree<T>::AVLTree(T const &item)
    {
        root_=AVLTNode<T>::create(item);
        curr_=root_;
        parent_=nullptr;

        assert(is_a_binary_search_tree());
        assert(is_a_balanced_tree());
        assert(!is_empty());
        assert(item() == item);
        assert(current_exists());
        assert(current() == item);
    #ifndef __ONLY_BSTREE__
        assert(current_level() == 0);
        assert(height() == 0);
    #endif
    }

    #ifdef __ONLY_BSTREE__
    template <class T>
    void create_inserting_median(std::vector<T> const &data,
                                size_t begin,
                                size_t end,
                                AVLTree<T> &tree)
    {
        assert(begin <= end);
        assert(end <= data.size());
        assert(begin == end || data[begin] <= data[end - 1]);

        if (begin < end)
        {
            size_t median_idx = begin + (end - begin) / 2;
            tree.insert(data[median_idx]);
            create_inserting_median(data, begin, median_idx, tree);
            create_inserting_median(data, median_idx + 1, end, tree);
        }
    }


    template <class T>
    AVLTree<T>
    create_perfectly_balanced_bstree(std::vector<T> &data)
    {
        AVLTree<T> tree;

        std::sort(data.begin(), data.end());
        create_inserting_median(data, 0, data.size(), tree);

        return tree;
    }
    #endif //__ONLY_BSTREE__

    template <class T>
    bool AVLTree<T>::is_empty() const
    {
        if(root_==nullptr){
            return true;
        }

        return false;
    }

    template <class T>
    T const &AVLTree<T>::item() const
    {
        assert(!is_empty());

        return root_->item();
    }

    template <class T>
    bool AVLTree<T>::current_exists() const
    {
        if(curr_==nullptr){
            return false;
        }
        return true;
    }

    template <class T>
    T const &AVLTree<T>::current() const
    {
        assert(current_exists());

        return curr_->item();
    }

    template <class T>
    int AVLTree<T>::current_level() const
    {
        assert(current_exists());
        int level = 0;

        auto aux =curr_;
        while (aux != root_){
            level++;
            aux=aux->parent();
        }

        return level;
    }

    template <class T>
    AVLTree<T> AVLTree<T>::left() const
    {
        assert(!is_empty());
        AVLTree<T> subtree;

        subtree=AVLTree(root_->left());

        return subtree;
    }

    template <class T>
    AVLTree<T> AVLTree<T>::right() const
    {
        assert(!is_empty());
        AVLTree<T> subtree;

        subtree=AVLTree(root_->right());

        return subtree;
    }

    template <class T>
    size_t AVLTree<T>::size() const
    {
        size_t s = 0;

        if(is_empty()){
            return 0;
        }else{
            s=left().size()+1+right().size();
        }

        return s;
    }

    template <class T>
    int AVLTree<T>::height() const
    {
        int h = -1; // Por defecto para árbol vacío
        
        if (root_node() != nullptr)
        {
            h = root_node()->height();
        }

        return h;
    }

    template <class T>
    int AVLTree<T>::balance_factor() const
    {
        int bf = 0;
        
        if (root_node() != nullptr)
        {
            bf = root_node()->balance_factor();
        }
        
        return bf;
    }

    template <class T>
    bool AVLTree<T>::has(const T &k) const
    {
    #ifndef NDEBUG
        bool old_current_exists = current_exists();
        T old_current;
        if (old_current_exists)
            old_current = current();
    #endif

        bool found = false;

        if(!is_empty()){
            if(k<item()){
                found = left().has(k);
            }else if(k>item()){
                found = right().has(k);
            }else{
                return true;
            }
        }

    #ifndef NDEBUG
        assert(!old_current_exists || old_current == current());
    #endif
        return found;
    }

    /**
     * @brief infix process of a node.
     * The Processor must allow to be used as a function with a parameter  (the
     * item to be processed) and returning true if the process must continue or
     * false if not.
     * @param node is the node to be processed.
     * @param p is the Processor.
     * @return true if all the tree was in-fix processed.
     */
    template <class T, class Processor>
    bool infix_process(typename AVLTNode<T>::Ref node, Processor &p)
    {
        bool retVal = true;

        if(node!=nullptr){
            retVal=infix_process<T>(node->left(), p);
            if(retVal){
                retVal = p(node->item());
            }
            if(retVal){
            retVal=infix_process<T>(node->right(), p);
            }
        }

        return retVal;
    }

    template <class T>
    bool AVLTree<T>::is_a_binary_search_tree() const
    {
        bool is_bst = true;
        bool first_time=true;
        T last_val;

        auto p=[&last_val,&is_bst,&first_time](const T &node_item){
            if(first_time){
                first_time=false;
                last_val=node_item;
            }else{
                if(last_val>node_item){
                    is_bst=false;
                    return is_bst;
                }
                last_val=node_item;
            }
            return is_bst;
        };

        infix_process<T>(root_, p);
        return is_bst;
    }

template <class T>
bool AVLTree<T>::is_a_balanced_tree() const
{
    bool is_balanced = true;
    #ifndef __ONLY_BSTREE__
    if (!is_empty())
    {
        int bf = root_->balance_factor();
        if (bf < -1 || bf > 1)
            is_balanced = false;
        else
        {
            if (root_->left() != nullptr)
            {
                AVLTree<T> left_subtree(root_->left());
                is_balanced = left_subtree.is_a_balanced_tree();
                left_subtree.root_ = nullptr;
            }
            if (is_balanced && root_->right() != nullptr)
            {
                AVLTree<T> right_subtree(root_->right());
                is_balanced = right_subtree.is_a_balanced_tree();
                right_subtree.root_ = nullptr;
            }
        }
    }
    #endif
    return is_balanced;
}

    template <class T>
    void AVLTree<T>::create_root(T const &v)
    {
        assert(is_empty());

        root_=AVLTNode<T>::create(v);

        curr_ = root_;
        parent_ = nullptr;

        assert(is_a_binary_search_tree());
        assert(is_a_balanced_tree());
        assert(!is_empty());
        assert(item() == v);
        assert(current_exists());
        assert(current() == v);
    #ifndef __ONLY_BSTREE__
        assert(current_level() == 0);
        assert(height() == 0);
    #endif
    }

    template <class T>
    bool AVLTree<T>::search(T const &k)
    {
        bool found = false;
        curr_=root_;
        parent_=nullptr;

        while ((curr_!=nullptr) && (!found))
        {
            if (curr_->item()==k){
                found=true;
            }else{
                parent_=curr_;
                if (curr_->item()<k)
                {
                    curr_=curr_->right();
                }else{
                    curr_=curr_->left();

                }
                
            }
        }
        
        assert(!found || current() == k);
        assert(found || !current_exists());
        return found;
    }

    template <class T>
    void AVLTree<T>::insert(T const &k)
    {
        assert(is_a_binary_search_tree());
        assert(is_a_balanced_tree());

        if(is_empty()){
            create_root(k);
        } else if (!search(k)){
            curr_ = AVLTNode<T>::create(k);

            if (parent_->item() <= k){
                parent_->set_right(curr_);
            } else {
                parent_->set_left(curr_);
            }
            make_balanced();
        }


        assert(is_a_binary_search_tree());
        assert(is_a_balanced_tree());
        assert(current_exists());
        assert(current() == k);
    }


    template <class T>
    void AVLTree<T>::remove()
    {
        // check preconditions.
        assert(current_exists());

    #ifndef NDEBUG
        // the invariants only must be checked for the first recursive call.
        // We use a static variable to count the recursion levels.
        static int recursion_count = 0;
        recursion_count++;
        if (recursion_count == 1)
        {
            // Check invariants.
            assert(is_a_binary_search_tree());
            assert(is_a_balanced_tree());
        }
    #endif // NDEBUG

        bool replace_with_subtree = true;
        typename AVLTNode<T>::Ref subtree;

        if (curr_->left() == nullptr && curr_->right() == nullptr)
        {
            subtree = nullptr;
        }
        else if (curr_->right() == nullptr)
        {
            subtree = curr_->left();
        }
        else if (curr_->left() == nullptr)
        {
            subtree = curr_->right();
        }
        else
        {
            replace_with_subtree = false;
        }

        if (replace_with_subtree)
        {
            if (parent_ == nullptr)
            {
                root_ = subtree;
            }
            else if (parent_->right() == curr_)
            {
                parent_->set_right(subtree);
            }
            else
            {
                parent_->set_left(subtree);
            }

            curr_ = nullptr;

            assert(check_parent_chains());
            make_balanced();
            assert(check_parent_chains());
        }
        else
        {
            auto tmp=curr_;
            find_inorder_sucessor();
            tmp->set_item(curr_->item());
            remove();
        }

    #ifndef NDEBUG
        // We come back so the recursion count must be decreased.
        recursion_count--;
        assert(recursion_count >= 0);
        if (recursion_count == 0)
        {
            // Only check for the last return.
            // Check invariants.
            assert(is_a_binary_search_tree());
            assert(is_a_balanced_tree());

            // Check postconditions.
            assert(!current_exists());
        }
    #endif
    }

    template <class T>
    AVLTree<T>::AVLTree(typename AVLTNode<T>::Ref const &root)
    {
        root_=root;
        curr_=root_;
        parent_=nullptr;

        assert(is_a_binary_search_tree());
        assert(is_a_balanced_tree());
        assert(root_node() == root);
        assert(current_node() == root);
        assert(parent_node() == nullptr);
    }

    template <class T>
    void AVLTree<T>::set_left(AVLTree<T> &subtree)
    {
        assert(!is_empty());

        curr_->set_left(subtree.root_node());

        assert(subtree.is_empty() || left().item() == subtree.item());
        assert(!subtree.is_empty() || left().is_empty());
    }

    template <class T>
    void AVLTree<T>::set_right(AVLTree<T> &subtree)
    {
        assert(!is_empty());
        
        curr_->set_right(subtree.root_node());

        assert(subtree.is_empty() || right().item() == subtree.item());
        assert(!subtree.is_empty() || right().is_empty());
    }

    template <class T>
    typename AVLTNode<T>::Ref const &AVLTree<T>::current_node() const
    {
        return curr_;
    }

    template <class T>
    typename AVLTNode<T>::Ref &AVLTree<T>::current_node()
    {
        return curr_;
    }

    template <class T>
    void AVLTree<T>::set_current_node(typename AVLTNode<T>::Ref const &new_c)
    {
        curr_=new_c;

        assert(current_node() == new_c);
    }

    template <class T>
    typename AVLTNode<T>::Ref const &AVLTree<T>::root_node() const
    {
        return root_;
    }

    template <class T>
    typename AVLTNode<T>::Ref &AVLTree<T>::root_node()
    {
        return root_;
    }

    template <class T>
    void AVLTree<T>::set_root_node(typename AVLTNode<T>::Ref const &new_root)
    {
        root_=new_root;
        
        assert(root_node() == new_root);
    }

    template <class T>
    typename AVLTNode<T>::Ref const &AVLTree<T>::parent_node() const
    {
        return parent_;
    }

    template <class T>
    typename AVLTNode<T>::Ref &AVLTree<T>::parent_node()
    {
        return parent_;
    }

    template <class T>
    void AVLTree<T>::set_parent_node(typename AVLTNode<T>::Ref const &new_p)
    {
        parent_=new_p;

        assert(parent_node() == new_p);
    }

    template <class T>
    void AVLTree<T>::find_inorder_sucessor()
    {
        assert(current_exists());
        assert(is_a_binary_search_tree());

    #ifndef NDEBUG
        T old_curr = current();
    #endif
        
        parent_=curr_;
        curr_=curr_->right();

        while (curr_->left() != nullptr)
        {
            parent_=curr_;
            curr_=curr_->left();
        }

        assert(current_exists() && current_node()->left() == nullptr);
    #ifndef NDEBUG
        assert(current() > old_curr);
    #endif
    }

    template <class T>
    typename AVLTNode<T>::Ref AVLTree<T>::rotate(typename AVLTNode<T>::Ref &P, int dir)
    {
        assert(P != nullptr);
        assert(dir == 0 || dir == 1);
        assert(P->child(1 - dir) != nullptr);
    #ifdef __DEBUG__
        if (__DEBUG__ > 1)
            std::clog << "Rotating to " << (dir == 0 ? "left" : "right") << " on key " << P->item() << std::endl;
    #endif
        auto G=P->parent();
        auto gpDir=0;
        if (G != nullptr && G->child(0) == P){
            gpDir = 0;
        }else{
            gpDir = 1;
        }
        auto N = P->child(1 - dir);
        auto CN=N->child(dir);

        P->set_child(1-dir, CN); 
        N->set_child(dir, P); 

        
        if (G != nullptr) 
        {
            G->set_child(gpDir, N);
        }else{
            N->set_parent(nullptr);
            set_root_node(N);
        }
        return N;
    }

    template <class T>
    void AVLTree<T>::make_balanced()
    {
    #ifdef __ONLY_BSTREE__
        return; // for a BSTree there is no need to balance.
    #else
        auto P = parent_node(); // the subtree root node.

        while (P != nullptr){
            P->update_height();
            int bfP = P->balance_factor();

            // 3. Si el subárbol está desbalanceado (|bf| > 1)
            if (std::abs(bfP) > 1) 
            {
                // Determinar la dirección del hijo "pesado"
                // Si bfP < 0, el peso está a la izquierda (0). Si no, a la derecha (1).
                int dir = (bfP < 0) ? 0 : 1;
                auto N = P->child(dir);
                int bfN = N->balance_factor();

                // Comprobar si los signos coinciden para decidir rotación simple o doble
                if (bfP * bfN >= 0) 
                {
                    // CASOS 1 o 2: Rotación simple
                    // Si el desequilibrio es a la izquierda (dir=0), rotamos a la derecha (1-0=1)
                    P = rotate(P, 1 - dir);
                } 
                else 
                {
                    // CASOS 3 o 4: Rotación doble
                    // Primero rotamos el hijo en su propia dirección
                    rotate(N, dir);
                    // Luego rotamos el padre en la dirección opuesta
                    P = rotate(P, 1 - dir);
                }
            }
            P = P->parent();
        }
        // Update the cursor's parent_ node if needed.
        if (current_exists())
            set_parent_node(current_node()->parent());

        assert(!current_exists() || current_node()->parent() == parent_node());
    #endif //__ONLY_BSTREE__
    }

    template <class T>
    bool AVLTree<T>::check_parent_chains() const
    {
    #ifdef __ONLY_BSTREE__
        return true; // for a BSTree there is no need to check this.
    #else
        if (!is_empty())
        {
            std::function<void(typename AVLTNode<T>::Ref, std::vector<typename AVLTNode<T>::Ref>)> go_down;
            go_down = [&go_down](typename AVLTNode<T>::Ref node, std::vector<typename AVLTNode<T>::Ref> branch) -> void
            {
                if (node->left() != nullptr || node->right() != nullptr)
                {
                    branch.push_back(node);
                    if (node->left())
                        // go down by the left
                        go_down(node->left(), branch);
                    if (node->right())
                        // go down by the right
                        go_down(node->right(), branch);
                }
                else
                {
                    // The node is a leaf node, so check the branch
                    // to the tree root node.
                    typename AVLTNode<T>::Ref parent = node->parent();
                    int idx = static_cast<int>(branch.size()) - 1;
                    while (parent && idx >= 0)
                    {
                        assert(parent == branch[idx]);
                        --idx;
                        parent = parent->parent();
                    }
                    assert(idx == -1 && parent == nullptr);
                }
            };
            std::vector<typename AVLTNode<T>::Ref> branch;
            go_down(root_node(), branch);
        }
        return true;
    #endif
}

template <class T>
std::tuple<int, int>
compute_min_max_branch_length(AVLTree<T> const &tree)
{
int min_path_l = std::numeric_limits<int>::max();
    int max_path_l = 0;

    if (tree.is_empty()){
        min_path_l = -1;
        max_path_l = -1;
    }else{
        std::function<void(AVLTree<T> const &, int)> go_down;
        go_down = [&go_down, &min_path_l, &max_path_l](AVLTree<T> const &subtree, int level) -> void
        {
            bool has_left  = !subtree.left().is_empty();
            bool has_right = !subtree.right().is_empty();

            if (!has_left && !has_right){
                if (level < min_path_l) min_path_l = level;
                if (level > max_path_l) max_path_l = level;
            }else{
                if (has_left)
                    go_down(subtree.left(), level + 1);
                if (has_right)
                    go_down(subtree.right(), level + 1);
            }
        };

        go_down(tree, 0);
    }

    return std::make_tuple(min_path_l, max_path_l);
}

    template <class T>
    AVLTreeIterator<T> AVLTree<T>::begin() const
    {
        typename AVLTNode<T>::Ref node=root_node();
            
        while (node != nullptr && node->left() != nullptr){
            node = node->left();
        }

        return AVLTreeIterator<T>(node);
    }

    template <class T>
    AVLTreeIterator<T> AVLTree<T>::end() const
    {
        return AVLTreeIterator<T>(nullptr);
    }


    template <class T>
    std::ostream &
    operator<<(std::ostream &out, const AVLTree<T> &tree) noexcept
    {
        if (tree.is_empty())
        {
            out << "[]";
        }
        else
        {
            out << "[ " << tree.item() << " ";
            out << tree.left() << " ";
            out << tree.right() << " ]";
        }
        return out;
    }

    template <class T>
    std::istream &
    operator>>(std::istream &in, AVLTree<T> &tree) noexcept(false)
    {
        tree=AVLTree<T>();

        std::string token;

        if(!(in>>token)){
            throw std::runtime_error("Wrong input format.");
        }

        if(token=="["){
            std::istringstream iss;
            T t;
            AVLTree<T> l,r;

            if(!(in >> t)){
                throw std::runtime_error("Wrong input format.");
            }
            tree.create_root(t);
            if(!(in >> l)){
                throw std::runtime_error("Wrong input format.");
            }
            tree.set_left(l);
            if(!(in >> r)){
                throw std::runtime_error("Wrong input format.");
            }
            tree.set_right(r);
            if(!(in >> token) || token != "]"){
                throw std::runtime_error("Wrong input format.");
            }
        } else if(token != "[]"){
            throw std::runtime_error("Wrong input format.");
        }

        if (!tree.is_a_binary_search_tree())
            throw std::runtime_error("It is not a binary search tree");
        
    #ifndef __ONLY_BSTREE__
        if (!tree.is_a_balanced_tree())
            throw std::runtime_error("It is not an avl tree");
    #endif

        return in;
    }