#include <iostream>
#include "classes.h"

using namespace std;

node * bin_tree :: getnode (void)
{
	node *p;
	
	p = new node;
	
	p->info = 0;
	p->leftson = NULL;
	p->rightson = NULL;
	p->father = NULL;
	
	return p;
}

void bin_tree :: add_node (int a)
{
	node *p = getnode ();
	p->info = a;
	
	if (root == NULL)
		root = p;
	else
	{
		node *q, *r;
		
		q = NULL, r = root;
		
		while (r != NULL)
		{
			q = r;
			
			if (a < r->info)
				r = r->leftson;
			else
				r = r->rightson;
		
		}
		
		if (a < q->info)
			q->leftson = p;
		else
			q->rightson = p;
		p->father = q;
	}
	
	// following for AVL rotations
	
	while (p != NULL)
	{
		int hright = height (p->rightson);
		int hleft = height (p->leftson);
		p->balance_factor = hleft - hright;
		
		if (p->balance_factor == 2)
		{
			if ((p->leftson)->balance_factor == 1)
				rrotate (p);
			else if ((p->leftson)->balance_factor == -1)
				rlrotate (p);
			break;
		}
		if (p->balance_factor == -2)
		{
			if ((p->rightson)->balance_factor == -1)
				lrotate (p);
			else if ((p->rightson)->balance_factor == 1)
				lrrotate (p);
			break;
		}
		
		p = p->father;
	}
}

void bin_tree :: preorder (node *tree)
{
	node *p = tree;
	
	if (p != NULL)
	{
		cout << p->info << ' ';
		preorder (p->leftson);
		preorder (p->rightson);
	}
}

void bin_tree :: inorder (node *tree)
{
	node *p = tree;
	
	if (p != NULL)
	{
		inorder (p->leftson);
		cout << p->info << ' ';
		inorder (p->rightson);
	}
}

void bin_tree :: postorder (node *tree)
{
	node *p = tree;
	
	if (p != NULL)
	{
		postorder (p->leftson);
		postorder (p->rightson);
		cout << p->info << ' ';
	}
}

void bin_tree :: display (traversal_type type)
{

	switch (type)
	{
		case bfs_order:
			cout << "Bredth First Traversal: ";
			bredth_first (root);
			break;
		case dfs_preorder:
			cout << "Preorder Traversal: ";
			preorder (root);
			break;
		case dfs_inorder:	
			cout << endl << "Inorder Tranversal: ";
			inorder (root);
			break;
		case dfs_postorder:
			cout << endl << "Postorder Tranversal: ";
			postorder (root);
			break;
	}	
	cout << endl;
}

int bin_tree :: height (node *p)
{
	int a, b;
	if (p == NULL)
		return -1;
	else
	{
		a = height (p->leftson);
		b = height (p->rightson);
		
		return (a > b) ? a+1 : b+1;
	}
}

void bin_tree :: rrotate (node *p)
{
	node *pfather, *pleftson;
	
	pfather = p->father, pleftson = p->leftson;
	
	pleftson->father = p->father;
	if (pfather == NULL)
		root = pleftson;
	else
	{
		if (pfather->leftson == p)
			pfather->leftson = pleftson;
		else
			pfather->rightson = pleftson;
	}
	
	if (pleftson->rightson != NULL)
		(pleftson->rightson)->father = p;
	p->leftson = pleftson->rightson;
	
	pleftson->rightson = p;
	p->father = pleftson;
}

void bin_tree :: lrotate (node *p)
{
	node *pfather, *prightson;
	
	pfather = p->father, prightson = p->rightson;

	prightson->father = p->father;
	if (pfather == NULL)
		root = prightson;
	else
	{
		if (pfather->leftson == p)
			pfather->leftson = prightson;
		else
			pfather->rightson = prightson;
	}
	
	if (prightson->leftson != NULL)
		(prightson->leftson)->father = p;
	p->rightson = prightson->leftson;
	
	prightson->leftson = p;
	p->father = prightson;
}

void bin_tree :: rlrotate (node *p)
{
	node *pfather, *pleftson, *newp;
	
	pfather = p->father, pleftson = p->leftson;
	newp = pleftson->rightson;
	
	if (newp->rightson != NULL)
		(newp->rightson)->father = p;
	p->leftson = newp->rightson;
	
	if (newp->leftson != NULL)
		(newp->leftson)->father = pleftson;
	pleftson->rightson = newp->leftson;
	
	if (pfather == NULL)
		root = newp;
	else
	{
		if (pfather->leftson == p)
			pfather->leftson = newp;
		else
			pfather->rightson = newp;
	}
	newp->father = pfather;
	
	p->father = newp;
	newp->rightson = p;
	newp->leftson = pleftson;
	pleftson->father = newp;
}

void bin_tree :: lrrotate (node *p)
{
	node *pfather, *prightson, *newp;
	
	pfather = p->father, prightson = p->rightson;
	newp = prightson->leftson;
	
	if (newp->leftson != NULL)
		(newp->leftson)->father = p;
	p->rightson = newp->leftson;
	
	if (newp->rightson != NULL)
		(newp->rightson)->father = prightson;
	prightson->leftson = newp->rightson;
	
	if (pfather == NULL)
		root = newp;
	else
	{
		if (pfather->leftson == p)
			pfather->leftson = newp;
		else
			pfather->rightson = newp;
	}
	newp->father = pfather;
	
	p->father = newp;
	newp->leftson = p;
	newp->rightson = prightson;
	prightson->father = newp;
}

void bin_tree :: bredth_first (node *tree)
{
	queue q;
	
	q.insert (tree);
	
	if (tree == NULL)
		return;
	
	while (q.isempty() == false)
	{
		tree = q.remove();
		cout << tree->info << ' ';
		if (tree->leftson != NULL)
			q.insert (tree->leftson);
		if (tree->rightson != NULL)
			q.insert (tree->rightson);
	}
}