/** BTree Animation
	June.4 Friday 2004
	Implemented by Jung-Ho, Yoo & Chang-Hwan, Park
	in Seoul, S.Korea
 **/
 
import java.awt.*;
import ciips.animation.*;
import ciips.animation.tree.*;

public class BNode extends TreeNode { 
	private static int offset = 3;

	/** key array **/
	protected int key[];
	/** subtree array **/
    protected BNode child[];
    /** actual number of key **/
    private int key_cnt;
    /** actual number of child **/
    private int child_cnt;
    ///** show inner node or outnode **/
	//private boolean sentinel;
	/** maximum number of children **/
    protected int max_children;
	/** maximum number of key **/
    protected int max_key;
	/** height of node **/
    protected int height;

	protected static Nodespace nodespace;
	private Dimension node_size;
	private Dimension key_size;
	protected Color nodeColor = Color.black;
	protected Color labelColor = Color.pink;
	protected Color highlightColor = Color.blue;

	protected Font hugeFont, bigFont;
	private static final boolean DEBUG = true;

    /**
     * Create a new leaf node with multiple weight and children.
     */
	public BNode( int max_key ) {
		this.max_key = max_key;
		this.max_children = max_key+1;
		key = new int [max_key];
		child = new BNode[max_children];
		child_cnt = 0;
		key_cnt = 0;
		colour = DEF_TREENODE_COL;
		key_size = new Dimension( 20, 20 );
		node_size = new Dimension( key_size.width*(max_children-1), key_size.height );
		height = 0;
		if(DEBUG) System.out.print("BNode constructed max" + max_children + "children subtrees");
		if(DEBUG) System.out.println(" key " + (max_children-1));
    }

    /**
     * Create a new node with multiple weight and children
     * with weight to insert
      */
	public BNode( int weight, int max_key ) {
		this.max_key = max_key;
		this.max_children = max_key+1;
		key = new int [max_key];
		child = new BNode[max_children];
		key[0]=weight;
 		key_cnt = 1;
		child_cnt = 0;
		colour = DEF_TREENODE_COL;
		key_size = new Dimension( 20, 20 );
		node_size = new Dimension( key_size.width*(max_children-1), key_size.height );
		height = 0;
		if(DEBUG) System.out.print("BNode constructed max " + max_children + "   children subtrees");
		if(DEBUG) System.out.println(" key " + (max_children-1));
    }

	/**
     * insert specifickey and set two children on the left of weight and right of weight.
     */    
	public void insertKey(int specifickey, BNode left, BNode right)
	{
		int i;
		i = key_cnt; 
		while( i >0 && key[i-1] > specifickey)
		{
			// insertion sort
			key[i] = key[i-1];
			child[i+1] = child[i];
			i--;
		}
		key_cnt++;	
		key[i] = specifickey;
		
		child[i] = left;  
		child[i+1] = right;
		
		child_cnt = 0;

		for(i=0;i<=key_cnt;i++)
		{
			if(child[i] != null)
				child_cnt++;
		}
		}

	/** Adds a new key at index **/
    public void setKey ( int index, int newkey )
	{
		this.key[index] = newkey;
	}

	/** Adds a new key in appropriate position **/
    public void appendKey ( int newkey )
	{
		int i=0;
		i = key_cnt; 
		while( i >0 && key[i-1] > newkey )
		{
			
			key[i] = key[i-1];
			if(child[i] != null)
				child[i+1] = child[i];
			i--;
		}

		if(DEBUG) System.out.println("appendKey" + newkey);

			if (key_cnt <= max_children - 2 )
			{
				key[i]=newkey;
				key_cnt++;
				if(DEBUG) System.out.println("appended key number" + key_cnt);
			}
			else System.out.println("BNode: append key overflow");
	}

	public void setNodespace( Nodespace nodespace)
	{
		this.nodespace = nodespace;
	}


	/** Adds a new node **/
    public void setChild (BNode newnode )
	{
		int index;
		int minkey = newnode.key[0];
		index = findChildPosition(minkey);
		if(DEBUG) System.out.println("Index"+index);
		if (child_cnt < max_children - 1 && index >= 0) {
			child[index] = newnode;
			child_cnt++;
			if(DEBUG) System.out.println("BNode: setChild " + child_cnt);
		}
		else System.out.println("BNode: append child overflow");
    }
	
