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

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

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

    public Tree (){
	interiorNodes = new NodeVector();
	leaves = new NodeVector();
	root = new Node();
	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 Node getRoot(){return root;}
    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 breakUp(Vector triples,Vector fans) 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());
		triples.add(triple(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() + ")");
			    fans.add(fan(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 Triple triple(Node a,Node b,Node c) throws ContradictionException {
	int i = a.getSpeciesNo();
	int j = b.getSpeciesNo();
	int k = c.getSpeciesNo();
	//System.out.println("tri: (" + a.getSpecies() + "," + b.getSpecies() + ")" + c.getSpecies());
	return new Triple(a,b,c,1);
    }

     private Triple fan(Node a,Node b,Node c) throws ContradictionException {
	int i = a.getSpeciesNo();
	int j = b.getSpeciesNo();
	int k = c.getSpeciesNo();
	//System.out.println("fan: [" + a.getSpecies() + "," + b.getSpecies() + "," + c.getSpecies() + "]");
	return new Triple(a,b,c,2);
    }
    
    public static void OneTree(Vector triples,Vector fans,Node v,Dict d,Tree T) throws Exception {
	int n = d.size();
	Vector species = new Vector();
	for (int i=0;i<n;i++) species.add(new Integer(i));
	OneTree(triples,fans,species,v,d,T);
    }
    
    private static void OneTree(Vector triples,Vector fans,Vector species,Node v,Dict d,Tree T) throws Exception {
	//System.out.println("CALL OneTree");
	//System.out.println(species);
	//System.out.print("triples: ");
	//for (int i=0;i<triples.size();i++) System.out.print(((Triple)triples.get(i)).look());
	//System.out.println();
	//System.out.print("fans:    ");
	//for (int i=0;i<fans.size();i++) System.out.print(((Triple)fans.get(i)).look());
	//System.out.println();
	//System.out.println("--------------------------");
	if (species.size() == 1) {
	    v.setSpecies((Integer)species.get(0),d);
	    //System.out.println("species: " + v.getSpecies());
	}
	else if (species.size() == 2){
	    String s0 = getSpecies((Integer)species.get(0),d);
	    String s1 = getSpecies((Integer)species.get(1),d);
	    //System.out.println("species: " + s0 + " " + s1);
	    Node v1 = new Node(1,1,s0,v,d,T);
	    Node v2 = new Node(1,1,s1,v,d,T);	
	}
	else{	    
	    Vector S = new Vector();
	    for (int i=0;i<species.size();i++){
		Vector s = new Vector();
		s.add(species.get(i));
		S.add(s);
	    }
	    //for (int i=0;i<S.size();i++) System.out.print(S.get(i));
	    //System.out.println();
	    //for (int i=0;i<triples.size();i++) System.out.println(((Triple)triples.get(i)).look());
	    for (int i=0;i<triples.size();i++){
		Triple t = (Triple)triples.get(i);
		int j = find(t.getA(),S);
		int k = find(t.getB(),S);
		if (j != k){
		    merge((Vector)S.get(j),(Vector)S.get(k));
		    S.remove(k);
		}
	    }
	    //for (int i=0;i<S.size();i++) System.out.print(S.get(i));
	    //System.out.println();
	    //for (int i=0;i<fans.size();i++) System.out.println(((Triple)fans.get(i)).look());
	    for (int i=0;i<fans.size();i++){
		Triple f = (Triple)fans.get(i);
		int j = find2(f,S);
		int k = findNextAny(j,f,S);
		if (k>=0){
		    merge((Vector)S.get(j),(Vector)S.get(k));
		    S.remove(k);
		}
	    }
	    if (S.size() == 1) throw new Exception(); // System.out.println("FAIL");
	    //for (int i=0;i<S.size();i++) System.out.print(S.get(i));
	    //System.out.println();
	    for (int i=0;i<S.size();i++){
		Vector s = (Vector)S.get(i);
		Vector newTriples = new Vector();
		for (int j=0;j<triples.size();j++){
		    Triple t = (Triple)triples.get(j);
		    if (allPresent(t,s)) newTriples.add(t);
		}
		Vector newFans = new Vector();
		for (int j=0;j<fans.size();j++){
		    Triple t = (Triple)fans.get(j);
		    if (allPresent(t,s)) newFans.add(t);
		}
		Node newV = new Node(1,1,"",v,d,T);
		OneTree(newTriples,newFans,s,newV,d,T);
	    }
	}
    }

    private static void merge(Vector s1,Vector s2){
	for (int i=0;i<s2.size();i++){
	    if (!s1.contains(s2.get(i)))
		s1.add(s2.get(i));
	}
    }
    //
    // merge the two sets of Integers
    //

    private static int find(int x,Vector S){
	int loc = -1;
	Integer j = new Integer(x);
	for (int i=0;i<S.size() && loc<0;i++){
	    Vector s = (Vector)S.get(i);
	    if (s.contains(j)) loc = i;
	}
	return loc;
    }
    //
    // S is a set of sets of Integer. 
    // return the index of the set S_i that contains Integer(x)
    //

    private static int findNextAny(int w,Triple t,Vector S){
	int loc = -1;
	if (w >= 0){
	    Integer j = new Integer(t.getA());
	    Integer k = new Integer(t.getB());
	    Integer l = new Integer(t.getC());
	    for (int i=0;i<S.size() && loc<0;i++){
		Vector s = (Vector)S.get(i);
		if ((s.contains(j) || s.contains(k) || s.contains(l)) && i != w) loc = i;
	    }
	}
	return loc;
    }
    //
    // Find the index of a set in S that contains any one of x, y or z
    //

    private static boolean anyPresent(Triple t,Vector s){
	Integer j = new Integer(t.getA());
	Integer k = new Integer(t.getB());
	Integer l = new Integer(t.getC());
	return (s.contains(j) || s.contains(k) || s.contains(l));
    }
    
    private static boolean allPresent(Triple t,Vector s){
	Integer j = new Integer(t.getA());
	Integer k = new Integer(t.getB());
	Integer l = new Integer(t.getC());
	return (s.contains(j) && s.contains(k) && s.contains(l));
    }

    private static int find2(Triple t,Vector S){
	int loc = -1;
	Integer j = new Integer(t.getA());
	Integer k = new Integer(t.getB());
	Integer l = new Integer(t.getC());
	for (int i=0;i<S.size() && loc<0;i++){
	    Vector s = (Vector)S.get(i);
	    if ((s.contains(j) && s.contains(k)) ||
		(s.contains(j) && s.contains(l)) ||
		(s.contains(k) && s.contains(l))) loc = i;
	}
	return loc;
    }
    //
    // Find the index of a set in vector S that contains x and y, or x and z, or y and z
    //

    private static String getSpecies(Integer i,Dict d){
	int j = i.intValue();
	return (String)d.get(j);
    }
	
}