/** AVLTree class **/
import java.util.*;
import java.applet.*;
import java.awt.*;
import java.lang.*;

import ciips.animation.*;
import ciips.animation.tree.*;

class AVLTree {
	private	AVLNode root, node;
	private int height;

	private DrawingPanel dpAfter;
	private TreeEdgeList tl;
	private Dimension edge_off = new Dimension( 7, 5 );
	private Graphics g;

	private boolean avlt_display = false;
	private static final ComBox no_fixup = new ComBox( 5, 20, "No fixup needed" );
	private static final ComBox fixup = new ComBox( 5, 20, "Re-balancing" );

	/*-*/ ShadowLabel bforeLabel = new ShadowLabel("Before Rotation");
	/*-*/ ShadowLabel rotLeftLab = new ShadowLabel("Rotate Left");
	/*-*/ ShadowLabel rotRightLab = new ShadowLabel("Rotate Right");

	private static final boolean DEBUG = true;
	
	private static final int LEFT_HEAVY = -1;
	private static final int RIGHT_HEAVY = 1;

	public AVLTree() {
		node = new AVLNode(0,0,0,null,0); 
		node.setWeight(-1);
		root = null;
		/*-*/ dpAfter = AlgAnimFrame.getPanel();
	}

	/** getAVLHeight() returns Height of Current AVL Tree
		**/
	public int getAVLHeight() {
		AVLNode xl, xr;
		int height = 1;
		xl = xr = root;
		while ((xl != null) && (xr != null)) {
			if(xl != null) xl = (AVLNode)xl.getLeft();
			if(xr != null) xr = (AVLNode)xr.getRight();
			height++;
		}
		return height; 	
	}

	/** represents weather x is balanced or not
	**/
	private boolean isXunbalanced(AVLNode x) {
		if(x == null) return false;

		if ((x.getBalance() <= -2) || (x.getBalance() >= 2)) {
			System.out.println("X is unbalanced");
			return true;
		}
		else {
			System.out.println("X is balanced");
			return false;
		}
	}

	/** Find Node containding data **/
	public AVLNode FindNode(int data) {
		AVLNode current = root;
		while(current != null) {
		if (data == current.getWeight())
				return (current);
			else {
				if(data < current.getWeight())
					current = (AVLNode)current.getLeft();
				else 	current = (AVLNode)current.getRight();
			}
		} 	
		return null;
	}

	// Standard labels to be added to drawing
	// Common positions
	static final int ENTRY_X = 20, ENTRY_Y = 20; // First position for a new node
	static final Point start = new Point( ENTRY_X, ENTRY_Y );
	static final Point find_off = new Point( 2, -2 ); // Offset as point tracks down tree

	/*-------------------------------------------------------------*/
	/** Rotate node x to left **/
	private void RotateLeft( AVLNode x, Graphics g ) {
		AVLNode current, parent;
		/*-*/ addLabelNear( rotLeftLab, x ); drawAVLTree(); AlgAnimFrame.pauseStep();

		AVLNode y = (AVLNode)x.getRight();
		/* establish x.right link */
		x.setRight(y.getLeft());
		if ((AVLNode)y.getLeft() != null) {
			((AVLNode)y.getLeft()).SetParent(x);
			/*-*/ tl.reLink( y, y.getLeft(), x, y.getLeft() );
		}

		/* update balance */
		if(isXunbalanced(x)) {
/*			if((x.getLeft() != null) )
			{
				x.SetBalance(x.getBalance()-3);
				current = x;
				parent = x.getParent();
				while (parent != null)
				{
					if(current == (AVLNode)parent.getLeft())
						parent.SetBalance(parent.getBalance() +1);
					else
						parent.SetBalance(parent.getBalance() -1);
					current = parent;
					parent = parent.getParent();
				}
				if((y != null) && (x.getLeft().getLeft() != null))
					y.SetBalance(y.getBalance()-1);
				else if (y != null)
					y.SetBalance(y.getBalance()-2);
			}
			else
			{
*/				x.SetBalance(x.getBalance()-2);
				current = x;
				parent = x.getParent();
				while (parent != null) {
					if(current == (AVLNode)parent.getLeft())
						parent.SetBalance(parent.getBalance() +1);
					else
						parent.SetBalance(parent.getBalance() -1);
					current = parent;
					parent = parent.getParent();
				}
				if(y != null)
					y.SetBalance(y.getBalance()-1);
//			}
		}
		else {
			x.SetBalance(x.getBalance()-1);
			if (y != null)
				y.SetBalance(y.getBalance()-1);
		}
		/*-----------------------------------------------------*/

		/* establish y.parent link */
		if (y != null) {
			y.SetParent(x.getParent());
			System.out.println("y.getBalance() = " + y.getBalance());
		}
		if (x.getParent() != null) {
			if (x == x.getParent().getLeft())
				x.getParent().setLeft(y);
			else 
				x.getParent().setRight(y);
		/*-*/ tl.reLink( x.getParent(), x, x.getParent(), y );
		}
		else root = y;

		/* link x and y */
		y.setLeft(x); 	/*-*/ tl.reLink( x, y, y, x );
		if (x != null)
			x.SetParent(y);

		/*-*/ drawAVLTree(); AlgAnimFrame.pauseStep(); removeLabel( rotLeftLab ); 
		}

