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

/**
 * @author beal
 *
 */
public class Quotient {
    private final Graph g;
    private final Partition p;
    private final List<NodeData> data;
    
	public Quotient(Graph 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());
		}
	}

	public Partition getPartition() {
		return p;
	}
	public Graph getG() {
		return g;
	}
	public List<NodeData> getData() {
		return data;
	}
	public NodeData getData(int x) {
		return data.get(x);
	}
	
	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()));
		   }
   	   }
	   return sb.toString();
	}
	
	
    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.succ(lx,c),g.succ(ly,c));
    		}
    	}
    }
    
	// depth first search of the quotient which computes level and root for each vertex
	public 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 = p.find(g.getEdges().get(0).get(i));
		 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();
				 while (x != j) {
					 data.get(x).setLevel(0);
					 data.get(x).setRoot(x);
					 marque[x] = 3; 
					 stack.removeFirst();
					 x = stack.getFirst();
				 }
				 data.get(j).setLevel(0);
				 data.get(j).setRoot(j);
				 marque[j] = 3; 
				 stack.removeFirst();
			 } 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();
		 }
	 }

	// flip the outgoing edges of the vertex x labeled by c and d 
	private void flip(int x, int c, int d) {
		int y = g.getEdges().get(c).get(x);
		g.getEdges().get(c).set(x,g.getEdges().get(d).get(x));
		g.getEdges().get(d).set(x,y);
	}
	
	public StablePair findStablePair() {
       return new StablePair(3,4);
	}
	
	public void upLiftFlips() {
		for (int i = 0; i < g.size(); i++) {
			for (int l = 0; l < g.arity(); l++) {
				if (p.find(g.getEdges().get(l).get(i))
				    != p.find(g.getEdges().get(l).get(p.find(i)))
				    ) {
					int m = 0;
					while (p.find(g.getEdges().get(m).get(i))
						 != p.find(g.getEdges().get(m).get(p.find(i)))
					      ) {
						m++;
					}
					flip(i,l,m);	
				}
			}
		} 
	}
	
	public void findColoring() {
		while (size() > 1) {
			StablePair stab = findStablePair();
			upLiftFlips();
			merge(stab.getX(),stab.getY());
			System.out.println(this);
		}
	}
}