//==========================================================================
//// cs12xia                     Homework 8      Arvin Bhattacharya
////--------------------------------------------------------------------------
//// File: Tree.c
////
//// Description: Contains the Node structure and the member functions of
////              the Tree class.
////==========================================================================

#include <cstdlib>
#include <string>
#include "Tree.h"
using namespace std;

// messages
static const char AND[] = " and ";
static const char CHECK[] = " - Checking ";
static const char COMPARE[] = " - Comparing ";
static const char DEALLOCATE[] = " - Deallocating]\n";
static const char INSERT[] = " - Inserting ";
static const char REPLACE[] = " - Replacing ";
static const char UPDATE[] = " - Updating ";

template <class Whatever>
int Tree<Whatever>::debug = 0;

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif

#define THRESHOLD 2

template <class Whatever>
ostream & operator << (ostream &, const TNode<Whatever> &);

/**
 * Description: Defines the fields of TNode
 *
 * Fields:
 *   balance - the balance of the node (lheight - rheight, -1 for null child)
 *   data - the info the node stores
 *   height - the height of the node (1 + child node height)
 *   left - the left child
 *   occupancy - the number of nodes in the tree
 *   right - the right child
 *   tree_count - the number of trees made
 *
 *   delete_AllTNodes - clears the tree of all TNodes
 *   Insert - Inserts a TNode into the tree
 *   lookup - searches tree to see if a certain node is in the tree
 *   Remove - Removes a node from the tree
 *   RemoveAndReplaceMax - handles two child removal case
 *   SetHeightAndBalance - sets height and balance for each node in the tree
 *   Write_AllTNodes - writes all TNodes in the tree
 */
template <class Whatever>
struct TNode {
  long balance;
  Whatever data;
  long height;
  TNode<Whatever> * left;
  long & occupancy;
  TNode<Whatever> * right;
  unsigned long & tree_count;

	/**
	 * Description: Ctor which initializes the TNode fields and increments
	 * occupancy
	 */
  TNode (const Whatever & element, Tree<Whatever> & theTree)
  : balance (0), data (element), height (0), left (0),
  occupancy (theTree.occupancy), right (0),
  tree_count (theTree.tree_count) {
    //increment occupancy since new tnode made
    occupancy++;
  }

	/**
	 * Description: Ctor which initializes the TNode fields and increments
	 * occupancy
	 */
  TNode (const Whatever & element, TNode<Whatever> & parentTNode)
  : balance (0), data (element), height (0), left (0),
  occupancy (parentTNode.occupancy), right (0),
  tree_count (parentTNode.tree_count) {
    //increment occupancy since new tnode made
    occupancy++;
  }

	/**
	 * Description: Destructor which decrements occupancy
	 */
  ~TNode (void) {
    //decrement occupancy since tnode destroyed
    occupancy--;
  }

	/**
	 * Description: Delete all nodes in the tree
	 *
	 * Parameters: None
	 *
	 * Returns: None
	 */
  void delete_AllTNodes (void) {
		//if there is a left child, recursive call
    if (left)
      left->delete_AllTNodes ();

		//if there is a right child, recursive call
    if (right)
      right->delete_AllTNodes ();

		//delete this node
    delete(this);
  }

	/**
	 * Description: Inserts a node into the tree
	 *
	 * Parameters: element - the element to insert
	 *             PointerInParent - the node to insert from
	 *
	 * Returns: True after successful insert
	 */
  unsigned long Insert (const Whatever & element,
  TNode<Whatever> *& PointerInParent) {
    if (element == PointerInParent->data) { //inserting a duplicate
      //return true since successful "insert"
      return true;
    } else if (element > this->data) { //if element is greater
      //debug statement
      if (Tree<Whatever> :: debug) {
        cerr << TREE << tree_count << COMPARE << element << AND <<
        this->data << "]" << endl;
      }

      //check if right node is null
      if (!PointerInParent->right) {
				//debug statement
				if (Tree<Whatever> :: debug) {
					cerr << TREE << tree_count << INSERT << element << "]" << endl;
				}

        //insert at right node if it is null
        PointerInParent->right = new TNode<Whatever> (element, *this);
      } else {
        //recursively iterate through tree if right node isnt null
        PointerInParent->right->Insert(element, PointerInParent->right);
      }
    } else { //if element is less
      //check if left node is null
      if (!PointerInParent->left) {
				//debug statement
				if (Tree<Whatever> :: debug) {
					cerr << TREE << tree_count << INSERT << element << "]" << endl;
				}

        //insert at left node if it is null
        PointerInParent->left = new TNode<Whatever> (element, *this);
      } else {
        //recursively iterate through tree if left node isnt null
        PointerInParent->left->Insert(element, PointerInParent->left);
      }
    }

    //return true since successful insert
    return true;
  }

