/** BinTree class
	Animation: John Morris
 **/
import java.util.*;
import java.applet.*;
import java.awt.*;
import java.lang.*;

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

class BinTree {
	private	TreeNode root;

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

	private static final boolean DEBUG = true;
	
	public BinTree() {
		root = null;	/*-*/ dpAfter = AlgAnimFrame.getPanel();
		}

	/* Find Node containding data */
	public TreeNode FindNode( int data ) {
		if( DEBUG ) System.out.println("BinTree:FindNode " + data );
		TreeNode current = root;
		while( current != null ) {
		if ( data == current.getWeight() )
				return current;
			else {
				if(data < current.getWeight())
					current = current.getLeft();
				else current = current.getRight();
				}
			} 	
		return null;
		}

	// 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( 5, 5 ); // Offset as point tracks down tree
	static final String exists = "Already exists!";
	/*-------------------------------------------------------------*/
	/* allocate node for data and insert in tree */
	public boolean InsertNode( int data ) {
		TreeNode parent;
		TreeNode current;	
		TreeNode x;		/*-*/ AlgAnimFrame.showText(1,"Inserting " + data ); String direction;
		/*-*/ System.out.println("BinTree:InsertNode: value " + data );
		/*-*/ if( tl == null ) { tl = new TreeEdgeList();
		/*-*/			System.out.println("BinTree:InsertNode - created TEL");
		/*-*/			addObj( tl, 0, 0 ); } ComBox c = new ComBox( ENTRY_X, ENTRY_Y, "New item" );
		/*-*/ updateNodePositions(); // Make sure the tree has some sensible node locations

		/* setup new node */
		x = new TreeNode( data ); /*-*/ x.setGrey( true ); addObj( x, 0, 0 ); int x_off;
		/*-*/ if( DEBUG ) System.out.println("BinTree:InsertNode - new node is " + data );
		if (x == null) { if( DEBUG) System.out.println("x is null"); return false; }
		/* find where node belongs */
		current = root; /*-*/ AlgAnimFrame.showText(2,"Locate insertion point");
		parent = null; /*-*/ Trajectory t = new Trajectory(); t.addPoint( start );
		while ( current != null ) { /*-*/ t.addPoint( current, find_off ); animate( x, t );
			if (data == current.getWeight()) { /*-*/ AlgAnimFrame.showText(3, exists );
				/*-*/ dpAfter.addCom( new ComBox( current, exists ) ); dpAfter.removeObj( x ); drawPanel();
				return true; 
				}
			parent = current; 
			if (data < current.getWeight()) {
				current = current.getLeft(); /*-*/ direction = "<, go left"; 
				}
			else {
				current = current.getRight(); /*-*/ direction = ">, go right";
				}
			/*-*/ ComBox left_right = new ComBox( parent, direction ); AlgAnimFrame.showText(3,direction);
			/*-*/ dpAfter.addCom( left_right ); t = new Trajectory( t );
			}

		/* insert node in tree */
		if (parent != null) {
			if (data < parent.getWeight()) { parent.setLeft(x); /*-*/ x_off = -TreeNode.last_dx;
				}
			else { parent.setRight(x); /*-*/ x_off = TreeNode.last_dx; }
			/*-*/ direction = "New node is a leaf"; x.setPosition( parent.getX()+x_off/2, parent.getY()+TreeNode.last_dy,0,0 );
			}
		else {
			root = x; /*-*/ direction = "First node - make it the root"; 	updateNodePositions();
			}
		/*-*/ if( DEBUG ) System.out.println("BinTree:Insert - Before DT"); AlgAnimFrame.showText(3,direction);
		/*-*/ t.addPoint( x, find_off ); animate( x, t ); x.setGrey( false );
		/*-*/ ComBox final_com = new ComBox( x, direction ); dpAfter.addCom( final_com );
		/*-*/ if( parent != null ) { System.out.println("TL add " + parent.getWeight() + "-" + x.getWeight() ); tl.add( new TreeEdge( parent, x, edge_off ) ); }
		/*-*/ drawPanel(); AlgAnimFrame.showText(4, "New node added"); AlgAnimFrame.pauseStep();
		if( DEBUG ) System.out.println("BinTree:InsertNode - complete");
		return true;
		}	

	private TreeNode parent;

	public TreeNode findParent( TreeNode z ) {
		if( DEBUG ) System.out.println("BinTree:findNode " + z );
		TreeNode current = root;
		int data = z.getWeight();
		parent = null;
		while( current != null ) {
			if ( z == current )
				return parent;
			else {
				parent = current;
				current = (data < current.getWeight())? current.getLeft():
																		current.getRight();
				}
			} 	
		return null;
		}

