/**
 * CopyRight F. J. Madrid-Cuevas <fjmadrid@uco.es>
 *
 * Sólo se permite el uso de este código en la docencia de las asignaturas sobre
 * Estructuras de Datos de la Universidad de Córdoba.
 *
 * Está prohibido su uso para cualquier otro objetivo.
 */
#pragma once

#include <cassert>
#include <exception>
#include <memory>
#include <iostream>
#include <queue>

#include <btree_utils.hpp>

template <class T>
int compute_height(const BTree<T> &t)
{
    int height = 0;

    if(t.is_empty()){
        height=-1;
        return height;
    }else{
        height=1+std::max(compute_height(t.left()), compute_height(t.right()));
    }
    return height;
}

template <class T>
size_t compute_size(const BTree<T> &t)
{
    size_t ret_val = 0;

    if(!(t.is_empty())){
        ret_val=1+compute_size(t.left())+compute_size(t.right());
    }
    return ret_val;
}

template <class T>
bool prefix_process(const BTree<T> &tree, BinaryTreeProcessor<T> &p)
{
    bool retVal = true;
        if(!(tree.is_empty())){
            retVal = p(tree.item());
            if(retVal){
                retVal=prefix_process(tree.left(), p);
            }
            if(retVal){
                retVal=prefix_process(tree.right(), p);
            }
        }

    return retVal;
}

template <class T>
bool infix_process(const BTree<T> &tree, BinaryTreeProcessor<T> &p)
{
    bool retVal = true;
        if(!(tree.is_empty())){
            retVal=infix_process(tree.left(), p);
            if(retVal){
                retVal = p(tree.item());
            }
            if(retVal){
                retVal=infix_process(tree.right(), p);
            }
        }

    return retVal;
}

template <class T>
bool postfix_process(const BTree<T> &tree, BinaryTreeProcessor<T> &p)
{
    bool retVal = true;
        if(!(tree.is_empty())){
            retVal=postfix_process(tree.left(), p);
            if(retVal){
                retVal=postfix_process(tree.right(), p);
            }
            if(retVal){
                retVal = p(tree.item());
            }
        }
    return retVal;
}

template <class T>
bool breadth_first_process(const BTree<T> &tree, BinaryTreeProcessor<T> &p)
{
    bool go_on = true;
    if (tree.is_empty()) 
        return go_on;

    std::queue<BTree<T>> q;
    q.push(tree);

    while (!q.empty() && go_on) {
        BTree<T> subtree = q.front();
        q.pop();

        // Procesamos el nodo actual
        go_on = p(subtree.item());

        // Si el proceso debe continuar, añadimos los hijos a la cola
        if (go_on) {
            if (!subtree.left().is_empty()) {
                q.push(subtree.left());
            }
            if (!subtree.right().is_empty()) {
                q.push(subtree.right());
            }
        }
    }
    return go_on;
}

template <class T>
std::ostream &
print_prefix(std::ostream &out, const BTree<T> &tree)
{

    BinaryTreeProcessor<T> p = [&out](const T &it) {
        out << it << " ";
        return true;
    };

    prefix_process(tree, p);
    return out;
}

template <class T>
std::ostream &
print_infix(std::ostream &out, const BTree<T> &tree)
{
    BinaryTreeProcessor<T> p = [&out](const T &it) {
        out << it << " ";
        return true;
    };

    infix_process(tree, p);
    return out;
}

template <class T>
std::ostream &
print_postfix(std::ostream &out, const BTree<T> &tree)
{
    BinaryTreeProcessor<T> p = [&out](const T &it) {
        out << it << " ";
        return true;
    };

    postfix_process(tree, p);
    return out;
}

template <class T>
std::ostream &
print_breadth_first(std::ostream &out, const BTree<T> &tree)
{
    BinaryTreeProcessor<T> p = [&out](const T &it) {
        out << it << " ";
        return true;
    };

    breadth_first_process(tree, p);
    return out;
}

template <class T>
bool search_prefix(const BTree<T> &tree, const T &it, size_t &count)
{
    bool found = false;
    count = 0;

    BinaryTreeProcessor<T> p = [&found, &count, it](const T &node_item) {
        count++; 
        if (node_item == it) {
            found = true;
            return false; 
        }
        return true;
    };

    prefix_process(tree, p);
    return found;
}

template <class T>
bool search_infix(const BTree<T> &tree, const T &it, size_t &count)
{
    bool found = false;
    count = 0;
    
    BinaryTreeProcessor<T> p = [&found, &count, it](const T &node_item) {
        count++; 
        if (node_item == it) {
            found = true;
            return false; 
        }
        return true; 
    };

    infix_process(tree, p);
    return found;
}

template <class T>
bool search_postfix(const BTree<T> &tree, const T &it, size_t &count)
{
    bool found = false;
    count = 0;

    BinaryTreeProcessor<T> p = [&found, &count, it](const T &node_item) {
    count++; 
        if (node_item == it) {
            found = true;
            return false; 
        }
        return true;
    };

    postfix_process(tree, p);
    return found;
}

template <class T>
bool search_breadth_first(const BTree<T> &tree, const T &it, size_t &count)
{
    bool found = false;
    count = 0;

    BinaryTreeProcessor<T> p = [&found, &count, it](const T &node_item) {
    count++; 
        if (node_item == it) {
            found = true;
            return false; 
        }
        return true;
    };

    breadth_first_process(tree, p);
    return found;
}

template <class T>
bool check_btree_in_order(const BTree<T> &tree)
{
    bool ret_val = true;
    bool first_time=true;
    T last_val;

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

    infix_process(tree, p);
    return ret_val;
}

template <class T>
bool has_in_order(const BTree<T> &tree, T const &v)
{
    assert(check_btree_in_order<T>(tree));
    bool ret_val = false;

    if (!tree.is_empty())
    {
        if (v == tree.item()) {
            ret_val = true;
        }
        else if (v < tree.item()) {
            ret_val = has_in_order(tree.left(), v);
        }
        else {
            ret_val = has_in_order(tree.right(), v);
        }
    }
    
    return ret_val;
}

template <class T>
void insert_in_order(BTree<T> &&tree, T const &v)
{
    assert(check_btree_in_order<T>(tree));

    if (tree.is_empty()) {
        tree = BTree<T>(v);
    } 
    else if (v < tree.item()) {
        auto left_tree = tree.left();
        insert_in_order(std::move(left_tree), v);
        tree.set_left(left_tree);
    } 
    else if (v > tree.item()) {
        auto right_tree = tree.right();
        insert_in_order(std::move(right_tree), v);
        tree.set_right(right_tree);
    }
    
    assert(has_in_order<T>(tree, v));
}

template <class T>
void insert_in_order(BTree<T> &tree, T const &v)
{
    insert_in_order<T>(std::move(tree), v);
}