import java.util.*;
import java.awt.*;
import java.text.*;

public class BinaryTreeNode {

	int node_data;                     // Node data stored as an int value.

	BinaryTreeNode leftChild = null;   // Left and right chidren for this node
	BinaryTreeNode rightChild = null;
	BinaryTreeNode parent = null;      // Parent node

	UUID nodeId = null;             // we will use this to uniquely identify each node                

	boolean rotateAlternate()
	{
		// Currently this method is a carbon copy of rotate().
		// 
		// DO NOT MODIFY LINES IN THIS METHOD TILL "START MODIFY" BELOW
		// The variables below are essential and correspond to the graphics 
		// on the lab page.
		
		
		BinaryTreeNode leftLeftChild = null,
		leftRightChild = null,
		rightLeftChild = null,
		rightRightChild = null,
		curLeftChild = null,
		curRightChild = null,
		curParent = this.parent;

		if( this.leftChild != null )
		{
			curLeftChild = this.leftChild;
			leftLeftChild = leftChild.leftChild;
			leftRightChild = leftChild.rightChild;
		}
		if( this.rightChild != null )
		{
			curRightChild = this.rightChild;
			rightLeftChild = rightChild.leftChild;
			rightRightChild = rightChild.rightChild;
		}

		// START MODIFYING LINES IN THIS METHOD FROM HERE TILL END OF METHOD
		
		// Minimal but thoughtful changes are needed :)
		
		if( curLeftChild == null )
			return false; // Unsuccessful rotation

		this.leftChild = leftRightChild;
		if( leftRightChild != null )
			leftRightChild.parent = this;

		curLeftChild.rightChild = this;
		this.parent = curLeftChild;

		curLeftChild.parent = curParent;

		// We use nodeId to check if the current node, i.e. "this" is a 
		// left or right child of its parent so we can change the 
		// parent to point to its new child.
		
		if( curParent.leftChild != null && curParent.leftChild.nodeId == this.nodeId )
			//current node is left child of its parent
			curParent.leftChild = curLeftChild;
		else
			curParent.rightChild = curLeftChild;
		
		return true; // successful rotation
	}

	boolean rotate()
	{
		// THIS IS A WORKING METHOD, NOTHING TO CHANGE
		
		
		BinaryTreeNode leftLeftChild = null,
		leftRightChild = null,
		rightLeftChild = null,
		rightRightChild = null,
		curLeftChild = null,
		curRightChild = null,
		curParent = this.parent;

		if( this.leftChild != null )
		{
			curLeftChild = this.leftChild;
			leftLeftChild = leftChild.leftChild;
			leftRightChild = leftChild.rightChild;
		}
		if( this.rightChild != null )
		{
			curRightChild = this.rightChild;
			rightLeftChild = rightChild.leftChild;
			rightRightChild = rightChild.rightChild;
		}

		if( curLeftChild == null )
			return false; // Unsuccessful rotation

		this.leftChild = leftRightChild;
		if( leftRightChild != null )
			leftRightChild.parent = this;

		curLeftChild.rightChild = this;
		this.parent = curLeftChild;

		curLeftChild.parent = curParent;

		if( curParent.leftChild != null && curParent.leftChild.nodeId == this.nodeId )
			//current node is left child of its parent
			curParent.leftChild = curLeftChild;
		else
			curParent.rightChild = curLeftChild;
		
		return true; // successful rotation
	}


	void addGraphics( Graphics g )
	{
		treeNodes = new Vector<BinaryTreeNode>();
		preorderDisplayGraphics(g, 50, 50);
	}
	
	int height()
	{
		if(leftChild == null && rightChild == null )
			return 0;
		else if (leftChild == null)
			return rightChild.height() + 1;
		else if (rightChild == null)
			return leftChild.height() + 1;
		else
			return Math.max(leftChild.height(), rightChild.height()) + 1;
	}
	
	boolean isNodeBalanced()
	{
		int leftHeight = 0, rightHeight = 0;
		if( leftChild != null )
			leftHeight = leftChild.height() + 1;
		if( rightChild != null )
			rightHeight = rightChild.height() + 1;
		return Math.abs(leftHeight - rightHeight) < 2;
	}

