/**
 *	@ AVLTreeNode.java
 *	@ Designed by BySelf
 */

import java.util.Stack;
import java.lang.Math;
/**
 *	AVLTreeNode
 *		Tree node used to implemennt the AVLTree.
 *	NOTE:
 *		1. The node has a unique value, that will used to decide its in tree position
 *		2. You should implement rotateLeft and rotateRight for further implementation
 *		   did in AVLTree.
 */
class AVLTreeNode 
{
	/**
	 *	Constructor
	 *		initialize all the node fields values.
	 */
	public AVLTreeNode(int value)
	{
		subTreeHeight = 0;		// initialize to be zero
		leftChild = null;
		rightChild = null;
		parent = null;
		this.value = value;
	}

	/**
	 *	public int balanceValue
	 *		balance value of this TreeNode, initialized to be 0
	 *		balanceValue = leftChild.getSubTreeHeight() - rightChild.getSubTreeHeight().
	 *	NOTE:
	 *		You can use this field and make your AVLTree insert and delete a little 
	 *		easier, but you can also omit it.
	 */
	public int balanceValue;


	/**
	 *	private int value
	 *		Decide the value of this node, which is used to decide the 
	 *		insert position of this node.
	 */
	private int value;

	/**
	 *	public int getValue()
	 *		Get the value of this node.
	 *	NOTE: 
	 *		leftChild.value < this.value < rightChild.value
	 */
	public int getValue()
	{
		return value;
	}

	/**
	 *	private int subTreeHeight
	 *		The balance value of this AVLTreeNode
	 *	NOTE:
	 *		1. initialized to be zero
	 *		2. value = the height of its subtree, i will use this feature
	 *		   to test the correctness of your subTreeHeight
	 *		3. whenever rotate or do something change the height of subtree
	 *		   remember to change its value
	 */
	private int subTreeHeight;

	/**
	 *	public int setValue(int newValue)
	 *		Set this.subTreeHeight to be newValue.
	 *		Return old subTreeHeight;
	 */
	public int setSubTreeHeight(int newValue)
	{
		int oldValue = subTreeHeight;
		subTreeHeight = newValue;
		return oldValue;
	}

	/**
	 *	public int getValue()
	 *		Get current node's subTreeHeight.
	 *		Return this.subTreeHeight.
	 */
	public int getSubTreeHeight()
	{
		return subTreeHeight;
	}

	/**
	 *	private AVLTreeNode leftChild
	 *		The left child of current tree node. It is true that 
	 *		child.subTreeHeight <= this.subTreeHeight-1.
	 */
	private AVLTreeNode leftChild;

	/**
	 *	public AVLTreeNode setLeftChild(AVLTreeNode leftChild)
	 *		Set the left child node.
	 *		Return old child.
	 */
	public AVLTreeNode setLeftChild(AVLTreeNode leftChild)
	{
		AVLTreeNode oldChild = this.leftChild;
		this.leftChild = leftChild;
		return oldChild;
	}

	/**
	 *	public AVLTreeNode getLeftChild()
	 *		Get the left child node of this.
	 */
	public AVLTreeNode getLeftChild()
	{
		return leftChild;
	}

	/**
	 *	private AVLTreeNode rightChild
	 *		The right child of current tree node. It is true that 
	 *		child.subTreeHeight <= this.subTreeHeight-1.
	 *  NOTE: 
	 *      this.subTreeHeight = max(rightChild.subTreeHeight+1, 
	 *								leftChild.subTreeHeight+1).
	 */	
	private AVLTreeNode rightChild;

	/**
	 *	public AVLTreeNode setRightChild(AVLTreeNode rightChild)
	 *		Set the right child node.
	 *		Return old child.
	 */
	public AVLTreeNode setRightChild(AVLTreeNode rightChild)
	{
		AVLTreeNode oldChild = this.rightChild;
		this.rightChild = rightChild;
		return oldChild;
	}

	/**
	 *	public AVLTreeNode getRightChild()
	 *		Get the right child node of this.
	 */
	public AVLTreeNode getRightChild()
	{
		return rightChild;
	}

	/**
	 *	private AVLTreeNode parent
	 *		The parent node of this tree node, it may be useful when
	 *		doing rotating.
	 */
	private AVLTreeNode parent;

	/**
	 *	public AVLTreeNode setParent(AVLTreeNode parent)
	 *		Set the parent node.
	 *		Return old parent.
	 */
	public AVLTreeNode setParent(AVLTreeNode parent)
	{
		AVLTreeNode oldParent = this.parent;
		this.parent = parent;
		return oldParent;
	}

	/**
	 *	public AVLTreeNode getParent()
	 *		Get the parent node of this.
	 */
	public AVLTreeNode getParent()
	{
		return parent;
	}

