/* definitions are residing in this header since that's how templates get
 * expanded, we could have a separate bst.cpp is compiler supports export keyword,
 * instantiations of code are compiled along with the translation units that spawn them
 */

#ifndef _BST_H_
#define _BST_H_

#include <iostream>
#include <cstdio>
#include <cassert>
#include "node.h"

using namespace std;

template <class T>
class Bst
{
    public:
        Bst();
        Bst(const Bst &);
        /* Bst(Node<T> &); */
        Bst(const T &); /* above was hairy, just startup a bst from a T t */
        ~Bst();

        int insert(const T &);
        int remove(const T &);
        int list(void) const;

    private:
        unsigned int element_count;
        void traverse(Node<T> *) const;
        void free();
        void freePostOrder(Node<T> *);

    protected:
        Node<T> *root;
};

template <class T>
Bst<T>::Bst() : element_count(0), root(NULL)
{
}

template <class T>
Bst<T>::Bst(const Bst& tree)
{
    this->free();
    /* still a shallow copy, dupe it! */
    this->root = tree.root;
}

template <class T>
Bst<T>::Bst(const T& t)
{
    Node<T> *first = new Node<T>(t);
    this->root = first;
}

template <class T>
Bst<T>::~Bst()
{
    this->free();
}


template <class T>
int Bst<T>::insert(const T& e)
{
    Node<T> *iter = this->root;
    Node<T> *new_node = new Node<T>(e);

    while (iter)
    {
        if (iter->getVal() == e)
        {
            std::cout << e << " is already in the tree" << std::endl;
            return 1;
        }
        else if (iter->getVal() < e)
        {
            if (&iter->getRight() == NULL)
            {
                iter->setRight((new_node));
                return 1;
            }
            else
                iter = &iter->getRight(); /* taking addr of alias/reference? */
        }
        else
        {
            if (&iter->getLeft() == NULL)
            {
                iter->setLeft((new_node));
                return 1;
            }
            else
                iter = &iter->getLeft();
        }
    }

    std::cout << "creating root node " << e << endl;
    this->root = new_node;

    return 0;
}

template <class T>
int Bst<T>::remove(const T& e)
{
    /* assign the value of leftmost subtree of nodes right child to node to be
     * removed, and delete the leaf where value was taken from */
    if (!this->root)
        return 1;

    Node<T> *iter = this->root;
    while (iter)
    {
        if (iter->getVal() < e)
        {   /* working on right subtree */
            if (&iter->getRight() && (iter->getRight().getVal() == e)) /* lookahead */
            {
                Node<T> *child_left = &iter->getRight().getLeft();
                Node<T> *child_right = &iter->getRight().getRight();
                Node<T> *node_toremove = &iter->getRight();

                if (!child_left && !child_right)
                {   /* leaf */
                    delete node_toremove;
                    iter->setRight(NULL);
                }
                else if (child_left && child_right)
                {   /* node to be remove has 2 children */
                    if (&child_right->getLeft() == NULL)
                    {   /* move up righ subtree if right child has no left child */
                        child_right->setLeft(&node_toremove->getLeft());
                        iter->setRight(child_right);
                        delete node_toremove;
                    }
                    else
                    {
                        Node<T> *iter = child_right;
                        while (&iter->getLeft().getLeft())
                            iter = &iter->getLeft(); /* seek */

                        node_toremove->setVal(iter->getLeft().getVal());
                        delete &iter->getLeft();
                        iter->setLeft(NULL);
                    }
                }
                else
                {   /* got one child, delete e and link child to grandfather */
                    if (child_left)
                        iter->setRight(child_left);
                    else
                        iter->setRight(child_right);
                    delete node_toremove;
                }

                return 0;
            }
            else
                iter = &iter->getRight();
        }
        else if (iter->getVal() > e)
        {    /* working with left subtree */
            if (&iter->getLeft() && (iter->getLeft().getVal() == e)) /* lookahead */
            {

                Node<T> *child_left = &iter->getLeft().getLeft();
                Node<T> *child_right = &iter->getLeft().getRight();
                Node<T> *node_toremove = &iter->getLeft();

                if (!child_left && !child_right)
                {   /* leaf */
                    delete node_toremove;
                    iter->setLeft(NULL);
                    return 0;
                }
                else if (child_left && child_right)
                {   /* node to be remove has 2 children */
                    if (&child_right->getLeft() == NULL)
                    {   /* move up righ subtree if right child has no left child */
                        child_right->setLeft(&node_toremove->getLeft());
                        iter->setLeft(child_right);
                        delete node_toremove;
                    }
                    else
                    {
                        Node<T> *iter = child_right;
                        while (&iter->getLeft().getLeft())
                            iter = &iter->getLeft(); /* seek */

                        node_toremove->setVal(iter->getLeft().getVal());
                        delete &iter->getLeft();
                        iter->setLeft(NULL);
                    }
                }
                else
                {   /* got one child, delete e and link child to grandfather */
                    if (child_left)
                        iter->setLeft(child_left);
                    else
                        iter->setLeft(child_right);
                    delete node_toremove;
                }

                return 0;
            }
            else
                iter = &iter->getLeft();
        }
        else
        {   /* root removal */
            /* assign root left subtree into lowest leaf in the right subtree */
            if ((&this->root->getLeft() == NULL) && (&this->root->getRight() == NULL))
            {
                delete this->root;
                this->root = NULL;
                return 0;
            }

            Node<T> *iter = &this->root->getRight();
            while (&iter->getLeft())
                iter = &iter->getLeft();
            iter->setLeft(&this->root->getLeft()); /* set left subtree */
            this->root = &root->getRight();
            delete this->root;
            return 0;
        }
    }

    /* not in the tree */
    return 2;
}

template <class T>
int Bst<T>::list(void) const
{
    if (!this->root)
        return 1;

    this->traverse(this->root);
    return 0;
}

template <class T>
void Bst<T>::traverse(Node<T> *node) const
{
    if (!node)
        return;

    this->traverse(&node->getLeft());
    std::cout << node->getVal() << " " << endl;
    this->traverse(&node->getRight());
}

template <class T>
void Bst<T>::free(void)
{
    if (this->root)
        this->freePostOrder(this->root);
}

template <class T>
void Bst<T>::freePostOrder(Node<T> *node)
{
    if (!node)
        return;

    this->freePostOrder(&node->getLeft());
    this->freePostOrder(&node->getRight());
    #ifdef DEBUGMSG
    std::cout << "nuking " << node->getVal() << std::endl; 
    #endif
    delete node;
}

#endif