tree.java

生物物种进化历程的演示

    public TreeNode posorderStartNode;

    void setRoot(TreeNode rn){
	root = rn;
    }

    void setName(String tn) {
	name = new String(tn);
    }

    void printName() {
	if(name != null)
	    System.out.println("Tree Name: " + name);
    }

    public int getLeafCount() {
	return leaf.length;
    }

    /**
     * Post processing includes computing size of each node, 
     * linking nodes in different order, etc.
     * Sets left and right-most leaves of the tree
     * Computes and stores pre- and post-orders for leaves
     * can't do minmax until after linkNodesInPreorder is called 
     * to set index values! 	
     * @author  Li Zhang, Yunhong Zhou
     *
     * @see     TreeNode
     */

    public void postProcess() {
	
	root.setSubtreeExtremeLeaves();
	root.setSubtreeNumberLeaves();
	linkNodesInPreorder();  // this sets the hashmap with all node names from original 
	linkNodesInPosorder();
	linkLeaves();

	root.setSubtreeMinMax();
    }

    /**
     * 
     * Traverses the tree in pre-order, stores the ordering in the preorderNext field of TreeNodes
     * Sets nodecount for the tree
     * @author  Li Zhang, Yunhong Zhou
     *
     * @see     TreeNode
     */

    private void linkNodesInPreorder() {
	
	// munge names here, names become fully qualified, labels are what names were
	final char separator = '/'; // separator between name fields
	// arbitrary seen by users in search, no parsing on this is required later
	  
	preorderStartNode = root;
	linkSubtreeNodesInPreorder(root);
	int index = 0;
	height = 1;
	for(TreeNode n = preorderStartNode; n != null; n = n.preorderNext) {
		
		n.label = n.name;
		if (AccordionTreeDrawer.fullyQualified && n.parent != null)
				n.name = n.parent.name + separator + n.name;
	    n.key = index++;
	    nodes.add(n);
	    if(n.name.length() > 0) {
		// don't put an empty string in the
		// hash table
	    	nodesByName.put(n.name, n);
	    }
	    n.height = (null != n.parent) ? n.parent.height+1 : 1;
	    height = (n.height > height) ? n.height : height;
	}
	nodeCount = index;
    }

    /**
     * 
     * Traverses the subtree rooted at TreeNode n in pre-order, stores the
     * ordering in the preorderNext field of TreeNodes. 
     * @author  Li Zhang, Yunhong Zhou
     * @param   n the root of the subtree
     *
     * @see     TreeNode
     */

    private void linkSubtreeNodesInPreorder(TreeNode n) {

	if(n.isLeaf()) return;
	for(int i=0; i<n.numberChildren(); i++) {
	    linkSubtreeNodesInPreorder(n.getChild(i));
	}

	n.preorderNext = n.firstChild();
	for(int i=0; i<n.numberChildren()-1; i++) {
	    n.getChild(i).rightmostLeaf.preorderNext = n.getChild(i+1);
	}
	n.rightmostLeaf.preorderNext = null;
    }


    /**
     * Traverses the tree in pos-order, stores the ordering in the posorderNext field of TreeNodes
     * @author  Li Zhang, Yunhong Zhou
     *
     * @see     TreeNode
     */
    
    private void linkNodesInPosorder() {
	
	posorderStartNode = root.leftmostLeaf;
	linkSubtreeNodesInPosorder(root);
    }

    /**
     * 
     * Traverses the subtree rooted at TreeNode n in post-order, stores the
     * ordering in the posorderNext field of TreeNodes. 
     * @author  Li Zhang
     * @param   n the root of the subtree
     *
     * @see     TreeNode
     */

    private void linkSubtreeNodesInPosorder(TreeNode n) {

	if(n.isLeaf()) return;
	for(int i=0; i<n.numberChildren(); i++) {
	    linkSubtreeNodesInPosorder(n.getChild(i));
	}
	n.posorderNext = null;
	for(int i=0; i<n.numberChildren()-1; i++) {
	    n.getChild(i).posorderNext = n.getChild(i+1).leftmostLeaf;
	}
	n.lastChild().posorderNext = n;
    }


    /**
     * 
     * Links leaves of the tree in pre-order
     * check to see whether leaves have distinct names
     * if leaves have the same name, add a suffix index separated by ":"
     *
     * @author  Li Zhang, Yunhong Zhou
     * 
     * @see     #linkNodesInPreorder()
     * @see     TreeNode
     * @see     NameComparator
     */

    private void linkLeaves() {
	
	TreeNode pren = root.leftmostLeaf;
	Vector leaves = new Vector();
	leaves.add(pren);
//	pren.lindex = 0;
	for(TreeNode n = pren.preorderNext; n!=null; n=n.preorderNext)
	{
	    if(n.isLeaf())
	    {
	    	leaves.add(n);
	    }
	}

	leaf = (TreeNode[])leaves.toArray(new TreeNode[leaves.size()]);
	

	NameComparator myNameComparator = new NameComparator();
	TreeNode[] sortedLeafArray = (TreeNode[])leaves.toArray(new TreeNode[leaves.size()]);
	Arrays.sort(sortedLeafArray, myNameComparator);
	StringBuffer sb;
	int index = 0;
	TreeNode curr = sortedLeafArray[0];
	TreeNode next;
	for(int i=0; i<leaves.size()-1; i++){
		next = sortedLeafArray[i+1]; // only 1 index lookup per iteration
		boolean compare = myNameComparator.compare(curr, next) == 0; 
	    if (compare || index > 0)
	    {
	    	String name = curr.getName();
	    	nodesByName.remove(curr); // before all nodes with
	    	// same name were being ignored in search and comparing two identically named
	    	// leaves was broken, much fewer differences in trees with many leaves that
	    	// have the same name (imagine: all index.html occurences being marked as
	    	// different since numbering convention doesn't string match the original node name)
			curr.setName(name+ " " + index); //sb.toString());
			nodesByName.put(name+ " " + index, curr);//sortedLeafArray[i].getName(), sortedLeafArray[i]); // add the node back with number convention
			if (!compare)
				index = 0;
			else
				index++;
	    }
	    curr = next;
	}
	
    }


    public void printLeaves()
    {
    	for (int i = 0; i < leaf.length; i++)
    		leaf[i].print();
    }

	// return a "bin" for setting font size based on number of leaves in tree
	// bin is count of tree size ranges (logarithmic) for a specific font size
	// floor of result is <= leaf count for tree, +1 for > leaf count 
	public int computeBin(int fontRange)
	{
		return (int)Math.floor(Math.exp(Math.log((double)nodeCount) / (double)fontRange)) + 1;
	}

	// recalculate font size for each node based on number of subtree nodes
	// font size is min size + (some number n < font range)
	// where the number n is determined by the logarithmic base of the number determined by computeBin
	// this isn't done too often (usually) so it helps to cache it for every node when font sizes are changed
	public void setNodeFontSize(int maxFontSize, int minFontSize)
	{
		if(getInteriorCount() > 0){ // ?? the only "tree" that fails this is a single node...
			int fontRange = maxFontSize - minFontSize + 1;
			double maxValue = Math.log(nodeCount) / fontRange; // biggest "subtree" is the whole tree
			Iterator iter = nodes.iterator();
			while (iter.hasNext())
			{
				TreeNode currNode = (TreeNode)iter.next();
				int fontSize = minFontSize;
				if (fontRange > 1 && !currNode.isLeaf())
					fontSize = (int)(Math.log(currNode.getMax() - currNode.key) / maxValue) + minFontSize;
					// log base num bins of number of leaves in subtree + min font size 
				currNode.setFontSize(fontSize);
			}
		}
	}
	
	public TreeNode getLeaf(int index)
	{
		if (index >= 0 && index < leaf.length)
			return leaf[index];
		return null;
	}

	/* (non-Javadoc)
	 * @see AccordionDrawer.OlduvaiObject#getMinObjectKey()
	 */
	public int getMinObjectKey() {
		// TODO Auto-generated method stub
		return 0;
	}

	/* (non-Javadoc)
	 * @see AccordionDrawer.OlduvaiObject#getMaxObjectKey()
	 */
	public int getMaxObjectKey() {
		// TODO Auto-generated method stub
		return 0;
	}

	/* (non-Javadoc)
	 * @see AccordionDrawer.OlduvaiObject#getMinObjectValue()
	 */
	public float getMinObjectValue() {
		// TODO Auto-generated method stub
		return 0;
	}

	/* (non-Javadoc)
	 * @see AccordionDrawer.OlduvaiObject#getMaxObjectValue()
	 */
	public float getMaxObjectValue() {
		// TODO Auto-generated method stub
		return 0;
	}

	/* (non-Javadoc)
	 * @see AccordionDrawer.OlduvaiObject#getObjectKeyAt(int)
	 */
	public int getObjectKeyAt(int i) {
		// TODO Auto-generated method stub
		return 0;
	}

	/* (non-Javadoc)
	 * @see AccordionDrawer.OlduvaiObject#getObjectValueAt(int)
	 */
	public float getObjectValueAt(int i) {
		// TODO Auto-generated method stub
		return 0;
	}

	/* (non-Javadoc)
	 * @see AccordionDrawer.OlduvaiObject#getObjects()
	 */
	public ArrayList getObjects() {
		// TODO Auto-generated method stub
		return null;
	}
	
    /**
     * @return Returns the number.
     */
    public int getNumber()
    {
        return number;
    }
}


class NameComparator implements Comparator{
    Collator myCollator = Collator.getInstance(Locale.US);

    public int compare(Object o1, Object o2){
	String s1 = ((TreeNode)o1).getName();
	String s2 = ((TreeNode)o2).getName();
	return myCollator.compare(s1, s2);
    }
    
}