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 String name;

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

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

    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 int height(){return root.height();}
    public String getName(){return name;}
    public boolean equals(Tree t){return name.equals(t.getName());}

    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);
	    }
    }

    private void predates(UMatrix um,Node a,Node b,Node c,Node d) throws ContradictionException {
	Problem pb = um.getProblem();
	IntDomainVar [][] M = um.getM();
	int i = a.getSpeciesNo();
	int j = b.getSpeciesNo();
	int k = c.getSpeciesNo();
	int l = c.getSpeciesNo();
	//System.out.println("tri: (" + a.getSpecies() + "," + b.getSpecies() + ")" + c.getSpecies());
	//um.addTriple(new Triple(a,b,c,1));
	pb.post(pb.lt(M[i][j],M[k][l]));
    }
    //
    // div(a,b) < div(c,d)
    //

    public void toUMatrix(UMatrix um) throws ContradictionException {
	NodeVector V = getLeaves();
	int n = V.size();
	Problem pb = um.getProblem();
	IntDomainVar [][] M = um.getM();
	int x;
	//System.out.println("******************************");
	//look();
	//System.out.println("********************************");
	for (int i=0;i<n-2;i++)
	    for (int j=i+1;j<n-1;j++)
		for (int k=j+1;k<n;k++){
		    Node a = V.elementAt(i);
		    Node b = V.elementAt(j);
		    Node c = V.elementAt(k);
		    Node ab = Node.mrca(a,b);
		    Node ac = Node.mrca(a,c);
		    Node bc = Node.mrca(b,c);
		    //um.addTriple(new Triple(a,b,c,1,um));
		    if (ab == ac && bc.getDepth() > ab.getDepth()) um.addTriple(new Triple(b,c,a,1,um));
		    if (ab == bc && ac.getDepth() > ab.getDepth()) um.addTriple(new Triple(a,c,b,1,um));
		    if (ac == bc && ab.getDepth() > ac.getDepth()) um.addTriple(new Triple(a,b,c,1,um));
		    if (ab == ac && ac == bc) um.addTriple(new Triple(a,b,c,2,um));
		}
    }
    //
    // determine the values that the decision variables CANNOT have
    //
    // This whole thing is flawed!
    //


    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());
		um.addTriple(new Triple(c1,c2,c3,1,um));
		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() + ")");
			    um.addTriple(new Triple(v.getChildren().get(x),
						    v.getChildren().get(y),
						    v.getChildren().get(z),2,um));
			}
		v.clearChildren();
		v.getChildren().addElement(c1);
		v.getChildren().addElement(c2);
	    }
	    else i++;
	}
    }

    public void softBreakUp(UMatrix um) throws ContradictionException {
	//System.out.println("call softBreakUp");
	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());
	    Node c1 = v.getChildren().get(0);
	    Node c2 = v.getChildren().get(1);
	    Node c3 = Node.getASiblingOf(c1);
	    Triple t = new Triple(c1,c2,c3,1,um);
	    //System.out.println(t);
	    if (v.degree() == 2){
		v.setSpecies(c2);
		v.clearChildren();
		um.addTriple(t);
		i++;
	    }
	    else {
		(v.getChildren()).remove(c1);
		um.addTriple(t);
	    }
	}
    }

    public void XbreakUp(UMatrix um) throws ContradictionException {
	NodeVector V = getLeaves();
	int n = V.size();
	Problem pb = um.getProblem();
	IntDomainVar [][] M = um.getM();
	int x;
	//System.out.println("******************************");
	//look();
	//System.out.println("********************************");
	for (int i=0;i<n-2;i++)
	    for (int j=i+1;j<n-1;j++)
		for (int k=j+1;k<n;k++){
		    Node a = V.elementAt(i);
		    Node b = V.elementAt(j);
		    Node c = V.elementAt(k);
		    Node ab = Node.mrca(a,b);
		    Node ac = Node.mrca(a,c);
		    Node bc = Node.mrca(b,c);
		    if (ab == ac && bc.getDepth() > ab.getDepth()) um.addTriple(new Triple(b,c,a,1,um));
		    if (ab == bc && ac.getDepth() > ab.getDepth()) um.addTriple(new Triple(a,c,b,1,um));
		    if (ac == bc && ab.getDepth() > ac.getDepth()) um.addTriple(new Triple(a,b,c,1,um));
		    if (ab == ac && ac == bc) um.addTriple(new Triple(a,b,c,2,um));
		}
    }

    public void softXbreakUp(UMatrix um) throws ContradictionException {
	NodeVector V = getLeaves();
	int n = V.size();
	Problem pb = um.getProblem();
	IntDomainVar [][] M = um.getM();
	int x;
	//System.out.println("******************************");
	//look();
	//System.out.println("********************************");
	for (int i=0;i<n-2;i++)
	    for (int j=i+1;j<n-1;j++)
		for (int k=j+1;k<n;k++){
		    Node a = V.elementAt(i);
		    Node b = V.elementAt(j);
		    Node c = V.elementAt(k);
		    Node ab = Node.mrca(a,b);
		    Node ac = Node.mrca(a,c);
		    Node bc = Node.mrca(b,c);
		    if (ab == ac && bc.getDepth() > ab.getDepth()) um.addTriple(new Triple(b,c,a,1,um));
		    if (ab == bc && ac.getDepth() > ab.getDepth()) um.addTriple(new Triple(a,c,b,1,um));
		    if (ac == bc && ab.getDepth() > ac.getDepth()) um.addTriple(new Triple(a,b,c,1,um));
		    //if (ab == ac && ac == bc) um.addTriple(new Triple(a,b,c,2,um));
		}
    }

    /*
    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());
	um.addTriple(new Triple(a,b,c,1,um));
	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() + "]");
	um.addTriple(new Triple(a,b,c,2,um));
	//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 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("*** *** ***");
    }
}