import java.io.*;
import java.lang.*;
import choco.ContradictionException;
import choco.Problem;
import choco.integer.*;
import java.util.Vector;
import choco.Constraint;

public class Tree {
    private Node root;
    private NodeVector interiorNodes;
    private NodeVector leaves;
    private int count;
    private Vector constraints;

    public Tree (String fname,Dict D) throws FileNotFoundException, IOException {
	interiorNodes = new NodeVector();
	leaves = new NodeVector();
	Node p = Node.readNode(fname,D,this);
	root = p;
	constraints = new Vector();
    }

    public Tree (){
	interiorNodes = new NodeVector();
	leaves = new NodeVector();
	root = null;
	count = 0;
	constraints = new Vector();
    }

    public String toString(){return root.toString() + ";";}
    public void addInteriorNode(Node p){interiorNodes.insertInDepthOrder(p);}
    public void addLeafNode(Node p){leaves.insertInSpeciesOrder(p);}
    public NodeVector getLeaves(){return leaves;}
    public NodeVector getInteriorNodes(){return interiorNodes;}
    public int noLeaves(){return leaves.size();}
    public void setRoot(Node N){root = N;}
    public int getCount(){return count;}
    public void incCount(){count++;}

    public void look(){
	NodeEnumeration e1 = interiorNodes.elements();
	while (e1.hasMoreElements()) System.out.println(e1.nextElement().look());
	NodeEnumeration e2 = leaves.elements();
	while (e2.hasMoreElements()) System.out.println(e2.nextElement().look());
    }
	
    public int getMaxDDate(){
	int m = -1;
	NodeEnumeration e = interiorNodes.elements();
	while (e.hasMoreElements()) m = Math.max(m,e.nextElement().getDivergenceDate());
	return m;
    }

     public void getRanks(UMatrix um) throws ContradictionException {
	NodeVector V = getLeaves();
	int n = V.size();
	for (int i=0;i<n-1;i++)
	    for (int j=i+1;j<n;j++){
		Node x = V.elementAt(i);
		Node y = V.elementAt(j);
		Node z = Node.mrca(x,y);
		IntDomainVar v = um.getM()[x.getSpeciesNo()][y.getSpeciesNo()];
		int dd = z.getDivergenceDate();
		//System.out.println(x.getSpecies() + " " + y.getSpecies() + " diverged " + dd);
		if (dd > 0) v.setVal(dd);
	    }
    }

    public void breakUp(UMatrix um) throws ContradictionException {
	//System.out.println("call breakup");
	NodeVector V = interiorNodes;
	int i=0;
	while (i<V.size()){// && V.get(i).getId() != 0){
	    Node v = V.get(i); // an interior node
	    //System.out.println(v.look());
	    if (v.degree() == 2 && v.getId() != 0) { // 2 kids and not the root -> make a triple
		Node p  = v.getParent(); 
		Node c1 = v.getChildren().get(0);
		Node c2 = v.getChildren().get(1);
		Node c3 = Node.getASiblingOf(c1);
		v.setSpecies(c2);
		v.clearChildren();
		// System.out.println("tri: " + "(" + c1.getSpecies() + "," + 
		//		   c2.getSpecies() + ")" + c3.getSpecies());
		triple(um,c1,c2,c3);
		i++;
	    }
	    else if (v.degree() > 2){// & v.getId() != 0) { // make a fan		
		Node c1 = v.getChildren().get(0);
		Node c2 = v.getChildren().get(1);
		for (int x=0;x<v.degree()-2;x++)
		    for (int y=x+1;y<v.degree()-1;y++)
			for (int z=y+1;z<v.degree();z++){
			    // System.out.println("fan: " + "(" + v.getChildren().get(x).getSpecies() + "," + 
			    //                                 v.getChildren().get(y).getSpecies() + "," + 
			    //		                       v.getChildren().get(z).getSpecies() + ")");
			    fan(um,v.getChildren().get(x),v.getChildren().get(y),v.getChildren().get(z));
			}
		v.clearChildren();
		v.getChildren().addElement(c1);
		v.getChildren().addElement(c2);
	    }
	    else i++;
	}
    }

    private void triple(UMatrix um,Node a,Node b,Node c) throws ContradictionException {
	Problem pb = um.getProblem();
	IntDomainVar [][] M = um.getM();
	int i = a.getSpeciesNo();
	int j = b.getSpeciesNo();
	int k = c.getSpeciesNo();
	//System.out.println("tri: (" + a.getSpecies() + "," + b.getSpecies() + ")" + c.getSpecies());
	constraints.add(new Triple(a,b,c,1));
	pb.post(pb.and(pb.eq(M[i][k],M[j][k]),pb.and(pb.gt(M[i][j],M[j][k]),pb.gt(M[i][j],M[i][k]))));
    }

    private void relaxedTriple(UMatrix um,Node a,Node b,Node c) throws ContradictionException {
	Problem pb = um.getProblem();
	IntDomainVar [][] M = um.getM();
	int i = a.getSpeciesNo();
	int j = b.getSpeciesNo();
	int k = c.getSpeciesNo();
	Constraint U1 = pb.and(pb.eq(M[i][k],M[j][k]),pb.and(pb.gt(M[i][j],M[j][k]),pb.gt(M[i][j],M[i][k])));
	Constraint U2 = pb.and(pb.eq(M[i][j],M[i][k]),pb.eq(M[i][k],M[j][k]));
	pb.post(pb.or(U1,U2));
    }

     private void fan(UMatrix um,Node a,Node b,Node c) throws ContradictionException{
	Problem pb = um.getProblem();
	IntDomainVar [][] M = um.getM();
	int i = a.getSpeciesNo();
	int j = b.getSpeciesNo();
	int k = c.getSpeciesNo();
	//System.out.println("fan: [" + a.getSpecies() + "," + b.getSpecies() + "," + c.getSpecies() + "]");
	constraints.add(new Triple(a,b,c,2));
	pb.post(pb.and(pb.eq(M[i][j],M[i][k]),pb.and(pb.eq(M[i][k],M[j][k]),pb.eq(M[i][j],M[j][k]))));
    }

    public static void compare(Tree t1,Tree t2){
	int n1 = (t1.constraints).size();
	int n2 = (t2.constraints).size();
	for (int i=0;i<n1;i++)
	    for (int j=0;j<n2;j++){
		Triple x = (Triple)((t1.constraints).get(i));
		Triple y = (Triple)((t2.constraints).get(j));
		if (Triple.sameSpeciesBug(x,y)) System.out.println(x + " " + y);
	    }
    }


    public static void main(String[] args) throws Exception {
	Dict d = new Dict();
	Tree t1 = new Tree("cats1.tre",d);
	//System.out.println(t1);
	Tree t2 = new Tree("cats2.tre",d);
	//System.out.println(t2);
	int n = d.size();
	System.out.println(n);
	for (int i=0;i<n;i++) System.out.println(d.elementAt(i));
	//t1.triples();
	//t2.triples();
	System.out.println("*** *** ***");
    }
}