#include "nodes.h"


BasicInfo::~BasicInfo(){}


// This method searches a Node in the tree by comparing its data with the
// data in the existing nodes. 
// Parameters: The data to search.
// Return value: A pointer to the found node, if found, NULL pointer otherwise.
NodePtr Node::Find(const BasicInfo& toFind)
{
	if((*data) == toFind) return this;
	if(toFind > (*data)){
		if(right == NULL) return NULL;
		return right->Find(toFind);
	}
	if(left == NULL) return NULL;
	return left->Find(toFind);
}


// This method inserts a new node into the tree after making sure it's not
// already there.
// Parameters: The information to insert.
// Return value: A pointer to the new node, or NULL if it exists / a failure
// occured.
NodePtr Node::Insert(BasicInfo& toInsert, NodePtr& Root)
{
	if((*data) == toInsert) return NULL;
	NodePtr* nextSon = NULL;
	if(toInsert > (*data)) nextSon = &right;
	else nextSon = &left;
	if(*nextSon == NULL){
		if((*nextSon = new Node(&toInsert)) == NULL) return NULL;
		(*nextSon)->daddy = this;
		if((*nextSon) == right) hRight++;
		else hLeft++;
		weight++;
		return *nextSon;
	}
	NodePtr returnVal = (*nextSon)->Insert(toInsert, Root);
	if(returnVal != NULL){
		if((*nextSon) == right) hRight = max(right->hRight, right->hLeft)+1;
		else hLeft = max(left->hRight, left->hLeft)+1;
		weight++;
		checkBF(Root);
	}
	return returnVal;
}


//remove leaf detaches the leaf-node from the tree
//parameters - none
//return value - none
void Node::removeLeaf(NodePtr& Root)
{
	if(daddy == NULL){
		Root = NULL;
		return;
	}
	if(IsRightSon()){
		daddy->right = NULL;
		daddy->hRight = 0;
	}else{
		daddy->left = NULL;
		daddy->hLeft = 0;
	}
	daddy->weight--;
	daddy = NULL;
	return;
}


//this function updates hights and checks if rolls are necessary recursively 
//until it reaches the root.
//parameters: the root, as a reference to its pointer
//return value: none
void Node::chBF(NodePtr& Root)
{
	calcWeight();
	if(left) hLeft = max(left->hLeft, left->hRight)+1;
	else hLeft = 0;
	if(right) hRight = max(right->hLeft, right->hRight)+1;
	else hRight = 0;
	int balanceFactor = hLeft - hRight;
	if(balanceFactor > -2 && balanceFactor < 2){
		if(daddy) daddy->chBF(Root);		
		return;
	}
	if(balanceFactor == -2){
		int RbalanceFactor = right->hLeft - right->hRight;
		if(RbalanceFactor <= 0) rollRR(Root);
		else rollRL(Root);
		if(daddy) daddy->chBF(Root);
		return;
	}
	int LbalanceFactor = left->hLeft - left->hRight;
	if(LbalanceFactor >= 0) rollLL(Root);
	else rollLR(Root);
	if(daddy) daddy->chBF(Root);
	return;
}


// this function finds a nodes replacer using the following algorithm:
// 1. if the node has a right son, than go all the way left from it and return
// 	  this node.
// 2. if the node has a right son with no left sons, return the right son.
// 3. if the node only has a left son, return it.
// otherwise it's a leaf and being taken care of earlier.
// parameters: none. It's a node's function.
// return value: the node that will replace "this".
NodePtr Node::getReplacer()
{
	NodePtr tRight = NULL;
	NodePtr tLeft = NULL;
	tRight = right;
	tLeft = left;
	if(right == NULL) return left; 
	NodePtr retVal = right;
	while(retVal->left) retVal = retVal->left;
	return retVal;
}


// The next 4 functions replace a-soon-to-be-deleted node with its replacer,
// that is given to it (as well as the tree's root pointer, so it can be 
// updated if needed.
// The first function determines what replacement we need, since there're 
// differences between replacing a node with its right or left son, or
// with some other node.
// parameters: the node to be removed, the tree's root pointer.
// return value: a pointer to the node from which the tree will check its
// correctness.
NodePtr Node::Replace(NodePtr toKill, NodePtr& Root)
{
	hRight = toKill->hRight;
	hLeft = toKill->hLeft;
	NodePtr retVal = NULL;
	// replacer is the right son of the replaced
	if(toKill->right == this)
		retVal = replaceRightSon(toKill, Root);
	// replacer is the left son of the replaced
	else if(toKill->left == this) 
		retVal = replaceleftSon(toKill, Root);
	//the replacer is not any son of the replaced
	else 
		retVal = replaceNotASon(toKill, Root);
	toKill->right = NULL;
	toKill->left = NULL;
	delete toKill;
	return retVal;
}


NodePtr Node::replaceRightSon(NodePtr toKill, NodePtr& Root)
{
	weight = toKill->weight-1;
	if(toKill->daddy == NULL){
		Root = this;
		daddy = NULL;
		left = toKill->left;
	}else{
		if(toKill->IsRightSon()) toKill->daddy->right = this;
		else toKill->daddy->left = this;
		daddy = toKill->daddy;
		left = toKill->left;
		toKill->daddy = NULL;
	}
	if(left) left->daddy = this;
	return this;
}


