#include <iostream>
using namespace std;

template <class T>
class avl
{
private:
	struct node
	{
		node * left;
		node * right;
		T key;
		int skew;
	};

	node * head;
	node * insert(node *, T);
	void inorderPrint(node *);
	node * leftRotation(node *);
	node * rightRotation(node *);


public:
	
	avl();
	void insert(T);
	void inorderPrint();
	
};


template <class T>
avl<T>::avl()
{
	head = NULL;
}

template <class T>
void avl<T>::insert(T val)
{
	head = insert(head, val);
}

template <class T>
typename avl<T>::node * avl<T>::leftRotation(node * thead)
{
	node * temp1, * temp2;

	temp1 = thead->right;
	temp2 = temp1->right;
	temp1->left = thead;
	thead->right = temp2;
	return temp1;
}

template <class T>
typename avl<T>::node * avl<T>::rightRotation(node * thead)
{
	node * temp1, * temp2;

	temp1 = thead->left;
	temp2 = temp1->left;
	temp1->right = thead;
	thead->left = temp2;
	return temp1;
}

template <class T>
typename avl<T>::node * avl<T>::insert(node * p, T key)
{
	node * looker;

	//when we hit a NULL (bottom of tree
	if(p == NULL)
	{
		//make a new node and set its shit up
		node * temp = new node;
		temp->left = NULL;
		temp->right = NULL;
		temp->key = key;
		temp->skew = 0;
		return temp;
	}

	//if the new key is less than the one we're looking at
	//we go to the left
	if(key < p->key)
	{
		p->left = insert(p->left, key);
		--(p->skew);
		if(p->skew == 0) throw "";

		//looker = p->left;
		//if(p->skew == -2 && looker->skew == 1)
		//{
		//	rightRotation(p);
		//	//throw "";
		//}

		//looker = p->right;
		//if(p->skew == -2 && looker->skew == 1)
		//{
		//	rightRotation(p);
		//	//throw "";
		//}

		//looker = p->left;
		//if(p->skew == -2 && looker->skew == -1)
		//{
		//	leftRotation(looker);
		//	rightRotation(p);
		//	//throw "";
		//}

		//looker = p->right;
		//if(p->skew == -2 && looker->skew == -1)
		//{
		//	leftRotation(looker);
		//	rightRotation(p);
		//	//throw "";
		//}
	}
	//otherwise if it's greater than or equal to the current one
	//we go to the right
	else
	{
		p->right = insert(p->right, key);
		++(p->skew);
		if(p->skew == 0) throw "";

		//looker = p->left;
		//if(p->skew == 2 && looker->skew == 1)
		//{
		//	leftRotation(p);
		//	//throw "";
		//}

		/*looker = p->right;
		if(p->skew == 2 && looker->skew == 1)
		{
			leftRotation(p);
			throw "";
		}*/

		//looker = p->left;
		//if(p->skew == 2 && looker->skew == -1)
		//{
		//	rightRotation(looker);
		//	leftRotation(p);
		//	//throw "";
		//}

		//looker = p->right;
		//if(p->skew == 2 && looker->skew == -1)
		//{
		//	rightRotation(looker);
		//	leftRotation(p);
		//	//throw "";
		//}
	}
	//eventually return
	return p;
}

template <class T>
void avl<T>::inorderPrint()
{
	inorderPrint(head);
}

template <class T>
void avl<T>::inorderPrint(node * head)
{
	//as long as we point at a valid memory address...
	//we perform a preorder traversal
	if(head != NULL)
	{
		//go to the left
		//uncomment for pre-order
		cout<<head->key<<"  skew "<<head->skew<<endl;
		inorderPrint(head->left);
		//insert crap
		//uncomment for in-order
		//cout<<head->key<<"  skew "<<head->skew<<endl;
		//go to the right
		inorderPrint(head->right);
		//uncomment for post-order
		//cout<<head->key<<"  skew "<<head->skew<<endl;
	}
}