/** BTree Animation
	June.4 Friday 2004
	Implemented by Jung-Ho, Yoo & Chang-Hwan, Park
	in Seoul, S.Korea
 **/

import java.util.*;
import java.applet.*;
import java.awt.*;
import java.lang.*;

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

/** Nodespace class store space between adjacent node in the same level **/
 class Nodespace{
		
		public int totalwidth[];
		public int totalnode_cnt[];
		public int spacewidth[];
		public int currentposX[];

		public Nodespace()
		{
			totalwidth = new int[5];
			totalnode_cnt = new int[5];
			spacewidth =new int [5];
			currentposX = new int [5];
		}

	};
	
public class BTree {

	/** main root node **/
	private	BNode root;
	private DrawingPanel dpAfter;
	private TreeEdgeList tl;
	private Dimension edge_off = new Dimension( 4, 4 );
	/** edge start point offet **/
	private Dimension start_off ;
	/** edge end point offet **/
	private Dimension end_off ;
	private Graphics g;

	/** maximum children count in a node **/
	private int max_children;
	/** maximum key count in a node **/
	private int max_key;
	
	private BNode insertednode;
	private BNode newkey;
	private BNode lastsplitednode=null;
	private boolean bt_display = false;
	private static final boolean DEBUG = true;

	/**
	** Construct max_key ary BTree 
	**/
	public BTree(int max_key){
		this.max_key = max_key;
		this.max_children = max_key + 1;
		root = new BNode(max_key);
		end_off = new Dimension();
		end_off.width = root.getNodesize().width/2;
		end_off.height = 0;
		
		/*-*/ dpAfter = AlgAnimFrame.getPanel();
		
		}

	/** Find Node containding data and add trajectory **/
	public BNode FindNode(int key, Trajectory t){
		BNode current = root;
		int i;
		t.addPoint( root, find_off );
		while( current != null && current.findKey(key) == -1)
		{
			
			for(i=0;i<current.getKeyCount() && key>=current.getKey(i);i++);
				current = current.getChild(i);
				if(current!= null)
				t.addPoint( current, find_off );
		}
		return current;
		}

	/** Find Node containding data **/
	public BNode FindNode(int key){
		BNode current = root;
		int i;
		while( current != null && current.findKey(key) == -1)
		{
			
			for(i=0;i<current.getKeyCount() && key>=current.getKey(i);i++);
				current = current.getChild(i);
		}
		return current; 
		}

	// Standard labels to be added to drawing
	static ShadowLabel split = new ShadowLabel("Split full node");
	static ShadowLabel insert = new ShadowLabel("Insert in non-full node");
	static ShadowLabel bind = new ShadowLabel("Bind two nodes");
	static ShadowLabel swapkey = new ShadowLabel("Swap the key" );
	// 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

	/** split full node on down way **/
	private BNode split(int key, BNode pivot){
		
		BNode base;
		base = root;
		BNode left, right; 
		BNode childnode;	
		int i;
		int middlekey;
		right = new BNode(max_key);
		if( pivot == base && base.getKeyCount() == max_key) 
		{
		// split root node 
			/*-*/ Color origColour = pivot.getColour(); pivot.setHighlight(g);		
			/*-*/ AlgAnimFrame.showText( 3, "Split the node : " + pivot.getAllKeyString() );	
			/*-*/ addLabelNear( split, pivot ); drawBTree(); AlgAnimFrame.pauseStep(); removeLabel( split ); pivot.setColour(origColour);
			childnode = root ; // 
			left = new BNode(max_key);
			addObj(left, 0, 0);
			for(i=0;i<(max_key/2);i++)	// make left node
			{
				left.setKey(i, childnode.getKey(i));
				left.setChild(i, childnode.getChild(i));
			}
			if(i!=(max_key/2)+1)
			left.setChild(i, childnode.getChild(i));
			left.setKeyCount(max_key/2); 
			
			
			for(i=(max_key/2)+1;i<(max_key);i++)	// make right node
			{
			right.setChild(i-(max_key/2)-1, childnode.getChild(i));
			right.setKey(i-(max_key/2)-1, childnode.getKey(i));
			}
		right.setChild(i-(max_key/2)-1, childnode.getChild(i));
		
		if(max_key%2 == 0)
			right.setKeyCount((max_key-1)/2);
		else
			right.setKeyCount(max_key/2);
		middlekey = childnode.getKey(max_key/2);
		childnode.setKeyCount(0);	
		childnode.insertKey(middlekey, left, right);
		
		
	}else{
		// split node which is not a leaf
		for(i=0; i<pivot.getKeyCount() && key>=pivot.getKey(i) ;i++);
		left = pivot.getChild(i);	
		/*-*/ Color origColour = left.getColour(); left.setHighlight(g);		
		/*-*/ AlgAnimFrame.showText( 3, "Split the node : " + left.getAllKeyString() );	
		/*-*/ addLabelNear( split, left ); drawBTree(); AlgAnimFrame.pauseStep(); removeLabel( split ); left.setColour(origColour);
		for(i=(max_key/2)+1;i<(max_key) ; i++)	// make new node on the right
		{
			right.setChild(i-(max_key/2)-1, left.getChild(i));
			right.setKey(i-(max_key/2)-1, left.getKey(i));
		}
		right.setChild(i-(max_key/2)-1, left.getChild(i));
		if(max_key%2 == 0)
			right.setKeyCount((max_key-1)/2);
		else
			right.setKeyCount(max_key/2);
			
		middlekey = left.getKey(max_key/2);
		pivot.insertKey(middlekey, left, right);
		childnode = pivot;						// return parent
		left.setKeyCount(max_key/2);			// setup key count
		}

		dpAfter.removeObj(childnode);
		dpAfter.removeObj(left);
		dpAfter.removeObj(right);

		addObj(childnode, 0, 0);
		addObj(left, 0, 0);
		addObj(right, 0, 0);
	return childnode;
	}

