/*
 *_________________________________________________________________________*
 *      POEMS: PARALLELIZABLE OPEN SOURCE EFFICIENT MULTIBODY SOFTWARE     *
 *      DESCRIPTION: SEE READ-ME                                           *
 *      FILE NAME: poemstree.h                                             *
 *      AUTHORS: See Author List                                           *
 *      GRANTS: See Grants List                                            *
 *      COPYRIGHT: (C) 2005 by Authors as listed in Author's List          *
 *      LICENSE: Please see License Agreement                              *
 *      DOWNLOAD: Free at www.rpi.edu/~anderk5                             *
 *      ADMINISTRATOR: Prof. Kurt Anderson                                 *
 *                     Computational Dynamics Lab                          *
 *                     Rensselaer Polytechnic Institute                    *
 *                     110 8th St. Troy NY 12180                           *
 *      CONTACT:        anderk5@rpi.edu                                    *
 *_________________________________________________________________________*/

#ifndef TREE_H
#define TREE_H

#include "poemstreenode.h"
#include "poemsnodelib.h"


// constants to indicate the balance factor of a node
const int leftheavy = -1;
const int balanced = 0;
const int rightheavy = 1;



class Tree{
protected:
        // pointer to tree root and node most recently accessed
        TreeNode *root;
        TreeNode *current;

        // number of elements in the tree
        int size;
        // used by the copy constructor and assignment operator
        TreeNode *CopyTree(TreeNode *t);

    // callback function to delete aux data
    void (*DeleteAuxData)(void *);

        // used by insert and delete method to re-establish
        // the avl conditions after a node is added or deleted
        // from a subtree
        void SingleRotateLeft (TreeNode* &p);
        void SingleRotateRight (TreeNode* &p);
        void DoubleRotateLeft (TreeNode* &p);
        void DoubleRotateRight (TreeNode* &p);
        void UpdateLeftTree (TreeNode* &p, int &reviseBalanceFactor);
        void UpdateRightTree (TreeNode* &p, int &reviseBalanceFactor);


        // used by destructor, assignment operator and ClearList
        void DeleteTree(TreeNode *t);
        void ClearTree(TreeNode * &t);

        // locate a node with data item and its parent in tree
        // used by Find and Delete
        TreeNode *FindNode(const int& item, TreeNode* & parent) const;

public:
        // constructor, destructor
        Tree(void);
        ~Tree(void)
        {
                ClearTree(root);
        };

        // assignment operator
        Tree& operator= (const Tree& rhs);

        // standard list handling methods
        void * Find(int& item);
        void * GetAuxData(int item) {
      return (void *)(FindNode(item, root)->GetAuxData());
    }
    void SetDeleteAuxData(void (*callback)(void *)) {
      DeleteAuxData = callback;
    }

        void Insert(const int& item, const int& data, void * AuxData = nullptr);
        void Delete(const int& item);
        void AVLInsert(TreeNode* &tree, TreeNode* newNode, int &reviseBalanceFactor);
        void ClearList(void);

        // tree specific methods
        void Update(const int& item);
        TreeNode *GetRoot(void) const;
};


// constructor
Tree::Tree(void)
{
        root = 0;
        current = 0;
        size = 0;
    DeleteAuxData = nullptr;
}



// return root pointer
TreeNode *Tree::GetRoot(void) const
{
        return root;
}


// assignment operator
Tree& Tree::operator = (const Tree& rhs)
{
        // can't copy a tree to itself
        if (this == &rhs)
                return *this;

        // clear current tree. copy new tree into current object
        ClearList();
        root = CopyTree(rhs.root);

        // assign current to root and set the tree size
        current = root;
        size = rhs.size;

        // return reference to current object
        return *this;
}

// search for data item in the tree. if found, return its node
// address and a pointer to its parent; otherwise, return a null pointer
TreeNode *Tree::FindNode(const int& item,
                                                                   TreeNode* & parent) const
{
        // cycle t through the tree starting with root
        TreeNode *t = root;

        // the parent of the root is a null pointer
        parent = nullptr;

        // terminate on empty subtree
        while(t != nullptr)
        {
                // stop on a match
                if (item == t->data)
                        break;
                else
                {
                        // update the parent pointer and move right of left
                        parent = t;
                        if (item < t->data)
                                t = t->left;
                        else
                                t = t->right;
                }
        }

        // return pointer to node; a null pointer if not found
        return t;
}

