#ifdef CMPT225RBTREE

/*

    CMPT 225 D2 Summer 2014  --- Assignment 4 (RedBlack Tree)

    Student:    Echo Liu
    Professor:  John Edgar

    Class: RedBlack Tree

    Description:
        Before we describe what a red black tree is we must go over briefly what a binary search tree is. A binary
        search tree or BST for short is a tree in which each node has at most two children with the left and right children having
        the following set of properties.
            1. The children themselves are roots of their own subtrees
            2. The left child and its associated subtree is less than the "main" root of the whole tree
            3. The right child and its associated subtree is greater than the "main" root of the whole tree
        The order the keys inserted into the BST affect the shape of the tree, if the keys come in sorted order
        then the tree becomes anaemic closely resembling a linear chain of nodes forcing its performance to be O(n) instead of
        O(logn).

        A Red Black tree is a variation of a binary search tree in which preserves the logarithmic height of a binary search tree
        by colouring a node red or black and also imposing the following set of properties to make the tree approximately balanced.
            1. No consecutive red nodes are allowed along any path.
            2. The root is always black
            3. Every red node has two black children
            4. The amount of black nodes from the root to any descendent leaves on a simple path are equal, the root does
            not get factored into the calculation this calculation is the black height.
            5. Consecutive black nodes along a path are allowed


    Prof: John Edgar


*/
#include <iostream>
#include <string>
//#include "RedBlackTree.h"
using namespace std;


/*
    Start of Node constructors
*/

/* This constructor takes a datum as its parameter and initializes its parent, left, and right pointer to the default NULL as well
    and isBlack to true false i.e red
*/
template <class T>
Node<T>::Node(T Tdata)
{
    data = Tdata;
    parent = NULL;
    left = NULL;
    right = NULL;
    isBlack = false;
}
/*
    This constructor takes in a datum and three node pointers as its parameters. The
    three parameters represent left, right, and parent respectively and the default colour to red [false]
*/
template <class T>
Node<T>::Node(T Tdata, Node* pL, Node *pR, Node* pParent)
{
    data = Tdata;
    parent = pParent;
    left = pL;
    right = pR;
    isBlack = false;
}
/*
    Node constructor that has four parameters
    that takes in a datum, three node pointers and a colour which is denoted by a boolean flag
    the three node pointers represent the values of the left, right, and parent pointer respectively

*/
template <class T>
Node<T>::Node(T Tdata, Node *pL, Node* pR, Node *pParent, bool bColour)
{
    data = Tdata;
    parent = pParent;
    left = pL;
    right = pR;
    parent = pParent;
    isBlack = bColour;
}
/*
    C'tor that takes in four parameters
    a datum, node pointers representing left and right child respectively and a colour value by a boolean
*/
template <class T>
Node<T>::Node(T Tdata, Node *pL, Node* pR, bool bColour)
{
    data = Tdata;
    parent = NULL;
    left = pL;
    right = pR;
    isBlack = bColour;
}

/*
    End of Node class constructors,

    Red Black tree constructor is below, initializing the root pointer to NULL
    and other private attributes to defaults

*/
template <class T>
RedBlackTree<T>::RedBlackTree()
{
    root = NULL;
    aDumpData = NULL;
    iNodePos = 0;
    aDumpTemp = NULL;

}
/*
    RB Copy constructor which uses an internal helper function to make a deep copy of the tree
*/
template <class T>
RedBlackTree<T>::RedBlackTree(const RedBlackTree<T> &rhs)
{
    root = CloneTree(rhs.root);
}

/*
    Overloaded assignment operator which returns a pointer to a RB [Red Black] Tree object,
        Logic:
            1. Run alias test
            2. Deallocate memory for calling object
            3. Make deep copy of target
*/
template <class T>
RedBlackTree<T> & RedBlackTree<T>::operator=(const RedBlackTree<T> &rhs)
{
    if(this != &rhs)
    {
        // deallocate memory for the calling object

        removeAll();
        // make a deep copy of its target
        root = CloneTree(rhs.root);
    }
    return *this;

}
/*
    Destructor for RB tree,
    uses a helper function to deallocate all nodes allocated on the heap to build the tree
*/
template <class T>
RedBlackTree<T>::~RedBlackTree()
{
    removeAll();
}