	/**
	** Insert data in BTree 
	**/
	public boolean insertNode(int data){
		

		if(lastsplitednode!=null){ lastsplitednode.Unhighlight_Node(); lastsplitednode=null; }
		int i;
		boolean isSplited=false;
		newkey = new BNode(data, 1);
		newkey.setColour(Color.red);
		BNode parent;
		BNode current;	
		BNode splitednode=null;
		BNode x;		
		/*-*/ AlgAnimFrame.showText(1,"Inserting " + data ); 
		/*-*/ System.out.println("BTree: InsertNode: value " + data );
		/*-*/ if( tl == null ) {
						System.out.println("BTree:InsertNode - create TEL");
						tl = new TreeEdgeList();
						System.out.println("BTree:InsertNode - created TEL");
						addObj( tl, 0, 0 ); }
		/* find where node belongs */
		current = root; /*-*/ AlgAnimFrame.showText(2,"Locate insertion point");
		parent = root; /*-*/ Trajectory animatept = new Trajectory();	animatept.addPoint( start ); removeLabel( split );  
		while (current != null) {
			if (current.findKey(data) >=0) { /*-*/ AlgAnimFrame.showText(3,"This data already exists!");
				return false; 
				}
			if(current.getKeyCount() == max_key) 
			{
				/*-*/ AlgAnimFrame.showText(3,"Split fully filled node");
				current = split(data, parent); 
				if(current == null ) return false;
				isSplited = true;
				splitednode = parent;
			}
			parent = current;
			for(i=0;i<current.getKeyCount()&&data>=current.getKey(i);i++);
			current = current.getChild(i); /*-*/ AlgAnimFrame.showText(3,"Go to " + (i+1)+ " key position");
		}
		insertednode = parent;
		x = parent;


		/*-*/ 		
		/*-*/  
		/*-*/  
			

		//clearPanel(root);
		//addAllnode(root);
		//setEdges(tl);

		/*-*/ if( DEBUG ) System.out.println("BTree:Insert - Before DT"); Color origColour = parent.getColour(); 
		
		/*-*/ updateNodePositions(); setEdges(tl); drawBTree();  addObj(newkey, 0, 0); FindNode(data, animatept); 
		/*-*/ addLabelNear( insert, x );parent.setColour(Color.green);animate( newkey, animatept );
		/*-*/ if( parent != null ) { System.out.println("TL add " + parent.getAllKeyString() + "-" + x.getAllKeyString() );  }
		parent.appendKey( data); //append key in the leaf 
		/*-*/ removeLabel( insert ); parent.setColour(origColour); addObj(parent, 0, 0);  dpAfter.removeObj(newkey);  updateNodePositions(); setEdges(tl);drawBTree(); AlgAnimFrame.pauseStep(); 
		if(splitednode != null){
			splitednode.Unhighlight_Node();
			removeLabel(split);
		} 

		
		return true;
	}