	public void setBalance(AVLTreeNode node)
	{
		if ( node == null)
			return;
		if ( node.leftChild == null && node.rightChild == null ) 
			node.balanceValue = 0;
		else if ( node.leftChild == null )
			node.balanceValue = -1;
		else if ( node.rightChild == null )
			node.balanceValue = 1;
		else
		{
			if ( node.leftChild.subTreeHeight == node.rightChild.subTreeHeight )
				node.balanceValue = 0;
			else if ( node.leftChild.subTreeHeight < node.rightChild.subTreeHeight )
				node.balanceValue = -1;
			else
				node.balanceValue = 1;
		}
	}

	public void setSubHeight(AVLTreeNode node)
	{
		if ( node == null)
			return;
		if ( node.leftChild == null && node.rightChild == null )
			node.setSubTreeHeight(0);
		else if ( node.leftChild == null )
			node.setSubTreeHeight( node.rightChild.subTreeHeight + 1 );
		else if ( node.rightChild == null )
			node.setSubTreeHeight( node.leftChild.subTreeHeight + 1 );
		else
			node.setSubTreeHeight( Math.max( node.leftChild.subTreeHeight + 1, node.rightChild.subTreeHeight + 1 ) );
	}
	/**
	 *	public AVLTreeNode rotateLeft();
	 *		Rotate current AVLTreeNode left, then return the parent node
	 *	NOTE:
	 *		Do not forget to change balance value when doing rotate
	 */
	public AVLTreeNode rotateLeft()
	{
		// fill your implementation code here
		// you can change the return value as you like
		// remember that you cannot change the _value_ field
		AVLTreeNode temp = this.parent;
		AVLTreeNode node1 = this;
		AVLTreeNode node2 = this.leftChild;
		
		if ( temp == null )
			return null;

		node1.setParent(temp.parent);
		if ( temp.parent != null )
		{
			if ( temp.value < temp.parent.value )
				temp.parent.setLeftChild(node1);
			else
				temp.parent.setRightChild(node1);
		}

		node1.setLeftChild(temp);
		temp.setParent(node1);
		
		temp.setRightChild(node2);
		if ( node2 != null )
			node2.setParent(temp);

		setSubHeight(temp);
		setSubHeight(node1);
		setSubHeight(node2);
		setBalance(temp);
		setBalance(node1);
System.out.println(node1.value+" "+node1.subTreeHeight);/////////////////////////////////
		return node1;
	}

	/**
	 *	public AVLTreeNode rotateRight();
	 *		Rotate current AVLTreeNode right, then return the parent node
	 *	NOTE:
	 *		Do not forget to change balance value when doing rotate
	 */
	public AVLTreeNode rotateRight()
	{
		// fill your implementation code here
		// you can change the return value as you like
		// remember that you cannot change the _value_ field
		AVLTreeNode temp = this;
		AVLTreeNode node1 = this.leftChild;
		AVLTreeNode node2 = this.leftChild.rightChild;

		if ( node1 == null )
			return null;

		node1.setParent(this.parent);
		if ( this.parent != null )
		{
			if ( this.value < this.parent.value )
				this.parent.setLeftChild(node1);
			else
				this.parent.setRightChild(node1);
		}

		node1.setRightChild(temp);
		temp.setParent(node1);

		temp.setLeftChild(node2);
		if ( node2 != null )
			node2.setParent(temp);

		setSubHeight(temp);
		setSubHeight(node1);
		setSubHeight(node2);
		setBalance(temp);
		setBalance(node1);
System.out.println(node1.subTreeHeight);//////////////////////////////
		return node1;
	}

	/**
	 *	public void inOrder(AVLTreeNode node)
	 *		Do inOrder walk in this subnode.
	 */
	public static void inOrder(AVLTreeNode node)
	{
		Stack stack=new Stack();
		stack.push(node);
		while(!stack.empty())
		{
			Object obj = stack.pop();
			if(obj instanceof AVLTreeNode)
			{
				AVLTreeNode curNode = (AVLTreeNode)obj;
				if (curNode.rightChild != null)
					stack.push(curNode.rightChild);
				stack.push(new Integer(curNode.value));
				if (curNode.leftChild != null)
					stack.push(curNode.leftChild);
			}
			else
			{
				System.out.print("[" + obj + "] ");
			}
		}
	}

