/*********************************************************************
Filename:  avltree.cpp

Programmer:  Br. David Carlson

Reference:  Data Structures with C++, by Ford and Topp.

Date:  October 12, 1997

Revised:  June 9, 1999 to use the type AVLNodePtr, to supply code for 
a copy constructor, and also to change each C-style cast to a 
reinterpret_cast.

This file implements the functions of the AVLClass as set up in 
avltree.h.

Source code publicly available from:
http://cis.stvincent.edu/carlsond/swdesign/avltrees/avltrees.html

Modifications made by N. Loontjer (04/24/01)
*********************************************************************/

#include "avltree.h"


/* Given:   Item          A data item to insert in a new node.
            LeftPtr       A pointer to place in Left field of the new node.
            RightPtr      A pointer to place in the Right field.
            BalanceValue  A value to put in Balance field of the node.
   Task:    To create a new node filled with the above 4 values.
   Return:  A pointer to the new node in the function name.
*/
AVLNodePtr AVLClass::GetNode(const ItemType & Item, 
		  AVLNodeClass * LeftPtr, AVLNodePtr RightPtr, int BalanceValue)
{
	AVLNodePtr NodePtr;

	NodePtr = new AVLNodeClass(Item, LeftPtr, RightPtr, BalanceValue);
	if (NodePtr == NULL)
	{
		cerr << "Memory allocation error!" << endl;
		exit(1);
	}
	return NodePtr;
}


/* Given:  NodePtr   A pointer to a node of the implicit AVL tree.
   Task:   To reclaim the space used by this node.
   Return: Nothing directly, but the implicit object is modified.
*/
void AVLClass::FreeNode(AVLNodePtr NodePtr)
{
	delete NodePtr;
}


/* Given:  Nothing (other than the implicit AVLClass object).
   Task:   This is the destructor.  It's job is to wipe out all data
           storage used by this AVL tree.
   Return: Nothing directly, but the implicit AVLClass object is destroyed.
*/
AVLClass::~AVLClass(void)
{
	ClearTree();
}


/* Given:  Nothing (other than the implicit AVLClass object).
   Task:   To clear out all nodes of the implicit AVL tree.
   Return: Nothing directly, but the implicit AVLClass object is modified
           to be an empty AVL tree.
*/
void AVLClass::ClearTree(void)
{
	ClearSubtree(reinterpret_cast <AVLNodePtr> (Root));
	Root = NULL;
	UniqueCount = 0;
	DuplicateCount = 0;
	Comparisons = 0;
}


/* Given:  Current   A pointer to a node in the implicit AVLClass object.
   Task:   To wipe out all nodes of this subtree.
   Return: Nothing directly, but the implicit AVLClass object is modified.
*/
void AVLClass::ClearSubtree(AVLNodePtr Current)
{
//  Use a postorder traversal:
	if (Current != NULL)
	{
		ClearSubtree(reinterpret_cast <AVLNodePtr> (Current->Left));
		ClearSubtree(reinterpret_cast <AVLNodePtr> (Current->Right));
		FreeNode(Current);
	}
}


/* Given:  Tree   An AVL tree.
   Task:   To copy Tree into the current (implicit) AVL tree object.
   Return: Nothing directly, but the implicit AVL tree is modified.
*/
void AVLClass::CopyTree(const AVLClass & Tree)
{
	Root = CopySubtree(reinterpret_cast <AVLNodePtr> (Tree.Root));
	UniqueCount = Tree.UniqueCount;
	DuplicateCount = Tree.DuplicateCount;
	Comparisons = Tree.Comparisons;
}


