tree.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.util.*;
import java.io.*;
import java.text.Collator;

import Parser.*;
import Parser.nexus.*;
import AccordionDrawer.OlduvaiObject;

/**
 * A public class representing a (phylognenetic) tree.
 * Nodes of the tree are of type TreeNode.
 * Nodes are traversed in pre- and post-orders.
 * 
 * @author  Yunhong Zhou, Li Zhang
 * @version 
 * @see     TreeNode
 * @see     Parser.Newick
 * @see     Parser.nexus.Nexus
 * @see     Parser.status.Status
 */

public class Tree extends Object implements OlduvaiObject {

	// array of all leaves, instead of pointers in TreeNode structure
	private TreeNode[] leaf;

    /** the parser responsible for parsing Newick format file, normally with a suffix nh */
    static Newick parser = new Newick(System.in);

    /** 
     * the parser responsible for parsing Nexus format file, normally with
     * a suffix nexus or nxs 
     */  
    static Nexus parser_nexus = new Nexus(System.in);

    /** The list of nodes of the tree indexed by their keys, indexed by key */ 
    public ArrayList nodes; 
    

    /** 
     * Most internal nodes don't have names. Do we assign a unique
     * name to each of them? No! each node has a key and the key is unique
     * for nodes. 
     */
    HashMap nodesByName; 

    /** total number of nodes for the tree */
    private int nodeCount;

    /** key should be unique for each tree, set by object that creates trees  */
    private int key;


    public Tree() {
	root = new TreeNode();
	nodes = new ArrayList();
	nodesByName = new HashMap();
    }

    // not used
    public Tree(String tn) {
	name = new String(tn);
	root = new TreeNode();
    }

    public Tree(TreeNode rn) {
	root = rn;
    }

    // copy a tree, for matrix mode
    // why not use clone?
    public Tree(Tree t) {
	nodes = new ArrayList();
	nodesByName = new HashMap();
	// we need to create nodes with these fields set: name,
	// weight, parent, children. also need to have root node. 
	// everything else is done in postProcess()
	// 
	// use temporary nodes array for storage of nodes already
	// created, indexed by same key as nodes arraylist in tree t. 
	// (which happens to be preorder). but - we're filling in this
	// temporary array through *postorder* traversal of tree, so
	// we know children created before parents.
	
	TreeNode arraytemp[] = new TreeNode[t.getSize()];
	for (TreeNode n = t.posorderStartNode; n != null; n = n.posorderNext) {
	    TreeNode myn = new TreeNode(n.getName(), n.getWeight());
	    arraytemp[n.getKey()] = myn;
	    for (int i = 0; i < n.numberChildren(); i++) {
		TreeNode nkid = (TreeNode)n.children.get(i);
		// addChild sets children and parent fields
		myn.addChild(arraytemp[nkid.getKey()]);
	    }
	}
	root = arraytemp[0]; // key is preorder
	postProcess();
    }


	/**
	 * clean up method, called when the tree is deleted
	 * @see TreeJuxtaposer.TreeJuxtaposer.deleteTree
	 * @see TreeNode.close
	 *
	 */   
		public void close(){
    	
					  TreeNode pren = root.leftmostLeaf;
		
					  for(TreeNode n = pren.preorderNext; n!=null; n=n.preorderNext) {
//						   n.cleanUp();
						   n.close();				 
						  }
//				  parser.close();
//				  parser_nexus = null;
				  nodes = null;
				  nodesByName = null;
//				  this = null;
				  System.out.println("clean tree");
    	
			  }
    
			  protected void finalize() throws Throwable {
		 
						   try {
//						       System.out.println("finalize?  what?");
							   close();
//							   System.out.println("finalized?  on what?");
						   }
						   finally {
							   super.finalize();     
							   System.out.println("finally clean a tree");
						   }
			   }


