/** Trie class
**/
import java.awt.*;

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

public class Trie {
    private TrieNode root, parent_node, child_node;
    private int[] level_count;
    private int max_children=256;
    /** public final TrieNode sentinel = new TrieNode(null,0,0,0); **/
    
    private DrawingPanel dpAfter;
    private static final int labelFontSize = 12;
    private static final boolean DEBUG = true;
    private Dimension panel_dim = null;
    
  public Trie() {
		root = null;
		level_count = new int[max_children];
		for (int i=0; i < max_children; i++){
	    level_count[i]=0;
			} 
    }    
    
  public Trie( Dimension d ){
		this();
		this.panel_dim = d;
    }

  /** Search the trie for a node that has the same key **/
  public boolean find( RadixKey key ) {
		TrieNode current;	
		int level = 0;
		int next_level = 0;
		int pos,prev_pos;
	
		if (DEBUG) System.out.println("Trie:FindNode - Searching node (" 
				      + key.toString() + ")");
	
		// Check if the Trie is empty
		if (root == null){
	    System.out.println("Trie:FindNode - The Trie is empty!");
	    return false;
			}
		else {
	    current = root;
	    prev_pos = -1;
	    while ( true ){
		next_level = level + 1;
		pos = key.getRadix( level );
		//System.out.println("Current position : " + prev_pos);
		TrieNode child = current.getChild( pos );
		
		// Check if this is the end of the node
		if (child == null){
		    // Is this an intermediate node?
		    if (current.getData() == null) {
			System.out.println("Data does not exist");
			break;
		    }
		    else {
			// This is a leaf node
			RadixKey current_data = (RadixKey) (current.getData());
			if ( key.keyEqual(current_data)){
			    System.out.println ( "Trie:FindNode - Node (" + key.toString() + ") found!");
			    return true;
			}
			else {
			    System.out.println("Trie:FindNode - Node not Found");
			    break;
			}
		    }
		}
		else {
		    // Continue searching...
		    System.out.println("Trie:FindNode - Continue searching to the next level");
		    level=next_level;
		    prev_pos=pos;
		    current=child;
		}
	    }
	}	
	System.out.println (" "); 
	return false;
    }   
    
    
/*-------------------------------------------------------*/   
    /* Add a new data item to the trie */
	public boolean add( RadixKey data ){
		/*-*/TrieNode current, parent;	
		/*-*/int level = 0;
		/*-*/int next_level = 0;
		/*-*/int pos, prev_pos;
		/*-*/if( DEBUG ) System.out.println("Trie:InsertNode - Adding (" + data.toString() + ")" );
		/*-*/// Make the new node
		TrieNode x = new TrieNode( data,data.maxValue( next_level ) );
		/*-*/AlgAnimFrame.showText( 1, "Inserting Node ("+ data +") to the Trie");
		/*-*/AlgAnimFrame.highlightText(2);
		/*-*/AlgAnimFrame.highlightText(3);
		if ( root == null ) {    
	    root = x;
	    /*-*/AlgAnimFrame.highlightText(4);
	    /*-*/AlgAnimFrame.showText( 2, "Inserting Node to the Trie as the Root"); 
	    /*-*/drawTree( data );
      	}
		else {
	    current = root;
	    /*-*/current.setHighlight();
	    /*-*/drawTree( data );
	    /*-*/AlgAnimFrame.highlightText(6);	    
	    /*-*/AlgAnimFrame.highlightText(7);
	    /*-*/parent = null;
	    /*-*/prev_pos = -1;
	    while ( true ) {
		/*-*/AlgAnimFrame.highlightText(8);
		/*-*/next_level = level + 1;
		/*-*/pos = data.getRadix( level );
		/*-*/TrieNode child = current.getChild( pos );
		
		// Check if the child is null
		/*-*/AlgAnimFrame.highlightText(11); 
		if ( child == null ) {

		    // Is this node an intermediate node?
		    /*-*/AlgAnimFrame.highlightText(14);
		    if ( current.getData() == null ) {
			
			// Just add the new node
			current.setChild( x, pos );
			/*-*/AlgAnimFrame.highlightText(17);

			/*-*/current.setChildCount();
			/*-*/AlgAnimFrame.showText( 5, " Node (" + data +") added to The Trie"); 
			/*-*/current.unHighlight();
			/*-*/drawTree( data );			
			/*-*/AlgAnimFrame.highlightText(18);
			break;
		    }
		    else {
			/*-*/AlgAnimFrame.highlightText(20);
			/*-*/AlgAnimFrame.highlightText(24);
			
			// It's a leaf node
			// Check for a duplicate
			/*-*/RadixKey current_data = (RadixKey)(current.getData());
			if ( data.keyEqual( current_data )) {
			    /*-*/if( DEBUG ) System.out.println("Trie:InsertNode - Adding duplicate (" + data.toString() + "/" + current_data.toString() + ")" );
			    /*-*/AlgAnimFrame.showText( 3, "Data already exists" );
			    /*-*/AlgAnimFrame.highlightText(25);
			    /*-*/current.unHighlight();
			    /*-*/drawTree( data );	
			    return false;
			}
			
			// Make a new intermediate node
			// and attach the current node 
			// at the right position
			/*-*/AlgAnimFrame.highlightText(31);
			TrieNode inter = new TrieNode( current.getRadixCount(), current, current_data.getRadix( level ) );
			/*-*/inter.setChildCount();
			// Attach inter to the parent
			/*-*/AlgAnimFrame.highlightText(33);
			if ( parent == null ) {
			   /*-*/AlgAnimFrame.highlightText(34); 
			   root = inter;
			} else { 
			    /*-*/AlgAnimFrame.highlightText(35);
			    /*-*/AlgAnimFrame.highlightText(36);
			    parent.setChild( inter, prev_pos );
			}
			/*-*/drawTree( data );
			/*-*/AlgAnimFrame.showText(4,"Adding Intermediate node with null value");
			/*-*/System.out.println("Trie : InsertNode - Adding Intermediate node (" + inter.getData()  + ") at position (" + prev_pos + ") and level (" + level + ")");	    
		      
			// Try to add the new node to the intermediate one
			/*-*/AlgAnimFrame.highlightText(40);
			if ( inter.getChild( pos ) == null ) {
		
			    // Add new node and finish
			    /*-*/AlgAnimFrame.highlightText(43);
			    inter.setChild( x, pos );
			    /*-*/inter.setChildCount();
			    /*-*/AlgAnimFrame.showText( 5, " Node (" + data +") added to The Trie"); 
			    /*-*/current.unHighlight();
			    /*-*/drawTree( data );
			    /*-*/AlgAnimFrame.highlightText(44);
			    break;
			}
			else {
			    /*-*/AlgAnimFrame.highlightText(46);

			    // We need to continue
			    /*-*/level=next_level;
			    /*-*/prev_pos = pos;
			    /*-*/parent = inter;
			    /*-*/AlgAnimFrame.highlightText(49);
			    /*-*/current.unHighlight();
			    current = inter.getChild(pos);
			    /*-*///AlgAnimFrame.getPanel().repaint();
			    /*-*/current.setHighlight();
			    /*-*/drawTree( data );
			    /*-*/AlgAnimFrame.showText(2, " Continue to the next corresponding node...");
			}							
		    }
		}
		else{ 
		   
		    // The child is not null, go to the 
		    // child node and set as current node
		    /*-*/AlgAnimFrame.highlightText(53);
		    /*-*/System.out.println("Trie:add - Child not null and continuing....");
		    /*-*/parent = current;
		    /*-*/AlgAnimFrame.highlightText(57);
		    /*-*/current.unHighlight();
		    current = child;
		    /*-*/level=next_level;
		    /*-*/prev_pos=pos;
		    /*-*/current.setHighlight();
		    /*-*/drawTree( data );
				}
	    }
	  /*-*/System.out.println ( "Adding string " + data.toString() +" at level = ( " + next_level + ") and position = (" + pos + ")");  
		}
	/*-*/AlgAnimFrame.highlightText(61); if( DEBUG ) System.out.println("Trie:InsertNode - Added (" + data.toString() + ")" );
	return true;		
  }	
   
//---------------

