package de.uniaugsburg.isse.constraints.solvers;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

import ua.cr2csop.graph.DirectedConstraintGraph;
import de.isse.wcsp.CostFunction;
import de.isse.wcsp.CostFunctionNetwork;
import de.isse.wcsp.Tuple;
import edu.uci.ics.jung.graph.SparseGraph;
import edu.uci.ics.jung.graph.UndirectedGraph;
import edu.uci.ics.jung.graph.UndirectedSparseGraph;
import edu.uci.ics.jung.graph.event.GraphEvent.Edge;

/**
 * Solves cost function networks by means of constraint backtracking
 * @author alexander
 *
 */
public class ConstraintBacktrackingSolver {
	
	public class MaxCostComparator implements Comparator<CostFunction> {

		@Override
		public int compare(CostFunction o1, CostFunction o2) {
			return Integer.compare(o2.getMaxCost(), o1.getMaxCost());
		}

	}

	List<CostFunction> costFunctions;
	CostFunctionNetwork cfn;
	private int[] assignment;
	private boolean[] assigned;
	private int noSolutions; 
	private int upperBoundToBeat;
	private UndirectedGraph<CostFunction, String> constraintGraph;
	private boolean[][] forbidden; // forbidden[i][j] means that tuple j of cfn i is forbidden
	private int bestToExpect;
	private int worstToExpect;
	private boolean doPropagate = true;
	
	public void solve(CostFunctionNetwork cfn) {
		this.cfn = cfn;
		costFunctions = new ArrayList<CostFunction>(cfn.getCostFunctions());
		Collections.sort(costFunctions, new MaxCostComparator());
		assignment = new int[cfn.getDomainSizes().length];
		assigned = new boolean[cfn.getDomainSizes().length];
		noSolutions = 0;
		upperBoundToBeat = cfn.getUpperBound();
		int maxNoTuples = 0;
		for(CostFunction cf : costFunctions) {
			cf.fillExtensionTableau(cfn.getDomainSizes());
			maxNoTuples = Math.max(maxNoTuples, cf.getTuples().size());
		}
		
		forbidden = new boolean[costFunctions.size()][maxNoTuples];
				
		constraintGraph = new UndirectedSparseGraph<CostFunction, String>();
		buildGraph();
		solveBacktrack(cfn, 0, 0);
		
	}

	private void buildGraph() {
		List<List<CostFunction>> costFunctionsAtVariable = new ArrayList<List<CostFunction>>(cfn.getDomainSizes().length);
		for(int v = 0; v < cfn.getDomainSizes().length; v++) {
			costFunctionsAtVariable.add(new LinkedList<CostFunction>());
		}
		
		for(CostFunction costFunction : cfn.getCostFunctions()) {
			for(int varIndex : costFunction.getScope()) {
				costFunctionsAtVariable.get(varIndex).add(costFunction);
			}
		}
		
		int edgeId = 0;
		for(int v = 0; v < cfn.getDomainSizes().length; v++) {
			List<CostFunction> bucket = costFunctionsAtVariable.get(v);
			for(int i = 0; i < bucket.size(); ++i) {
				for(int j = i+1; j < bucket.size(); ++j) {
					CostFunction first = bucket.get(i);
					CostFunction second = bucket.get(j);
					constraintGraph.addEdge("e_"+edgeId, first, second);
					++edgeId;
				}
			}
		}
	}