	/** Adds a new node at index**/
    public void setChild ( int index, BNode newnode )
	{
			child[index] = newnode;
			child_cnt++;
    }

	public String getLabel() {
		return new String(label);
		}
	
	/** Get Maximum key in this Node **/
	public int getMaxKey(){
		return key[key_cnt-1];
	}

	/** Find specific key in this Node
	** Return founded position(index) return -1, if didn't find
	**/
	public int findKey(int specifickey){
		int i;
		// sequence search
		for( i=0;i<key_cnt;i++)
		{
			if(specifickey ==key[i])
				return i; 
		}
		return -1;	
	}
	
	/** find child position which has spechfic key **/ 
	public int findChildPosition(int specifickey){
		if(findKey(specifickey)==-1){
			int index=0;
			if(key_cnt != 0){
				while(index<key_cnt && key[index]<specifickey )
				{
					index++;
				}
				if(index == key_cnt-1 && key[key_cnt-1] > specifickey)
					return ++index;
			return index; 
			}
			return 0; 
		}
		return -1;	
	}

	/** Delete specific key(at index) 
	** return current key count
	**/
	public void deleteKey(int index){

		int i;
		for(i=index+1;i<key_cnt;i++)
		{
			key[i-1] = key[i];
			child[i-1] = child[i];
		}
		child[i-1] = child[i];
		key_cnt--; 
	}

	/** return actual child number **/
	public int getChildCount(){
		return child_cnt;
    }
	
	/** return child at index **/
	public BNode getChild(int index){
		return child[index];
	}

	/** return actual key number **/
    public int getKeyCount(){
		return key_cnt;
    }

	/** set actual key number **/
    public void setKeyCount(int key_cnt){
		this.key_cnt = key_cnt;
    }

	/** return true if it is leaf **/
  	public boolean isLeaf() {
		boolean leaf = true;
		for(int i=0;i<max_children;i++){
			if(isSentinel(i)==false)
				leaf = false;
		}
		return leaf;
    }

	/** return true if child is null at index **/
	public boolean isSentinel(int index){
		return (child[index]==null || index>key_cnt);
	}
	
	/** return maximum node size **/
	public Dimension getNodesize(){
		return node_size;
	}

	/** return actual node size which was filled by inserted key**/
	public int getFilledkeywidth(){
		return key_size.width*key_cnt;
	}
	
	/** return height in the tree **/
	public int getHeight(){
		return this.height;
	}

	/** return all key as string  **/
	public String getAllKeyString(){
		StringBuffer weightstring;
		weightstring = new StringBuffer(30);
		weightstring.append(" ");
		
		int i;
		for(i=0;i<key_cnt;i++)
		{
			weightstring.append(key[i]);
			weightstring.append(" ");
         }

		weightstring.append(" ");

		return weightstring.toString();
	}

	/** return all key and height as string  **/
	public String toString(){
		return "BNode( height : "+ height + " key : " +getAllKeyString()+" )";
	}

    /** return key at index  **/
	public int getKey(int index){
		
                if(key_cnt>index)
                        return key[index];
                else
                        return -1;
	}

	
	/** Start at a node and set the positions for the sub-tree elements **/
	public void setPosition( int x, int y, int dx, int dy ) {
		// set root height = 0
		height = 0;
		int childorder=0;
		this.x = x; this.y = y;
		
		for(int i=0;i<max_children;i++){
			if(isSentinel(i) == false){
				child[i].setPosition( x, y+dy, dx, dy, this.height );
				childorder++;
			}
		}
	}

	/** Start at a node and set the positions for the sub-tree elements **/
	public void setPosition( int x, int y, int dx, int dy, int height  ) {
		this.height = height + 1;
		this.y = y;
		int childorder=0;
		x = nodespace.currentposX[this.height] + nodespace.spacewidth[this.height];
		
		if(nodespace.currentposX[this.height] == 0)
			nodespace.currentposX[this.height] = (x+getFilledkeywidth());
		else
			nodespace.currentposX[this.height] += (getFilledkeywidth()+ nodespace.spacewidth[this.height]);
		
		this.x = x;
		
		for(int i=0;i<max_children;i++){
			if(isSentinel(i) == false){
				child[i].setPosition( x, y+dy, dx, dy+30 , this.height);
				childorder++;
			}
		}
	}