	/**
	** Delete data in BTree 
	**/
	public int deleteNode( int key, AlgAnimFrame frame ){
		
		// find the key
		BNode base = root;
		BNode current, parent;
		int pi=0; // index of parent node
		int ti;	// index of current node
		parent = base;
		current = root;
		while(current != null)
		{
			if(current.getKeyCount() <= (max_key/2) && parent != base) 
				if(!borrowKey(parent, pi)) current = bindNode(parent, pi, base); // borrowkey or bind two node
			if((ti = current.findKey(key) ) >= 0) 
			{

				if(current.getChild(0) == null ) break; 
				else key = swapKey(current, key, ti);  // swap the key with replaced key
			}
			parent = current;
			for(pi=0;pi<current.getKeyCount() && key >= current.getKey(pi);pi++);
			current = current.getChild(pi); 
		}
		if(current == null) return 0; 
		if(current.getKeyCount() <= (max_key/2) && parent!=base) 
		if(!borrowKey(parent, pi)) current = bindNode(parent, pi, base);
		current.deleteKey(current.findKey(key));
		if(current.getKeyCount()==0)
			parent.setChild(pi, null);
		
		/*-*/ setEdges(tl); frame.showText( 2, "The key is removed" ); updateNodePositions();drawBTree(); addComNear( current, "Remove this key" );                     
		/*-*/ drawBTree(); AlgAnimFrame.pauseStep(); dpAfter.removeAllCom();
		/*-*/ if( DEBUG ) System.out.println("BTree:Delete " + key);
		/*-*/ updateNodePositions();drawBTree(); AlgAnimFrame.pauseStep(); dpAfter.removeAllCom();
		
		return 1;
		}

	/**
	** Borrow key from siblings
	**/
	private boolean borrowKey(BNode startnode, int index)
	{
		int from, to;
		BNode lendnode, borrownode;
		if(index == startnode.getKeyCount())
		{
			// borrow from left child
			from = index-1;
			to = index;
		}
		else
		{
			// borrow from right child
			from = index+1;
			to = index;
		}
		if(startnode.isSentinel(from) == true) return false;
		if(startnode.isSentinel(to) == true) return false;
		lendnode = startnode.getChild(from); 
		borrownode = startnode.getChild(to); 
		if(lendnode.getKeyCount() <=(max_key/2)) return false; 
		if(from > to)
		{
			borrownode.insertKey(startnode.getKey(to), borrownode.getChild(borrownode.getKeyCount()), lendnode.getChild(0));
			startnode.setKey(to, lendnode.getKey(0));
			lendnode.deleteKey(0);
		}
		else{
		
		borrownode.insertKey(startnode.getKey(from), lendnode.getChild(lendnode.getKeyCount()), borrownode.getChild(0));
		startnode.setKey(from, lendnode.getKey(lendnode.getKeyCount()-1));
		lendnode.deleteKey(lendnode.getKeyCount()-1);
	}
	return true; 
	}
	
	/**
	** Bind two nodes which are not fully filled
	**/
	private BNode bindNode(BNode firstnode, int index, BNode secondnode )
	{
		BNode left, right;
		int i;
		if(index == firstnode.getKeyCount() ) index--; 
		left = firstnode.getChild(index);	// left child
		right = firstnode.getChild(index+1); // right child
		
		left.setKey(left.getKeyCount(), firstnode.getKey(index)); 
		
		left.setKeyCount(left.getKeyCount()+1);
		for (i=0;i<right.getKeyCount();i++) // copy all key and child from right node to left node
		{

			left.setKey(left.getKeyCount(), right.getKey(i));
			left.setChild(left.getKeyCount(), right.getChild(i));
			left.setKeyCount(left.getKeyCount()+1);
		}
		left.setChild(left.getKeyCount(), right.getChild(i));
		firstnode.deleteKey(index);
		firstnode.setChild(index, left);
		
		if(firstnode.getKeyCount() == 0) // root node 
		{
			secondnode.setChild(0, left); 
		}
		return left; // binded node
		}	
	