/*
    Internal private helper function that gets called by the public insert method
        Takes in a pointer to a node as a parameter
        Returns true if the insert is successful false if the client attempts to insert duplicate items into the tree
        pointer x determines point of insertion
        pointer y determines the node before x so we know where to wedge the node we want to insert
*/
template <class T>
bool RedBlackTree<T>::bInsert(Node<T>* pNode)
{
    Node<T> *y = NULL;
    Node<T> *x = root;
    bool bIns = false; // return value
    bool bFound = false;

    // false to indicate that the value is not already in the tree, true to denote that the value is already there
    if(bPrivSearch(pNode->data, root) == true)
    {
        bIns = false;
        bFound = true;
    }
    if(bFound == false)
    {
        while(x != NULL)
        {
            y = x;
            if(pNode->data < x->data)
            {
                x = x->left;

            }
            else
            {
                x = x->right;

            }
        }  // while loop
        pNode->parent = y;
        if(y == NULL)
        {
            root = pNode;
        }
        else if(pNode->data < y->data)
        {
            y->left = pNode;
        }
        else
        {
            y->right = pNode;
        }
        pNode->left = NULL;
        pNode->right = NULL;
        pNode->isBlack = false;
        vInsertFixViolation(pNode);
        bIns = true;
    }

    return bIns;
}


/*
    Helper function that allows us to fix any violations that we may have when inserting into the tree
        Returns nothing since the function is void, takes in a node pointer as a parameter

        Violations that can occur when inserting a node into an RB tree
            1.  the node's left uncle is red
            2.  the node's uncle is black and the node is a right child
            3.  the node's uncle is black and the node is a left child
            =========================================================
            Symmetric cases
            =========================================================
            4.  the node's right uncle is red
            5.  the node's uncle is black and the node is a left child
            6.  the node's uncle is black and the node is a right child
        How to fix these issues, note case 1,2, and 3 and 4,5,6 are symmetrical counterparts
            To fix case one we just perform colour changes by making the node's parent black and its uncle also black
            To fix case two, we just simply make case 2 fall into case 3 since the two cases are not mutually exclusive
                To enter case 2 via 3 we immediately perform a left rotation about the node we have just inserted
                Afterwards we can fix case 3 by performing colour changes and a right rotation about that node's grandparent
        Return type is void and the function does not return anything
        Parameter is a node pointer which represents the node we would like to insert

*/
template <class T>
void RedBlackTree<T>::vInsertFixViolation(Node<T> *pNode)
{
    Node<T> *y;
    while((pNode != root)&&(pNode->parent->isBlack == false))// start of while
    {
        //start if
        if((pNode->parent != NULL )&&(pNode->parent == pNode->parent->parent->left))
        {
            y = pNode->parent->parent->right; // the right uncle of y
            if((y!=NULL)&&(y->isBlack == false))
            {
                pNode->parent->isBlack = true;
                y->isBlack = true;
                pNode->parent->parent->isBlack = false;
                pNode = pNode->parent->parent;
            }
            else
            {
                if(pNode == pNode->parent->right)
                {
                    pNode = pNode->parent;
                    LeftRotation(pNode);
                }
                if(pNode->parent != NULL)
                {
                    pNode->parent->isBlack = true;
                    if(pNode->parent->parent != NULL)
                    {
                        pNode->parent->parent->isBlack = false;//
                        RightRotation(pNode->parent->parent);
                    }

                }

            }
        }// end if
        else
        {//
        /*start of else*/
            if(pNode->parent == pNode->parent->parent->right)
            {
                y = pNode->parent->parent->left; // uncle of node pNode on the left side;
                if((y!= NULL)&&(y->isBlack == false))
                {
                    pNode->parent->isBlack = true;
                    y->isBlack = true;
                    pNode->parent->parent->isBlack = false;
                    pNode = pNode->parent->parent;
                }
                else
                {
                    if(pNode == pNode->parent->left)
                    {
                        pNode = pNode->parent;
                        RightRotation(pNode);
                    }
                    if(pNode->parent != NULL)
                    {
                        pNode->parent->isBlack = true;
                        if(pNode->parent->parent != NULL)
                        {
                            pNode->parent->parent->isBlack = false;
                            LeftRotation(pNode->parent->parent);
                        }
                    }

                }
            }
        }// end of else
    }// end of while
    root->isBlack = true;
}
/*
    A private helper function that will enable us to return a pointer to a node in a tree,
    if it doesn't exist we just simply return NULL
    else we keep searching the right or left subtrees as needed until we reach the appropriate spot in the
    tree in which its node contains the appropriate datum that we are trying to find.
    Takes in two parameters: the data we would like to search for and a node pointer indicating where we would
    like to start the recursion
    Return: a pointer to the node indicating where in the tree our data is contained in, if it doesn't exist it simply returns NULL
*/
template <class T>
Node<T>* RedBlackTree<T>::pSearchPriv(T dataS, Node<T> *pTr)
{
    if(pTr == NULL)
    {
        return NULL;
    }
    else if(dataS < pTr->data)
    {
        return pSearchPriv(dataS,pTr->left);
    }
    else if(pTr->data < dataS)
    {
        return pSearchPriv(dataS,pTr->right);
    }
    else
    {
        return pTr;
    }

}

