treenode.java

生物物种进化历程的演示

    }

    public float getWeight() { return weight; }
    
    public TreeNode firstChild() {
	return (TreeNode) children.get(0);
    }

    public TreeNode lastChild() {
	return (TreeNode) children.get(children.size()-1);
    }

    /** 
     * @return <code>true</code> if this is an ancestor of <code>that</code>
     * @param that Another TreeNode object 
     */
    public boolean isAncestorOf(TreeNode that) {
	if(leftmostLeaf.getLindex() > that.leftmostLeaf.getLindex() ||
	  	rightmostLeaf.getLindex() < that.rightmostLeaf.getLindex()) return false;
	return true;
	
    }

    /**
     * Compute the lowest common ancestor between this node and <code>that</that>.
     * The two nodes must belong to the same tree.
     * @author   Li Zhang
     * 
     * @param    that A TreeNode in the Tree that this TreeNode belongs to
     * @return   the lowest common ancestor between this node and "that"
     */
    
    public TreeNode lca(TreeNode that) {
	if(that.isAncestorOf(this)) return that;
	TreeNode current = this;
	while(current != null) {
	    if(current.isAncestorOf(that)) return current;
	    current = current.parent;
	}
	return null;
    }


    /**
     * Compute the lowest common ancestor between this leaf and "that"
     * The two nodes must belong to the same tree and must be leaves
     * @author   Li Zhang
     * 
     * @param    that A TreeNode in the Tree that this TreeNode belongs to
     * @return   the lowest common ancestor between this leaf and <code>that</code>, null if one of the nodes is not a leaf 
     */
    public TreeNode leafLca(TreeNode that) {


	if(!isLeaf()) return null;
	if(!that.isLeaf()) return null;
	TreeNode current = this;
	int a = that.getLindex();
	if(getLindex() > that.getLindex()) {
	    current = that;
	    a = getLindex();
	}
	for(;current!=null;current = current.parent) {
	    if(current.rightmostLeaf.getLindex()>=a)
		return current;
	}
	return null;
    }

    public void print() {
	if(name != null)
	    System.out.print("node name: " + name + "\t");
	else 
	    System.out.print("node name null,\t");
	System.out.println("key: " + key);
    }

    public void printSubtree(){

	print();
	
	for(int i=0; i< children.size(); i++)
	    getChild(i).printSubtree();
    }
       
    public void setSubtreeExtremeLeaves() {
	if(isLeaf()) {
	    leftmostLeaf = this;
	    rightmostLeaf = this;
	    return;
	}

	int i;
	for(i=0; i<children.size();i++) {
	    getChild(i).setSubtreeExtremeLeaves();
	}
	leftmostLeaf = firstChild().leftmostLeaf;
	rightmostLeaf = lastChild().rightmostLeaf;
    }

    
    void setSubtreeMinMax() {
	if(isLeaf()) {
	    min = key;
	    max = key;
	    return;
	}
	for(int i=0; i<children.size();i++) {
	    getChild(i).setSubtreeMinMax();
	    int childMin = getChild(i).min;
	    min = (childMin < min) ? childMin : min;
	    int childMax = getChild(i).max;
	    max = (childMax > max) ? childMax : max;
	}
    }

    /** set numberLeaves field for each subnode */
    int setSubtreeNumberLeaves()
    {
    	numberLeaves = 0;
    	if(isLeaf())
    		numberLeaves = 1; 
    	else
    		for(int i=0; i<children.size(); i++)
    			numberLeaves += getChild(i).setSubtreeNumberLeaves();
    	return numberLeaves;
    }
    
    public String toString()
    {
    	String edge[] = {edges[0]!=null?edges[0].toString():"X", edges[1]!=null?edges[1].toString():"Y"};
    	return name + "(" + key + " @ " + height + ")"+ edge[0] + "&" + edge[1];
    }
    
	public void setFontSize(int fs){ fontSize=fs;}
	   public int getFontSize(){ return fontSize;}
    
	   public boolean isInteriorNode() {
		   return children.size()>0?true:false;
	   }

    public void setBcnScore(float n){
    	bcnScore =new Double(n);
    }
    
    public Double getBcnScore(){
    	return bcnScore;
    }
    
    // where the horizontal line is drawn
    // this CAN'T be recursive, that would be too expensive
    public double getMidY()
    {
    	if (computedFrame >= cell.drawer.getFrameNum())
    		return midYPosition;
    	if (isLeaf())
    	{
    		midYPosition = getSize(AccordionDrawer.Y) * 0.5 + cell.getMin(AccordionDrawer.Y);
    	}
		else if (children.size() == 1)
		{
			midYPosition = ((TreeNode)children.get(0)).getMidY();
		}
		else
		{
    		// halfway between the offsets of end children:
    		TreeNode child0 = (TreeNode)children.get(0);
    		TreeNode childN = (TreeNode)children.get(children.size() - 1);
			midYPosition = (child0.cell.getMax(AccordionDrawer.Y) + childN.cell.getMin(AccordionDrawer.Y))/2;
		}
		computedFrame = cell.drawer.getFrameNum();
		return midYPosition;
    }
    
    // where the vertical line stops
    public double getMinY()
    {
    	if (isLeaf()) return -1.0; // no vertical line for leaf
    	return ((TreeNode)children.get(0)).getMidY();
    }

	// where the vertical line stops
	public double getMaxY()
	{
		if (isLeaf()) return -1.0; // no vertical line for leaf
		return ((TreeNode)children.get(children.size()-1)).getMidY();
	}
	
	public double getSize(int xy)
	{
		return cell.getMax(xy) - cell.getMin(xy);
	}
    
	// called on the root node only
    public TreeNode pickNode(double x, double y, double xFuzz, double yFuzz)
    {
    	if (isNodePicked(x, y, xFuzz, yFuzz))
    		return this; // picked this cell
    	if (!isLeaf() && // root == leaf
    			x > cell.getMax(AccordionDrawer.X) && // x too shallow, go deeper
    			xyInRange(y, 0.0, AccordionDrawer.Y)) // y is in range, go deeper, no fuzz
    		return pickDescend(x, y, xFuzz, yFuzz);
    	return null;
    }
    
    public boolean isNodePicked(double x, double y, double xFuzz, double yFuzz)
    {
		double min[] = {cell.getMin(AccordionDrawer.X), cell.getMin(AccordionDrawer.Y)};
		double max[] = {cell.getMax(AccordionDrawer.X), cell.getMax(AccordionDrawer.Y)};
    	double midY = getMidY(); // where to draw the horizontal line
    	return (x > max[AccordionDrawer.X] - xFuzz && x < max[AccordionDrawer.X] + xFuzz &&
    			y > min[AccordionDrawer.Y] - yFuzz && y < max[AccordionDrawer.Y] + yFuzz) ||
	    		(x > min[AccordionDrawer.X] - xFuzz && x < max[AccordionDrawer.X] + xFuzz &&
	    			y > midY - yFuzz && y < midY + yFuzz);
    }
    
    private boolean xyInRange(double value, double fuzz, int xy)
    {
    	return cell.getMin(xy) - fuzz <= value && cell.getMax(xy) + fuzz >= value;
    }

    // removed recursion
    // needs to be stack based for picking to left/right of large subtrees
    public TreeNode pickDescend(double x, double y, double xFuzz, double yFuzz)
    {
    	Stack pickingStack = new Stack();
    	pickingStack.push(this);
    	while (pickingStack.size() > 0)
    	{
    		TreeNode currRoot = (TreeNode)pickingStack.pop(); // next root to check
    		if (currRoot.isNodePicked(x, y, xFuzz, yFuzz))
    			return currRoot;
    		if (currRoot.isLeaf() || // unpicked leaf
    				!currRoot.xyInRange(y, yFuzz, AccordionDrawer.Y) || // bad Y value
    				currRoot.cell.getMin(AccordionDrawer.X) > x) // bad X value
    		{
    			continue;
    		}
    		// some child must have y in range
    		int minChild = 0;
    		int maxChild = currRoot.children.size() - 1;
    		int midChild = (minChild + maxChild + 1) / 2;
    		TreeNode currChild = (TreeNode)(currRoot.children.get(midChild));
    		while (minChild != maxChild && // converged to currChild, currChild is descended or picked
    				!currChild.xyInRange(y, 0.0, AccordionDrawer.Y)) // binary search in Y, no fuzz
    		{ // find appropriate child
    			if (currChild.cell.getMin(AccordionDrawer.Y) > y) // curr child is too big, max = mid
    				maxChild = midChild;
    			else
    				minChild = midChild;
    			if (minChild+1==maxChild && midChild==minChild)
    				midChild = maxChild;
    			else
    				midChild = (minChild + maxChild) / 2;
    			currChild = (TreeNode)(currRoot.children.get(midChild));
    		}
    		if (currChild.isNodePicked(x, y, xFuzz, yFuzz))
    		{
    			return currChild; // found something
    		}
    		if (midChild > 0)
    			pickingStack.push(currRoot.children.get(midChild-1));
    		if (midChild < currRoot.children.size()-1)
    			pickingStack.push(currRoot.children.get(midChild+1));
    		pickingStack.push(currChild); // the next root
    	}
    	return null;
    }

	// assuming this is a leaf, return the leaf index (the split position in Y direction, actually)
	public int getLindex()
	{
		if (cell == null)
			System.out.println("Error when finding Lindex for " + this);
		return cell.getMaxLine(AccordionDrawer.Y);
	}
	
	// don't draw self, just call this on parents after calling drawDescend
	// ascend drawing until the root is drawn or the node drew in the frame already
	public void drawAscend(int frameNum, float plane)
	{
		if (cell.getDrawnFrame() < frameNum)
		{
			drawInCell(cell.drawer.getColorsForCellGeom(this), plane);
			if (!isRoot())
				parent.drawAscend(frameNum, plane);
			cell.setDrawnFrame(frameNum);
		}
	}
	
	// don't draw self, just call this
	public void drawDescend(int frameNum, float plane, int min, int max)
	{
		drawInCell(cell.drawer.getColorsForCellGeom(this), plane);
		TreeNode currNode = this;
		// binary search
		int minChild = 0;
		int maxChild = currNode.children.size() - 1;
		int midChild = (minChild + maxChild) / 2;
		while (!currNode.isLeaf())
		{
			TreeNode midNode = currNode.getChild(midChild);
			if (midNode.key <= max && // mid node is either some tree above max or is an ancestor of max 
					midNode.rightmostLeaf.key >= min) // midnode has some leaf bigger than min 
			{
				midNode.drawInCell(cell.drawer.getColorsForCellGeom(midNode), plane);
				currNode = midNode;
				minChild = 0;
				maxChild = currNode.children.size() - 1;
			}
			else if (midNode.key <= max) // mid node too small, make it bigger
				minChild = midChild+1;
			else
				maxChild = midChild-1;
			midChild = (minChild + maxChild) / 2;
		}		
	}

	/* (non-Javadoc)
	 * @see AccordionDrawer.CellGeom#drawInCell(double)
	 */
	public void drawInCell(double plane, boolean doFlash) {
		// TODO Auto-generated method stub
		
	}
    
}