/* Given:  Current   Pointer to the current node of the implicit AVL tree.
   Task:   To make a copy of the subtree starting at node Current.
   Return: A pointer to the root node of this copy.
*/
AVLNodePtr AVLClass::CopySubtree(const AVLNodePtr Current)
{
	AVLNodePtr NewLeftPtr, NewRightPtr, NewParentPtr;
   
	if (Current == NULL)
		return NULL;

	if (Current->Left == NULL)
		NewLeftPtr = NULL;
	else
		NewLeftPtr = CopySubtree(reinterpret_cast <AVLNodePtr> (Current->Left));

	if (Current->Right == NULL)
		NewRightPtr = NULL;
	else
		NewRightPtr = CopySubtree(reinterpret_cast <AVLNodePtr> (Current->Right));

	NewParentPtr = GetNode(Current->Info, NewLeftPtr, NewRightPtr, 
		Current->Balance);

	return NewParentPtr;
}


/* Given:  ParentPtr   A pointer to the node at which to rotate left.
   Task:   To do a left rotation at the node specified above in the implicit
           AVL tree object.
   Return: ParentPtr   Points to the new root node of the rotated subtree.
           Note that the implicit AVL tree is modified.
*/
void AVLClass::SingleRotateLeft(AVLNodePtr & ParentPtr)
{
	AVLNodePtr RightChildPtr;

	RightChildPtr = reinterpret_cast <AVLNodePtr> (ParentPtr->Right);
	ParentPtr->Balance = Balanced;
	RightChildPtr->Balance = Balanced;
	ParentPtr->Right = RightChildPtr->Left;
	RightChildPtr->Left = ParentPtr;
	ParentPtr = RightChildPtr;
}


/* Given:  ParentPtr   A pointer to the node at which to rotate right.
   Task:   To do a right rotation at the node specified above in the
           implicit AVL tree object.
   Return: ParentPtr   Points to the new root node of the rotated subtree.
           Note that the implicit AVL tree is modified.
*/
void AVLClass::SingleRotateRight(AVLNodePtr & ParentPtr)
{
AVLNodePtr LeftChildPtr;

	LeftChildPtr = reinterpret_cast <AVLNodePtr> (ParentPtr->Left);
	ParentPtr->Balance = Balanced;
	LeftChildPtr->Balance = Balanced;
	ParentPtr->Left = LeftChildPtr->Right;
	LeftChildPtr->Right = ParentPtr;
	ParentPtr = LeftChildPtr;
}


/* Given:  ParentPtr   A pointer to the node at which to double rotate left.
   Task:   To do a double left rotation at the node specified above in the
           implicit AVL tree object.
   Return: ParentPtr   Points to the new root node of the rotated subtree.
           Note that the implicit AVL tree is modified.
*/
void AVLClass::DoubleRotateLeft(AVLNodePtr & ParentPtr)
{
	AVLNodePtr RightChildPtr, NewParentPtr;

	RightChildPtr = reinterpret_cast <AVLNodePtr> (ParentPtr->Right);
	NewParentPtr = reinterpret_cast <AVLNodePtr> (RightChildPtr->Left);

	if(NewParentPtr->Balance == LeftHeavy)
    {
		Comparisons++;
		ParentPtr->Balance = Balanced;
		RightChildPtr->Balance = RightHeavy;   // patched to fix bug in book
	}
	else if (NewParentPtr->Balance == Balanced)
    {
		Comparisons += 2;
		ParentPtr->Balance = Balanced;
		RightChildPtr->Balance = Balanced;
    }
	else
    {
		Comparisons += 2;
		ParentPtr->Balance = LeftHeavy;
		RightChildPtr->Balance = Balanced;
    }

	NewParentPtr->Balance = Balanced;
	RightChildPtr->Left = NewParentPtr->Right;
	NewParentPtr->Right = RightChildPtr;
	ParentPtr->Right = NewParentPtr->Left;
	NewParentPtr->Left = ParentPtr;
	ParentPtr = NewParentPtr;
}