		/**
		 * Move the node and all its branches based on the parameters.
		 * @param x The horizontal destination position of this node.
		 * @param y The vertical destination position of this node.
		 */
	public void move(int x, int y) {
		int dx = x - this.x;
		int dy = y - this.y;
		moveTreeNode(dx, dy);
		}

		/**
		 * Move the tree starting with node dx pixels to the right and dy
		 * pixels down.
		 * @param dx The change in x direction.
		 * @param dy The change in y direction.
		 */
	public void moveTreeNode(int dx, int dy) {
		x += dx;
		y += dy;
		if (!isLeaf()) {
			for(int i=0;i<max_children;i++){
				if(child[i] != null)
					child[i].moveTreeNode(dx,dy);
				}
			}
		}

		/**
		 * Assign some font instances to reduce initialization over during
		 * redraw.
		 */
	public void initFonts(Font hugeFont, Font bigFont) {
		this.hugeFont = hugeFont;
		this.bigFont = bigFont;
		}


	/**
	 * Set the color of the node.
	 * @param nodeColor new color of the node.
	 */
	public void initColors(Color nodeColor) {
		this.nodeColor = nodeColor;
		}

	public void setLabel( String label ){

		this.label = new String(label);
		}

	public void setColour( Color x ) {
		nodeColor = x;
		}
	
	public Color getColour() {
		return nodeColor;
		}
	
	public void setLabelColour( Color x ) {
		labelColor = x;
		}

	public void setHighlight( Graphics g ) {
		setColour( highlightColor );
		// draw( g );
		}

	public void Unhighlight_Node() {
		setColour(nodeColor );
		// draw( g );
		}

	/** Adjust the node size by a factor
	** @param factor - expansion factor: <CODE>factor > 1.0 => expansion,
	**											factor < 1.0 => shrinkage
	**/
	public void expandSize( float factor ) {
		float x = (float)(node_size.width) * factor;
		node_size.width = Math.round( x );
		x = (float)(node_size.height) * factor;
		node_size.height = Math.round( x );
		}


	public void drawEdge( Graphics g, BNode child ) {
		g.setColor( Color.black );
		for(int i=0;i<max_children;i++){
			
			if(DEBUG) System.out.println("BNode : drawEdge - " + toString() + " - " + child.toString());
			if(isSentinel(i) == false && this.child[i].equals(child) == true)
				g.drawLine( x + key_size.width*i, y + node_size.height, child.getX() + node_size.width/2, child.getY());
		}
	}

	public Dimension getHeadXY()
	{
		Dimension headedge;
		headedge = new Dimension();
		headedge.width = key_size.width*key_cnt/2;
		headedge.height = 0;
		return headedge;
	}

	public Dimension getEdgeXY(BNode child)
	{
		Dimension Edge;
		Edge = new Dimension();
		for(int i=0;i<max_children;i++){
			
			if(isSentinel(i) == false && this.child[i].equals(child) == true)
			{
				Edge.width = key_size.width*i;
				Edge.height = node_size.height;
				return Edge;
			}
		}
		return null;
	}


	/**
	 * This method draws the node on the corresponding graphical context
	 * normally passed in from the drawing panel.
	 */
	public void draw( Graphics g ) {
		node_size.width = key_size.width*key_cnt;
		if(this.key_cnt!= 0){
		g.setColor( nodeColor );
		g.fillRect( x, y, node_size.width, node_size.height );
		g.setColor(Color.black);
		g.drawRect( x, y, node_size.width, node_size.height );
		if ( label != null ) {
			if (getLabel().length() > 0) {
				g.setColor( labelColor );
				g.setFont( hugeFont );
				g.drawString(getLabel(), x + 5, y + 12);
				}
			}
		g.setColor( Color.white );
		g.setFont( bigFont );

		// draw multikey
		for(int i=0;i<key_cnt;i++)
			g.drawString("" + key[i],x + offset+key_size.width*i , y+node_size.height-offset);
		}
		}


} // class BNode