/*
    Public search function:
    Takes in the data we would like to find as a parameter
    Returns true or false depending if we find that specific data or not.
*/
template <class T>
bool RedBlackTree<T>::search(T data) const
{
    return bPrivSearch(data,root);
}
/*
    Follows the same structure as the other privateSearch function
    but returns a boolean instead
    takes in a datum to search for and a node pointer to start the recursion as parameters
*/
template <class T>
bool RedBlackTree<T>::bPrivSearch(T dataS, Node<T> *pTr) const
{//
    if((pTr == NULL))
    {
        return false;
    }
    else if(dataS < pTr->data)
    {
        return bPrivSearch(dataS,pTr->left);
    }
    else if(pTr->data < dataS)
    {
        return bPrivSearch(dataS, pTr->right);
    }
    else
    {
        return true;
    }
}
/*
    Void helper function that enables us to perform a left rotation
    takes in a Node pointer which indicates the node we are rotating about
    while maintaining the BST properties

    Return is none since the function is void
*/
template <class T>
void RedBlackTree<T>:: LeftRotation(Node<T> *pNode)
{
    Node<T> *y = pNode->right; // y is pNode's right child
    pNode->right = y->left; // make y's left subtree  into Pnode's right

    if(y->left != NULL)
    {
        y->left->parent = pNode;
    }
    y->parent = pNode->parent; // link the parent of y to pNode's
    if(pNode->parent == NULL) // special case if we are rotating about the root
    {
        root = y;
    }
    else
    {
        if(pNode == pNode->parent->left) // checking if pNode is a left or right child
        {
            pNode->parent->left = y;
        }
        else
        {
            pNode->parent->right = y;
        }
    }

    y->left = pNode; // reposition subtrees
    pNode->parent = y;
}
/*
    Private helper function that enables right rotations
    takes in a node pointer that indicates the node we perform the
    rotation about,

    Return type is void so function does not return anything
*/
template <class T>
void RedBlackTree<T>::RightRotation(Node<T> *pNode)
{
    Node<T> *y = pNode->left; // y is pNode's left child
    pNode->left = y->right; // make pNode's left subtree become y's right
    if(y->right != NULL)
    {
        y->right->parent = pNode;
    }
    y->parent = pNode->parent;
    if(pNode->parent == NULL) // special case if pNode is the root
    {
        root = y;
    }
    else
    {
        if(pNode == pNode->parent->right) // checking if the node we want to rotate about is a right or left child
        {
            pNode->parent->right = y;
        }
        else
        {
            pNode->parent->left = y;
        }
    }
    /* repositioning subtrees */
    y->right = pNode;
    pNode->parent = y;
}

