#ifndef AVLTreeUtils
#define AVLTreeUtils

/*
void AVLTree::Insert(TNode *&head, TNode *ins);

TNode *AVLTree::Remove(TNode *&head, TKey &rem);
TNode *AVLTree::RemoveMin(TNode *&head);
TNode *AVLTree::RemoveMax(TNode *&head);

TNode *AVLTree::Merge(TNode *head1, TNode *head2);
void AVLTree::Partition(TNode *headIn1, const TKey &splitter, TNode *&headOut1, TNode *&headOut2);

bool AVLTree::Verify(const TNode *head);
*/

namespace AVLTree {

// *** Internal Stuff ***
//rotR
template <class TNode>
bool SingleRotateWithLeft(TNode *&head) {
    //Item B with A as left-subtree becomes
	//Item A with B as right-subtree
	bool heightDecrease = (head->left->bal != 0);
	TNode *const oldHead = head;
	head = oldHead->left;
    oldHead->left = head->right;
    head->right = oldHead;
	oldHead->bal = -(++head->bal);
	return heightDecrease;
}

//rotL
template <class TNode>
bool SingleRotateWithRight(TNode *&head) {
    //Item A with B as right-subtree becomes
	//Item B with A as left-subtree
	bool heightDecrease = (head->right->bal != 0);
	TNode *const oldHead = head;
	head = oldHead->right;
    oldHead->right = head->left;
    head->left = oldHead;
	oldHead->bal = -(--head->bal);
	return heightDecrease;
}

//rotRL
template <class TNode>
bool DoubleRotateWithLeft(TNode *&head) {	
	//Item C with A as left-subtree and B as A's right sub-tree becomes
	//Item B with A as left-subtree and C as B's right sub-tree
	TNode *const oldHead = head;
	TNode *const oldLeftSubtree = head->left;
	// assign new head
	head = oldHead->left->right;
	// new-head exchanges it's right subtree for it's grandparent
	oldHead->left = head->right;
	head->right = oldHead;
	// new-head exchanges it's left subtree for it's parent
	oldLeftSubtree->right = head->left;
	head->left = oldLeftSubtree;
	// update balances
	int newBal = -head->bal;
	oldLeftSubtree->bal = (newBal < 0) ? newBal : 0;
	oldHead->bal = (newBal > 0) ? newBal : 0;
	head->bal = 0;
	// A double rotation always shortens the overall height of the tree
	return true;
}

//rotLR
template <class TNode>
bool DoubleRotateWithRight(TNode *&head) {	
    //Item A with C as right-subtree and B as C's left sub-tree becomes
    //Item B with A as left-subtree and C as B's right sub-tree
	TNode *const oldHead = head;
	TNode *const oldLeftSubtree = head->right;
	// assign new head
	head = oldHead->right->left;
	// new-head exchanges it's left subtree for it's grandparent
	oldHead->right = head->left;
	head->left = oldHead;
	// new-head exchanges it's right subtree for it's parent
	oldLeftSubtree->left = head->right;
	head->right = oldLeftSubtree;
	// update balances
	int newBal = -head->bal;
	oldHead->bal = (newBal < 0) ? newBal : 0;
	oldLeftSubtree->bal = (newBal > 0) ? newBal : 0;
	head->bal = 0;
	// A double rotation always shortens the overall height of the tree
	return true;
}

//returns true if the height decreased
template <class TNode>
bool LeftRebalance(TNode *&head) {
	//is the left branch too heavy?
	if (head->bal < -1) {
		//is a single or double rotate required to restore balance?
		if (head->left->bal != 1)
			return SingleRotateWithLeft(head);
		else
			return DoubleRotateWithLeft(head);
	}
	return false;
}

//returns true if the height decreased
template <class TNode>
bool RightRebalance(TNode *&head) {
	//is the left branch too heavy?
	if (head->bal > 1) {
		//is a single or double rotate required to restore balance?
		if (head->right->bal != -1)
			return SingleRotateWithRight(head);
		else
			return DoubleRotateWithRight(head);
	}
	return false;
}

// *** Utilities ***
// O(log(n)) : Insert caller-allocated item
// returns true if the height increased
template <class TNode>
bool Insert(TNode *&head, TNode *ins) {
	//base case: the empty spot where the node should be has been found
	if (head == NULL) {
		ins->bal = 0;
		ins->left = ins->right = NULL;
		//put it here, replacing the NULL
		head = ins;
		return true;
	} else if (*ins < *head) {
		//it goes somewhere in the left sub-tree
		bool increase = AVLTree::Insert(head->left, ins);
		if (increase && (--head->bal != 0))
			return !LeftRebalance(head);
	} else
#ifndef ALLOW_DUPLICATES
	if (*head < *ins)
#endif
	{
		//it goes somewhere in the right sub-tree
		bool increase = AVLTree::Insert(head->right, ins);
		if (increase && (++head->bal != 0))
			return !RightRebalance(head);
	}
#ifndef ALLOW_DUPLICATES
	else {
		// 'ins' is in the tree already; do nothing
	}
#endif
	return false;
}

template <class TNode>
TNode *RemoveMin(TNode *&head, bool &heightDecrease) {
	TNode *found;
	//special case used for finding the node to replace a higher deleted node
	if (head->left != NULL) {
		//remove node from left subtree
		found = RemoveMin(head->left, heightDecrease);
		if (heightDecrease && (++head->bal != 0))
			heightDecrease = RightRebalance(head);
	} else {
		found = head;
		//there is no left node, put any right one as the new parent
		head = head->right;
		heightDecrease = true;
	}
	return found;
}

// O(log(n)) : Remove leftmost selected item - caller responsible for deallocation
template <class TNode>
TNode *RemoveMin(TNode *&head) {
	bool heightDecrease;
	if (head == NULL) return NULL;
	return RemoveMin(head, heightDecrease);
}

template <class TNode>
TNode *RemoveMax(TNode *&head, bool &heightDecrease) {
	TNode *found;
	//special case used for finding the node to replace a higher deleted node
	if (head->right != NULL) {
		//remove node from left subtree
		found = RemoveMax(head->right, heightDecrease);
		if (heightDecrease && (--head->bal != 0))
			heightDecrease = LeftRebalance(head);
	} else {
		found = head;
		//there is no right node, put any left one as the new parent
		head = head->left;
		heightDecrease = true;
	}
	return found;
}

// O(log(n)) : Remove rightmost selected item - caller responsible for deallocation
template <class TNode>
TNode *RemoveMax(TNode *&head) {
	bool heightDecrease;
	if (head == NULL) return NULL;
	return RemoveMax(head, heightDecrease);
}

// O(log(n)) : Remove selected item - caller responsible for deallocation
template <class TNode, class TKey>
TNode *Remove(TNode *&head, TKey &rem, bool &heightDecrease) {
	TNode *found;
	//unexpected case: the item was not even in the tree
	if (head == NULL) {
		found = NULL; // Not found
		heightDecrease = false;
	} else if (rem < *head) {
		//the item to be removed is in the left sub-tree
		found = AVLTree::Remove(head->left, rem, heightDecrease);
		//if something was removed then the tree needs rebalancing
		if (heightDecrease && (++head->bal != 0))
			heightDecrease = RightRebalance(head);
	} else if (*head < rem) {
		//the item to be removed is in the right sub-tree
		found = AVLTree::Remove(head->right, rem, heightDecrease);
		//if something was removed then the tree needs rebalancing
		if (heightDecrease && (--head->bal != 0))
			heightDecrease = LeftRebalance(head);
	} else {
		//if we got here then we have found the item
		found = head;
		if (head->left == NULL) {
			//there is no left node, put any right one as the new parent
			//the right could be NULL, but if so this also does what we want.
			head = head->right;
			heightDecrease = true;
		} else if (head->right == NULL) {
			//there was no right node, but we already know there is a left one so use that
			head = head->left;
			heightDecrease = true;
		} else {
			//difficult case: We need to find a replacement for this node in the tree.
			//this uses leftmost node of the right sub-tree
			TNode *temp = RemoveMin(head->right, heightDecrease);
			//now copy all of the old details in the node being reused
			temp->left = head->left;
			temp->right = head->right;
			temp->bal = head->bal;
			//switch it with the old one
			head = temp;
			//rebalance in case the remove above unbalanced the tree
			if (heightDecrease && (--head->bal != 0))
				heightDecrease = LeftRebalance(head);
		}
	}
	return found;
}

// *** Combining ***
// O(nlog(n+m)) fastest if head2 has fewer items
template <class TNode>
TNode *Merge(TNode *head1, TNode *head2) {
	TNode *l, *r, *curr = head2;
	while (curr != NULL) {
		//remember both children
		l = curr->left;
		r = curr->right;
		//insert current node into other tree
		Insert(head1, curr);
		//recursively add original left subtree
		head1 = Merge(head1, l);
		//iteratively add original right subtree
		curr = r;
	}
	return head1;
}

// O(nlog(n))
template <class TNode, class TKey>
void Partition(TNode *headIn1, const TKey &splitter, TNode *&headOut1, TNode *&headOut2) {
	TNode *l, *r, *curr = headIn1;
	while (curr != NULL) {
		//remember both children
		l = curr->left;
		r = curr->right;
		//decide which list to insert into
		if (*curr < splitter)
			AVLTree::Insert(headOut1, curr);
		else
			AVLTree::Insert(headOut2, curr);
		//recursively continue partitioning left subtree
		AVLTree::Partition(l, splitter, headOut1, headOut2);
		//iteratively continue partitioning right subtree
		curr = r;
	}
}

template <class TNode>
bool Verify(const TNode *head, int &height) {
	if (head != NULL) {
		int leftHeight=0, rightHeight=0;
		if (head->left != NULL) {
			if ((*head < *(head->left))
			|| !Verify(head->left, leftHeight)) return false;
		}
		if (head->right != NULL) {
			if ((*(head->right) < *head)
			|| !Verify(head->right, rightHeight)) return false;
		}
		if ((head->bal < -1)
		|| (head->bal > 1)
		|| (head->bal != rightHeight - leftHeight)) return false;
		height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
	}
	return true;
}	

template <class TNode>
bool Verify(const TNode *head) {
	int height = 0;
	return Verify(head, height);
}

} //namespace AVLTree

#endif