	int preorderDisplayGraphics(Graphics g, int x_offset, int y_offset )
	{
		int x_jump = 70, y_jump = 50;

		if( nodeId == null )  // Dummy root node
		{
			leftChild.preorderDisplayGraphics(g, x_offset, y_offset );
			return 0;
		}
		
		if( this.isNodeBalanced() )
			g.setColor(Color.ORANGE);
		else
			g.setColor(Color.gray);
		drawNumberCircle( g, node_data, x_offset, y_offset, node_diameter );
		
		this.node_x = x_offset + node_diameter / 2;
		this.node_y = y_offset + node_diameter / 2;
		treeNodes.add(this);

		int new_x = x_offset + x_jump;
		int new_y = y_offset;

		if( leftChild != null )
		{
			drawLine(g, x_offset, y_offset, new_x, new_y, node_diameter );
			new_y = y_jump + leftChild.preorderDisplayGraphics(g, new_x, new_y);
		}
		else
			new_y += y_jump;

		if( rightChild != null )
		{
			drawLine(g, x_offset, y_offset, new_x, new_y, node_diameter );
			new_y = y_jump + rightChild.preorderDisplayGraphics(g, new_x, new_y);
		}
		new_y -= y_jump;

		return new_y;
	}

	// Draws a circle at coordinates (node_x, node_y) with the node_value inside 
	void drawNumberCircle(Graphics g, int node_value, int node_x, int node_y, int diameter)
	{
		
		g.fillOval( node_x, node_y, diameter, diameter );

		g.setColor(Color.RED);
		g.setFont(new Font("Verdana",Font.BOLD,15));
		g.drawString( ""+node_value, node_x + diameter/2 - 12, node_y + diameter/2 +5 );
	}

	// Draws a line between node1 coordinates (node1_x, node1_y) 
	// and node2 coordinates (node2_x, node2_y)
	void drawLine( Graphics g, int node1_x, int node1_y, int node2_x, int node2_y, int diameter )
	{
		int radius = diameter / 2;
		int x1 = node1_x + radius;
		int y1 = node1_y + radius;
		int x2 = node2_x + radius;
		int y2 = node2_y + radius;
		double dist = Math.sqrt(Math.pow((x1 - x2), 2)+Math.pow((y1 - y2), 2));
		double alpha1 = radius / dist;
		double alpha2 = (dist - radius) / dist;
		int xn1 = (int)(alpha1 * x1 + (1 - alpha1) * x2);
		int yn1 = (int)(alpha1 * y1 + (1 - alpha1) * y2);
		int xn2 = (int)(alpha2 * x1 + (1 - alpha2) * x2);
		int yn2 = (int)(alpha2 * y1 + (1 - alpha2) * y2);

		g.drawLine(xn1, yn1, xn2, yn2);
	}

	static Random rand = new Random(222);
	static int node_diameter = 40;
	
	BinaryTreeNode( int height, BinaryTreeNode parent_node, int lowerRange, int upperRange )
	{
		if( parent_node == null )
		{
			nodeId = null;
			leftChild = new BinaryTreeNode( height, this, lowerRange, upperRange );
			return;
		}
		
		nodeId = UUID.randomUUID();
		this.parent = parent_node;
		
		if( upperRange == lowerRange )
			node_data = lowerRange;
		else
			node_data = rand.nextInt(upperRange - lowerRange) + lowerRange;
		
		if( height > 0 && rand.nextInt(2) > 0 && node_data - lowerRange > 0 )
		{
			leftChild = new BinaryTreeNode(height - 1, this, lowerRange, node_data - 1);
		}
		if( height > 0 && rand.nextInt(2) > 0 && upperRange - node_data > 0)
		{
			rightChild = new BinaryTreeNode(height - 1, this, node_data + 1, upperRange);
		}
	}

	int getData()
	{
		return node_data;
	}

	static Vector<BinaryTreeNode> treeNodes = new Vector<BinaryTreeNode>();
	public int node_x, node_y;

	static BinaryTreeNode getNodeMouseClick( Point clickPoint )
	{
		Iterator<BinaryTreeNode> iter = treeNodes.iterator();
		while(iter.hasNext())
		{
			BinaryTreeNode node = iter.next(); 
			if( clickPoint.distance(node.node_x, node.node_y) < node_diameter / 2 )
				return node;
		}
		return null;
	}

	boolean checkNodeMouseClick(Point pt)
	{
		int diff = (int) (Math.pow( pt.x - node_x, 2 ) + Math.pow( pt.y - node_y, 2 ));  
		return ( Math.sqrt(diff) < node_diameter / 2 );
	}
}