/*
    Private helper function that enables us to print the whole tree
    takes in a pointer to a node to indicate the start of the recursion
    return type is none since it is void
*/
template <class T>
void RedBlackTree<T>::PrintRecurse(Node<T> *pTr)
{
    int i = 0;
    if(pTr != NULL)
    {
        //i++;
        PrintRecurse(pTr->left);
        std::cout << pTr->data << "";
        //i++;
        std::cout << "[" ;
        if(pTr->isBlack == true)
        {
            std::cout << "Black" << " ";
        }
        else
        {
            std::cout << "Red" << " ";
        }
        std::cout << "]";
        if(pTr->parent != NULL)
        {
            std::cout<< "(" << "parent is " << pTr->parent->data << ")" <<endl;
        }
        else
        {
            std::cout << endl;
        }
        PrintRecurse(pTr->right);
        //i++;

    }
    return;
}
/*
    Public print function that takes in no parameters and calls a private
    helper print function which starts its recursion from the root
*/
template <class T>
void RedBlackTree<T>::Print()
{
    PrintRecurse(root);
}
/*
    Public insert function which takes a data that one wants to insert
    and calls a private helper function which takes a node allocated in dynamic memory as a parameter
    Returns a boolean
*/
template <class T>
bool RedBlackTree<T>::insert(T datum)
{
    Node<T> *pNewNode = new Node<T>(datum);
    pNewNode->isBlack = true;
    pNewNode->parent = NULL;
    pNewNode->left = NULL;
    pNewNode->right = NULL;
    return bInsert(pNewNode);
}

/*
    Helper function that allows us to find the successor node in the Red-Black tree
    takes in a pointer to a node as a parameter to indicate the start of the recursion
    returns the minimum value in the subtree it was starting the recursion from
*/
template <class T>
Node<T>* RedBlackTree<T>::findMinPriv(Node<T> *pNode)
{
    if(pNode == NULL)
    {
        return NULL;
    }
    if(pNode->left == NULL)
    {
        return pNode;
    }
    return findMinPriv(pNode->left);
}
/*
    Public function for debugging purposes,
    calls a private helper function so we can recursively
    search the left subtree for the appropriate node
*/
template <class T>
T RedBlackTree<T>::findMin()
{
    Node<T> *pTr = findMinPriv(root);

    T iMin;
    if(pTr != NULL)// check if the pointer is NULL first since the tree can be empty
    {
        iMin = pTr->data;
    }
    return iMin;
}
/*
    Public function that takes in a datum that we would like to remove as a parameter
    returns false if the removal was unsuccessful or the datum is already there
    returns true  if the removal was successful or the datum wasn't inserted previously
        calls a private helper function that does the removal
*/
template <class T>
bool RedBlackTree<T>::remove(T data)
{
    bool bRmv = false;
    Node<T>* pNodetoRemove = pSearchPriv(data,root);
    if(pNodetoRemove!= NULL)
        bRmv = bRemove(pNodetoRemove);
    else
    {
        bRmv = false;
    }
    return bRmv;
}
/*
    Private helper function that enables us to reassign pointers as needed to remove the node
    while preserving the BST tree properties
*/
template <class T>
bool RedBlackTree<T>::bRemove(Node<T> *pNode)
{
    Node<T> *y;
    Node<T> *x;
    bool bYOrigColour = false;
    bool bFound = false;// boolean flag indicating to us if the node is found or not
    bool bDel = false; // return value
    /* Checks if the node we would like to remove exists*/
    if ((pNode != NULL)&&(bPrivSearch(pNode->data,root) == true))
    {
        bDel = false;
        bFound = true;
    }


    // Case 1: node has no children = remove
    // Case 2: node has 1 children = move right or left, ignore node
    // Case 3: node has 2 children = find the successor and swap contents
    // case that z has one or no children else z has two children

    y = ((pNode->left == NULL)) || ((pNode->right == NULL)) ?
    pNode:
    findMinPriv(pNode->right);
    // the node we want to remove

    x =  (y->left != NULL)?
    y->left:
    y->right;
    // indicates point of insertion

    if(x != NULL)
    {
        x->parent = y->parent;
    }
    if(y->parent == NULL)
    {
        root = x;
    }
    else
    {
        if( y == y->parent->left)
        {
            y->parent->left = x;
        }
        else
        {
            y->parent->right = x;
        }

    }
    if( y!= pNode)
    {
        pNode->data = y->data;
    }
    if( (x!= NULL)&& (y->isBlack == true))
    {
        vPrivDeleteFix(x);
    }
    delete y;
    y = NULL;
    bDel = true;
    return bDel;
}