NodePtr Node::replaceleftSon(NodePtr toKill, NodePtr& Root)
{
	weight = toKill->weight-1;
	if(toKill->daddy == NULL){
		Root = this;
		daddy = NULL;
	}else{
		if(toKill->IsRightSon()) toKill->daddy->right = this;
		else toKill->daddy->left = this;
		daddy = toKill->daddy;
		toKill->daddy = NULL;
	}
	return this;
}


NodePtr Node::replaceNotASon(NodePtr toKill, NodePtr& Root)
{
	daddy->weight --;
	NodePtr retVal = daddy;
	if(right){
		daddy->left = right;
		right->daddy = daddy;
	}else daddy->left = NULL;
	left = toKill->left;
	right = toKill->right;
	right->daddy = this;
	left->daddy = this;
	if(toKill->daddy == NULL){
		Root = this;
		daddy = NULL;
	}else{
		if(toKill->IsRightSon()) toKill->daddy->right = this;
		else toKill->daddy->left = this;
		daddy = toKill->daddy;
		toKill->daddy = NULL;
	}
	return retVal;
}


int max(int a, int b)
{
	return (a > b) ? a : b;
}

float max(float a, float b)
{
	return (a > b) ? a : b;
}


// This function checks for "this" if it's a balanced node (heights-wise) and
// if not, it determines what sort of "roll" should be done in order to balance
// the tree again.
// parameters: the tree's root, if needs to be updated.
// return value: none.
void Node::checkBF(NodePtr& Root)
{
	int balanceFactor = hLeft - hRight;
	if(balanceFactor > -2 && balanceFactor < 2) return;
	if(balanceFactor == -2){
		int RbalanceFactor = right->hLeft - right->hRight;
		if(RbalanceFactor <= 0) rollRR(Root);
		else rollRL(Root);
		return;
	}
	int LbalanceFactor = left->hLeft - left->hRight;
	if(LbalanceFactor >= 0) rollLL(Root);
	else rollLR(Root);
	return;
}


// The next 4 functions are the 4 different rolls that the tree can perform
// in order to make itself balanced again. 
// parameters: the tree's root, if needs to be updated.
// return value: none.
void Node::rollRR(NodePtr& Root)
{
	right->daddy = daddy;
	if(daddy == NULL) Root = right;
	else{
		if(this == daddy->left) daddy->left = right;
		else daddy->right = right;
	}
	daddy = right;
	right = daddy->left;
	daddy->left = this;
	if(right != NULL) right->daddy = this;
	hRight = daddy->hLeft;
	daddy->hLeft = max(hLeft, hRight) + 1;
	calcWeight();
	daddy->calcWeight();
	return;
}


void Node::rollLL(NodePtr& Root)
{
	left->daddy = daddy;
	if(daddy == NULL) Root = left;
	else{
		if(this == daddy->left) daddy->left = left;
		else daddy->right = left;
	}
	daddy = left;
	left = daddy->right;
	daddy->right = this;
	if(left != NULL) left->daddy = this;
	hLeft = daddy->hRight;
	daddy->hRight = max(hLeft, hRight) + 1;
	calcWeight();
	daddy->calcWeight();
	return;
}


void Node::rollRL(NodePtr& Root)
{
	right->left->daddy = daddy;
	if(daddy == NULL) Root = right->left;
	else{
		if(this == daddy->left) daddy->left = right->left;
		else daddy->right = right->left;
	}
	daddy = right->left;
	right->left = daddy->right;
	if(right->left != NULL) right->left->daddy = right;
	daddy->right = right;
	right->daddy = daddy;
	right = daddy->left;
	daddy->left = this;
	if(right != NULL) right->daddy = this;
	hRight = daddy->hLeft;
	daddy->right->hLeft = daddy->hRight;
	daddy->hRight = max(daddy->right->hLeft, daddy->right->hRight) + 1;
	daddy->hLeft = max(hLeft, hRight) + 1;
	calcWeight();
	daddy->right->calcWeight();
	daddy->calcWeight();
	return;
}


void Node::rollLR(NodePtr& Root)
{
	left->right->daddy = daddy;
	if(daddy == NULL) Root = left->right;
	else{
		if(this == daddy->left) daddy->left = left->right;
		else daddy->right = left->right;
	}
	daddy = left->right;
	left->right = left->right->left;
	if(left->right != NULL) left->right->daddy = left;
	daddy->left = left;
	left->daddy = daddy;
	left = daddy->right;
	if(left != NULL) left->daddy = this;
	daddy->right = this;
	hLeft = daddy->hRight;
	daddy->left->hRight = daddy->hLeft;
	daddy->hRight = max(hLeft, hRight) + 1;
	daddy->hLeft = max(daddy->left->hLeft, daddy->left->hRight) + 1;
	calcWeight();
	daddy->left->calcWeight();
	daddy->calcWeight();
	return;
}


// This function finds the median node according to its weight and returns its
// salary as the median salary.
// parameters: the index to be searched (which represents the number of nodes 
// that need to be in the median's subtree).
// return value: the medain salary.
float Node::calcMedian(int medIndex)
{
	int leftWeight = (left == NULL) ? (0) : left->weight;
	if(medIndex == (leftWeight+1)) 
		return static_cast<SalaryInfo*>(getData())->getSal();
	if(medIndex <= leftWeight) return left->calcMedian(medIndex);
	return right->calcMedian(medIndex-leftWeight-1);
}


// This function's going all the way "right" in the tree - to its biggest
// value.
// parameters: none.
// return value: the node which contains the biggest value.
NodePtr Node::goRight()
{
	if(right) return right->goRight();
	return this;
}