package road;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;

import partition.Partition;

/**
 * @author beal
 *
 */
public class Quotient {
    private final DeterministicAutomaton g;
    private final Partition p;
    private final List<NodeData> data;
    private final NonDeterministicAutomaton inv; // inverse of the quotient
    private int maxLevel;  // maximal level
    private int maxLevelNumber; // number of nodes of maximal level
    private List<Integer> maxRootList; // list of roots of maximal trees
    
	public Quotient(DeterministicAutomaton g, Partition p) {
		this.g = g;
		this.p = p;
		data = new ArrayList<NodeData>();
		for (int i = 0; i < g.size(); i++) {
			data.add(new NodeData());
			data.get(i).setMaxPredList(new ArrayList<IntPair>());
		}
		inv = new ImpNonDetAutomaton(g.size(),g.arity());
	}

	public Partition getPartition() {
		return p;
	}
	public DeterministicAutomaton getG() {
		return g;
	}
	public NonDeterministicAutomaton getInv() {
		return inv;
	}
	public List<NodeData> getData() {
		return data;
	}
	public NodeData getData(int x) {
		return data.get(x);
	}
	public int getMaxLevel() {
		return maxLevel;
	}
	
	public void setMaxLevel(int maxLevel) {
		this.maxLevel = maxLevel;
	}
	
	public int size () {
		return p.classNumber();
	}
	
	@Override
	public String toString() {
	   StringBuilder sb = new StringBuilder();
	   sb.append(g.toString());
	   sb.append(p.toString());
	   sb.append("Level\n");
	   for (int i = 0; i < g.size(); i++) {
		   if (i == p.find(i)){
			   sb.append(String.format("%4d",i));
		   }
   	   }
	   sb.append("\n");
	   for (int i = 0; i < g.size(); i++) {
		   if (i == p.find(i)){
			   sb.append(String.format("%4d",data.get(i).getLevel()));
		   }
   	   }
	   sb.append("\nRoot\n");
	   for (int i = 0; i < g.size(); i++) {
		   if (i == p.find(i)){
			   sb.append(String.format("%4d",i));
		   }
   	   }
	   sb.append("\n");
	   for (int i = 0; i < g.size(); i++) {
		   if (i == p.find(i)){
			   sb.append(String.format("%4d",data.get(i).getRoot()));
		   }
   	   }
	   sb.append("\nPred\n");
	   for (int i = 0; i < g.size(); i++) {
		   if (i == p.find(i)){
			   sb.append(String.format("%4d",i));
		   }
   	   }
	   sb.append("\n");
	   for (int i = 0; i < g.size(); i++) {
		   if (i == p.find(i)){
			   sb.append(String.format("%4d",data.get(i).getPred()));
		   }
   	   }
	   sb.append("\nS\n");
	   for (int i = 0; i < g.size(); i++) {
		   if (i == p.find(i)){
			   sb.append(String.format("%4d",i));
		   }
   	   }
	   sb.append("\n");
	   for (int i = 0; i < g.size(); i++) {
		   if (i == p.find(i)){
			   sb.append(String.format("%4d",data.get(i).getS()));
		   }
   	   }
	   return sb.toString();
	}
	
	
	// 0(1)
	public int edgeQuotient(int x, int c) {
		if (p.find(x) != x) throw new IllegalArgumentException();
		return p.find(g.edge(x,c));
	}
	
    public void merge(int x, int y){
        //System.out.print(x); System.out.println(y);
    	int lx = p.find(x);
    	int ly = p.find(y);
    	if (lx != ly)  {
    		p.union(lx,ly);
    		for (int c = 0; c < g.arity(); c++) {
    			merge(g.edge(lx,c),g.edge(ly,c));
    		}
    	}
    }
   
    // O(n)
    // respect the order 
    public void update() {
    	computeNodeData(); // computes root, level, length (r), pred (r)
    	computeMax(); // computes maxLevel, maxLevelNumber, IsMaxRoot, maxRootList, maxNodeNumber
    	computeInv(); // computes the inverse of the quotient
    	computeS();  // computes the node s of any node of positive level
       // preliminaryStep()  computes maxPredList (r max)
    }
  