	private void solveBacktrack(CostFunctionNetwork cfn, int cfIndex, int costsSoFar) {
		if(cfIndex >= costFunctions.size()) {
			if(costsSoFar < cfn.getUpperBound()) {
				// arrived at a solution		
				++noSolutions;
				System.out.println("Found solution no. "+noSolutions + ": " + Arrays.toString(assignment) + " costs "+costsSoFar);
				upperBoundToBeat = Math.min(upperBoundToBeat, costsSoFar);
			}
			return;
		}
		
		// select next cost function
		CostFunction nextCostFunction = costFunctions.get(cfIndex);
		// branch possible tuple assignments
		List<Tuple> tuples = nextCostFunction.getTuples();
		
		for(int i = 0; i < tuples.size(); ++i) {
			// try and assign tuple[i] and propagate
			Tuple nextTuple = tuples.get(i);
			if(costsSoFar + nextTuple.getCost() >= upperBoundToBeat) 
				break; // cannot find better values
			
			if(forbidden[cfIndex][i]) // by forward checking
				continue;
			
			int[] nextTupleValues = nextTuple.getValues();
			int[] scope = nextCostFunction.getScope();

			boolean possible = true;
			
			for(int scopeInd = 0; scopeInd < scope.length; ++ scopeInd) {
				int nextVar = scope[scopeInd];
				if(assigned[nextVar]) {
					if(assignment[nextVar] != nextTupleValues[scopeInd]) {
						possible = false;
						break;
					}
				}
			}
			
			// if possible 
			if(!possible)
				continue;
			else {
				boolean[] oldAssigned = Arrays.copyOf(assigned, assigned.length);
				int[] oldAssignment = Arrays.copyOf(assignment, assignment.length);
				
				for(int scopeInd = 0; scopeInd < scope.length; ++ scopeInd) {
					int nextVar = scope[scopeInd];
					assigned[nextVar] = true;
					assignment[nextVar] = nextTupleValues[scopeInd];
				}
				
				// propagate 
				boolean[][] changed = null;
				if(doPropagate ) {
					changed = propagate(cfIndex+1);
				}
			
				if(costsSoFar + bestToExpect < upperBoundToBeat) {
					solveBacktrack(cfn, cfIndex+1, costsSoFar + nextTuple.getCost());
				}
				
				if(doPropagate) {
					retractChanges(changed);
				}
				// retract
				for(int scopeInd = 0; scopeInd < scope.length; ++ scopeInd) {
					int nextVar = scope[scopeInd];
					assigned[nextVar] = oldAssigned[nextVar];
					assignment[nextVar] = oldAssignment[nextVar];
				}
				
			}
		}
		
	}

	private void retractChanges(boolean[][] changed) {
		for(int i = 0; i < changed.length; ++i) {
			for(int j = 0; j < changed[i].length; ++j) 
				if(changed[i][j])
					forbidden[i][j] = !forbidden[i][j];
		}
	}

	private boolean[][] propagate(int startCfIndex) {
		boolean[][] changes = new boolean[forbidden.length][forbidden[0].length];
		bestToExpect = 0;
		worstToExpect = 0;
		
		for(int i = startCfIndex; i < costFunctions.size(); ++i) {
			CostFunction cf = costFunctions.get(i);
			int max = Integer.MIN_VALUE;
			int min = Integer.MAX_VALUE;
			
			for(int j = 0; j < cf.getTuples().size(); ++j) {
				if(!forbidden[i][j]) { // only consider not yet forbidden tuples, otherwise another cf is responsible for forbidding
					Tuple tupleUnderTest = cf.getTuples().get(j);
					int[] values = tupleUnderTest.getValues();
					int[] scope = cf.getScope();
					boolean forbidTuple = false;
					
					for(int scopeInd = 0; scopeInd < scope.length; ++ scopeInd) {
						int nextVar = scope[scopeInd];
						if(assigned[nextVar]) {
							if(assignment[nextVar] != values[scopeInd]) {
								forbidTuple = true;
								break;
							}
						}
					}
					
					if(forbidTuple) {
						changes[i][j] = true;
						forbidden[i][j] = true;
					} else {
						max = Math.max(tupleUnderTest.getCost(), max);
						min = Math.min(tupleUnderTest.getCost(), min);
					}
				}
			}
			bestToExpect += min;
			worstToExpect += max;
		}
		return changes;
	}
}