/*
    Helper function that allows us to fix RB tree violations when deleting a node from a tree
    Eight cases to consider, the latter three are symmetrical:
    1. The child of the node we want to remove [x] has a red sibling
    2. The child of the node we want to remove has a sibling that is black and both of that sibling's children are black
    3. The child of the node we want to remove has a sibling that is black, the sibling's left child is red, and the sibling's right child is black
    4. The child of the node we want to remove has a black sibling and that sibling's right child is red.
    ================================================================================================================================================

    Symmetric cases:
        5. The child of the node we want to remove [x] has a red sibling
        6. The child of the node we want to remove has a sibling that is black and both of that sibling's children are black
        7. The child of the node we want to remove has a sibling that is black, the sibling's right child is red, and the sibling's left child is black
        8. The child of the node we want to remove has a black sibling and that sibling's left child is red.
    How to deal with case 1/[5]:
        Switch the colours of the sibling and x's parent then perform a left rotation about x's parent
        Case 1 can then be converted to case 2,3,4 or 6,7,8 depending on the shape of the tree
    How to deal with case 2/[6]:
        Both of the sibling's children are black. In addition that sibling node is also black so one can take a
        black off both the child of the node we want to remove. To compensate we add an extra black to the x's parent
    How to deal with case 3/[7]:
        We swap the colours of x's sibling and its left [right] child and then perform a right [left] rotation
    How to deal with case 4/[8]:
        Perform colour changes and a left [right] rotation
    Return type is none since the function is of type void parameter is a node pointer which represents
    the child of the node we want to remove

*/
template <class T>
void RedBlackTree<T>::vPrivDeleteFix(Node<T> *pNode)
{
    //Node *rootChild = root->left;
    Node<T> *w; // pointer to allow us to find pNode's sibling which will take y's place in the tree
    while((pNode!= NULL)&&(pNode != root) && (pNode->isBlack == true))
    {
        if(pNode == pNode->parent->left)
        {
            w = pNode->parent->right;
            if((w!= NULL)&&(w->isBlack == false))// case 1
            {
                w->isBlack = true;
                pNode->parent->isBlack = false;
                LeftRotation(pNode->parent);
                w = pNode->parent->right;
            }
            if((w != NULL)&& (w->left!=NULL) && (w->right!=NULL)
                && (w->left->isBlack == true) && (w->right->isBlack == true))
            {
                w->isBlack = false;
                pNode = pNode->parent;
            }
            else
            {
                if((w != NULL) && (w->left!=NULL) && (w->right!=NULL)
                    &&(w->right->isBlack == true))
                {
                    w->left->isBlack = true;
                    w->isBlack = false;
                    RightRotation(w);
                    w = pNode->parent->right;
                }
                if((w!= NULL) && (pNode->parent != NULL))
                {
                    w->isBlack = pNode->parent->isBlack;
                }
                if(pNode->parent != NULL)
                {
                    pNode->parent->isBlack = true;
                }
                if( (w != NULL) && (w->right != NULL))
                {
                    w->right->isBlack = true;
                }
                if(pNode->parent != NULL)
                {
                    LeftRotation(pNode->parent);
                }
                pNode = root;
            }
        }
        else
        {
            if(pNode == pNode->parent->right)
            {
                w = pNode->parent->left;
                if( (w!= NULL) && (w->isBlack == false))
                {
                    w->isBlack = true;
                    pNode->parent->isBlack = false;
                    if(pNode->parent != NULL)
                    {
                        RightRotation(pNode->parent);
                        w = pNode->parent->left;
                    }

                }
                if( (w != NULL) && (w->left!=NULL) && (w->right!=NULL)
                    && (w->right->isBlack == true) && (w->left->isBlack == true))
                {
                    w->isBlack = false;
                    pNode = pNode->parent;
                }
                else
                {
                    if((w != NULL) && (w->left != NULL) && (w->right!=NULL)
                        &&(w->left->isBlack == true))
                    {
                        w->right->isBlack = true;
                        w->isBlack = false;
                        LeftRotation(w);
                        w = pNode->left;
                    }
                    if((w!= NULL) && (pNode->parent != NULL))
                    {
                        w->isBlack = pNode->parent->isBlack;
                    }
                    if(pNode->parent != NULL)
                    {
                        pNode->parent->isBlack = true;
                    }
                    if( (w != NULL) && (w->left != NULL))
                    {
                        w->left->isBlack = true;
                    }
                    if(pNode->parent != NULL)
                    {
                        RightRotation(pNode->parent);
                    }
                    pNode = root; // to exit while loop
                }
            }
        }
    }
    if(pNode != NULL)
    {
        pNode->isBlack = true;
    }

}