    ////////////////////////  UPDATING ///////////////////////
    // inverse of the quotient
    // O(n)
    private void computeInv() {
    	for (int c = 0; c < g.arity(); c++) {
			for (int x= 0; x < g.size(); x++) {
				inv.getEdges().get(c).set(x, new ArrayList<Integer>()); 
			}
    	}
		for (int c = 0; c < g.arity(); c++) {
			for (int x= 0; x < g.size(); x++) {
				if (x == p.find(x)){
					inv.getEdges().get(c).get(edgeQuotient(x,c)).add(x);
				}
			}
		}
    }

    // O(n)
    private void computeMax() {
    	maxLevelNumber = 0;
    	maxLevel = 0;
    	maxRootList = new ArrayList<Integer>(); 
    	for (int x = 0; x < g.size(); x++) {
    		data.get(x).setIsMaxRoot(false);
    		data.get(x).setMaxNodeNumber(0);
    		data.get(x).setHeight(0);
    		if (x == p.find(x)) {
    		    maxLevel = Math.max(maxLevel,data.get(x).getLevel());
    		}
    	}
    	for (int x = 0; x < g.size(); x++) {
    		if (x == p.find(x)) {
    			int r = p.find(data.get(x).getRoot());
    			int h = Math.max(data.get(r).getHeight(),data.get(x).getLevel());
    			data.get(r).setHeight(h);
    		}
    	}
    	for (int x = 0; x < g.size(); x++) {
    		if ((x == p.find(x)) && (data.get(x).getLevel()== maxLevel)){
    			int r = p.find(data.get(x).getRoot());
    			data.get(r).setMaxNodeNumber(data.get(r).getMaxNodeNumber()+1);
    			if (data.get(r).getIsMaxRoot() == false) {
    				data.get(r).setIsMaxRoot(true);
        			maxLevelNumber ++;
        			maxRootList.add(r);
    			}
    		}
    	}
    }
	// depth first search of the quotient which computes the data for each vertex
	// O(n)
    private void computeNodeData() {
        int n = g.size();
        int[] marque = new int[n];
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; i++) {
        	marque[i] = 0;
        }
        for (int i = 0; i < n; i++) {
        	int x = p.find(i);
        	if (marque[x] == 0) {
        		explore(x, marque, stack);
        	}
        }
	 }
	 
    
	
	private void explore(int i, int[] marque, Deque<Integer> stack) {
		 marque[i] = 1; 
		 stack.addFirst(i);
		 int j = edgeQuotient(i,0);
		 if (marque[j] == 0) {
			explore(j, marque, stack);
			if (marque[i] != 3) {
			// root[i] <--- root[j] 
			data.get(i).setRoot(data.get(j).getRoot());
			// level[i] <--- level[j]+1 
			data.get(i).setLevel(data.get(j).getLevel()+1);
			}
		 } else {
			 if (marque[j] == 1) {
				 int x = stack.getFirst(); // it is the node i
				 data.get(j).setPred(x);
				 List<Integer> cycle = new ArrayList<Integer>();
				 while (x != j) {
					 cycle.add(x);
					 data.get(x).setLevel(0);
					 data.get(x).setRoot(x);
					 int next = x;
					 marque[x] = 3; 
					 stack.removeFirst();
					 x = stack.getFirst();
					 data.get(next).setPred(x);
				 }
				 cycle.add(j);
				 data.get(j).setLevel(0);
				 data.get(j).setRoot(j);
				 marque[j] = 3; 
				 stack.removeFirst();
				 for (int r :cycle) {
					 data.get(r).setLength(cycle.size());
				 }
			 } else { 
				// marque[j] = 2 or 3
				// root[i] <--- root[j] 
				data.get(i).setRoot(data.get(j).getRoot());
				// level[i] <--- level[j]+1 
				data.get(i).setLevel(data.get(j).getLevel()+1);
			 }
		 }
		 if (marque[i] != 3) {
			 marque[i] = 2; 
			 stack.removeFirst();
		 }
	 }
	   
    // O(n)
    // compute s for each node of positive level
    // after computeNodeData, computeMax, computeInv
    public void  computeS() {
      	for (int r = 0; r < g.size(); r++) {
      		 if ((r == p.find(r)) && (data.get(r).getLevel() == 0)) { //r is a root 
      		      computeSRoot(r);
      		 }
      	}
    }
    // O(T(r))
    // after computeNodeData , computeMax , computeInv
    private void  computeSRoot(int r) {
    	for (int s : inv.edges(r,0)) {
    		if (s != data.get(r).getPred()) {
    			computeSRoot(s,s);
    		}
    	}
    }
    
    // O(T(r))
    // after computeNodeData , computeMax , computeInv
    private void  computeSRoot(int x, int s) {
       data.get(x).setS(s);
       if (inv.edges(x,0).size() > 0) {
    	   for (int y : inv.edges(x,0)) {
    		   computeSRoot(y,s);
    	   }
       }
    }
    
    
    
	
    ///////////////// PRELIMINARY STEP //////////////////////////
	
	// return the list of triples (t,b,n(t))
	// O(|T(r)|)
    public List<IntTriple> scanTree(int r, List<IntTriple> list) {
    	data.get(r).setMaxPredList(new ArrayList<IntPair>());
		for (int s : inv.edges(r,0)) {
			if (s != data.get(r).getPred()) {
				 scanTreeRec(s,list,s,r);
			}
		}
		return list;
	}
	
    private void scanTreeRec(int t, List<IntTriple> list, int s, int r){
    	int n;
    	// data.get(t).setS(s);
    	for (int c  = 1; c < g.arity(); c++){
    		int z = edgeQuotient(t,c);
    		if ((data.get(z).getLevel() == maxLevel)&&(data.get(z).getRoot()==r)){
    			n = scanTreeRec2(t,list,s,r);
        		list.add(new IntTriple(t,c,n));
        		return;
        	}
    	}
    	if (data.get(t).getLevel() == maxLevel) {
    		if (data.get(s).getMark() == false) {
    			data.get(r).getMaxPredList().add(new IntPair(s,t));
    		}
    	}
    	for (int y : inv.edges(t,0)) {
    		scanTreeRec(y,list,s,r);
		}
    }
  
    
    
	private int scanTreeRec2(int t, List<IntTriple> list, int s, int r) {
		int n = 0;
		// data.get(t).setS(s);
		if (inv.edges(t,0).size() == 0) {
			if (data.get(t).getLevel() == maxLevel) {
				n = 1;
	    		if (data.get(s).getMark() == false) {
	    			data.get(r).getMaxPredList().add(new IntPair(s,t));
	    			data.get(s).setMark(true);
	    		}
			}
		} else {
		  for (int y : inv.edges(t,0)) {
    		 n += scanTreeRec2(y,list,s,r);
		  }
		}
		return n;
	}
    
	// O(n)
    private List<IntTriple>  scanTrees() {
    	List<IntTriple> list = new ArrayList<IntTriple>();
        for (int s = 0; s < g.size(); s++) {
        	data.get(s).setMark(false);
        }
		for (int r : maxRootList) {
			list = scanTree(r,list);
		}
		for (int s = 0; s < g.size(); s++) {
	        	data.get(s).setMark(false);
	    }
		return list;
    }
  

    
    //////////////////// FLIPS ////////////////////////////////
    
  // flip the outgoing edges of the vertex x labeled by c and d in g
	private void flipG(int x, int c, int d) {
		int y = g.edge(x,c);
		g.getEdges().get(c).set(x,g.edge(x,d));
		g.getEdges().get(d).set(x,y);
	}
	
	// flip the outgoing edges of the vertex x labeled by c and d in the quotient
	// inv n est pas mis a jour apres un flip
	private void flipQ(int x, int c, int d) {
		if (p.find(x) != x) throw new IllegalArgumentException();
		int y = edgeQuotient(x,c);
		int z = edgeQuotient(x,d);
		g.getEdges().get(c).set(x,z);
		g.getEdges().get(d).set(x,y);
	}
	
	
	// flip the outgoing edges of the vertex x labeled by c and d in the quotient
	// inv est mis a jour apres un flip
	private void flipQInv(int x, int c, int d) {
		if (p.find(x) != x) throw new IllegalArgumentException();
		int y = edgeQuotient(x,c);
		int z = edgeQuotient(x,d);
		g.getEdges().get(c).set(x,z);
		g.getEdges().get(d).set(x,y);
		inv.getEdges().get(c).get(z).add(x);
		inv.getEdges().get(d).get(y).add(x);
		Iterator<Integer> it = inv.getEdges().get(c).get(y).iterator();
		while ((it.hasNext()) && (it.next() != x)) {
	    }
		it.remove();
		it = inv.getEdges().get(d).get(z).iterator();
		while ((it.hasNext()) && (it.next() != x)) {
	    }
		it.remove();
	}
	
	// true if the set of outgoing egdes of x is a bunch
	private boolean isBunch(int x) {
		int y = edgeQuotient(x,0);
		for (int c = 1; c < g.arity(); c++) {
			if (edgeQuotient(x,c) != y) {
				return false;
			}
		}
		return true;
	}	
	
	
	////////////// Flips level 0 ///////////////////////////
	private IntPair flipEdgesLevelZero() throws PeriodicException {
		for (int x = 0;  x < g.size(); x++){
			if (x == p.find(x)) {
				if (!(isBunch(x))) {
					int y = edgeQuotient(x,0);
					for (int c = 1; c < g.arity(); c++) {
						if (edgeQuotient(x,c) != y) {
							flipQ(x,0,c);
							int z = getData(edgeQuotient(x,c)).getPred();
							return new IntPair(x,z);
						}
					}
				}
		
			}
		}
		throw new PeriodicException();
	}
	
   /////////////   Preliminary Flips Max Level > 0//////////////////////////////////
	
    // after upDate(), computes maxPredList
    public IntTriple preliminaryStep() {
    	IntTriple tr = null;
    	int count = 0;
    	List<IntTriple> list = scanTrees();
		System.out.println(list);
		System.out.println(maxLevelNumber);
		for (IntTriple triple : list) {
			if (triple.getZ() < maxLevelNumber) {
				flipQ(triple.getX(),0,triple.getY());
				maxLevelNumber = maxLevelNumber - triple.getZ();
				count++;
			} else {
				tr = triple;
			}
		}
        if (count == list.size()) {
        	return new IntTriple(2,0,0); //  end of preliminary flips, bad edges purged
			} else {                     
				int r= data.get(tr.getX()).getRoot();
				int x = data.get(r).getPred();
				int maxNode = edgeQuotient(tr.getX(),tr.getY());
				int y = data.get(maxNode).getS();
				return new IntTriple(1,x,y); // (x,y) stable pair
			}
		}
    
       // Preliminary step for new T(r), O(T(r))
       public IntTriple preliminaryStepSector(int r) {
    	   	IntTriple tr = null;
        	int count = 0;
        	List<IntTriple> list = new ArrayList<IntTriple>();
		    // return the list of triples (t,b,n(t)) for new T(r) 
		    list = scanTree(r,list);
		    for (IntTriple triple : list) {
				if (triple.getZ() < data.get(r).getMaxNodeNumber()) {
					flipQ(triple.getX(),0,triple.getY());
					data.get(r).setMaxNodeNumber(data.get(r).getMaxNodeNumber() - triple.getZ());
					count++;
				} else {
					tr = triple;
				}
			 }
		    if (count == list.size()) {
	        	return new IntTriple(2,0,0); //  end of preliminary flips, bad edges purged
				} else {    
					return new IntTriple(3,tr.getX(),tr.getY()); // edge (t,b,p)
				}
       }

    /////////////   FlipEdges //////////////////////////////////
     
    // returns true if x belongs to [rk .... r[ 
    // (if r is the only maximal root of the cycle, position r is outside the sector)
    // getPred(r)= r if the length of the cycle is 1
    // returns true if the length of the cycle is 1   
    // O(|[rk .... r[ |)
    
     private boolean insideSector(int x, int r) {
        if (data.get(r).getLength() == 1) {
           return false;
        }
        int pred = data.get(r).getPred();
        while ((pred != x) && (data.get(pred).getIsMaxRoot())== false) {
        	pred = data.get(pred).getPred();
        }
        // if r is the only maximal root of the cycle, position r is inside the sector
        if (pred == r) {
        	return true;
        }
        if (pred == x) {
        	return true;
        }
        return false;
     }
    
    // r is a root of a maximal tree of the quotient
    // maxLevel > 0
    // O(|sector(r)|)
    // verifier quand  le cycle a un seul arbre max
    //  verifier quand  le cycle est de taille 1
     
    public IntTriple flipEdges(int r) {
      if (data.get(r).getMaxPredList().size() == 1) {
    	  return flipEdgesOneMaximalChild(r); 
      } else {
    	  return flipEdgesTwoMaximalChildren(r); 
      }
    }
    // Easy case, findOutsideSectorEdge
    // The number of children rho is 1 or more
    // returns (t1,b1,p1),s1 or  -1, ...
    
    public int[] findOutsideSectorEdge(int r) {
    	int[] res = new int[4];  // (t1,b1,p1),s1
    	for (int i = 0; i < 4; i++) res[i] = -1;
    	boolean gotOutsideSectorEdge = false;
        // list of (si,pi)
        List<IntPair> maxPredList = data.get(r).getMaxPredList();
        int i = 0;
        while ((gotOutsideSectorEdge  == false) && (i < maxPredList.size())) {
            int pi = maxPredList.get(i).getY();
            for (int c = 1; c < g.arity(); c++) {
          	 List<Integer> list = getInv().edges(pi,c);
               for (int t : list) {
          	    if (!(insideSector(t,r))){
          	    	res[0]=  t;  // t1
          	    	res[1]=  c;  // b1
          	    	res[2]=  pi;  //p1
          	    	res[3]=  maxPredList.get(i).getX(); // s1
          	    	gotOutsideSectorEdge = true;
          	    } 
               }
            }
            i++;
        }
        if (gotOutsideSectorEdge == true) {
        	  return res;
          }
        return res;
    }
    
   // The number of maximal children rho is 1
   // returns (1, stable pair) or (0, edge)
    public IntTriple flipEdgesOneMaximalChild(int r) {
    	int[] res = findOutsideSectorEdge(r);
    	int t1 = res[0]; int b1 = res[1]; int p1 = res[2]; int s1 = res[3]; // (t1,b1,p1),s1
    	if (res[0] != -1) {
    	   flipQ(res[0],0,res[1]);
    	   return new IntTriple(1,s1,data.get(r).getPred()); // checked
    	}
    	// special case of a cycle of length 1, res[0] == r
    	if (data.get(r).getLength()==1) {
    		return new IntTriple(0,res[0],res[1]);
    	}
   	    /////////////  easy case impossible //////////////
        return flipEdgesOneChildEqual(r, t1, b1, p1, s1);
    }
    
    
    // The number of maximal children rho is AT LEAST two
    public IntTriple flipEdgesTwoMaximalChildren(int r) {
      	int[] res = findOutsideSectorEdge(r);
    	int t1 = res[0]; int b1 = res[1]; int p1 = res[2]; int s1 = res[3]; // (t1,b1,p1),s1
    	if (res[0] != -1) {
    	   flipQ(res[0],0,res[1]);
    	   return new IntTriple(1,s1,data.get(r).getPred());
    	}
    	List<IntPair> maxPredList = data.get(r).getMaxPredList();
        /////////////  echec de la recherche secteur //////////////
        // (t1,b1,p1),s1
        int t2; int b2; int p2; int s2; // (t2,b2,p2),s2 
        b1 = 1; b2 = 1;
        p1 = maxPredList.get(0).getY();
        t1 = getInv().edges(p1,b1).get(0); // c == 1
        s1 = maxPredList.get(0).getX(); 
        p2 = maxPredList.get(1).getY();
        t2 = getInv().edges(p2,b2).get(0); // c == 1
        s2 = maxPredList.get(1).getX(); 
        // test for t1 < t2 and computation of heightTPrime
        int pred = data.get(r).getPred(); 
        int heightTPrime = data.get(pred).getHeight()+1;
        while ((pred != t1) && (pred != t2)) {
        	pred = data.get(pred).getPred();
        	heightTPrime = Math.max(heightTPrime,data.get(pred).getHeight()+1);
        }
        if (pred == t1 ) { // t2 before t1 (clock order) exchange (t1,b1,p1),s1 and (t2,b2,p2),s2 
            p2 = maxPredList.get(0).getY();
            t2 = getInv().edges(p2,b2).get(0); // c == 1
            s2 = maxPredList.get(0).getX(); 
            p1 = maxPredList.get(1).getY();
            t1 = getInv().edges(p1,b1).get(0); // c == 1
            s1= maxPredList.get(1).getX();   
        } 
        pred = data.get(r).getPred(); 
    	heightTPrime = Math.max(heightTPrime,data.get(pred).getHeight()+1);
        while (pred != t1) {
        	pred = data.get(pred).getPred();
        	heightTPrime = Math.max(heightTPrime,data.get(pred).getHeight()+1);
        }
        // end of the computation of heightTPrime
    	if (t1 != t2) {
    		flipQ(t1,0,b1);
    		if (heightTPrime > data.get(r).getHeight()) {
    			return new IntTriple(1,s1,data.get(r).getPred()); 
    		} else { // heightTPrime < = data.get(r).getHeight()
    			flipQ(t2,0,b2);
    			return new IntTriple(1,s1,s2); 
    		} 
    	} else { // t1 == t2  		
    		return flipEdgesChildrenEqual(r, t1, b1, p1, s1, b2, p2, s2);
    	}
    }
    
    // The number of children rho is at least two . Case t1 == t2
    // args : t, b1, p1, s1, b2, p2, s2
    public IntTriple flipEdgesChildrenEqual(int r, int... args) {
       	int t = args[0];
    	int b1 = args[1];
    	int p1 = args[2];
    	int s1 = args[3];
    	int b2 = args[4];
    	int p2 = args[5];
    	int s2 = args[6];
        int s0 = data.get(r).getPred(); // s0
        int heightT0 = data.get(s0).getHeight()+1;
        // checked for t == r
        int x = s0;
        while (x != t) {
        	x = data.get(x).getPred();
        	heightT0 = Math.max(heightT0,data.get(x).getHeight()+1);
        }
        if (heightT0 > data.get(r).getHeight()) {
        	flipQ(t,0,b1);
        	return new IntTriple(1,s1,s0); // stable pair 
        } else { 
        	if (heightT0  < data.get(r).getHeight()) {
				flipQInv(t,0,b1); // mise a jour de inv pour x0 et p1
				upDateSector(r,t,b1,p1,s0,s1);
				return flipEdges(r);
        	} else { //  (heightT0 ==  data.get(r).getHeight())
        		// find one i such that isBunch(si)
        		int i = 0;
        		int si= s1;
        		while (!(isBunch(si))){
        			i++;
        			si= data.get(r).getMaxPredList().get(i).getX();
        		}
            	if ((isBunch(s0)) && (isBunch(si))) {
            		return new IntTriple(1,s0,si); // stable pair 
        		} else {
        			if ((isBunch(s0)) && (!(isBunch(si)))) {
           				flipQInv(t,0,b1); // mise a jour de inv pour x0 et p1
        				upDateSector(r,t,b1,p1,s0,s1);
        				return flipEdges(r);
        			} else {
        				// isBunch(s0) is false
        				int b0 = 1;
        				while (edgeQuotient(s0,b0) == r){
        					b0++;
        				}
        				int q0 = edgeQuotient(s0,b0);
        				int r0 = data.get(q0).getRoot();
        				if (r0 != r){
        					flipQ(s0,0,b0);
        					if (data.get(q0).getLevel()>0){ // i.e. q0 == r0
        						return new IntTriple(1,data.get(r0).getPred(),data.get(q0).getS());
        					}
        					return new IntTriple(1,data.get(r0).getPred(),s0);
        				} else { // r0 == r
        				  // check whether qO is descendant of s1
        				   boolean descendant = false;
        				   int z = q0;
        				   while ((descendant == false) && (z != r0)) {
        				      z = edgeQuotient(z,0);
        				   }
        				   // the case t == s0 is not possible (=> h(TO) == 0)
        				   if (!(descendant)) {
        					   flipQ(t,0,b1);
        					   flipQ(s0,0,b0);
        					   return new IntTriple(1,s1,data.get(q0).getS()); 
        				   } else {
        					   flipQ(t,0,b2);
        					   flipQ(s0,0,b0);
        					   return new IntTriple(1,s1,s2); 
        				   }
        				}				
        			}
        		}
        	}
        }
    }
    
    // The number of maximal children rho is 1.
    // args : t, b1, p1, s1
    public IntTriple flipEdgesOneChildEqual(int r, int... args) {
    	int t = args[0];
    	int b1 = args[1];
    	int p1 = args[2];
    	int s1 = args[3];
        int s0 = data.get(r).getPred(); // s0
        int heightT0 = data.get(s0).getHeight()+1;
        // checked for t == r
        int x = s0;
        while (x != t) {
        	x = data.get(x).getPred();
        	heightT0 = Math.max(heightT0,data.get(x).getHeight()+1);
        }
        if (heightT0 > data.get(r).getHeight()) {
        	flipQ(t,0,b1);
        	return new IntTriple(1,s1,s0); // stable pair 
        } else { 
        	if (heightT0  < data.get(r).getHeight()) {
        		// r is no more a maximal root
        		return new IntTriple(0,t,b1); // edge (t,b1,p1) 
        	} else { //  (heightT0 ==  data.get(r).getHeight())
        		if ((isBunch(s0)) && (isBunch(s1))) {
        		return new IntTriple(1,s0,s1); // stable pair 
        		} else {
        			if ((isBunch(s0)) && (!(isBunch(s1)))) {
        				flipQInv(t,0,b1); // mise a jour de inv pour x0 et p1
        				upDateSector(r,t,b1,p1,s0,s1);
        				IntTriple tr = preliminaryStepSector(r);
        				if (tr.getX() == 2) {
        				  return flipEdgesOneMaximalChild(r);
        				} else { // tr.getX() == 3
        					return tr; // on renvoie cette fleche type 3
        				}
        			} else {
        				// isBunch(s0) is false
        				int b0 = 1;
        				while (edgeQuotient(s0,b0) == r){
        					b0++;
        				}
        				int q0 = edgeQuotient(s0,b0);
        				int r0 = data.get(q0).getRoot();
        				if (r0 != r){
        					flipQ(s0,0,b0);
        					if (data.get(q0).getLevel()>0){ // i.e. q0 == r0
        						return new IntTriple(1,data.get(r0).getPred(),data.get(q0).getS());
        					}
        					return new IntTriple(1,data.get(r0).getPred(),s0);
        				} else { // r0 == r
        				  // check whether qO is descendant of s1
        				   boolean descendant = false;
        				   int z = q0;
        				   while ((descendant == false) && (z != r0)) {
        				      z = edgeQuotient(z,0);
        				   }
        				   // the case t == s0 is not possible (=> h(TO) == 0)
        				   if (!(descendant)) {
        					   flipQ(t,0,b1);
        					   flipQ(s0,0,b0);
        					   return new IntTriple(1,s1,data.get(q0).getS()); 
        				   }
        				}
        			}
        		}
        	} 
        }
		return null;
    }
   
    /////////////////////// UPDATE SECTOR dans  flipEdgesOneChildEqual ////////////////
    // args (r,t,b1,p1,s0,s1) (so is a bunch)
    // for r, height is unchanged
    private void upDateSector(int... args) {
        int r = args[0]; int t = args[1]; int p1 = args[3]; int s0 = args[4]; int s1 = args[5]; 
    	int p0 = upDateSectorNewTree(s0,1,r,s0,t);
    	upDateSectorCycle(p1,t,r,s1,p1);
    	data.get(r).setPred(s1);
    	List<IntPair> l = data.get(r).getMaxPredList();
    	l.remove(new IntPair(s1,p1));
    	l.add(new IntPair(s0,p0));
    	data.get(r).setMaxPredList(l);
    }
    
    // recursive method
    // return 0 or a node max 
    private int upDateSectorNewTree(int x, int level, int r, int s0, int t) {
    	int res = 0;
    	data.get(x).setRoot(r);
    	data.get(x).setS(s0);
    	data.get(x).setLevel(level);
    	if (data.get(x).getLevel() == maxLevel) {
    		res = x; 
    	} 
    	for (int y : inv.edges(x,0)) {
    		res = upDateSectorNewTree(y,level+1,r,s0,t);
    	}
    	return res;
    }
    
    // flipQinv (t,b1,p1) and (t,0,x0) has been done
    private void upDateSectorCycle(int x, int before, int r, int s1, int p1) {
      if (x != r) { 
        data.get(x).setPred(before);
        data.get(x).setLevel(0);
        data.get(x).setRoot(x);
        if (x == p1) {
          upDateSectorCycle(edgeQuotient(x,0),x,r,s1,p1);       
        } else {
          computeSHeightRoot(x,0);
          upDateSectorCycle(edgeQuotient(x,0),x,r,s1,p1);       
        }
      }
    }
    
    // O(T(r))
    // S and height for a root r
    private void  computeSHeightRoot(int r, int level) {
    	for (int s : inv.edges(r,0)) {
    		if (s != data.get(r).getPred()) {
    			computeSHeightRoot(s,level+1,s);
    		}
    	}
    }

    // O(T(r))
    private void  computeSHeightRoot(int x, int level, int s) {
    	data.get(x).setS(s);
    	if (inv.edges(x,0).size() > 0) {
    		for (int y : inv.edges(x,0)) {
    			computeSHeightRoot(y,level+1,s);
    		}
    	}
    }
    ////////////////////////   MAIN  //////////////////////////////////////////
	public IntPair findStablePair() throws PeriodicException {
		update();
	    if (maxLevel == 0) {
	    	return flipEdgesLevelZero();
	    } 
	    IntTriple tr = preliminaryStep();
	    if (tr.getX() == 1) {
	    	return new IntPair(tr.getY(), tr.getZ()); // stable pair returned
	    } else { // tr.getX() == 2
	    	update();
			for (int r : maxRootList) {
				tr = flipEdges(r);
	            if (tr.getX() == 1) {
	    	    	return new IntPair(tr.getY(), tr.getZ()); // stable pair returned
	    	    } else { // tr.getX() == 0 edge (t,b)
	    	    	data.get(r).setEdge(tr);
	    	    }
			}
			int r0 = maxRootList.get(0);
			for (int i = 1; i < maxRootList.size(); i++) {
				tr = data.get(maxRootList.get(i)).getEdge();
				flipQ(tr.getX(),0,tr.getY());
			}
			return new IntPair(data.get(r0).getPred(),data.get(r0).getMaxPredList().get(0).getX()); 
	    }
	}
	    
	   
	    
		
	 	public void upLiftFlips() {
			for (int i = 0; i < g.size(); i++) {
				for (int l = 0; l < g.arity(); l++) {
					if (p.find(g.edge(i,l))
					    != p.find(g.edge(p.find(i),l))
					    ) {
						int m = 0;
						while (p.find(g.edge(i,m))
							 != p.find(g.edge(p.find(i),m))
						      ) {
							m++;
						}
						flipG(i,l,m);	
					}
				}
			} 
		}
		
		public void findColoring() throws PeriodicException {
			while (size() > 1) {
				IntPair stab = findStablePair();
				upLiftFlips();
				merge(stab.getX(),stab.getY());
				System.out.println(this);
			}
		}
		
}