	/**
	** Swap the key to be deleted with borrowed key from siblings
	**/
	private int swapKey(BNode siblings, int key, int index)
	{
		int swappedkey;
		BNode  center, pcenter; // center node has replace key
		pcenter = siblings;
		center = pcenter.getChild(index+1); // right child of pcenter(deleted key)
		while(center.getChild(0) != null ) // the left most child of center
		{
			pcenter = center;
			center = center.getChild(0);
		}
		siblings.setKey(index, center.getKey(0)); // replace key with borrowed key
		return center.getKey(0); // replaced key
		
	}

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

	private void drawST( Graphics g, BNode parent, BNode child ) {
		if( DEBUG ) System.out.println("drawST: p " + parent.getAllKeyString() + " " + (parent.isLeaf()) );
		if ( (child.getKeyCount()!=0 ) && (child != null) ) {
			parent.drawEdge( g, child );
			drawBSubTree( child, g );
			}
		}

	private void drawBSubTree( BNode x, Graphics g ) {
		BNode child;
		if( DEBUG ) System.out.println("drawBSubTree: x " + x.getAllKeyString() + " " + (x.isLeaf()) );
		if ( x != null ) {
			x.draw( g);//, sentinel );
			for(int i=0;i<max_children;i++){
				if(x.isSentinel(i) == false)
					drawST( g, x, (BNode)x.getChild(i) );
			}
			}
		}

	private void updateNodePositions() {
		Dimension d = dpAfter.size();
		if( DEBUG ) System.out.println("BTree: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 - root.getNodesize().width;
		int dx = d_width / 2;
		int dy = d.height / 10;
		Nodespace nodespace;
		nodespace = new Nodespace();
		// calculate space of nodes in the same level
		computeNodePositions(nodespace);
		root.setNodespace(nodespace);
		root.setPosition( dx, dy, dx, dy+30);
		// inserted new key position
		if(newkey != null) newkey.setPosition( insertednode.getX(), insertednode.getY(), dx, dy );
		}

	/** travesal all node to calculate nodespace **/
	private void computeNodePositions(Nodespace nodespace) {
		Dimension d = dpAfter.size();
		Stack nodestack;
		BNode current;
		nodestack = new Stack();
		nodestack.push(root);
		
		for(int i=0;i<5;i++){
			nodespace.totalwidth[i] = d.width;
			nodespace.totalnode_cnt[i] = 0;
			nodespace.currentposX[i] = 0;
		}
		while(nodestack.empty() == false){
			current = (BNode) nodestack.pop();
			nodespace.totalwidth[current.getHeight()] -= current.getFilledkeywidth();
			nodespace.totalnode_cnt[current.getHeight()]++;
			for(int i=0;i<max_children;i++){
				if(current.isSentinel(i) == false)
					nodestack.push(current.getChild(i));
				}
			}	

		for(int i=0;i<5;i++){
			// compute the space between node in the same height
			nodespace.spacewidth[i] = nodespace.totalwidth[i]/(nodespace.totalnode_cnt[i]+1);
			}
	}


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

	public void PrintNode(BNode x){
	
		System.out.println((max_children-1)+ " ary node ");
		if (x.isLeaf() == true) System.out.println("x is a leaf node.");
		
		System.out.print("Node has data: ");
		System.out.println(x.getAllKeyString());
			
		for(int i=0;i<max_children;i++){

			System.out.print(i + " child has ");
			if(x.isSentinel(i) == true) System.out.println(" none ");
			else System.out.println(x.getChild(i).getAllKeyString());
			System.out.println("");
			}
		}

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

	private void addEdges( BNode rootnode, TreeEdgeList tel ) {
		
		BNode childnode;
		for(int i=0;i<max_children;i++){

			if(rootnode.isSentinel(i) == false){
			childnode = rootnode.getChild(i);
			tel.addElement( new BTreeEdge( rootnode, childnode, rootnode.getEdgeXY(childnode), childnode.getHeadXY() ) );
			addEdges( childnode, tel );

			}
		}
	}

private void clearPanel(BNode current){
		dpAfter.removeObj(current);
			for(int i=0;i<max_children;i++){
				if(current.isSentinel(i) == false)
					clearPanel(current.getChild(i));
		}

	}

private void addAllnode(BNode current){
		addObj(current, 0, 0);
			for(int i=0;i<max_children;i++){
				if(current.isSentinel(i) == false)
					addObj(current.getChild(i), 0, 0);
		}

	}
		
public void setEdges( TreeEdgeList tel ) {
		tel.clear();
		if ( root.getKeyCount() != 0 ) {
			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 );
		}

}