	/** Rotate node x to right **/
	private void RotateRight(AVLNode x, Graphics g) {
		AVLNode current, parent;

		AlgAnimFrame.showText( 3, "Rotate Right about " + x.getWeight() );	
		/*-*/ addLabelNear( rotRightLab, x ); drawAVLTree(); AlgAnimFrame.pauseStep();

		AVLNode y = (AVLNode)x.getLeft(); 

		/* establish x.left link */
		x.setLeft((AVLNode)y.getRight());
		if (y.getRight() != null) {
			((AVLNode)y.getRight()).SetParent(x);
			/*-*/ tl.reLink( y, y.getRight(), x, y.getRight() );
		}

		/* establish y.parent link */
		if (y != null) {
			y.SetParent(x.getParent());
			System.out.println("y.getBalance() = " + y.getBalance());
			y.SetBalance(y.getBalance()+1);
			System.out.println("y.getBalance() = " + y.getBalance());
		}

		/* update balance */
		if(isXunbalanced(x)) {
			System.out.println("x : " + x.getWeight());
			x.SetBalance(x.getBalance()+2);
			current = x;
			parent = x.getParent();
			while (parent != null) {
				System.out.println("current = " + current.getWeight());
				if(current == (AVLNode)parent.getLeft())
					parent.SetBalance(parent.getBalance() +1);
				else
					parent.SetBalance(parent.getBalance() -1);
				current = parent;
				parent = parent.getParent();
			}
		}
		else
			x.SetBalance(x.getBalance()+1);
		/*-----------------------------------------------------*/

		if (x.getParent() != null) {
			if (x == ((AVLNode)x.getParent()).getRight())
				x.getParent().setRight(y);
			else
				x.getParent().setLeft(y);
			/*-*/ tl.reLink( x.getParent(), x, y.getParent(), y );
		}
		else root = y;

		/* link x and y */
		y.setRight(x);  /*-*/ tl.reLink( x, y, y, x );
		if (x != null)
			x.SetParent(y);

		/*-*/ drawAVLTree(); AlgAnimFrame.pauseStep(); removeLabel( rotRightLab );
	}

	/** allocate node for data and insert in tree **/
	public boolean InsertNode( int data ) {
		AVLNode parent;
		AVLNode current;	
		AVLNode x;
		/*-*/ System.out.println("AVLTree: InsertNode: value " + data );
		/*-*/ if( tl == null ) {
		/*-*/		System.out.println("AVLTree:InsertNode - create TEL");
		/*-*/		tl = new TreeEdgeList();
		/*-*/		System.out.println("AVLTree:InsertNode - created TEL");
		/*-*/		addObj( tl, 0, 0 );
		/*-*/		}

		/* find where node belongs */
		current = root;
		parent = null; /*-*/ Trajectory t = new Trajectory(); t.addPoint( start );
		while (current != null) {
			if (data == current.getWeight())
				return true; 
			parent = current; /*-*/ t.addPoint( current, find_off );
			
			if (data < current.getWeight())
				current = (AVLNode)current.getLeft();
			else
				current = (AVLNode)current.getRight();
		}

		/* setup new node */
		x = new AVLNode( 0, 0, 0, parent, 0 );
		x.setWeight( data ); /*-*/ addObj( x, 0, 0 ); 
		
		 System.out.println("data of x is "+data);
		if (x == null) {
			if( DEBUG) System.out.println("x is null");
			return false;
		}
		
		/* insert node in tree */
		if (parent != null) {
			if (data < parent.getWeight())
				parent.setLeft(x);
			else
				parent.setRight(x);
		}
		else {
			root = x;
		}

		/*-*/ dpAfter.clear();
		
		/*-*/ if( DEBUG ) System.out.println("AVLTree:Insert - Before DT");
		/*-*/ updateNodePositions(); t.addPoint( x, find_off ); animate( x, t );
		/*-*/ if( parent != null ) { System.out.println("TL add " + parent.getWeight() + "-" + x.getWeight() ); tl.addElement( new TreeEdge( parent, x, edge_off ) ); }
		/*-*/ drawAVLTree(); AlgAnimFrame.pauseStep(); 

		/* Update balance */
		current = x;
		parent = current.getParent();
		while ((current != null) && (parent != null)) {
			if((parent.getParent() != null)) {
				if(current == (AVLNode)parent.getLeft())
					parent.SetBalance(parent.getBalance() + LEFT_HEAVY);
				else if(current == (AVLNode)parent.getRight())
					parent.SetBalance(parent.getBalance() + RIGHT_HEAVY);
				System.out.println(" ");
				System.out.println("The balance of " + current.getWeight() + " = " + current.getBalance());
				System.out.println(" ");
			}
			else if(parent != null) {
				if(current == (AVLNode)parent.getLeft())
					parent.SetBalance(parent.getBalance() + LEFT_HEAVY);
				else if (current == (AVLNode)parent.getRight())
					parent.SetBalance(parent.getBalance() + RIGHT_HEAVY);
				System.out.println("The balance of " + current.getWeight() + " = " + current.getBalance());
				System.out.println(" ");
				System.out.println("The balance of " + parent.getWeight() + " = " + parent.getBalance());
				System.out.println(" ");
			}
			if(parent.getBalance() == 0)
				break;

			current = parent;
			parent = parent.getParent();
		}
		current = x;
		parent = current.getParent();

		InsertFixup( x );
		return true;
	}	