	/**
	 * Description: Searches Tree to see if passed in element is in it
	 *
	 * Parameters: element - the element to search for
	 *
	 * Returns: True if found, false otherwise
	 */
  unsigned long Lookup(Whatever & element) const {
    const TNode<Whatever> * working = this; //used to iterate through tree

    //iterate thorugh tree
    while (working) {
      //debug statement
      if (Tree<Whatever> :: debug) {
        cerr << TREE << tree_count << COMPARE << element << AND <<
        working->data << "]" << endl;
      }

			//if element and working->data are equal
      if (element == working->data) {
				//return true since found
        return true;
      } else if (element > working->data) {
        //traverse down right if element is greater than working
        working = working->right;
      } else {
        //traverse down left if element is less than working
        working = working->left;
      }
    }

		//reach here only if node isnt found
    return false;
  }

	/**
	 * Description: Used to handle removal of a node which has two children
	 *
	 * Parameters: targetTNode - the node to remove
	 *                           PointerInParent - the node used for recursive
	 *                           calls through the tree
	 *
	 * Returns - None
	 */
  void ReplaceAndRemoveMax (TNode<Whatever> & targetTNode,
  TNode<Whatever> *& PointerInParent) {
		TNode<Whatever> * temp = PointerInParent;
		TNode<Whatever> * temp_parent;
		bool hadLeft = false; //keep track of if node had a left child
		bool parentFound = false; //keep track of if parent node found

		//Predecessor algorithm
		temp = temp->left;
		while (temp->right) {
		  //checking for when parent of predecessor reached
			if (temp->right && !temp->right->right) {
				//store parent of predecessor node
        temp_parent = temp;

        //if the node has a left child
				if (temp->right->left) {
					//use single child insertion algorithm
					temp_parent->right = temp->right->left;

          //turn had left flag on
					hadLeft = true;
				}

				//turn parentfound flag on
				parentFound = true;
			}

      //iterate through tree
			temp = temp->right;
		}

		//replace the target node's data with predecessor's data
		targetTNode.data = temp->data;

    if (!hadLeft && parentFound) { //if no left child and had parent
			//set the parent's right node to NULL
			temp_parent->right = NULL;

			//delete the parent
			delete temp_parent;

			//set parent to NULL
			temp_parent = NULL;
		} else if (hadLeft && parentFound) { //if left child and had parent
		  //delete parent
			delete temp_parent;

			//set parent to NULL
		  temp_parent = NULL;
		} else if (!hadLeft && !parentFound) { //if no left child & no parent
		  //delete left child
			delete targetTNode.left;

			//set left child to NULL
			targetTNode.left = NULL;
		}
  }

  /**
	 * Description: Removes elementTNode from the tree if it exists in the tree
	 *
	 * Parameters: elementTNode - the node to remove
	 *             PointerInParent - used for recursive calls
	 *
	 * Returns: True if successful removal, false otherwise
	 */
  unsigned long Remove (TNode<Whatever> & elementTNode,
  TNode<Whatever> *& PointerInParent,
  long fromSHB = false) {

    //if element is not in the tree
    if (!Lookup(elementTNode.data)) {
      return false;
    }

    if (elementTNode.data == PointerInParent->data) {
      //node has 0 children
      if (!PointerInParent->left && !PointerInParent->right) {
				//delete this node since it has no children
        delete PointerInParent;

				PointerInParent = NULL;
      } else if (PointerInParent>left && !PointerInParent->right) {
        //node only has left child
        TNode<Whatever> * temp = PointerInParent->left;

				//point to left child
				PointerInParent = temp;
        delete temp;
      } else if (!PointerInParent->left && PointerInParent->right) {
        //node only has right child
        TNode<Whatever> * temp = PointerInParent->right;

        //point to right child
				PointerInParent = temp;
				/*for (int i = 0; i < 3; i++) {
					cerr << "node " << i << " is " << PointerInParent->data << endl;
					PointerInParent = PointerInParent->right;
				} */
				//cerr << "PIP IN REMOVE METHOD IS " << PointerInParent->data << endl;

				//delete temp only if not being called from SHB in order to avoid double
				//delete
				if (!fromSHB) {
					delete temp;
				}
      } else if (this->left && this->right) { //node has two children
			  ReplaceAndRemoveMax(*PointerInParent, PointerInParent);
      }
    } else if (elementTNode.data > PointerInParent->data) { //elem is greater
		  //recursive call with PointerInParent's right
      return Remove(elementTNode, PointerInParent->right);
    } else { //elem is less
		  //recursive call with PointerInParent's left
      return Remove(elementTNode, PointerInParent->left);
    }

	  //return true since successful removal
    return true;
  }