/* Given:  ParentPtr   Pointer to the node at which to double rotate right.
   Task:   To do a double right rotation at the node specified above in the
           implicit AVL tree object.
   Return: ParentPtr   Points to the new root node of the rotated subtree.
           Note that the implicit AVL tree is modified.
*/
void AVLClass::DoubleRotateRight(AVLNodePtr & ParentPtr)
{
	AVLNodePtr LeftChildPtr, NewParentPtr;

	LeftChildPtr = reinterpret_cast <AVLNodePtr> (ParentPtr->Left);
	NewParentPtr = reinterpret_cast <AVLNodePtr> (LeftChildPtr->Right);

	if(NewParentPtr->Balance == RightHeavy)
    {
		Comparisons++;
		ParentPtr->Balance = Balanced;
		LeftChildPtr->Balance = LeftHeavy;   // patched to fix bug in book
    }
	else if (NewParentPtr->Balance == Balanced)
    {
		Comparisons += 2;
		ParentPtr->Balance = Balanced;
		LeftChildPtr->Balance = Balanced;
    }
	else
    {
		Comparisons += 2;
		ParentPtr->Balance = RightHeavy;
		LeftChildPtr->Balance = Balanced;
    }

	NewParentPtr->Balance = Balanced;
	LeftChildPtr->Right = NewParentPtr->Left;
	NewParentPtr->Left = LeftChildPtr;
	ParentPtr->Left = NewParentPtr->Right;
	NewParentPtr->Right = ParentPtr;
	ParentPtr = NewParentPtr;
}


/* Given:  ParentPtr      Pointer to parent node, whose subtree needs
                          to be updated to an AVL tree (due to insertion).
           ReviseBalance  Indicates if we need to revise balances.
   Assume: Subtree rooted at this parent node is left heavy.
   Task:   To update this subtree so that it forms an AVL tree.
   Return: ParentPtr      Points to the root node of the updated subtree.
           ReviseBalance  Indicates if we need to revise balances.
           Note that the implicit AVL tree is modified.
*/
void AVLClass::UpdateLeftTree(AVLNodePtr & ParentPtr, bool & ReviseBalance)
{
	AVLNodePtr LeftChildPtr;

	LeftChildPtr = reinterpret_cast <AVLNodePtr> (ParentPtr->Left);
	if (LeftChildPtr->Balance == LeftHeavy)
    {   // left subtree is also left heavy
		Comparisons++;
		SingleRotateRight(ParentPtr);
		ReviseBalance = false;
    }
	else if (LeftChildPtr->Balance == RightHeavy)
    {   // right subtree is also right heavy
		Comparisons += 2;
		DoubleRotateRight(ParentPtr);
		ReviseBalance = false;
    }
}


/* Given:  ParentPtr      Pointer to parent node, whose subtree needs
                          to be updated to an AVL tree (due to insertion).
           ReviseBalance  Indicates if we need to revise balances.
   Assume: Subtree rooted at this parent node is right heavy.
   Task:   To update this subtree so that it forms an AVL tree.
   Return: ParentPtr      Points to the root node of the updated subtree.
           ReviseBalance  Indicates if we need to revise balances.
           Note that the implicit AVL tree is modified.
*/
void AVLClass::UpdateRightTree(AVLNodePtr & ParentPtr, bool & ReviseBalance)
{
AVLNodePtr RightChildPtr;

	RightChildPtr = reinterpret_cast <AVLNodePtr> (ParentPtr->Right);
	if (RightChildPtr->Balance == RightHeavy)
    {   // right subtree is also right heavy
		Comparisons++;
		SingleRotateLeft(ParentPtr);
		ReviseBalance = false;
    }
	else if (RightChildPtr->Balance == LeftHeavy)
    {   // right subtree is also left heavy
		Comparisons += 2;
		DoubleRotateLeft(ParentPtr);
		ReviseBalance = false;
    }
}


