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

public class MinSlackHeuristic implements VariableSelector<IntVar> {
    
    int n;             // number of decision variables
    IntVar[] decision; // 0/1 decision variables
    IntVar[] op1;      // start time of op1
    IntVar[] op2;      // start time of op2
    int[] duration1;   // duration of op1
    int[] duration2;   // duration of op2

    public MinSlackHeuristic(Decision[] decisions){
	n         = decisions.length;
	decision  = new IntVar[n];
	op1       = new IntVar[n];
	op2       = new IntVar[n];
	duration1 = new int[n];
	duration2 = new int[n];
	for (int i=0;i<n;i++){
	    decision[i]  = decisions[i].d;
	    op1[i]       = decisions[i].op_i.start;
	    op2[i]       = decisions[i].op_j.start;
	    duration1[i] = decisions[i].op_i.duration;
	    duration2[i] = decisions[i].op_j.duration;
	}
    }

@Override
    public IntVar getVariable(IntVar[] v){
	int minSlack = Integer.MAX_VALUE;
	int slack = 0;
	IntVar minSlackVar = null;
	for (int i=0;i<n;i++)
	    if (!decision[i].isInstantiated()){
		slack = slack(i);
		if (slack < minSlack){minSlackVar = decision[i]; 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(int i){
	return Math.max(slack(op1[i],duration1[i],op2[i],duration2[i]),
			slack(op2[i],duration2[i],op1[i],duration1[i]));
    }
    //
    // 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
    //

}