	/** delete node z from tree **/
	public void DeleteNode( AVLNode z, AlgAnimFrame frame ) {
		AVLNode x, y;
		AVLNode currentparent, parent;

		if ( z == null )
			return;
		if ( (z.getLeft() == null) || (z.getRight() == null) ) {
			/* y has a null node as a child */
			y = z;
		}
		else {
			y = (AVLNode)z.getRight();
			while ( y.getLeft() != null)
				y = (AVLNode)y.getLeft();
		}
	
		/* x is y's only child */
		if (y.getRight() != null) {
			x = (AVLNode)y.getRight();
			x.SetParent(y.getParent());
		}
		else
			x = null;

		/* remove y from the parent chain */
		currentparent = y.getParent();
		parent = y.getParent();

		if (y.getParent() != null) {
			if (x != null)
				y.getParent().setRight(x);
		}
		else
			root = x;

		addComNear( y, "Remove this leaf" );
		if (y != z)
			z.setWeight(y.getWeight());

		/*-*/ frame.showText( 2, "Node removed" ); setEdges( tl );
		/*-*/ drawAVLTree(); AlgAnimFrame.pauseStep(); dpAfter.removeAllCom();
		/*-*/ dpAfter.removeObj( y ); drawAVLTree();

		/* Update balance */
		while (parent != z) {
			parent.SetBalance(parent.getBalance() + 1);
			parent = parent.getParent();
		}
/*		while(parent != null) {
			parent.SetBalance(parent.getBalance() );////////////
		}
*/
		DeleteFixup( currentparent );
	}

	/**maintain AVL tree balance after inserting node x **/
	private void InsertFixup( AVLNode x ) {
		AVLNode current;
		AVLNode parent;

		current = x;
		parent = current.getParent();

		while((current != root) && (parent != null) && (parent.getParent() != null)) {
			if(parent.getParent().getBalance() <= -2 ) {
				/* RR rotation */
				if(current == (AVLNode)parent.getLeft())
					RotateRight(parent.getParent(), g);
				/* LR rotation */
				else {
					RotateLeft(parent, g);
					RotateRight(current.getParent(), g);
				}
			}
			else if(parent.getParent().getBalance() >= 2 ) {
				/* LL rotation */
				if(current == (AVLNode)parent.getRight()) {
					RotateLeft(parent.getParent(), g);
				}
				/* RL rotation */
				else {
					RotateRight(parent, g);
					RotateLeft(current.getParent(), g);
				}
			}
			current = current.getParent();
			parent = parent.getParent();
		}
		/*-*/ drawAVLTree(); AlgAnimFrame.pauseStep(); 
	}