	/**
	 * Description: Recursively set height and balane values of each node in the
	 * tree and reshape tree if it grows to be out of balance
	 *
	 * Parameters: PointerInParent - the node used to recurse through tree
	 *
	 * Returns: None
	 */
  void SetHeightAndBalance (TNode<Whatever> *& PointerInParent) {
    if (!PointerInParent->left && !PointerInParent->right) { //base case
      height = 0;
			balance = 0;
    } else {
      if (PointerInParent->left && PointerInParent->right) { //two child
        if (PointerInParent->left->height >
            PointerInParent->right->height) { //if left height greater

					//recursive call with PIP left child
          SetHeightAndBalance(PointerInParent->left);

					//set height of this node to 1 + updated value of child node height
          PointerInParent->height = 1 + PointerInParent->left->height;
        } else { //if right height greater

			    //recursive call with PIP right child
          SetHeightAndBalance(PointerInParent->right);

					//set height of this node to 1 + updated value of child node height
          PointerInParent->height = 1 + PointerInParent->right->height;
        }

        PointerInParent->balance = PointerInParent->left->height -
        PointerInParent->right->height;

				//TODO CHECK FOR BALANCE THRESHOLD HERE
				if (PointerInParent->balance >= THRESHOLD ||
					  PointerInParent->balance <= -THRESHOLD) {
					const Whatever & temp = PointerInParent->data;
					TNode<Whatever> * tempNode = this;
					Remove(*PointerInParent, tempNode);
					Insert(temp, tempNode);
					delete tempNode;
				}

      } else if (PointerInParent->left && !PointerInParent->right) {
        SetHeightAndBalance(PointerInParent->left);

        PointerInParent->height = 1 + PointerInParent->left->height;
        PointerInParent->balance = PointerInParent->left->height + 1;

				//TODO CHECK FOR BALANCE THRESHOLD HERE
				if (PointerInParent->balance >= THRESHOLD ||
					  PointerInParent->balance <= -THRESHOLD) {
					const Whatever & temp = PointerInParent->data;
					TNode<Whatever> * tempNode = this;
					Remove(*PointerInParent, tempNode);
					Insert(temp, tempNode);
					delete tempNode;
				}
      } else if (!PointerInParent->left && PointerInParent->right) {
        SetHeightAndBalance(PointerInParent->right);
        PointerInParent->height = 1 + PointerInParent->right->height;
        PointerInParent->balance = -1 - PointerInParent->right->height;

				//TODO CHECK FOR BALANCE THRESHOLD HERE
				if (PointerInParent->balance > THRESHOLD ||
					  PointerInParent->balance < -THRESHOLD) {
					const Whatever & temp = PointerInParent->data;

					TNode<Whatever> * tempNode = this;

					Remove(*PointerInParent, tempNode, true);
					SetHeightAndBalance(tempNode);
					Write_AllTNodes(cerr << "The nodes are\n");
					//Insert(temp, tempNode);

					delete tempNode;
				}
      }
    }
  }

  ostream & Write_AllTNodes (ostream & stream) const {
    if (left)
      left->Write_AllTNodes (stream);
    stream << *this;
    if (right)
      right->Write_AllTNodes (stream);

    return stream;
  }
};

/**
 * Desccription: Turns debug flag on
 *
 * Parameters: None
 *
 * Returns: None
 */