/*
    A private helper function that enables us to find the height of a binary search tree
    The function takes in a Node pointer which indicates the start of the recursion, the
    return type is an integer representing the height
    Logic is as follows:
        1. if the node is Null then the tree has height zero.
        2. else we employ the recursive definition of height to perform our desired calculation

*/
template <class T>
int RedBlackTree<T>:: heightHelper(Node<T> *pNode) const
{
    int iHeight = 0;
    if(pNode == NULL)
    {
        iHeight = 0;
    }
    else
    {
        iHeight = 1+ max(heightHelper(pNode->right),heightHelper(pNode->left));
    }
    return iHeight;
}
/*
    Private helper that enables us to find the amount of nodes in a binary search tree
    Takes in a Node pointer as a parameter which indicates the start of the recursion
    the return type is the amount of nodes in both of the subtrees including the root
*/
template <class T>
int RedBlackTree<T>::sizeHelper(Node<T> *pNode) const
{
    if(pNode == NULL)
    {
        return 0;
    }
    else
    {
        return (sizeHelper(pNode->left)+ sizeHelper(pNode->right))+1;
    }
}
/*
    Public function that enables us to find the height of a tree
    no parameters are taken and the return type is an integer value denoting
    the amount of nodes in the tree
*/
template <class T>
int RedBlackTree<T>::height() const
{
    return heightHelper(root);
}
/*
    Public function that allows us to find the amount of nodes in the tree
    no parameters are taken and the return type is an integer value denoting the amount of
    nodes in the tree
*/
template <class T>
int RedBlackTree<T>::size() const
{
     return sizeHelper(root);
}
/*
    Internal private function that takes in an node pointer in which to start the recursion so we clear all
    of the nodes in the binary search tree or any tree that contains two children, note we employ a post order traversal because
    we want to clear both the right and left subtrees before visiting the node. In addition, we set our node to NULL for good practice
*/
template <class T>
void RedBlackTree<T>:: DeleteTreePrivate(Node<T>* pNode)
{
    if(pNode != NULL)
    {
        DeleteTreePrivate(pNode->left);
        DeleteTreePrivate(pNode->right);
        delete pNode;
    }
    pNode = NULL;
}
/*
    Public remove function that allows us to deallocate all of the nodes in the binary search tree
    takes in no parameters and doesn't return anything
    Calls a private helper function that deletes all of the nodes of the tree with the recursion starting at the root
*/
template <class T>
void RedBlackTree<T>::removeAll()
{
    if (root)
    {
        DeleteTreePrivate(root);
        root = NULL;
    }
}
/*
    Private helper function that enables us to deep copy the binary search tree
*/
template <class T>
Node<T> *RedBlackTree<T>::CloneTree(const Node<T>* pTr)
{
    Node<T> *pNewRB = NULL;
    if(pTr != NULL)
    {
        //pNewRB = new Node<T>(pTr->data,NULL,NULL, NULL,pTr->isBlack); >> this piece was used for debugging purposes
        pNewRB = new Node<T>(pTr->data,pTr->left,pTr->right, pTr->parent,pTr->isBlack);
        pNewRB->left = CloneTree(pTr->left);
        pNewRB->right = CloneTree(pTr->right);
    }
    return pNewRB;
}
/*
    This function takes in no parameters and returns the root as a NODE POINTER!
*/
template <class T>
Node<T>* RedBlackTree<T>:: getRoot()
{
    return root;
}
/*
    The dump function takes in an integer reference parameter that returns the total amount of items in the array
    The function returns an array in dynamic memory
*/
template <class T>
T* RedBlackTree<T>::dump(int& iSize)
{
    //int iStart = 0;
    iSize = size();
    int iPosi = 0;
    iNodePos = 0;

    if(iSize > 0)
    {
        aDumpData = new T[iSize];
        dumpPrivate(root,iPosi);
    }
    return aDumpData;

}
/*
    This helper function takes in two parameters, a pointer to a node in which to start the recursion
    and an integer reference parameter to check if we incremented our index correctly 'i.e iNodePos
*/
template <class T>
void RedBlackTree<T>::dumpPrivate(Node<T> *pNode,int &iPos)
{
    if(pNode != NULL)
    {
        dumpPrivate(pNode->left,iPos);
        aDumpData[iNodePos] = pNode->data;
        iNodePos++;
        dumpPrivate(pNode->right,iPos);
    }

}
/*
    Ok we must admit, we are making a risky assumption that our first parameter is less than our second parameter however in practice
    we are probably going to have to switch that around.
    The function takes the following parameters:
        two values that represent the range that the user is looking for
        an integer reference parameter that denotes the amount of items in the returned array
    Returns a pointer to an array in dynamic memory
    If there are no values between the first and second parameters the function returns NULL
    i.e search(15,19,n) returns NULL if the array looks like this
    [1,5,11,13,14,21,25,30,63]
    If the first parameter equals second parameter and that particular value is in the tree then the function should return that value
    i.e search(0,0,n) should return 0 if the array looks like this
    [0.33.99]
    but returns NULL if the array looks like this
    [33,99]
    If the tree is empty it should return NULL
*/