	/** maintain AVL tree balance after deleting node x **/
	private void DeleteFixup( AVLNode x ) {
		AVLNode current, parent, temp;

		current = x;
		parent = current.getParent();

		while(current != null) {
			if(current.getBalance() <= -2 )
			{
				/* RR rotation */
				if((AVLNode)current.getLeft() == ((AVLNode)current.getLeft().getLeft()).getParent())
				{
					RotateRight(current, g);
				}
				/* LR rotation */
				else
				{
					RotateLeft((AVLNode)current.getLeft(), g);
					RotateRight(current, g);
				}
			}
			else if(current.getBalance() >= 2 )
			{
				/* LL rotation */
				if((AVLNode)current.getRight() == ((AVLNode)current.getRight().getRight()).getParent())
				{
					RotateLeft(current, g);
				}
				/* RL rotation */
				else
				{
					RotateRight((AVLNode)current.getRight(), g);
					RotateLeft(current, g);
				}
			}
			current = x.getParent();
			parent = current.getParent();
		}
		/*-*/ drawAVLTree();
		AlgAnimFrame.pauseStep();
	}

	public void setPanel( DrawingPanel dp ) {
		this.dpAfter = dp;
		g = dp.getGraphics();
		}
	/** update node position **/
	private void updateNodePositions() {
		Dimension d = dpAfter.getSize();
		int height2=0;
		if( DEBUG ) System.out.println("AVLTree:updateNodePositions");
		if( (d.width < 1) || (d.height < 1) ){
			System.out.println("d.height: "+d.height+ ", d.width: " +d.width);
			return;
			}
		// Allow space for the nodes to be drawn
		int d_width = d.width - AVLNode.getWidth();
		int dx = d_width / 2;
		int d_height = d.height ;
		int height = 0;
		int cur_height = getAVLHeight()+1;
		int dy = d_height / cur_height;	
		// Set position of root and all sub-trees
		root.setPosition( dx, dy/2, dx, dy );
	}

	/** Redraw the tree **/
	public void drawAVLTree() {
		if( DEBUG ) {
			System.out.println("AVLTree:drawAVLTree - edge list " + tl );
			}
		/* Move the images down one frame */
		dpAfter.shuffleDown();
		/* Clear the current frame */
		dpAfter.clear();
		/* Update the positions of nodes */
		updateNodePositions();
		/* Redraw */
		dpAfter.redraw();
		}

	/**  **/
	public void setAVLTDisplay( boolean avlt_display ) {
		if( DEBUG ) System.out.println("AVLTree:setAVLTDisplay " + avlt_display );
		this.avlt_display = avlt_display;
		}
	/**  **/
	private void addEdges( AVLNode root, TreeEdgeList tel )
	{
		AVLNode child = (AVLNode)root.getLeft();
		if ( child != null )
		{
			// tel.add( new TreeEdge( root, child ) );
			tel.addElement( new TreeEdge( root, child ) );
			addEdges( child, tel );
		}
		child = (AVLNode)root.getRight();
		if ( child != null )
		{
			// tel.add( new TreeEdge( root, child ) );
			tel.addElement( new TreeEdge( root, child ) );
			addEdges( child, tel );
		}
	}
	/** set edges for link **/
	public void setEdges( TreeEdgeList tel )
	{
		tel.clear();
		if ( root != null )
		{
			addEdges( root, tel );
		}
	}
	/** add object **/
	private void addObj( DrawingObj a, int x, int y ) {
		a.move( x, y );
		DrawingPanel dp = AlgAnimFrame.getPanel();
		dp.addDrawingObj( a );
		}
	/** add label **/
	public void addLabel( ShadowLabel label ) {
		int x = 10; int y = 10;
		label.move( x, y );
		DrawingPanel dp = AlgAnimFrame.getPanel();
		dp.addDrawingObj( label );
		}
	/** show text near the node **/
	public void addComNear( DrawingObj z, String s ) {
		int x = z.getX() + 15;
		ComBox c = new ComBox( x, z.getY(), s );
		DrawingPanel dp = AlgAnimFrame.getPanel();
		dp.addCom( c );
		}
	/** add label near node **/
	public void addLabelNear( ShadowLabel label, DrawingObj z ) {
		int x = z.getX() + 30; 
		label.move( x, z.getY() );
		DrawingPanel dp = AlgAnimFrame.getPanel();
		dp.addDrawingObj( label );
		dp.repaint();
		}
	/** remove object **/
	public void removeLabel( ShadowLabel label ) {
		DrawingPanel dp = AlgAnimFrame.getPanel();
		dp.removeObj( label );
		dp.repaint();
		}
	/** when inserting node to the tree animating **/
	private void animate( AVLNode x, Trajectory t ) {
		DrawingPanel dp = AlgAnimFrame.getPanel();
		x.noBalanceView(true);
		dp.setAnimStep(7);
		dp.setDelay(100);
		dp.animate( x, t );
		x.noBalanceView(false);
		}

	}