// search for item. if found, assign the node data to item
void * Tree::Find(int& item)
{
        // we use FindNode, which requires a parent parameter
        TreeNode *parent;

        // search tree for item. assign matching node to current
        current = FindNode (item, parent);

        // if item found, assign data to item and return True
        if (current != nullptr)
        {
                item = current->data;
        return current->GetAuxData();
        }
        else
                // item not found in the tree. return a null pointer
                return nullptr;
}


void Tree::Insert(const int& item, const int& data, void * AuxData)
{
        // declare AVL tree node pointer; using base class method
        // GetRoot. cast to larger node and assign root pointer
        TreeNode *treeRoot, *newNode;
         treeRoot = GetRoot();

        // flag used by AVLInsert to rebalance nodes
        int reviseBalanceFactor = 0;

        // get a new AVL tree node with empty pointer fields
        newNode = GetTreeNode(item,nullptr,nullptr);
        newNode->data = data;
        newNode->SetAuxData(AuxData);
        // call recursive routine to actually insert the element
        AVLInsert(treeRoot, newNode, reviseBalanceFactor);

        // assign new values to data members in the base class
        root = treeRoot;
        current = newNode;
        size++;

}

void Tree::AVLInsert(TreeNode *&tree, TreeNode *newNode, int &reviseBalanceFactor)
{
        // flag indicates change node's balanceFactor will occur
        int rebalanceCurrNode;

        // scan reaches an empty tree; time to insert the new node
        if (tree == nullptr)
        {
                // update the parent to point at newNode
                tree = newNode;

                // assign balanceFactor = 0 to new node
                tree->balanceFactor = balanced;
                // broadcast message; balanceFactor value is modified
                reviseBalanceFactor = 1;
        }
        // recursively move left if new data < current data
        else if (newNode->data < tree->data)
        {
                AVLInsert(tree->left,newNode,rebalanceCurrNode);
                // check if balanceFactor must be updated.
                if (rebalanceCurrNode)
                {
                        // went left from node that is left heavy. will
                        // violate AVL condition; use rotation (case 3)
                        if (tree->balanceFactor == leftheavy)
                                UpdateLeftTree(tree,reviseBalanceFactor);

                        // went left from balanced node. will create
                        // node left on the left. AVL condition OK (case 1)
                        else if (tree->balanceFactor == balanced)
                        {
                                tree->balanceFactor = leftheavy;
                                reviseBalanceFactor = 1;
                        }
                        // went left from node that is right heavy. will
                        // balance the node. AVL condition OK (case 2)
                        else
                        {
                                tree->balanceFactor = balanced;
                                reviseBalanceFactor = 0;
                        }
                }
        else
            // no balancing occurs; do not ask previous nodes
                        reviseBalanceFactor = 0;
        }
    // otherwise recursively move right
    else
        {
                AVLInsert(tree->right, newNode, rebalanceCurrNode);
                // check if balanceFactor must be updated.
                if (rebalanceCurrNode)
                {
                        // went right from node that is left heavy. wil;
                        // balance the node. AVL condition OK (case 2)
                        if (tree->balanceFactor == leftheavy)
                        {
                                // scanning right subtree. node heavy on left.
                                // the node will become balanced
                                tree->balanceFactor = balanced;
                                reviseBalanceFactor = 0;
                        }
                        // went right from balanced node. will create
                        // node heavy on the right. AVL condition OK (case 1)
                        else if (tree->balanceFactor == balanced)
                        {
                                // node is balanced; will become heavy on right
                                tree->balanceFactor = rightheavy;
                                reviseBalanceFactor = 1;
                        }
                        // went right from node that is right heavy. will
                        // violate AVL condition; use rotation (case 3)
                        else
                                UpdateRightTree(tree, reviseBalanceFactor);
                }
                else
                        reviseBalanceFactor = 0;
        }
}


void Tree::UpdateLeftTree (TreeNode* &p, int &reviseBalanceFactor)
{
        TreeNode *lc;

        lc = p->Left();                 // left subtree is also heavy
        if (lc->balanceFactor == leftheavy)
        {
                SingleRotateRight(p);
                reviseBalanceFactor = 0;
        }
        // is right subtree heavy?
        else if (lc->balanceFactor == rightheavy)
        {
                // make a double rotation
                DoubleRotateRight(p);
                // root is now balance
                reviseBalanceFactor = 0;
        }
}

