//
// Slack-Based Heuristics for Constraint Satisfaction Scheduling
// Stephen F. Smith and Cheng-Chung Cheng
// Proceedings AAAI-93
//
import org.chocosolver.solver.variables.IntVar;
import org.chocosolver.solver.search.strategy.selectors.variables.VariableSelector;

public class MinSlackHeuristic implements VariableSelector<IntVar> {
    
    @Override
    public IntVar getVariable(IntVar[] vars){
	int minSlack = Integer.MAX_VALUE;
	IntVar minSlackVar = null;
	for (IntVar v : vars)
	    if (!v.isInstantiated()){
		int slack = slack((Decision) v);
		if (slack < minSlack){minSlackVar = v; minSlack = slack;}
	    }
	return minSlackVar;
    }
    //
    // select the uninstantiated variable with minimum maximum slack
    //

    private int slack(IntVar op_i,int d_i,IntVar op_j,int d_j){
	return op_j.getUB() - Math.max(op_i.getLB() + d_i,op_j.getLB());
    }
    //
    // slack if op_i before op_j 
    // i.e. slack(op_i -> op_j) in S&C AAAI-93 parlance
    //
    // NOTE: we consider earliest and latest start times whereas S&C
    //       consider earliest start and latest finish, but our calculations
    //       are exactly the same
    //

    private int slack(Decision v){
	return Math.max(slack(v.op_i.start,v.op_i.duration,v.op_j.start,v.op_j.duration),
			slack(v.op_j.start,v.op_j.duration,v.op_i.start,v.op_i.duration));
    }
    //
    // get slack of ith decision variable, to be the largest slack
    // from either slack(op1 -> op2) or slack(op2 -> op1)
    // This differs from Smith & Cheng as they select the smaller of the two,
    // i.e. replace Math.max with Math.min
    //

}