    /**
     * Reads a tree in file fname described in Newick format 
     * and initiate the tree object.
     * Function load reads in the file, call the newick parser to parse it,  
     * and do some post processing afterwards.
     * The tree object is originally empty. After calling the parser, it
     * generates all the nodes decedant to the root. For each node of the
     * tree, its name and edge weight will be set after parsing is
     * complete. If the node has no name (internal nodes) or weight (some
     * trees have no edge weight), then these fields will take the default value.
     *
     * @author   Yunhong Zhou
     * 
     * @param    fname The file name
     *
     * @see      Parser.Newick
     */


    public void load(String fname) {

	setName(fname);
	
	try{
	    FileInputStream in = new FileInputStream(fname);
	    Newick.ReInit(in);
	    parser.parseTree(this);	
	}catch(FileNotFoundException e){
	    System.out.println("Error! File " + fname + " not found!");
	    System.exit(1); 
	};	

	postProcess();
    }


    /**
     * Reads a tree with giving index in a file fname with Nexus format 
     * and initiates the Tree object.
     * Function load_nexus reads in the file, call the nexus parser to
     * parse it, and do some post processing afterwards.
     * The tree object is originally empty. After calling the parser, it
     * generates all the nodes decedant to the root. For each node of the
     * tree, its name and edge weight will be set after parsing is
     * complete. If the node has no name (internal nodes) or weight (some
     * trees have no edge weight), then these fields will take the default
     * value.
     *
     * @author   Yunhong Zhou
     * 
     * @param    fname The file name
     * @param    index Index of the tree in the nexus file
     *
     * @see      Parser.nexus.Nexus
     */


    public void load_nexus(String fname, int index){
        
	setName(fname);
	number = index;
	try{
	    FileInputStream in = new FileInputStream(fname);
	    Nexus.ReInit(in);
	    parser_nexus.parseTree(this, index);
	    in = null;
	    System.gc();
	}catch(FileNotFoundException e){
	    System.out.println("Error! File " + fname + " not found!");
	    System.exit(1); 
	};	

	postProcess();	
    }

	// TODO: never called
    /**
     * @author Serdar Tasiran
     */		
    int getGapDistanceFromLeaves(TreeNode n1, TreeNode n2) {
	
	TreeNode lcaNode = n1.lca(n2);
	TreeNode n1Trace = n1;
	TreeNode n2Trace = n2;

	while (n1Trace.parent != lcaNode) {
	    n1Trace = n1Trace.parent;
	}

	while (n2Trace.parent != lcaNode) {
	    n2Trace = n2Trace.parent;
	}

	int num1 = n1Trace.getLeafCount();
	int num2 = n2Trace.getLeafCount();
	int geomMean = (int) Math.sqrt(num1*num2);

	double k = 0.01;
	double denom = leaf.length * k;

	return (int) (
		      0.5 * denom *
		      Math.log(1 + (geomMean/denom))
		      );

    }

    int getLCADistanceFromLeaves(TreeNode n1, TreeNode n2) {
	
	TreeNode lcaNode = n1.lca(n2);
	TreeNode n = n1;
	int distance = 0;

	while (n != lcaNode) {
	    distance++;
	    n = n.parent;
	}
	return distance; 
    }

    int getInteriorCount() { return nodeCount - leaf.length;}
    int getTotalNodeCount() { return nodeCount;}

    public TreeNode getNodeByKey(int key){ if (key >= nodes.size()) return null; return (TreeNode) nodes.get(key);}
    public TreeNode getNodeByName(String s){ 
	return (TreeNode) nodesByName.get(s);
    }
    
    private int height = 0;
    int getHeight() { return height; }

    public void setKey(int i) {key = i;}
    public int getKey() {return key;}
    public String getName() {return name;}
    public int getSize() {return nodeCount;}
    public TreeNode getLeftmostLeaf() { return root.leftmostLeaf; }
    public TreeNode getRightmostLeaf() { return root.rightmostLeaf; }
    public TreeNode getRoot() { return root;}

    String name = null; // the filename
    int number = 0; // the number (>0 for nexus, appended to nexus filename)
    TreeNode root=null;

//    /** the number of leave nodes */
//    private int leafCount; 

    /** the start node for preorder list of all the nodes */
    public TreeNode preorderStartNode;

    /** the start node for postorder list of all the nodes */