import java.awt.*;
//import java.lang.Math;
public class TreeCanvas extends Canvas{

    // the gap between neighboring subtrees, in symbols
    private int InterTreeGap = 3;
    // how many lines between the tree rows
    private int VerticalStep = 3;

    private TreeNode tree;
    private String recogn_input;

    public TreeCanvas(String[] rules, String recogn_input){
		this.recogn_input = recogn_input;
		this.tree = build_tree(rules);
    }

    public void paint(Graphics g){
	if(tree!=null) {
	  DrawTree(tree,g);
	}
    }

    public void DrawTree(TreeNode tree, Graphics g) {
	DrawTree(tree,0,0,g);
    }

    // draws the tree in a rectangle with the left upper corner (whereX,whereY)
    // returns the actual position of the root in the drawn tree
    public int DrawTree(TreeNode tree, int whereX, int whereY, Graphics g) {
	FontMetrics thisFM = g.getFontMetrics(g.getFont());
	// draw the root node
	//First, determine RootNodePosition
	int RootNodePosition = whereX + tree_width(tree, g)/2;
	if(tree.number_sons>0){
	    RootNodePosition +=
		(tree_width(tree.sons[0],g) -
		   tree_width(tree.sons[tree.number_sons-1],g))/4;
	}
	DrawNode(tree, RootNodePosition, whereY, g);
	// draw subtrees
	int currentX=whereX;
	int currentY=whereY+(VerticalStep+1)*thisFM.getHeight();
	// currentX,Y --- position of the next subtree to be drawn
	for(int i=0; i<tree.number_sons; i++) {
	    int lineend = DrawTree(tree.sons[i], currentX, currentY, g);
	    g.drawLine(lineend, currentY, RootNodePosition,
			whereY + thisFM.getHeight());
	    currentX += tree_width(tree.sons[i], g)
			+ InterTreeGap*thisFM.getMaxAdvance();
	}
	return RootNodePosition;
    }

    // draws the node
    // -----------(X,Y)--------------
    // | T  H  I  S   N   O   D   E |
    // ------------------------------
    public void DrawNode(TreeNode node, int X, int Y, Graphics g) {
	FontMetrics thisFM = g.getFontMetrics(g.getFont());
        if(node.is_endnode){
           g.setColor(Color.red);
        }  
	g.drawString(node.node_content,
		X - (node_width(node,g)/2),
		Y + thisFM.getHeight() );
        g.setColor(Color.black);
    }

    // tree-width for subtrees:
    //the space for the tree is the sum of those for the subtrees
    //(with inter-tree gaps) or the space needed for the root nore
    //if it is wider
    public int tree_width(TreeNode tree, Graphics g){
	   if (tree==null) {return 0;}
	   FontMetrics thisFM = g.getFontMetrics(g.getFont());
           int treewidth=0;
	   for(int i=0; i<tree.number_sons; i++){
               treewidth+=tree_width(tree.sons[i],g);              
           }
	   //add gaps between the subtrees (if any)
	   treewidth += java.lang.Math.max((tree.number_sons-1),0)
		* InterTreeGap * thisFM.getMaxAdvance();
	   //verify if the space for the node is wider than the subtrees
           return java.lang.Math.max(treewidth, node_width(tree, g));                  
    }
    //determines the width needed for a node of a tree
    public int node_width(TreeNode node, Graphics g){
	FontMetrics thisFM = g.getFontMetrics(g.getFont());
	return thisFM.stringWidth(node.node_content);
    }

    //find the width of the whole tree
    public int tree_width() {
	return tree_width(this.tree, this.getGraphics());
    }	

    //find the height of the whole tree
    public int tree_height() {
	return tree_height(this.tree, this.getGraphics());
    }	

    //tree_height for subtrees
    //how much vertical space is needed (in pixels)
    public int tree_height(TreeNode tree, Graphics g){
	   if (tree==null) {return 0;}
	   FontMetrics thisFM = g.getFontMetrics(g.getFont());
	   //first, how much space for this node
           int treeheight = thisFM.getHeight();
	   if(tree.number_sons>0) {
		//gap to subtrees = VerticalStep lines
		treeheight += thisFM.getHeight() * VerticalStep;
		//find the highest subtree
		int highestSubtreeHeight =0;
		for(int i=0; i<tree.number_sons; i++){
			highestSubtreeHeight = java.lang.Math.max( 
				highestSubtreeHeight,
				tree_height(tree.sons[i],g) );              
		}
		treeheight += highestSubtreeHeight;
	   }
           return treeheight;                  
    }

