treenode.java

生物物种进化历程的演示

/*
   Copyright (c) 2002 Compaq Computer Corporation
   
   SOFTWARE RELEASE
   
   Permission is hereby granted, free of charge, to any person obtaining
   a copy of this software and associated documentation files (the
   "Software"), to deal in the Software without restriction, including
   without limitation the rights to use, copy, modify, merge, publish,
   distribute, sublicense, and/or sell copies of the Software, and to
   permit persons to whom the Software is furnished to do so, subject to
   the following conditions:
   
   - Redistributions of source code must retain the above copyright
     notice, this list of conditions and the following disclaimer.
   
   - Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions and the following disclaimer in the
     documentation and/or other materials provided with the distribution.
   
   - Neither the names of Compaq Research, Compaq Computer Corporation
     nor the names of its contributors may be used to endorse or promote
     products derived from this Software without specific prior written
     permission.
   
   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
   IN NO EVENT SHALL COMPAQ COMPUTER CORPORATION BE LIABLE FOR ANY CLAIM,
   DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
   OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
   THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

package AccordionTreeDrawer;

import java.awt.*;
import java.util.*;

import AccordionDrawer.*;

/**
 * A class representing a node of a (phylognenetic) tree.
 * The tree that this node belongs to is of type Tree.
 * Nodes have fields that store a pre- and post-ordering. 
 *
 * A TreeNode has a list of children, a unique key, a leftmostleaf 
 * and a rightmost leaf
 *
 * @author  Tamara Munzner, Li Zhang, Yunhong Zhou
 * @version 
 * @see     Tree
 * @see     GridCell
 */

public class TreeNode extends Object implements CellGeom, Comparable {

    ArrayList children; // eventually turn this into an array (need to change parser)
    TreeEdge edges[] = new TreeEdge[2];
//    LabelBox lb;

    /** key is unique for nodes in one tree */
    public int key; 

    /** The GridCell that this node is attached to  */ 
    public GridCell cell; 

    /** 
     * The index of the smallest descendant node (Node in subtree rooted
     * at this node).
     */
    private int min; 

    /** The index of the largest descendant node */ 
    private int max; 
    
    private int fontSize;
    Double bcnScore;
//    /**
//     * The offset of the point with respect to the cell. We only have
//     * this for the row offset as we assume that the vertical edges
//     * are all aligned.  When computing the Y coordinate of a node, we
//     * add nodeOffsetR to the pointOffset[1], a fixed parameter set by
//     * AccordionDrawer.
//     */
	int computedFrame; // store frame midYPosition was last calculated (needed to place parents)
    double midYPosition;


    /** @return The index of the smallest descendant node */ 
    public int getMin() { return min; }

    /** @return The index of the smallest descendant node */ 
    public int getMax() { return max; }

    public int getKey() { return key;}
    public String getName() { return name;}

    public boolean pick(int x, int y) { return false; }

    /**
     * Draws this node inside cell, the GridCell that it is attached
     * to, if cell is drawn large enough Prints the label of the node
     * if the GridCell is drawn large enough
     * @author   Tamara Munzner, Serdar Tasiran, Li Zhang, Yunhong Zhou
     * 
     * @param    col The color to draw this node in
     * @param    plane The plane to draw this node in
     *
     * @see      AccordionDrawer.GridCell
     */
    
    public void drawInCell(Color col, double plane) {
	for (int xy = 0; xy < 2; xy++) {
	    TreeEdge e = edges[xy];
	    if (null != e) e.drawInCell(col, plane);
	}
    }
    
    public void drawInCell(ArrayList col, double plane)
    {
    	if (cell.getDrawnFrame() >= cell.drawer.getFrameNum())
    		return; // already drawn in this frame
    	cell.setDrawnFrame(cell.drawer.getFrameNum());
    	if (isLeaf())
    		((AccordionTreeDrawer)cell.drawer).leafDrawCount++;
    	else
			((AccordionTreeDrawer)cell.drawer).internalDrawCount++;
    	Color c = null;
    	if (col != null && col.size() > 0)
    	{
    		c = (Color)col.get(0);
    		plane = cell.drawer.hiliteplane - .004*c.getAlpha();
    	}
    	drawInCell(c, plane);
    }

    // cell max[X] boundary set to min[X] boundary over all children
    public void setCell(GridCell c) { cell = c;}
    public GridCell getCell() { return cell;}