    /** This method sets the (x,y) position of each node
     *  This method use the setPosition method in the MultiNode class
     **/
  public boolean setTreePosition ( TrieNode node, int width, int height ){
		int x = 0, y = 0, padd = 5;

		x = width / 2;
		y = height / 16;	
		node.setPosition ( x + padd, y, width - (2*padd), y );  
		return true;
    }
    


  public void drawNode( Graphics g, TrieNode parent, TrieNode child){
		if (DEBUG) System.out.println("Trie:DrawNode - ");
	
		if ( parent != null && child != null ){
	    parent.drawEdge( g, child );
	    child.draw( g );
			AlgAnimFrame.pauseStep();
			}
    }

  public void drawSubTree( Graphics g, TrieNode node, RadixKey data){
		if (DEBUG) System.out.println("Trie:DrawTree - ");
	
		node.draw( g );
		for ( int i=-1 ; i< node.getRadixCount()-1; i++) { 
	    TrieNode child = node.getChild(i);
	    if ( child != null ){
				if ( child.getData() != data ) {
		    	node.drawEdge( g, child );
		    	drawSubTree( g, child, data );		    
					}
				else {
		    	parent_node = node;
		    	child_node = child;
					}
	    	}
			}
    }
    
  public void drawTree( RadixKey data ) {
		int panel_height, panel_width;
		Graphics g;
		if( DEBUG ) System.out.println("Trie:drawTree - data (" + data + ")" );
		dpAfter = AlgAnimFrame.getPanel();
		g = dpAfter.getOffScreenGraphics();
		panel_height = dpAfter.getPanelHeight();
		panel_width = dpAfter.getPanelWidth();	
		Dimension d = dpAfter.getPreferredSize();

		// Check if width and height of the drawing panel is reasonable
		if(d.width < 1 || d.height < 1){
	    System.out.println("d.height: "+d.height+ ", d.width: " +d.width);
			}
	
		g.setColor( dpAfter.getBackground() );
		g.fillRect( 0, 0, d.width, d.height );
	
		// Set position of root and all sub-trees
		setTreePosition( root, panel_width, panel_height );
		parent_node = null;
		child_node = null;
		drawSubTree( g, root, data );
		// g.drawImage( offscreen, 0, 0, null );

		drawNode( g, parent_node, child_node);
		// g.drawImage( offscreen, 0, 0, null );
		// Update the panel
		dpAfter.drawFromOffscreen();
		if( DEBUG ) System.out.println("Trie:drawTree - to pauseStep" );
		AlgAnimFrame.pauseStep();
		if( DEBUG ) System.out.println("Trie:drawTree - exit" );
  	}
	}