	/**
	 *	public static void main(String[] args)
	 *		Do test.
	 */
	public static void main(String[] args) 
	{
		System.out.println("============ Testing Rotate ============");
		System.out.println(">>>> In order walk should always be:");
		System.out.println("[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18]");
		System.out.println();
//	init tree: 
//                           [15]
//                         /       \
//                    [11]           [17]
//                  /      \        /    \
//              [7]        [13]   [16]  [18]
//            /     \     /    \   
//         [3]      [9] [12]  [14]
//        /   \     / \  
//      [1]   [5] [8] [10]
//      / \   / \
//    [0][2][4][6]

		AVLTreeNode[] node = new AVLTreeNode[19];
		for (int i = 0; i < 19; i++)
		{
			node[i] = new AVLTreeNode(i);
		}
		node[0].parent = node[1];
		node[2].parent = node[1];
		node[1].leftChild = node[0];
		node[1].rightChild = node[2];

		node[4].parent = node[5];
		node[6].parent = node[5];
		node[5].leftChild = node[4];
		node[5].rightChild = node[6];

		node[1].parent = node[3];
		node[5].parent = node[3];
		node[3].leftChild = node[1];
		node[3].rightChild = node[5];

		node[8].parent = node[9];
		node[10].parent = node[9];
		node[9].leftChild = node[8];
		node[9].rightChild = node[10];

		node[3].parent = node[7];
		node[9].parent = node[7];
		node[7].leftChild = node[3];
		node[7].rightChild = node[9];

		node[12].parent = node[13];
		node[14].parent = node[13];
		node[13].leftChild = node[12];
		node[13].rightChild = node[14];

		node[7].parent = node[11];
		node[13].parent = node[11];
		node[11].leftChild = node[7];
		node[11].rightChild = node[13];

		node[16].parent = node[17];
		node[18].parent = node[17];
		node[17].leftChild = node[16];
		node[17].rightChild = node[18];

		node[11].parent = node[15];
		node[17].parent = node[15];
		node[15].leftChild = node[11];
		node[15].rightChild = node[17];

		System.out.println("First inwalk after init:");
		AVLTreeNode.inOrder(node[15]);
		System.out.println();
		System.out.println();

// After node[11].rotateRight:
//                         [15]
//                      /         \
//                [7]                [17]
//              /     \             /    \
//         [3]          [11]      [16]  [18]
//        /   \        /    \
//      [1]   [5]   [9]      [13]
//      / \   / \   / \     /    \     
//    [0][2][4][6][8] [10][12]  [14]

		System.out.println(">>>> Rotating right:");
		AVLTreeNode a7 = node[11].rotateRight();
		System.out.println("Rotating finished");
		System.out.println("Check subtree root node current subtree root node should be [ 7 ]:");
		System.out.println("> The result subtree root is : [ " + a7.getValue() + " ]");
		System.out.println("> Parent of node [ 7 ] should be [ 15 ] : [ " 
				+ node[7].parent.getValue() + " ]");
		System.out.println("> Left child of node [ 7 ] should be [ 3 ] : [ " 
				+ node[7].leftChild.getValue() + " ]");
		System.out.println("> Right child of node [ 7 ] should be [ 11 ] : [ " 
				+ node[7].rightChild.getValue() + " ]");
		System.out.println("> Parent of node [ 9 ] should be [ 11 ] : [ " 
				+ node[9].parent.getValue() + " ]");
		System.out.println("> Parent of node [ 11 ] should be [ 7 ] : [ " 
				+ node[11].parent.getValue() + " ]");
		System.out.println("> Left child of node [ 11 ] should be [ 9 ] : [ " 
				+ node[11].leftChild.getValue() + " ]");
		System.out.println("> Left child of node [ 15 ] should be [ 7 ] : [ " 
				+ node[15].leftChild.getValue() + " ]");

		System.out.println();

		System.out.println("Second inwalk after rotate right:");
		AVLTreeNode.inOrder(node[15]);
		System.out.println();
		System.out.println();

// After node[11].rotateLeft:
//                           [15]
//                         /       \
//                    [11]           [17]
//                  /      \        /    \
//              [7]        [13]   [16]  [18]
//            /     \     /    \   
//         [3]      [9] [12]  [14]
//        /   \     / \  
//      [1]   [5] [8] [10]
//      / \   / \
//    [0][2][4][6]
		System.out.println(">>>> Rotating left:");
		AVLTreeNode a11 = node[11].rotateLeft();
		System.out.println("Rotating finished");
		System.out.println("Check subtree root node current subtree root node should be [ 11 ]:");
		System.out.println("> The result subtree root is : [ " + a11.getValue() + " ]");
		System.out.println("> Parent of node [ 7 ] should be [ 11 ] : [ " 
				+ node[7].parent.getValue() + " ]");
		System.out.println("> Left child of node [ 7 ] should be [ 3 ] : [ " 
				+ node[7].leftChild.getValue() + " ]");
		System.out.println("> Right child of node [ 7 ] should be [ 9 ] : [ " 
				+ node[7].rightChild.getValue() + " ]");
		System.out.println("> Parent of node [ 9 ] should be [ 7 ] : [ " 
				+ node[9].parent.getValue() + " ]");
		System.out.println("> Parent of node [ 11 ] should be [ 15 ] : [ " 
				+ node[11].parent.getValue() + " ]");
		System.out.println("> Left child of node [ 11 ] should be [ 7 ] : [ " 
				+ node[11].leftChild.getValue() + " ]");
		System.out.println("> Left child of node [ 15 ] should be [ 11 ] : [ " 
				+ node[15].leftChild.getValue() + " ]");

		System.out.println();

		System.out.println("Third inwalk after rotate left:");
		AVLTreeNode.inOrder(node[15]);
		System.out.println();
		System.out.println();
	}
}