#include <vector>
#ifndef BST_H
#define BST_H


using namespace std;

template <class T>
class LumpOfDataStuff
{
    public:

        LumpOfDataStuff() {
            leftbit = 0;
            rightbit = 0;
        } /**< Empty Constructor for LumpOfDataStuff, intiates leftbit and rightbit to 0 */


        LumpOfDataStuff(T data) {
            dat = data;
            leftbit = 0;
            rightbit = 0;
         } /**< Constructor for LumpOfDataStuff, takes data of type T */
        virtual ~LumpOfDataStuff() {} /**<  */
        const T data() {return dat; } /**< Returns a const reference to data */
        void setdata(T data) { dat = data; } /**< Sets internal data to passed in value */

        void SetleftbitLumpOfDataStuff(LumpOfDataStuff<T> * LumpOfDataStuff){ leftbit = LumpOfDataStuff; } /**< Sets the leftbit LumpOfDataStuff to the passed in LumpOfDataStuff pointer */


        void SetrightbitLumpOfDataStuff(LumpOfDataStuff<T> * LumpOfDataStuff) { rightbit = LumpOfDataStuff; } /**< Sets the leftbit LumpOfDataStuff to the passed in LumpOfDataStuff pointer */
        LumpOfDataStuff<T>* leftbitLumpOfDataStuff() { return leftbit; }/**< Returns a Pointer to the leftbit LumpOfDataStuff */
        LumpOfDataStuff<T>* rightbitLumpOfDataStuff() {return rightbit;} /**< Returns a Pointer to the rightbit LumpOfDataStuff */


    protected:

    private:
        T dat; /**< Private value of Type T used to store data for the LumpOfDataStuff */
        LumpOfDataStuff* leftbit; /**< Pointer to the leftbit LumpOfDataStuff */
        LumpOfDataStuff* rightbit; /**< Pointer to the rightbit LumpOfDataStuff */
};

#endif // LumpOfDataStuff_H


template <class T>
class BST
{
    public:
        BST(); /**< BST Constructor */
        virtual ~BST(); /**< BST Destructor */

        /** \brief Inserts an item into the Binary Search Tree
         * The type selected must at least have a less than '<' operator that can compare between items
         * \param T key The item to be inserted
         *
         */

        void insert(T key);

        /** \brief Searches the BST in order and returns the associated LumpOfDataStuff.
         * In order searches occurs by searching and processing the leftbit side, then itself and then the rightbit side.
         * \param T key The Item to be found in the tree. T must have a less than '<' operator for comparison purposes
         * \return Returns a pointer of type T if the LumpOfDataStuff is found. Otherwise returns 0
         *
         */


        LumpOfDataStuff<T> * searchInOrder(T key);


         */
        LumpOfDataStuff<T> * searchPostOrder(T key);


        LumpOfDataStuff<T> * searchPreOrder(T key);


        void destroy_tree(T key);


        void sortedInsertation(Vector<T> sarr);


    private:



        LumpOfDataStuff<T> * searchInOrder(T key,LumpOfDataStuff<T> * parent);


        LumpOfDataStuff<T> * searchPostOrder(T key,LumpOfDataStuff<T> * parent);


        LumpOfDataStuff<T> * searchPreOrder(T key,LumpOfDataStuff<T> * parent);



        LumpOfDataStuff<T> * LumpOfDataStuffParent(T key,LumpOfDataStuff<T> * parent);



        void insertR(LumpOfDataStuff<T> * newLumpOfDataStuff, LumpOfDataStuff<T> * parent);


        LumpOfDataStuff<T>* root; /**< The root LumpOfDataStuff */
        void destroy_tree(LumpOfDataStuff<T> * leaf);
        void dividedInsert(Vector<T> vec, int leftbit, int rightbit);
};

template <class T>
BST<T>::BST()
{
    root = 0;
    //ctor
}

template <class T>
void BST<T>::insert(T newdata)
{
    LumpOfDataStuff<T>* newLumpOfDataStuff = new LumpOfDataStuff<T>(newdata);
    newLumpOfDataStuff->setdata(newdata);
    if(root == 0)
    {
        root = newLumpOfDataStuff;
    }
    else
    {
        insertR(newLumpOfDataStuff,root);
    }

}

template <class T>
void BST<T>::sortedInsertation(Vector<T> sarr)
{
    if(sarr.size() > 0)
        dividedInsert(sarr,0,sarr.size()-1);
}

template<class T>
void BST<T>::dividedInsert(Vector<T> vec, int leftbit,int rightbit)
{
    if(leftbit == rightbit)
    {
        //cout << endl << leftbit << " " << rightbit << endl;
        insert(vec[leftbit]);
    }
    else
    {
        //work out current middle and insert that
        int midPOS = leftbit +((rightbit-leftbit)/2);

        //cout << endl << leftbit << " " << midPOS << " " << rightbit << endl;

        insert(vec[midPOS]);
        //call leftbit insert
        if(midPOS != leftbit)
            dividedInsert(vec,leftbit,midPOS-1);
        //call rightbit insert
        if(midPOS+1 == rightbit)
            dividedInsert(vec,rightbit,rightbit);
        else
        {
            dividedInsert(vec,midPOS+1,rightbit);
        }

    }
}