	/* delete node z from tree */
	public void DeleteNode( TreeNode z, AlgAnimFrame frame ) {
		TreeNode x, y; /*-*/ Point offset = new Point( -10, +10 ); ComBox p_box;
		if ( z == null ) return;
		TreeNode z_left = z.getLeft(), z_right = z.getRight();
		/*-*/ ComBox z_lab = new ComBox( z, "z" ); dpAfter.addCom( z_lab );
		TreeNode parent = findParent( z );
		if( DEBUG ) System.out.println("BinTree:DeleteNode z " + ((z==null)?"null":z.toString()) );
		if( DEBUG ) System.out.println("BinTree:DeleteNode parent " + ((parent==null)?"null":parent.toString()) );
		y = z;
		if ( (z_left != null) && (z_right != null) ) {
			/* find tree successor */
			parent = z; y = z_right;
			while( y.getLeft() != null ) { parent = y; y = y.getLeft(); }				
			}

		if ( parent != null ) {
			p_box = new ComBox( parent, offset, "p", Color.white, Color.green );
			dpAfter.addCom( p_box );
			}
		/*-*/ ComBox y_lab = new ComBox( y, offset, "y", Color.white, Color.green ); dpAfter.addCom( y_lab ); drawPanel(); AlgAnimFrame.pauseStep();
		ComBox exp = makeBottomBox(  "z: node to be deleted; y: leaf to be excised", dpAfter );
		/*-*/ frame.showText( 2, "z is the node being deleted" );
		/*-*/ frame.showText( 3, "y is the node actually being removed from the tree");
		/*-*/ frame.showText( 4, "if z and y are different, y's value is moved to z" );
		/* Make x refer to y's only child */
		x = ( y.getLeft() != null )? y.getLeft() : y.getRight();
		/*-*/ if( x != null ) { ComBox x_lab = new ComBox( x, offset, "x", Color.white, Color.green ); dpAfter.addCom( x_lab ); }
		/*-*/ drawPanel(); AlgAnimFrame.pauseStep();

		/* remove y from the parent chain */
		if ( parent != null ){
			if (y == parent.getLeft()) parent.setLeft(x);
			else parent.setRight(x);
			/*-*/ if( x != null ) { TreeEdge new_link = new TreeEdge( parent, x, edge_off );
			/*-*/												new_link.setColour( Color.red ); tl.add( new_link );
			/*-*/												exp.setText("Link y's parent to y's child"); }
			}
		else {
			root = x;	/*-*/	exp.setText("Reset root");
			}
		/*-*/	if( (x != null)||(root==x) ) { drawPanel(); AlgAnimFrame.pauseStep(); }

		/*-*/ y.setGrey( true );
		if (y != z) { z.setWeight(y.getWeight()); /*-*/ exp.setText("Copy y's value to original z"); drawPanel(); }
		
		/*-*/ frame.showText( 2, "Node removed" ); setEdges( tl );
		/*-*/ exp.setText("Remove y"); /* dpAfter.addCom( exp ); */ 
		/*-*/ drawPanel(); /* Remove link to y also */ dpAfter.removeObj( y ); dpAfter.removeAllCom();
		}

	public void setPanel( DrawingPanel dp ) {
		this.dpAfter = dp;
		g = dp.getGraphics();
		}

	private int getMaxHeight() {
		int h;
		if ( root == null ) h = 0;
		else {
			h = root.getHeight();
			}
		return h;
		}

	public void updateNodePositions() {
		Dimension d = dpAfter.size();
		if( DEBUG ) System.out.println("BinTree: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 = 0;
		if ( root != null ) {
			d_width = d.width - root.getNodeSize().width;
			int dx = d_width / 2;
			int dy = d.height / (getMaxHeight() + 2);	
			// Set position of root and all sub-trees
			root.setPosition( dx, dy/2, dx, dy );
			}
		}

	/** drawPanel is called when the panel is complete: updates the panel, moves it down one
		and clears the current panel
	**/
	public void drawPanel() {
		if( DEBUG ) {
			System.out.println("BinTree:drawBinTree - edge list " + tl );
			}
		dpAfter.redraw();
		dpAfter.shuffleDown();
		if( DEBUG ) System.out.println("BinTree:drawBinTree - after shuffle");
		dpAfter.clear();
		if( DEBUG ) System.out.println("BinTree:drawBinTree - after clear");
		}

	public void draw() {
		dpAfter.redraw();
		}

	public void PrintNode( TreeNode x ) {
		System.out.print("Node has data: "); 
		System.out.println( x.getWeight() );
 
		System.out.print("Left child:	");
		if (x.getLeft() == null) System.out.println(" is null.");
		else System.out.println(x.getLeft().getWeight());

		System.out.print("Right child:	");
		if (x.getRight() == null) System.out.println(" is null.");
		else System.out.println(x.getRight().getWeight());
		}

	// public void PrintCoverage() { }

	private void addEdges( TreeNode root, TreeEdgeList tel ) {
		TreeNode child = root.getLeft();
		if ( child != null ) {
			tel.add( new TreeEdge( root, child, edge_off ) );
			addEdges( child, tel );
			}
		child = root.getRight();
		if ( child != null ) {
			tel.add( new TreeEdge( root, child, edge_off ) );
			addEdges( child, tel );
			}
		}

	public void setEdges( TreeEdgeList tel ) {
		tel.clear();
		if ( root != null ) {
			addEdges( root, tel );
			}
		}

	private void addObj( DrawingObj a, int x, int y ) {
		a.move( x, y );
		DrawingPanel dp = AlgAnimFrame.getPanel();
		dp.addDrawingObj( a );
		}

	private ComBox makeBottomBox( String s, DrawingPanel dp ) {
		Dimension d = dp.size();
		ComBox exp = new ComBox( 2, d.height - 30, s );
		dp.addCom( exp );
		return exp;
		}

	private void animate( DrawingObj x, Trajectory t ) {
		DrawingPanel dp = AlgAnimFrame.getPanel();
		dp.animate( x, t );
		}

	}