void Tree::UpdateRightTree (TreeNode* &p, int &reviseBalanceFactor)
{
        TreeNode *lc;

        lc = p->Right();                        // right subtree is also heavy
        if (lc->balanceFactor == rightheavy)
        {
                SingleRotateLeft(p);
                reviseBalanceFactor = 0;
        }
        // is left subtree heavy?
        else if (lc->balanceFactor == leftheavy)
        {
                // make a double rotation
                DoubleRotateLeft(p);
                // root is now balance
                reviseBalanceFactor = 0;
        }
}

void Tree::SingleRotateRight (TreeNode* &p)
{
        // the left subtree of p is heavy
        TreeNode *lc;

        // assign the left subtree to lc
        lc = p->Left();

        // update the balance factor for parent and left child
        p->balanceFactor = balanced;
        lc->balanceFactor = balanced;

        // any right subtree st of lc must continue as right
        // subtree of lc. do by making it a left subtree of p
        p->left = lc->Right();

        // rotate p (larger node) into right subtree of lc
        // make lc the pivot node
        lc->right = p;
        p = lc;
}

void Tree::SingleRotateLeft (TreeNode* &p)
{
        // the right subtree of p is heavy
        TreeNode *lc;

        // assign the left subtree to lc
        lc = p->Right();

        // update the balance factor for parent and left child
        p->balanceFactor = balanced;
        lc->balanceFactor = balanced;

        // any right subtree st of lc must continue as right
        // subtree of lc. do by making it a left subtree of p
        p->right = lc->Left();

        // rotate p (larger node) into right subtree of lc
        // make lc the pivot node
        lc->left = p;
        p = lc;
}

// double rotation right about node p
void Tree::DoubleRotateRight (TreeNode* &p)
{
        // two subtrees that are rotated
        TreeNode *lc, *np;

        // in the tree, node(lc) <= node(np) < node(p)
        lc = p->Left();                 // lc is left child of parent
        np = lc->Right();               // np is right child of lc

        // update balance factors for p, lc, and np
        if (np->balanceFactor == rightheavy)
        {
                p->balanceFactor = balanced;
                lc->balanceFactor = rightheavy;
        }
        else if (np->balanceFactor == balanced)
        {
                p->balanceFactor = balanced;
                lc->balanceFactor = balanced;
        }
        else
        {
                p->balanceFactor = rightheavy;
                lc->balanceFactor = balanced;
        }
        np->balanceFactor = balanced;

        // before np replaces the parent p, take care of subtrees
        // detach old children and attach new children
        lc->right = np->Left();
        np->left = lc;
        p->left = np->Right();
        np->right = p;
        p = np;
}

void Tree::DoubleRotateLeft (TreeNode* &p)
{
        // two subtrees that are rotated
        TreeNode *lc, *np;

        // in the tree, node(lc) <= node(np) < node(p)
        lc = p->Right();                        // lc is right child of parent
        np = lc->Left();                // np is left child of lc

        // update balance factors for p, lc, and np
        if (np->balanceFactor == leftheavy)
        {
                p->balanceFactor = balanced;
                lc->balanceFactor = leftheavy;
        }
        else if (np->balanceFactor == balanced)
        {
                p->balanceFactor = balanced;
                lc->balanceFactor = balanced;
        }
        else
        {
                p->balanceFactor = leftheavy;
                lc->balanceFactor = balanced;
        }
        np->balanceFactor = balanced;

        // before np replaces the parent p, take care of subtrees
        // detach old children and attach new children
        lc->left = np->Right();
        np->right = lc;
        p->right = np->Left();
        np->left = p;
        p = np;
}