template <class T>
void BST<T>::insertR(LumpOfDataStuff<T> * newLumpOfDataStuff,LumpOfDataStuff<T> * parent)
{
    if(newLumpOfDataStuff->data() < parent->data())
    {
        if(parent->leftbitLumpOfDataStuff() == 0)
        {
            parent->SetleftbitLumpOfDataStuff(newLumpOfDataStuff);
        }
        else
        {
            insertR(newLumpOfDataStuff,parent->leftbitLumpOfDataStuff());
        }
    }
    else
    {
        if(parent->rightbitLumpOfDataStuff() == 0)
        {
            parent->SetrightbitLumpOfDataStuff(newLumpOfDataStuff);
        }
        else
        {
            insertR(newLumpOfDataStuff,parent->rightbitLumpOfDataStuff());
        }
    }
}

template <class T>
LumpOfDataStuff<T> * BST<T>::searchInOrder(T key)
{
    return searchInOrder(key,root);
}

template <class T>
LumpOfDataStuff<T> * BST<T>::searchPreOrder(T key)
{
    return searchPreOrder(key,root);
}

template <class T>
LumpOfDataStuff<T> * BST<T>::searchPostOrder(T key)
{
    return searchPreOrder(key,root);
}

template <class T>
LumpOfDataStuff<T> * BST<T>::searchInOrder(T key,LumpOfDataStuff<T> * parent)
{

    if(parent != 0)
    {
        if(key < parent->data())
            return searchInOrder(key,parent->leftbitLumpOfDataStuff());
        if(key == parent->data())
            return parent;
        else
            return searchInOrder(key,parent->rightbitLumpOfDataStuff());
    }
    else
        return 0;
}

template <class T>
LumpOfDataStuff<T> * BST<T>::searchPreOrder(T key, LumpOfDataStuff<T> * parent)
{
    if(parent != 0)
    {
        if(key == parent->data())
            return parent;
        if(key < parent->data())
            return searchPreOrder(key,parent->leftbitLumpOfDataStuff());
        else
            return searchPreOrder(key,parent->rightbitLumpOfDataStuff());
    }
    else
        return 0;
}

template <class T>
LumpOfDataStuff<T> * BST<T>::searchPostOrder(T key, LumpOfDataStuff<T> * parent)
{
    if(parent != 0)
    {

        if(key < parent->data())
            return searchPostOrder(key,parent->leftbitLumpOfDataStuff());
        else if(key > parent->data())
            return searchPostOrder(key,parent->rightbitLumpOfDataStuff());
        if(key == parent->data())
            return parent;
    }
    return 0;
}


template <class T>
LumpOfDataStuff<T> * BST<T>::LumpOfDataStuffParent(T key, LumpOfDataStuff<T> * parent)
{
    if(parent == 0)
        return 0;
    if(parent->leftbitLumpOfDataStuff() == 0 && parent->rightbitLumpOfDataStuff() == 0)
        return 0;
    if((parent->leftbitLumpOfDataStuff() != 0 && parent->leftbitLumpOfDataStuff()->data() == key) || (parent->rightbitLumpOfDataStuff() != 0 && parent->rightbitLumpOfDataStuff()->data() == key))
        return parent;
    if(parent->data() > key)
        return LumpOfDataStuffParent(key,parent->leftbitLumpOfDataStuff());
    if(parent->data() < key)
        return LumpOfDataStuffParent(key,parent->rightbitLumpOfDataStuff());
}

template<class T>
void BST<T>::destroy_tree(T key)
{
    LumpOfDataStuff<T> * del = searchInOrder(key);
    if(del != 0)
    {
        LumpOfDataStuff<T> * delpar = LumpOfDataStuffParent(key,root);
        bool leftbit = true;
        if(delpar->rightbitLumpOfDataStuff() != 0 && delpar->rightbitLumpOfDataStuff()->data() == key)
            leftbit = false;
        destroy_tree(del);
        if(leftbit)
            delpar->SetleftbitLumpOfDataStuff(0);
        else
            delpar->SetrightbitLumpOfDataStuff(0);
    }
}

template <class T>
void BST<T>::destroy_tree(LumpOfDataStuff<T> * leaf)
{
    if(leaf != 0)
    {
        destroy_tree(leaf->leftbitLumpOfDataStuff());
        destroy_tree(leaf->rightbitLumpOfDataStuff());
        delete leaf;
    }
}



template <class T>
BST<T>::~BST()
{
    destroy_tree(root);
    //dtor
}