    /** Add edge in either X/horizontal (xy==0) direction, or
     * Y/vertical (xy==1)direction. Leaf nodes have no vertical edge. 
     * @author Tamara Munzner */
    public void addEdge(TreeEdge edge, int xy) {
	edges[xy] = edge;
    }
    public TreeEdge getEdge(int xy) { return edges[xy];}

    /** implement Comparable interface - sort on key field */
    public int compareTo(Object o) {
	if (key == ((TreeNode)o).key) return 0;
	else if (key < ((TreeNode)o).key) return -1;
	else return 1;
    }

    public TreeNode parent;

    /** 
     * node name with default "". 
     * Most internal nodes have no name and all leaf nodes have a name 
     */  
    String name = ""; // the long form in fully qualified names
    public String label = ""; // always short form

    int height;

    /** weight is actually edge length for the edge immediately above the node */
    public float weight = 0.0f;

    public TreeNode leftmostLeaf, rightmostLeaf;
    public int numberLeaves;
    public TreeNode preorderNext = null;

    public TreeNode posorderNext = null;

// this can be extracted from split cell position
//    /** leaf index */
//    public int lindex; 

// change next pointers to list of leaves with leaf indices corresponding to
// position in split cells
//    /** next leaf added by Li */
//    public TreeNode next=null;


    /**
     * Children list initial capacity 2 as in most case binary.
     */
    // used in 2 places:
    // - create the root when creating the tree
    // - the parser uses this to create nodes attached to the root
    public TreeNode() {

	children = new ArrayList(2); 
	max = -1;
	min = Integer.MAX_VALUE;
	bcnScore = new Double(0.0);
	//	nodeOffsetR = 0;
    }

	/**
	 * clean the node itself and the tree edge attached with it.
	 * @see TreeEdge.close
	 * @see Tree.close
	 *
	 */   
	   public void close(){
		   children.clear();
		   children=null;
		   name=null;
		   cell = null;
		   if (edges != null)
		   		for(int i=0; i<edges.length; i++)
		   			if(edges[i] !=null)
		   				edges[i].close();
		   edges=null;		
			parent=null;	
			label = null;
			leftmostLeaf=null;
			rightmostLeaf=null;	
			preorderNext = null;
			posorderNext = null;		
			bcnScore=null;
//		   this = null;
		  }
   
		  protected void finalize() throws Throwable {
		 
					   try {
						   close();
					   }
					   finally {
						   super.finalize();     
//						   System.out.println("finally clean treeNodes");
					   }
		   }

    /**
     * Allocate a new TreeNode object with node name and weight.   
     * @param s The name of the node given by a string
     * @param w The weight of the edge immediately above the node
     */
    // used only in copying trees
    public TreeNode(String s, float w){
	children = new ArrayList(2);
	name = new String(s);
	weight = w;
	max = -1;
	min = Integer.MAX_VALUE;
	// nodeOffsetR = 0;
    }

	// not used
    public TreeNode(String s){
	children = new ArrayList(2);
	name = new String(s);
	max = -1;
	min = Integer.MAX_VALUE;
	// nodeOffsetR = 0;
    }

    public void setName(String s){
	name = new String(s);
    }

    public int numberChildren() {
	return children.size();
    }

    public TreeNode getChild(int i){
	return (TreeNode) children.get(i);
    }

    public TreeNode getLeftmostLeaf() {
	
	TreeNode n = this;
	while(!n.isLeaf()) n= n.firstChild();
	return n;
    }

    public TreeNode getRightmostLeaf() {

	TreeNode n = this;
	while(!n.isLeaf()) n = n.lastChild();
	return n;
    }

    public boolean isLeaf() {
	return children.isEmpty();
    }

    public boolean isRoot() {
	return (null == parent);
    }


    /** @return the total number of leaves decedant to this node */
    public int getLeafCount() {	
	if(this == null)
	    return 0;
	else if(isLeaf())
	    return 1;
	else{
	    int sum = 0;
	    for(int i=0; i<numberChildren(); i++)
		sum += getChild(i).getLeafCount();
	    return sum;
	}
	
    }

    public boolean equals(TreeNode n){
	return (name.equals(n.name));
    }

    public void addChild(TreeNode n) {
	children.add(n);
	n.parent = this;
    }

    public TreeNode parent() {
	return parent;
    }

    public void setWeight(double w){
	weight = (float) w;