/* Given:  Tree           Pointer to node of implicit AVL tree.  This node
                          is the root of the subtree in which to insert.
           NewNodePtr     Pointer to the new node to be inserted.
           ReviseBalance  Indicates if we need to revise balances.
   Task:   To insert the new node in the subtree indicated above.
   Return: Tree           Pointer to the root node of the subtree.
           ReviseBalance  Indicates if we need to revise balances.
           Note that the implicit AVL tree object is modified.
*/
void AVLClass::AVLInsert(AVLNodePtr & Tree, AVLNodePtr NewNodePtr,
   bool & ReviseBalance)
{
	bool RebalanceCurrentNode;

	if (Tree == NULL)   // insert in empty subtree
	{
		UniqueCount++;
		Tree = NewNodePtr;
		Tree->Balance = Balanced;
		ReviseBalance = true;  // tell others to check balances due to new node
	}
	else if (NewNodePtr->Info < Tree->Info)
    {
		Comparisons++;
		AVLInsert(reinterpret_cast <AVLNodePtr &> (Tree->Left), NewNodePtr,
				  RebalanceCurrentNode);
		if (RebalanceCurrentNode)
        {
			if (Tree->Balance == LeftHeavy)   // now 1 node worse than this
			{
				Comparisons++;
				UpdateLeftTree(Tree, ReviseBalance);
			}
			else if (Tree->Balance == Balanced)   // was balanced, now 1 extra
			{
				Comparisons += 2;
				Tree->Balance = LeftHeavy;
				ReviseBalance = true;
			}
			else   // was right heavy, due to extra node on left now balanced
			{
				Comparisons += 2;
				Tree->Balance = Balanced;
				ReviseBalance = false;
			}
		}
		else
			ReviseBalance = false;
	}
	else if (NewNodePtr->Info > Tree->Info)
    {
		Comparisons += 2;
		AVLInsert(reinterpret_cast <AVLNodePtr &> (Tree->Right), NewNodePtr,
				  RebalanceCurrentNode);
		if (RebalanceCurrentNode)
        {
			if (Tree->Balance == LeftHeavy)  // extra node on right balances it
            {
				Comparisons++;
				Tree->Balance = Balanced;
				ReviseBalance = false;
            }
			else if (Tree->Balance == Balanced)   // now 1 node heavy on right
            {
				Comparisons += 2;
				Tree->Balance = RightHeavy;
				ReviseBalance = true;
            }
			else   // was right heavy, now off by 2 on right, must fix:
			{
				UpdateRightTree(Tree, ReviseBalance);
				Comparisons += 2;
			}
		}
		else
			ReviseBalance = false;
	}
	
	else	// Duplicate of current 'Tree'
	{
		DuplicateCount++;
		(Tree->Duplicates)++;
		ReviseBalance = false;
	}
	
}


/* Given:  Nothing.
   Task:   This is the default constructor for creating the implicit AVL
           tree object.
   Return: Nothing directly, but the implicit AVL tree object is created.
*/
AVLClass::AVLClass(void)
{
	// just use the automatic BSTClass default constructor
}


/* Given:  Tree   An AVLClass object.
   Task:   This is the copy constructor.  It copies Tree into the implicit
           AVL tree object.
   Return: Nothing directly, but the implicit AVL tree object is modified.
*/
AVLClass::AVLClass(const AVLClass & Tree)
{
	CopyTree(Tree);
}


/* Given:  Tree   AN AVLClass object.
   Task:   This is the overloaded = operator.  It places into the implicit
           AVL tree object an identical copy of Tree.
   Return: A reference to the modified AVLClass object (in case one wants
           to use something like C = B = A).
*/
AVLClass & AVLClass::operator=(const AVLClass& Tree)
{
	// cannot copy a tree to itself:
	if (this == &Tree)
		return *this;
	ClearTree();
	CopyTree(Tree);
	return *this;
}


/* Given:  Item  A data item to be inserted into the implicit AVL tree.
   Task:   To insert Item (in a new node) in the AVL tree.
   Return: Nothing directly, but the implicit AVL tree object is modified.
*/
void AVLClass::Insert(const ItemType & Item)
{
	AVLNodePtr NewNodePtr;
	bool ReviseBalance = false;

	NewNodePtr = GetNode(Item);
	AVLInsert(reinterpret_cast <AVLNodePtr &> (Root), NewNodePtr, 
		ReviseBalance);
}