/** RBTree class
	Original: Linda Luo
	Original Animation:		Mervyn Ng
	Update Animation: John Morris
 **/
import java.util.*;
import java.applet.*;
import java.awt.*;
import java.lang.*;

import ciips.animation.*;
import ciips.animation.tree.*;
// import ciips.animation.graph.*;

class RBTree {
	private	RBNode root;
	public final RBNode sentinel;

	// Counters for coverage checking
	private static int case1ct, case2ct, case3ct, case4ct, case5ct,
												case6ct, case7ct, case8ct;

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

	private boolean rbt_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" );
	private static final boolean DEBUG = true;
	
	public RBTree() {
		sentinel = new RBNode(0,0,0,null,null); 
		sentinel.setWeight(-1);
		sentinel.SetColorBlack();
		root = sentinel;
		case1ct = case2ct = case3ct = case4ct = 
		case5ct = case6ct = case7ct = case8ct = 0;
		/*-*/ dpAfter = AlgAnimFrame.getPanel();
		}

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

	// Standard labels to be added to drawing
	static ShadowLabel rot_left = new ShadowLabel("Rotate Left");
	static ShadowLabel rot_right = new ShadowLabel("Rotate Right");
	static ShadowLabel colour_root_black = new ShadowLabel( "Colour root black" );
	static ShadowLabel left_uncle = new ShadowLabel( "Left uncle" );
	static ShadowLabel right_uncle = new ShadowLabel( "Right uncle" );
	// 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
	/*-------------------------------------------------------------*/
	/* Rotate node x to left */
	private void RotateLeft( RBNode x, Graphics g ) {
		/*-*/ Color origColour = x.getColour(); x.Highlight(g, Color.yellow);		
		/*-*/ AlgAnimFrame.showText( 3, "Rotate Left about " + x.getWeight() );	
		/*-*/ addLabelNear( rot_left, x ); drawRBTree(); AlgAnimFrame.pauseStep();

		RBNode y = (RBNode)x.getRight();
		/* establish x.right link */
		x.setRight(y.getLeft());
		if ((RBNode)y.getLeft() != sentinel)
			((RBNode)y.getLeft()).SetParent(x); /*-*/ tl.reLink( y, y.getLeft(), x, y.getLeft() );
		/* establish y.parent link */
		if (y != sentinel) y.SetParent(x.getParent());
		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); /*-*/ System.out.println("RL x<->y"); tl.reLink( x, y, y, x );
		if (x != sentinel) x.SetParent(y); /*-*/ x.Unhighlight_Node(g, origColour);
		/*-*/ drawRBTree(); AlgAnimFrame.pauseStep(); removeLabel( rot_left ); 
		}

	/* Rotate node x to right */
	private void RotateRight(RBNode x, Graphics g){
		/*-*/ Color origColour = x.getColour(); x.Highlight(g, Color.yellow);		
		AlgAnimFrame.showText( 3, "Rotate Right about " + x.getWeight() );	
		/*-*/ addLabelNear( rot_right, x ); drawRBTree(); AlgAnimFrame.pauseStep();

		RBNode y = (RBNode)x.getLeft(); 
		/* establish x.left link */
		x.SetLeft((RBNode)y.getRight());
		if (y.getRight() != sentinel) {
			((RBNode)y.getRight()).SetParent(x); /*-*/ tl.reLink( y, y.getRight(), x, y.getRight() );
			}

		/* establish y.parent link */
		if (y != sentinel) y.SetParent(x.getParent());
		if (x.getParent() != null) {
			if (x == ((RBNode)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 != sentinel) x.SetParent(y);
		/*-*/ x.Unhighlight_Node(g, origColour);
		/*-*/ drawRBTree(); AlgAnimFrame.pauseStep(); removeLabel( rot_right );
		}

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

		/* find where node belongs */
		current = root; /*-*/ AlgAnimFrame.showText(2,"Locate insertion point");
		parent = null; /*-*/ Trajectory t = new Trajectory(); t.addPoint( start );
		while (current != sentinel) {
			//System.out.println("root is "+root.Get_ID());
			if (data == current.getWeight()) { /*-*/ AlgAnimFrame.showText(3,"This node already exists!");
				return true; 
				}
			parent = current; /*-*/ t.addPoint( current, find_off );
			if (data < current.getWeight()) {
				current = (RBNode)current.getLeft(); /*-*/ AlgAnimFrame.showText(3,"Less, go left");
				}
			else {
				current = (RBNode)current.getRight(); /*-*/ AlgAnimFrame.showText(3,"Greater, go right");
				}
			System.out.println("value of data is "+data+", current = "+current.getWeight());	
			}

		/* setup new node */
		x = new RBNode( 0, 0, 0, parent, sentinel );
		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; /*-*/ AlgAnimFrame.showText(3,"First node, make it the root");
			}
		/*-*/ if( DEBUG ) System.out.println("RBTree: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 */ ) ); }
		/*-*/ drawRBTree(); AlgAnimFrame.showText(4, "New node added - now rebalance (if necessary)"); AlgAnimFrame.pauseStep(); 
		InsertFixup( x );
		return true;
		}	

	/* delete node z from tree */
	public void DeleteNode( RBNode z, AlgAnimFrame frame ){
		RBNode x, y;
		if ( z == sentinel ) return;
		if ( (z.getLeft() == sentinel) || (z.getRight() == sentinel) ){
			/* y has a sentinel node as a child */
			y = z;
			}
		else{
			/* find tree successor with a sentinel node as a child */
			y = (RBNode)z.getRight();
			while ( y.getLeft() != sentinel) y = (RBNode)y.getLeft();
			}
	
		/* x is y's only child */
		if (y.getLeft() != sentinel) x = (RBNode)y.getLeft();
		else x = (RBNode)y.getRight();
	
		/* remove y from the parent chain */
		x.SetParent(y.getParent());
		if (y.getParent() != null){
			if (y == ((RBNode)y.getParent()).getLeft())
				y.getParent().SetLeft(x);
			else 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 );
		/*-*/ drawRBTree(); AlgAnimFrame.pauseStep(); dpAfter.removeAllCom();
		/*-*/ dpAfter.removeObj( y ); drawRBTree();
		if (y.IsBlack()) { /*-*/ frame.showText( 3, "Fixing" ); dpAfter.addCom( fixup );
			DeleteFixup( x );
			} /*-*/ else { frame.showText( 3, "No fixup needed" ); dpAfter.addCom( no_fixup ); }
		}

	/* maintain red-black tree balance after inserting node x */
	private void InsertFixup( RBNode x ) {
		// ShadowLabel colorLabel = new ShadowLabel("Restoring Red-Black Property...");
		// ShadowLabel bforeLabel = new ShadowLabel("Before Rotation");
		ShadowLabel rotLeftLab = new ShadowLabel("Rotating Left...");
		ShadowLabel rotRightLab = new ShadowLabel("Rotating Right...");
		if( DEBUG ) System.out.println("RBTree:InsertFixup " + x );

		if( (x == root) || x.getParent().IsBlack() ) { AlgAnimFrame.showText(4,"No fixup needed"); AlgAnimFrame.pauseStep(); }
		else {

		/* check red-black properties */
		while (x != root && x.getParent().IsRed()) { /*-*/ AlgAnimFrame.showText(3,"Parent is red - rebalance required");
			if( DEBUG ) System.out.println("InsertFixup: while loop");
			/* we have a violation */
			if (x.getParent() == (RBNode)(x.getParent().getParent().getLeft())) {
				RBNode y = (RBNode)x.getParent().getParent().getRight(); /*-*/ AlgAnimFrame.showText(4,"Case 1 - parent to left of grandparent");
				case1ct++;	
				if( DEBUG ) {	System.out.print("case 1 - x is " + x.getWeight() );
					System.out.println(" y is "+y.getWeight());
					}
				if ( y.IsRed() ) { /* uncle is red */ /*-*/ AlgAnimFrame.showText(4,"Case 2 - Red uncle");
					x.getParent().SetColorBlack();
					y.SetColorBlack();
					x.getParent().getParent().SetColorRed();
					x = x.getParent().getParent(); /*-*/ AlgAnimFrame.pauseStep();			
	
					case2ct++;
					if( DEBUG ) {
						System.out.print("Case 2 ");
						System.out.print("x is "+x.getWeight());
						System.out.println(" y is "+y.getWeight());
						}
					}
				else { /* uncle is black *//*-*/ AlgAnimFrame.showText(4, "Case 3 - Black uncle");
					case3ct++;	
					if( DEBUG ) {
						System.out.print("Case 3 ");
						System.out.print("x is "+x.getWeight());
						System.out.println(" y is "+y.getWeight());
						}
					if ( x == x.getParent().getRight() ) { /*-*/AlgAnimFrame.showText(4, "Case 4 - to right of parent");
						/* make x a left child */
						x = x.getParent();
						RotateLeft(x, g);
						case4ct++;
						if( DEBUG ) {
							System.out.print("Case 4 ");
							System.out.print("x is "+x.getWeight());
							System.out.println(" y is "+y.getWeight());
							}
						}
				
					/* recolor and rotate */
					if( DEBUG ) {
						System.out.print("Recolour and rotate ");
						System.out.print("x is "+x.getWeight());
						System.out.println(" y is "+y.getWeight());
						}
					x.getParent().SetColorBlack();
					x.getParent().getParent().SetColorRed();
					/*-*/ drawRBTree(); AlgAnimFrame.pauseStep();
					RotateRight(x.getParent().getParent(), g); 
					}
				}
			else{ /*-*/ AlgAnimFrame.showText(4,"Case 5 - parent to right of grandparent");	
				/* mirror image of above code */
				RBNode y = (RBNode)x.getParent().getParent().getLeft();
				case5ct++;
				// System.out.println("Case 5 - x is " + x.Get_ID() + " y is "+y.Get_ID());
				if ( y.IsRed() ){
					/* uncle is red */
					x.getParent().SetColorBlack();
					y.SetColorBlack();
					x.getParent().getParent().SetColorRed();
					x = x.getParent().getParent(); /*-*/ drawRBTree(); AlgAnimFrame.pauseStep();
					case6ct++;
					//System.out.println("In case 6");
					//System.out.println("Node x data is "+x.Get_ID());
					//System.out.println("Node y data is "+y.Get_ID());
					}
 				else {
					case7ct++;
					//System.out.println("In case 7");
					//System.out.println("Node x data is "+x.Get_ID());
					//System.out.println("Node y data is "+y.Get_ID());
					/* uncle is black */
					if (x == (RBNode)x.getParent().getLeft()){
						x = x.getParent();
						RotateRight(x, g); 
						case8ct++; 
						//System.out.println("In case 8");
						//System.out.println("Node x data is "+x.Get_ID());
						//System.out.println("Node y data is "+y.Get_ID());
						}
					x.getParent().SetColorBlack();
					x.getParent().getParent().SetColorRed(); 
					RotateLeft(x.getParent().getParent(), g); 
					}
				}
			}
		}
	/*-*/ boolean red_root = root.IsRed();
	root.SetColorBlack();	
	/*-*/ if ( red_root ) { 
	/*-*/						addLabelNear( colour_root_black, root );
	/*-*/						AlgAnimFrame.showText(4,"Colour root black"); AlgAnimFrame.pauseStep(); }
	/*-*/ if( DEBUG ) System.out.println("InsertFixup return");
	}

	/* maintain red-black tree balance after deleting node x */
	private void DeleteFixup( RBNode x ){
		while ( (x != root) && x.isBlack() ){
			if (x == (RBNode)x.getParent().getLeft()) {
				RBNode w = (RBNode)x.getParent().getRight(); /*-*/ addLabelNear( left_uncle, w );

				if ( w.IsRed() ) {
					w.SetColorBlack();
					x.getParent().SetColorRed();
					RotateLeft(x.getParent(), g);
					w = (RBNode)x.getParent().getRight();
					}
				if (((RBNode)w.getLeft()).IsBlack() && ((RBNode)w.getRight()).IsBlack()){
					w.SetColorRed();
					x = x.getParent();
					}
				else{
					if (((RBNode)w.getRight()).IsBlack()){
						((RBNode)w.getLeft()).SetColorBlack();
						w.SetColorRed();
						RotateRight(w, g);
						w = (RBNode)x.getParent().getRight();
						}
											
				if (x.getParent().IsBlack()) 
					w.SetColorBlack();
				else w.SetColorRed();
				x.getParent().SetColorBlack();
		
				((RBNode)w.getRight()).SetColorBlack();
				RotateLeft(x.getParent(), g);
				x = root;
							}
							}
						else{
						RBNode w = (RBNode)x.getParent().getLeft();

									if (w.IsRed()){
										w.SetColorBlack();
										x.getParent().SetColorRed();
											RotateRight(x.getParent(), g);
											w = (RBNode)x.getParent().getLeft();
											}
									if (((RBNode)w.getRight()).IsBlack() && ((RBNode)w.getLeft()).IsBlack()){
										w.SetColorRed();				
											x = x.getParent(); 
											}			
									else{	
																				
										if (((RBNode)w.getLeft()).IsBlack()){
												((RBNode)w.getRight()).SetColorBlack();
													w.SetColorRed();
													RotateLeft(w, g);
											w = (RBNode)x.getParent().getLeft();
													}
															
											if (x.getParent().IsBlack()) 
												w.SetColorBlack();
											else w.SetColorRed();
											x.getParent().SetColorBlack();
											((RBNode)w.getLeft()).SetColorBlack();
										RotateRight(x.getParent(), g);
											x = root;
											}
 
						}
					}
				x.SetColorBlack();

	}

	/* obtain the blackheight of the tree */
	public int BlackHeight(){
		RBNode x;
		RBNode xl, xr;
		int height = 0;
		x = root;
		while (x != sentinel){
 			x = (RBNode)x.getRight();
			if (x.IsBlack()) {
				height++;
				}
			}
		return height; 	
		}

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

	private void drawST( Graphics g, RBNode parent, RBNode child ) {
		if( DEBUG ) System.out.println("drawST: p " + parent.getWeight() + " " + (child==sentinel) );
		if ( (child != sentinel ) && (child != null) ) {
			parent.drawEdge( g, child );
			drawRBSubTree( child, g );
			}
		}

	private void drawRBSubTree( RBNode x, Graphics g ) {
		RBNode child;
		if( DEBUG ) System.out.println("drawRBSubTree: x " + x.getWeight() + " " + (x==sentinel) );
		if ( x != sentinel ) {
			x.draw( g, sentinel );
			drawST( g, x, (RBNode)x.getLeft() );
			drawST( g, x, (RBNode)x.getRight() );
			}
		}

	private void set234( RBNode c, int x, int y, int dx, int dy ) {
		RBNode child;
		int dx2 = dx/2; 
		// c.setX( x ); c.setY( y );
		c.move( x, y );
		child = (RBNode)c.getLeft();
		if ( child != sentinel ) {
			if( child.IsRed() ) {
				set234( child, x-dx2, y, dx2, dy );	
				}
			else  { set234( child, x-dx2, y+dy, dx2, dy ); }
			}
		child = (RBNode)c.getRight();
		if ( child != sentinel ) {
			if( child.IsRed() ) {
				set234( child, x+dx2, y, dx2, dy );	
				}
			else { set234( child, x-dx2, y+dy, dx2, dy ); }
			}
		}
	
	private void updateNodePositions() {
		Dimension d = dpAfter.getSize();
		if( DEBUG ) System.out.println("RBTree: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 - RBNode.getWidth();
		int dx = d_width / 2;
		int dy = d.height / (BlackHeight()*2 + 1);	
		// Set position of root and all sub-trees
		if ( rbt_display ) root.setPosition( dx, dy/2, dx, dy );
		else { // 234 tree display
			set234( root, dx, dy/2, dx, dy );
			}
		}

	public void drawRBTree() {
		if( DEBUG ) {
			System.out.println("RBTree:drawRBTree - edge list " + tl );
			}
		dpAfter.shuffleDown();
		dpAfter.clear();
		updateNodePositions();
		dpAfter.redraw();
		}

	public int RedCount(){
		RBNode x;
		int redct = 0;
		x = root;
		while (x != sentinel){
			x = (RBNode)x.getRight();
			if (x.IsRed()) redct++;
			}
		return redct;
		}

	public void PrintNode(RBNode x){
		if (x == sentinel) System.out.println("x is a sentinel node.");
		else{
			System.out.print("Node has data: "); 
			System.out.println(x.getWeight());
			System.out.print("Color: ");
			if(x.IsBlack()) System.out.println("Black");
			else System.out.println("Red");
 
			System.out.print("Left child:	");
			if (x.getLeft() == sentinel) System.out.println(" is a sentinel node.");
			else System.out.println(x.getLeft().getWeight());
			System.out.print("Color: ");
			if(((RBNode)x.getLeft()).IsBlack()) System.out.println("Black");
			else System.out.println("Red");		

			System.out.print("Right child:	");
			if ((RBNode)x.getRight() == sentinel) System.out.println(" is a sentinel node.");
			else System.out.println(x.getRight().getWeight());
			System.out.print("Color: ");						
			if(((RBNode)x.getRight()).IsBlack()) System.out.println("Black");
			else System.out.println("Red");

			System.out.print("Parent:	");
			if(x.getParent() != null){
		
				if (x.getParent() == sentinel) System.out.println(" is a sentinel node.");
				else System.out.println(x.getParent().getWeight());
				System.out.print("Color: ");						
				if(x.getParent().isBlack()) System.out.println("Black");
				else System.out.println("Red");
				}	
			else System.out.println("Null parent ie. root reached!");
			}
		}

	public void PrintCoverage(){
		System.out.println("case1 count: "+case1ct);
		System.out.println("case2 count: "+case2ct);
		System.out.println("case3 count: "+case3ct);
		System.out.println("case4 count: "+case4ct);
		System.out.println("case5 count: "+case5ct);
		System.out.println("case6 count: "+case6ct);
		System.out.println("case7 count: "+case7ct);
		System.out.println("case8 count: "+case8ct);
		}

	public void setRBTDisplay( boolean rbt_display ) {
		if( DEBUG ) System.out.println("RBTree:setRBTDisplay " + rbt_display );
		this.rbt_display = rbt_display;
		}

	private void addEdges( RBNode root, TreeEdgeList tel ) {
		RBNode child = (RBNode)root.getLeft();
		if ( child != sentinel ) {
			// tel.add( new TreeEdge( root, child ) );
			tel.addElement( new TreeEdge( root, child ) );
			addEdges( child, tel );
			}
		child = (RBNode)root.getRight();
		if ( child != sentinel ) {
			// tel.add( new TreeEdge( root, child ) );
			tel.addElement( new TreeEdge( root, child ) );
			addEdges( child, tel );
			}
		}

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

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

	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 );
		}

	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();
		}

	public void removeLabel( ShadowLabel label ) {
		DrawingPanel dp = AlgAnimFrame.getPanel();
		dp.removeObj( label );
		dp.repaint();
		}

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

	}