import static choco.Choco.*;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.kernel.model.Model;
import choco.kernel.solver.Solver;
import choco.kernel.solver.ContradictionException;
import choco.kernel.solver.constraints.integer.AbstractLargeIntSConstraint;
import choco.kernel.solver.variables.integer.IntDomainVar;
import choco.kernel.memory.IStateInt;
import choco.kernel.memory.trailing.StoredInt;
import choco.kernel.model.variables.integer.IntegerExpressionVariable;
import choco.kernel.model.variables.integer.IntegerVariable;

//
// Subtour Elimination Constraint
// see "Solving Small TSPs with Constraints" by Caseau & Laburthe
//

public class SubtourElimination extends AbstractLargeIntSConstraint {  

    private IStateInt[] start;   // the start of a chain
    private IStateInt[] end;     // the end of a chain
    private IStateInt[] length;  // the length of the chain
    private int n;

    public SubtourElimination(Solver s,IntDomainVar[] S) {   // (0)
	super(S);
	n      = S.length;
	start  = new StoredInt[n];
	end    = new StoredInt[n];
	length = new StoredInt[n];
	for (int i=0;i<n;i++){
	    vars[i]   = S[i];
	    start[i]  = s.getEnvironment().makeInt(i);
	    end[i]    = s.getEnvironment().makeInt(i);
	    length[i] = s.getEnvironment().makeInt(0);
	}
    }
    //
    // Note: we assume all variables in S are allDifferent
    //

    public boolean isSatisfied(){
	// System.out.println("isSatisfied()");
	return true;
    }
    
    public void awake() throws ContradictionException {
	// System.out.println("awake()");
    }

    public void propagate() throws ContradictionException {
	// System.out.println("propagate()");
    }

    public void awakeOnInf(int idx) throws ContradictionException {
    // System.out.println("awakeOnInf(" + idx + ")");
    }

    public void awakeOnSup(int idx) throws ContradictionException {
     // System.out.println("awakeOnSup(" + idx + ")");
    }

    public void awakeOnRem(int idx,int x) throws ContradictionException {
	// System.out.println("awakeOnRem(" + idx + "," + x + ")");
    }

    public void awakeOnInst(int idx) throws ContradictionException {
	// System.out.println("awakeOnInst(" + idx + "," + vars[idx].getVal() + ")");
	int i   = idx,
	    j   = vars[i].getVal(), // city_j comes immediately after city_i
	    s_i = start[i].get(),
	    e_j = end[j].get();	    
	length[e_j].add(length[i].get() + 1);
	start[e_j].set(s_i);	
	end[s_i].set(e_j);
	if (length[e_j].get() < n-1)
	    vars[e_j].remVal(s_i);
    }
}
//
// (0) note that we have IntDomainVar not IntegerVariable as these variables
//     come from the solver! See TSPTest to work this out.
//