// if item is in the tree, delete it
void Tree::Delete(const int& item)
{
        // DNodePtr = pointer to node D that is deleted
        // PNodePtr = pointer to parent P of node D
        // RNodePtr = pointer to node R that replaces D
        TreeNode *DNodePtr, *PNodePtr, *RNodePtr;

        // search for a node containing data value item. obtain its
        // node address and that of its parent
        if ((DNodePtr = FindNode (item, PNodePtr)) == nullptr)
                return;

        // If D has null pointer, the
        // replacement node is the one on the other branch
        if (DNodePtr->right == nullptr)
                RNodePtr = DNodePtr->left;
        else if (DNodePtr->left == nullptr)
                RNodePtr = DNodePtr->right;
        // Both pointers of DNodePtr are non-null pointers
        else
        {
                // Find and unlink replacement node for D
                // Starting on the left branch of node D,
                // find node whose data value is the largest of all
                // nodes whose values are less than the value in D
                // Unlink the node from the tree

                // PofRNodePtr = pointer to parent of replacement node
                TreeNode *PofRNodePtr = DNodePtr;

                // frist possible replacement is left child D
                RNodePtr = DNodePtr->left;

                // descend down right subtree of the left child of D
                // keeping a record of current node and its parent.
                // when we stop, we have found the replacement
                while (RNodePtr->right != nullptr)
                {
                        PofRNodePtr = RNodePtr;
                        RNodePtr = RNodePtr;
                }

                if (PofRNodePtr == DNodePtr)
                        // left child of deleted node is the replacement
                        // assign right subtree of D to R
                        RNodePtr->right =  DNodePtr->right;
                else
                {
                        // we moved at least one node down a right brance
                        // delete replacement node from tree by assigning
                        // its left branc to its parent
                        PofRNodePtr->right = RNodePtr->left;

                        // put replacement node in place of DNodePtr.
                        RNodePtr->left = DNodePtr->left;
                        RNodePtr->right = DNodePtr->right;
                }
        }

        // complete the link to the parent node
        // deleting the root node. assign new root
        if (PNodePtr == nullptr)
                root = RNodePtr;
        // attach R to the correct branch of P
        else if (DNodePtr->data < PNodePtr->data)
                PNodePtr->left = RNodePtr;
        else
                PNodePtr->right = RNodePtr;

        // delete the node from memory and decrement list size
        FreeTreeNode(DNodePtr);  // this says FirstTreeNode in the book, should be a typo
        size--;
}





// if current node is defined and its data value matches item,
// assign node value to item; otherwise, insert item in tree
void Tree::Update(const int& item)
{
        if (current !=nullptr && current->data == item)
                current->data = item;
        else
                Insert(item, item);
}

// create duplicate of tree t; return the new root
TreeNode *Tree::CopyTree(TreeNode *t)
{
        // variable newnode points at each new node that is
        // created by a call to GetTreeNode and later attached to
        // the new tree. newlptr and newrptr point to the child of
        // newnode and are passed as parameters to GetTreeNode
        TreeNode *newlptr, *newrptr, *newnode;

        // stop the recursive scan when we arrive at an empty tree
        if (t == nullptr)
                return nullptr;

        // CopyTree builds a new tree by scanning the nodes of t.
        // At each node in t, CopyTree checks for a left child. if
        // present it makes a copy of left child or returns a null pointer.
        // the algorithm similarly checks for a right child.
        // CopyTree builds a copy of node using GetTreeNode and
        // appends copy of left and right children to node.

        if (t->Left() !=nullptr)
                newlptr = CopyTree(t->Left());
        else
                newlptr = nullptr;

        if (t->Right() !=nullptr)
                newrptr = CopyTree(t->Right());
        else
                newrptr = nullptr;


        // Build new tree from the bottom up by building the two
        // children and then building the parent
        newnode = GetTreeNode(t->data, newlptr, newrptr);

        // return a pointer to the newly created node
        return newnode;
}


// use the postorder scanning algorithm to traverse the nodes in
// the tree and delete each node at the visit operation
void Tree::DeleteTree(TreeNode *t)
{
  if (t != nullptr) {
    DeleteTree(t->Left());
    DeleteTree(t->Right());
    void *aux = t->GetAuxData();
    if (aux != nullptr) {
      if (DeleteAuxData != nullptr) {
        (*DeleteAuxData)(aux);
      } else {
        delete (TreeNode *) aux;
      }
    }
    FreeTreeNode(t);
  }
}

// call the function DeleteTree to deallocate the nodes. then
// set the root pointer back to a null pointer
void Tree::ClearTree(TreeNode * &t)
{
        DeleteTree(t);
        t = nullptr;               // root now a null pointer
}

// delete all nodes in list
void Tree::ClearList(void)
{
        delete root;
        delete current;
        size = 0;
}

#endif