template <class T>
T *RedBlackTree<T>::search(T firstParem, T secondParem, int &iNumElements)
{
    iNumElements = size();
    int iLocIndex = 0;
    T *aDumpBetweenValues = NULL;
    iNodePos = 0;
    firstvalue = firstParem;
    secondvalue = secondParem;
    if(iNumElements > 0) // checks if the tree is empty
    {
        aDumpTemp = new T[iNumElements]; // allocates enough memory for all of the nodes in the tree
        searchPrivate(root,iLocIndex);// helper function to search the tree for the datums in the requested bounds
        if(iLocIndex > 0)// checks if there are any values in between the two parameters
        {
            aDumpBetweenValues = new T[iLocIndex]; // allocates enough memory for all of the values that are between parameter 1 and parameter 2
            // we use a local memory allocation so we don't have to worry about that memory block used by a previous search call


            // copies the values yielded from searchPrivate over to the memory allocated just enough for all of the values in
            // between the bounds
            for(int i = 0;i<iLocIndex;i++)
            {
                aDumpBetweenValues[i] = aDumpTemp[i];
            }
            // we set our iNumElements integer parameter to the amount of values that are in between our bounds
            iNumElements = iLocIndex;
        }
        else
        {
            iNumElements = 0;
        }
        if(aDumpTemp!= NULL)
        {
            delete [] aDumpTemp;
            aDumpTemp = NULL;
        }

    }
    else
    {
        iNumElements = 0;
    }
    return aDumpBetweenValues;

}
/*
    Helper function that will allow us to search the left and right subtrees
        Parameters are a pointer to a node that will enable us to start the recursion and an integer reference parameter
        to keep track the amount of items inserted into the array
*/
template <class T>
void RedBlackTree<T>::searchPrivate(Node<T>*pTr1, int &iNdex)
{
    // base case
    if(pTr1 == NULL)
    {
        return;
    }
    /*If the current value we are looking at is greater than the first value in the range
        that we are looking for we keep on traversing the left subtree
    */
    if(firstvalue < pTr1->data)
    {
        searchPrivate(pTr1->left,iNdex);
    }
    /*
        If the value we are looking for is indeed in the range we push its appropriate datum into the associated
        index in the array.
    */
    if( firstvalue <= pTr1->data && secondvalue >= pTr1->data)
    {
        aDumpTemp[iNdex] = pTr1->data;
        iNdex++;
    }

    /*
        If the current node with its associated datum is less than the datum in the second value of our interval
        then we keep on recursively going down its right subtree
    */
    if(secondvalue > pTr1->data)
    {
        searchPrivate(pTr1->right,iNdex);
    }
}
#endif