import java.io.*;
import java.lang.*;
import choco.integer.*;

public class Node  {
    private int branchLength;
    private int divergenceDate;
    private int speciesNo;
    private Node parent;
    private NodeVector children;
    private String species;
    private String label;
    private int depth;
    private Tree tree;
    private int id;

    public Node() {children = new NodeVector();}

    public Node(int bl,int dd,String s,Node p,Dict D,Tree tree) {
	branchLength = bl;
	divergenceDate = dd;
	label = "" + dd;
	parent = p;
	id = tree.getCount();
	tree.incCount();
	if (p != null) {
	    p.children.addElement(this);
	    branchLength = dd - p.getDivergenceDate();
	    depth = p.depth + 1;}
	else depth = 0;
	this.tree = tree;
	if (s == "") {
	    children = new NodeVector();
	    tree.addInteriorNode(this);
	    speciesNo = -1;
	}
	else {
	    speciesNo = D.find(s);
	    children = null;
	    species = s;
	    label = s;
	    tree.addLeafNode(this);
	}
    }

    public Node(IntDomainVar dd,Node p,Tree tree) {
	divergenceDate = dd.getInf();
	id = tree.getCount();
	tree.incCount();
	if (dd.getSup() == divergenceDate) label = "" + divergenceDate;
	else label = dd.getInf() + ".." + dd.getSup();
	parent = p;
	if (p != null) {
	    p.children.addElement(this);
	    branchLength = dd.getInf() - p.getDivergenceDate();
	    depth = p.depth + 1;}
	else depth = 0;
	this.tree = tree;
	children = new NodeVector();
	tree.addInteriorNode(this);
	speciesNo = -1;
    }

    public Node leafNode(int dd,int speciesNo,Dict D,Tree tree) {
	return new Node(1,dd,D.elementAt(speciesNo),this,D,tree);
    }

    public Node interiorNode(int dd,Dict D,Tree tree) {
	if (divergenceDate == dd) return this;
	else return new Node(1,dd,"",this,D,tree);
    }

    public Node interiorNode(IntDomainVar dd,Tree tree) {
	if (divergenceDate == dd.getInf()) return this;
	else return new Node(dd,this,tree);
    }

    protected static int readInt(MyIo fin) throws IOException {
	char c = fin.getNextChar();
	int v = 0;
	while (Character.isDigit(c)){v = v * 10 + Character.digit(c,10);c = fin.getNextChar();}
	return v;
    }
       
    public static Node readNode(String fname,Dict D,Tree T) throws FileNotFoundException, IOException {
	MyIo fin = new MyIo(fname);
	Node N = new Node();
	int v = 0;
	fin.getNextChar();
	while (fin.getLastChar() != ';') {
	    if (fin.getLastChar() == '(') {N = new Node(-1,-1,"",N,D,T);fin.getNextChar();} // an interior node
	    else if (fin.getLastChar() == ')') {
		N.divergenceDate = readInt(fin);
		if (fin.getLastChar() == ':') N.branchLength = readInt(fin);
		else N.branchLength = -1;
		N = N.parent;
	    }
	    else if (Character.isLetter(fin.getLastChar())){
		String s = "";
		while (Character.isLetter(fin.getLastChar()) || fin.getLastChar() == '_')
		    {s = s + fin.getLastChar();fin.getNextChar();}
		new Node(readInt(fin),-1,s,N,D,T);
	    }
	    else fin.getNextChar();
	}
	fin.close();
	return N.children.elementAt(0);
    }
    

    public boolean isLeaf(){return children == null || children.isEmpty();}
    public boolean isRoot(){return parent == null;}
    public NodeVector getChildren(){return children;}
    public String getSpecies(){return species;}
    public int getSpeciesNo(){return speciesNo;}
    public int getDivergenceDate(){return divergenceDate;}
    public int degree(){return children.size();}
    public int getDepth(){return depth;}
    public int getId(){return id;}
    public Node getParent(){return parent;}
    public void setSpecies(Node v){species = v.species; speciesNo = v.speciesNo;}
    public void clearChildren(){children.clear();}

    public String look(){
	String s = "id: " + id + " Depth: " + depth + " Species: " + species + " DDate: " + divergenceDate +
	           " BLen: " + branchLength + " SpecNo: " + speciesNo + " children: ";
	if (!isLeaf()){
	    NodeEnumeration e = children.elements();
	    while (e.hasMoreElements()) s = s + e.nextElement().getId() + " ";
	}
	if (!isRoot()) s = s + " parent: " + parent.getId();
	return s;
    }

    //
    // ---------------------------------------------------------------
    //                    breakUp functions
    //

    public static Node getAChildOf(Node v){
	if (v.isLeaf()) return v;
	else return getAChildOf(v.children.get(0));
    }

    public static Node getASiblingOf(Node v){
	Node p  = v.parent;
	Node gp = p.parent;
	int i = 0;
	while (p == gp.children.get(i)) i++;
	return getAChildOf(gp.children.get(i));
    }
    /*
    public void breakUp(){
	NodeVector V = tree.getInteriorNodes();
	for (int i=0;i<V.size();i++){
	    Node v = V.get(i); // an interior node
	    //System.out.println(v.look());
	    if (v.degree() == 2 && v.id != 0) { // make a triple
		Node p = v.parent; 
		Node c1 = v.children.get(0);
		Node c2 = v.children.get(1);
		Node c3 = getASiblingOf(c1);
		v.species = c2.species;
		v.children = null;
		//System.out.println("tri: " + "(" + c1.species + "," + c2.species + ")" + c3.species);
	    }
	    else if (v.degree() > 2 & v.id != 0) { // make a fan
		Node cLast = v.children.get(v.degree()-1);
		for (int j=0;j<v.degree()-2;j++){
		    Node c1 = v.children.get(j);
		    Node c2 = v.children.get(j+1);
		    Node c3 = v.children.get(j+2);
		    //System.out.println("fan: " + "(" + c1.species + "," + c2.species + "," + c3.species + ")");
		}
		v.species = cLast.species;
		v.children = null;
	    }
	}
    }
    */
			
    //
    //
    // ---------------------------------------------------------------
    //
	
    /*
    public static Node mrca(Node n1,Node n2){
	if (n1.depth > n2.depth) return mrca(n1.parent,n2);
	else if (n1.depth < n2.depth) return mrca(n1,n2.parent);
	else if (n1.depth == n2.depth && n1.parent != n2.parent) return mrca(n1.parent,n2.parent);
	else return n1.parent;
    }
    */

     public static Node mrca(Node n1,Node n2){
	if (n1.depth > n2.depth) return mrca(n1.parent,n2);
	else if (n1.depth < n2.depth) return mrca(n1,n2.parent);
	else if (n1.depth == n2.depth && !(n1.equals(n2))) return mrca(n1.parent,n2.parent);
	else {
	    //System.out.println("MRCA: " + n1.look()); 
	    return n1;
	}
    }
	
	
    public String toString(){
	String s = "";
	if (isLeaf()) return label;
	else {int n = children.size();
	      s = "(";
	      for (int i = 0;i < n-1;i++) s = s + children.elementAt(i) + ",";
	      s = s + children.elementAt(n-1) + ")" + label; //divergenceDate;
	      return s;}
    }
    
    public static void main(String[] args) throws Exception {
	Dict d = new Dict();
	Tree r = new Tree();
	Node p = readNode("cats1.tre",d,r);
	System.out.println(p);
    }
}