template <class Whatever>
void Tree<Whatever> :: Set_Debug_On(void) {
	//turn debug flag on
  Tree<Whatever> :: debug = true;
}

/**
 * Description: Turns debug flag off
 *
 * Paramters: None
 *
 * Returns: None
 */
template <class Whatever>
void Tree<Whatever> :: Set_Debug_Off(void) {
	//turn debug flag off
  Tree<Whatever> :: debug = false;
}

template <class Whatever>
ostream & operator << (ostream & stream, const TNode<Whatever> & nnn) {
  stream << "at height:  :" << nnn.height << " with balance:  "
  << nnn.balance << "  ";
  return stream << nnn.data << "\n";
}

/**
 * Description: Tree's Insert Method; handles insertion of root node, delegates
 * rest to TNode's insert
 *
 * Parameters: element - element to insert
 *
 * Returns: True after successful insert
 */
template <class Whatever>
unsigned long Tree<Whatever> :: Insert (const Whatever & element) {
  //inserting first node
  if (root == NULL) {
    root = new TNode<Whatever>(element, *this);
  } else {
		//delegate to TNode's insert
    root->Insert(element, root);
  }

	//set height and balance of each node in tree
  root->SetHeightAndBalance(root);

	//return true since successful insert
  return true;
}

/**
 * Description: Delegates to TNode's lookup
 *
 * Parameters: element - the element to lookup
 *
 * Returns: True if element is in the table, false otherwise
 */
template <class Whatever>
unsigned long Tree<Whatever> :: Lookup (Whatever & element) const {
	//delegate lookup to TNode's method
  return root->Lookup(element);
}

/**
 * Description: Removes node if there is only one in the tree, delegates task to
 * TNode's removal otherwise
 *
 * Parameters: element - the element to remove
 *
 * Returns: True if successful delete, false otherwise
 */
template <class Whatever>
unsigned long Tree<Whatever> :: Remove (Whatever & element) {
  bool removed = true;

  //if removing from empty tree
  if (root == NULL) {
    removed = false;
  } else if (Tree<Whatever> :: occupancy == 1) { //if only 1 node in tree
		//delete root since it is the only node in tree
    delete root;
		root = NULL;
  } else {
    //used for TNode remove recursive call
    TNode<Whatever> * temp = new TNode<Whatever>(element, *this);

	  //store result of recursive call here
    removed = root->Remove(*temp, root);

		//delete the temp variable usedfor calling TNode's remove
		delete temp;
  }

	//if there is at least one node in tree
	if (occupancy > 0) {
		//set height and balance of all the nodes in the tree
		root->SetHeightAndBalance(root);
	}

	//return result of removal attempt
  return removed;
}

/***************************************************************************
% Routine Name : Tree<Whatever> :: Tree  (public)
% File :         Tree.c
%
% Description :  Guarantee initialization of occupancy and root. It also
%                initializes the tree_count using a static counter.
***************************************************************************/
template <class Whatever>
Tree<Whatever> :: Tree (void): occupancy (0), root (NULL)

{
  static long counter;
  tree_count = ++counter;
}

template <class Whatever>
Tree<Whatever> :: ~Tree (void)
/***************************************************************************
% Routine Name : Tree<Whatever> :: ~Tree  (public)
% File :         Tree.c
%
% Description :  deallocates memory associated with the Tree.  It
%                will also delete all the memory of the elements within
%                the table.
***************************************************************************/

{
	//delete all nodes in the tree if there are nodes in the tree
  if (root != NULL) {
    root->delete_AllTNodes();
  }
}


template <class Whatever>
ostream & Tree<Whatever> :: Write (ostream & stream) const
/***************************************************************************
% Routine Name : Tree<Whatever> :: Write (public)
% File :         Tree.c
%
% Description : This function will output the contents of the Tree table
%               to the stream specificed by the caller.  The stream could be
%               cerr, cout, or any other valid stream.
%
% Parameters descriptions :
%
% name               description
% ------------------ ------------------------------------------------------
% stream             A reference to the output stream.
% <return>           A reference to the output stream.
***************************************************************************/

{
  stream << "Tree " << tree_count << ":\n"
  << "occupancy is " << occupancy << " elements.\n";

  return (root) ? root->Write_AllTNodes (stream) : stream;
}