    //space on the screen needed
    public Dimension preferredSize(){
	Dimension treeSize = new Dimension(tree_width(),tree_height());
	return treeSize;
    }
//    public Dimension size(){
//	return getParent().size();
//    }

    public TreeNode build_tree(String[] rules) {
	   if (rules.length==0) {return null;}
           TreeNode startnode=new TreeNode(find_node_content(rules[0]));
           startnode.is_endnode=false;
	   TreeNode tree = new TreeNode();
           try {
	     tree = add_sons(startnode,rules,0);
	   } catch(RuleAndNodeDontMatchException e) {
             System.out.println(e);        
           }
	   return tree;
    }

//build a tree from the rules array rules[i..length-1] recursively
//find a right place to add sons (which are on the right part of the rule),
//for all rules
    public TreeNode add_sons(TreeNode startnode, String[] rules, int i)
         throws RuleAndNodeDontMatchException
    {       
        if((i < rules.length) && (i>=0)){
              TreeNode new_node=new TreeNode();
              new_node=next_node_to_handle(startnode);
              //content of the found node to handle must be the same
              // as the left part of the given rule    
              if(!( (new_node.node_content).equals(find_node_content(rules[i])) ) ){
                   throw new RuleAndNodeDontMatchException(new_node);
              }else{
                   new_node.put_sons(find_sons(rules[i]));        
              }
              //call the function recursively for next nodes and next rules
              return add_sons(startnode, rules, i+1);
        } else {
	      return startnode;
	}
    }   

//find next left node which is not endnode and has no sons (where sons
//have to be added)
//assumes that non-processed decendants do exist
    public TreeNode next_node_to_handle(TreeNode curr_node) {  
	if(curr_node.number_sons==0){
	    return curr_node;
	}else{
	    //check the same for all sons recursively
	    int j=0;
	    while (!has_non_processed_nodes(curr_node.sons[j])){
		j++;
	    }
	    return next_node_to_handle(curr_node.sons[j]);    
	}
    }

//checks if the tree has non-processed nodes
//node is non-processed if it is not an endnode and it has no sons

    public boolean has_non_processed_nodes(TreeNode curr_node) { 
	if(curr_node.is_endnode){
	    return false; 
	}else if(curr_node.number_sons==0){
	    return true;
	}else{
	    //check the same for all sons recursively
	    int j=0;
	    while ( (j<curr_node.number_sons) &&
		    (!has_non_processed_nodes(curr_node.sons[j])) ){
		j++;
	    }
	    return (j!=curr_node.number_sons);    
	}
    }

//get the left part of the rule
//=node content
   public String find_node_content(String rule){
            int arrow=rule.indexOf("-->");
            String left=rule.substring(0,arrow);
            left=left.trim(); 
            return left;
   } 
   
//get the right part of the rule
//find sons - make an array of TreeNode's each with known node_content
// (constituent from the right part of the rule) and unknown sons

   public TreeNode[] find_sons(String rule){
            TreeNode[] sons = new TreeNode[15];     
            String son_content;
            int j=0;
            int arrow=rule.indexOf("-->");
            String right=rule.substring(arrow+3, rule.length());
            right=right.trim()+" ";     
            while ( !right.equals(" ") ) {	            
                   int next_blank = right.indexOf(" ");
      	           //next constituent from the right part is a content of the next son
                   son_content = right.substring(0, next_blank);                  
                   TreeNode next_son=new TreeNode(son_content);
                   //is son_content substring of input? (=word)
                   if( (" "+recogn_input+" ").indexOf(" "+son_content+" ") == -1){                   
		       next_son.is_endnode = false;
                   }else{
		       next_son.is_endnode = true;
                   }
                   sons[j]=next_son;
                   j++;                    
                   right = right.substring(next_blank);
                   right = right.trim()+" ";
            }
            return sons;               
   } 
}