/**
 * This class holds all the logic and procedures for the backward sampling algorithm.
 * 
 * Ref.: Lozano, L. and Smith, J. C. (2014). 
 * A Backward Sampling Framework for Interdiction Problems with Fortification
 * 
 * @author L. Lozano & J. C. Smith
 * @affiliation Clemson University
 * @url www.leo-loza.com
 * 
 */

package backwardAlgorithm;

import gurobi.GRB;
import gurobi.GRBEnv;
import gurobi.GRBException;
import gurobi.GRBLinExpr;
import gurobi.GRBModel;
import gurobi.GRBVar;

import java.awt.image.SampleModel;
import java.util.ArrayList;
import java.util.Random;

import javax.sound.sampled.ReverbType;
import javax.swing.text.DefaultEditorKit.CutAction;
import javax.swing.text.StyleContext.SmallAttributeSet;
import javax.swing.text.html.MinimalHTMLWriter;

import sampling.Sampler;


public class AlgorithmHandler {

	int[] w; 								// Defense
	int[] x; 								// Attack
	
	int[] wstar;							// Optimal defense
	int[] xstar;							// Optimal attack
	double zstar;

	double zbar; 							// Best upper bound
	double perDamage;						// Damaged perceived
	double realDamage;						// Real damage
	
	ArrayList<int[]> cutPool; 				// Pool with cuts in C
	ArrayList<int[]> guessCutPool; 			// Pool with cuts in C guess
	
	ArrayList<int[]> waitingList; 			// Waiting list with w hats
	ArrayList<Double> wListRealDamage; 	// Waiting list real damage
	double epsilon;							// Control for the waiting list
		
	boolean masterFeasible;				 	// If the fortification problem is feasible
	boolean globalStop;						// Stopping criterion for the backward sampling	
		
	static public ArrayList<Solution> sample;		// Current sample

	Sampler sampler;
	
	GRBEnv env;
	GRBModel dModel;
	GRBModel aModel;
	GRBModel tModel;
	
	int M;
		
	long hatTime;
	long maxMinTime;
	int maxMinIter;
	int wHatEval;
	int aborted;
	
	
	public AlgorithmHandler(DataHandler data) throws GRBException, InterruptedException {
		
		w=new int[data.T];
		x=new int[data.T];
		zbar = 999999999;
		perDamage = (int) Double.POSITIVE_INFINITY;
		realDamage = 0;
		masterFeasible = true;
		globalStop = false;
		
		cutPool = new ArrayList<int[]>();
		guessCutPool = new ArrayList<int[]>();
		waitingList = new ArrayList<int[]>();
		wListRealDamage = new ArrayList<Double>();
		
		sample = new ArrayList<Solution>();
		sampler = new Sampler(data);
		
		env = new GRBEnv(null);
		env.set(GRB.IntParam.OutputFlag, 0);
		env.set(GRB.DoubleParam.MIPGap, 10E-12);

		M=1000000;
		epsilon = 0.1;
		
		hatTime = 0;
		maxMinTime = 0;
		maxMinIter = 0;
		wHatEval = 0;
		aborted = 0;
		
		}



	public void solveDefenderProblem(DataHandler data) throws GRBException {
		long auxT = System.currentTimeMillis();
		dModel = new GRBModel(env);
		dModel.reset();
		masterFeasible=true;
		
		GRBVar[] wt = new GRBVar[data.T];
		//Create variables 
		for (int i = 0; i < wt.length; i++) {
			wt[i] = dModel.addVar(0, 1, 0, GRB.BINARY, "wt["+i+"]");
		}
		//Integrate variables
		dModel.update();
		
		//Add budget constraint
		GRBLinExpr budgetExpr = new GRBLinExpr();
				
		for (int j = 0; j <data.T; j++) {
			budgetExpr.addTerm(1, wt[j]);
		}
		dModel.addConstr(budgetExpr, GRB.LESS_EQUAL, data.dBudget, "cbudget");
				
		// add cuts in the pool
		for (int i = 0; i < cutPool.size(); i++) {
			GRBLinExpr coverExpr = new GRBLinExpr();
			
			for (int j = 0; j <data.T; j++) {
				coverExpr.addTerm(cutPool.get(i)[j], wt[j]);
			}
			
			dModel.addConstr(coverExpr, GRB.GREATER_EQUAL, 1, "cCover");
	
		}
		
		// add cuts in the guess pool
		for (int i = 0; i < guessCutPool.size(); i++) {
			GRBLinExpr coverExpr = new GRBLinExpr();
			
			for (int j = 0; j <data.T; j++) {
				coverExpr.addTerm(guessCutPool.get(i)[j], wt[j]);
			}
			
			dModel.addConstr(coverExpr, GRB.GREATER_EQUAL, 1, "cGuessCover");
	
		}		

			
		dModel.update();
		dModel.optimize();
		
		hatTime+=(System.currentTimeMillis() - auxT);
		wHatEval++;
		
		if(dModel.get(GRB.IntAttr.Status) == GRB.INFEASIBLE){
			masterFeasible=false;
		//	System.out.println("		Master is infeasible!");		
		}
		else{
		//Update defense plan
			for(int i=0; i<data.T; i++){
		    	w[i]=(int) wt[i].get(GRB.DoubleAttr.X);
		     }
		
		}

	}

public double solveAux(DataHandler data) throws GRBException {
	
		long auxT = System.currentTimeMillis();
		
		aModel = new GRBModel(env);
		
		GRBVar[] xt = new GRBVar[data.T];
		GRBVar z;
		
		//Create variables x 
		for (int i = 0; i < xt.length; i++) {
			xt[i] = aModel.addVar(0, 1-w[i], 0, GRB.BINARY, "x["+i+"]");
		}
		//Create variable z
			z = aModel.addVar(0, GRB.INFINITY, -1, GRB.CONTINUOUS, "z");
			
		//Integrate variables
		aModel.update();
		
		//Add constraints for each sol in the sample
				for (int j = 0; j <sample.size(); j++) {
					GRBLinExpr expr = new GRBLinExpr();
						for (int t = 0; t < data.T; t++) {
							if(sample.get(j).y[t]>0){
								//double bigM = Math.ceil(sample.get(j).y[t])*(data.q[t]-data.c[t]);
								double boundedM =Math.min(sample.get(j).M[t], (zbar+1-sample.get(j).obj));
								boundedM = Math.max(boundedM, 0);
								expr.addTerm(boundedM, xt[t]);
							}
						}
						expr.addTerm(-1, z);
					
					aModel.addConstr(expr, GRB.GREATER_EQUAL, -sample.get(j).obj, "c"+j);
				}
				
		
		//Add budget constraint
		GRBLinExpr budgetExpr = new GRBLinExpr();
		
		for (int j = 0; j <data.T; j++) {
			budgetExpr.addTerm(1, xt[j]);
		}
		aModel.addConstr(budgetExpr, GRB.LESS_EQUAL, data.aBudget, "cbudget");
	
		//Add bound on z
		GRBLinExpr boundExpr = new GRBLinExpr();
		boundExpr.addTerm(1, z);
		double RHS = zbar+1; 
		aModel.addConstr(boundExpr, GRB.LESS_EQUAL, RHS, "cbound");
		
		//Integrate constraints		
		aModel.update();
		
		aModel.optimize();
		
		maxMinIter++;
		maxMinTime+=(System.currentTimeMillis() - auxT);

		//Update attack plan
		for(int i=0; i<data.T; i++){
	    	x[i]=(int) Math.round(xt[i].get(GRB.DoubleAttr.X));
	     }
				
		double auxObj = (-1)*aModel.get(GRB.DoubleAttr.ObjVal);
		double obj = Math.round(auxObj*100)/100.0;
		
		// Print results
/*		 System.out.println("		Aux obj:"+(-1)*aModel.get(GRB.DoubleAttr.ObjVal));
		 	 for(int i=0; i<data.T; i++){
			 if(xt[i].get(GRB.DoubleAttr.X)>0)
			 System.out.println("		x"+i+": "+xt[i].get(GRB.DoubleAttr.X));
		 }
*/		 
	 
		aModel.reset();
		return obj;
	}


	public void printopt(DataHandler data) {
			System.out.println("Z^Star: "+zstar);
			System.out.println("		Optimal defense: ");
			for(int j=0; j<data.T; j++){
				 if(wstar[j]>0)
				 System.out.println("		w"+j+": "+wstar[j]);
			 }	
			System.out.println("		Optimal attack: ");
			for(int j=0; j<data.T; j++){
				 if(xstar[j]>0)
				 System.out.println("		x"+j+": "+xstar[j]);
			 }
	
	
	}
	
	public void sample(DataHandler data) throws InterruptedException, GRBException {
		
		sampler.sampleWithx(data,sample,zbar);
		
		}


	private void updateSample(DataHandler data) {

		for (int i = 0; i < sample.size(); i++) {
			if(sample.get(i).obj>zbar){
				sample.remove(i);
				i--;
			}
		}
							
	}

	// This procedure solves the restricted interdiction problems
	public void solveMaxMin(DataHandler data, double Atime) throws InterruptedException, GRBException {
		int timeLimit=3600*4;
		if(masterFeasible && (System.nanoTime()-Atime)/1000000000<timeLimit){
		// Initialize 
		perDamage = Double.POSITIVE_INFINITY;
		realDamage = 0;
		
	//	System.out.println("**********************************************************************************************");
		while(realDamage < zbar && (System.nanoTime()-Atime)/1000000000<timeLimit){
			// Get the perceived damage
			perDamage = solveAux(data);
	//		System.out.println("P: "+perDamage+" ZBAR: "+zbar);
			// Update zbar and the sample
			if (perDamage < zbar) {
				zbar = perDamage;
				realDamage = 0;
				updateSample(data);
				sample(data);
	//			System.out.println("ZBAR UPDATED: "+zbar);
			}
			
			else if(perDamage >= zbar){
				// Get the real damage
				realDamage = solveThirdStage(data, x); //new production plan is added to sample inside this method
	//			System.out.println("P: "+perDamage+" R: "+realDamage+" ZBAR: "+zbar);
				// Try to add covering constraint		
				if(realDamage>= zbar){
					cutPool.add(x.clone());
	//				System.out.println("CUT ADDED!");
				}
				// Try to update the incumbent solution
				if(realDamage==zbar && realDamage==perDamage){
					wstar = w.clone();
					xstar = x.clone();
					zstar = zbar;
	//				System.out.println("UPDATED SOLUTION P: "+perDamage+" R: "+realDamage+" ZBAR: "+zbar);
				}
				// Check the ratio for the waiting list
				double ratio = ((zbar-realDamage)/((double) zbar));
				if(realDamage<zbar && ratio <= epsilon){
					waitingList.add(w.clone());
					wListRealDamage.add(realDamage);
					guessCutPool.add(x.clone());
	//				System.out.println("WAITING LIST "+ratio+" P: "+perDamage+" R: "+realDamage+" ZBAR: "+zbar);
					realDamage = (int) Double.POSITIVE_INFINITY;
					aborted++;
				}
			}
		}
	}
}



private void printAtt(DataHandler data) {
		System.out.print("x: (");	
		for (int i = 0; i < data.T; i++) {
				System.out.print(x[i]);
			}
		System.out.println(" )");	
	}


private void printDef(DataHandler data) {
	System.out.print("w: (");	
	for (int i = 0; i < data.T; i++) {
			System.out.print(w[i]);
		}
	System.out.println(" )");	
}



public void evaluateGuessPool(DataHandler data, double Atime) throws GRBException, InterruptedException {
	double originalEpsilon = this.epsilon;
	masterFeasible = true;
	epsilon = -1;
	
	//System.out.println("EVALUATING GUESS POOL: "+guessCutPool.size()+" ZBAR: "+zbar);
	
	for(int k=0; k<guessCutPool.size(); k++){
//		System.out.println("GUESS NUMBER "+k);
		if(wListRealDamage.get(k)>zbar){
//			System.out.println("GOOD GUESS!!! "+wListRealDamage.get(k));
			cutPool.add(guessCutPool.get(k).clone());
			guessCutPool.remove(k);
			waitingList.remove(k);
			wListRealDamage.remove(k);
			k--;
		}
	}
	
	for(int k=0; k<guessCutPool.size(); k++){
		//	System.out.println("BAD GUESS!!! "+wListRealDamage.get(k)+" ZBAR: "+zbar);
			boolean w_hat_isFeasible = 	set_w_hat(data , waitingList.get(k).clone());
			if(w_hat_isFeasible){
				solveMaxMin(data, Atime);
			}
			guessCutPool.remove(k);
			waitingList.remove(k);
			wListRealDamage.remove(k);
			k--;
	} 
	//System.out.println("SIZE: "+guessCutPool.size()+" "+waitingList.size());
	epsilon = originalEpsilon;
	
}



private boolean set_w_hat(DataHandler data, int[] w_hat) throws GRBException {

	if(isFeasible(data,w_hat)==true){
		w = w_hat;
		return true;
	}
	else{
		return false;
		
	}
	
}



boolean isFeasible(DataHandler data, int[] w_hat) {


	// evaluate cuts in the pool
			for (int i = 0; i < cutPool.size(); i++) {
				int sum = 0;
				for (int j = 0; j <data.T; j++) {
					sum+=cutPool.get(i)[j]*w_hat[j];
				}
				if (sum < 1){
					return false;
				}
				
			}
	
	return true;
}

private void calcM(DataHandler data, GRBVar[][] a, Solution sol) throws GRBException {
	
	
	for (int t = 0; t < data.T; t++) {
		double M = 0;
		for (int j = t; j < data.T; j++) {
			M+=data.q[j]*a[t][j].get(GRB.DoubleAttr.X);
		}
		double holding = 0;
		for (int j = t+1; j < data.T; j++) {
			for(int l=t; l<j; l++){
				holding+=data.h[l]*a[t][j].get(GRB.DoubleAttr.X);
			}
		}
		M=M-holding;
		M=M-data.c[t]*sol.y[t];
		M=M-data.f[t]*sol.v[t];
		sol.M[t] = Math.ceil(M);
		if(sol.M[t]<0) System.out.println("PARITY CHECK: NEGATIVE M");
	}
	
	/*
	sol.print();
	double[][] aux = new double[data.T][data.T];
	for (int t = 0; t < data.T; t++) {
		for (int j = t; j < data.T; j++) {
			aux[t][j]=a[t][j].get(GRB.DoubleAttr.X);
			if(aux[t][j]>0){
			System.out.println("a["+t+","+j+"]: "+aux[t][j]);}
		}
	}
	*/

}

public double solveThirdStage(DataHandler data, int[] xcut) throws GRBException {
	
	tModel = new GRBModel(env);
	tModel.reset();
	
	GRBVar[] y = new GRBVar[data.T]; // Production
	GRBVar[] v = new GRBVar[data.T]; // Setup
	GRBVar[] I = new GRBVar[data.T]; // Inventory
	GRBVar[] s = new GRBVar[data.T]; // Shortage

	GRBVar[][] a = new GRBVar[data.T][data.T]; // Intended production
	
	//Create variables  
	for (int i = 0; i < data.T; i++) {
		v[i] = tModel.addVar(0, 1-xcut[i], data.f[i], GRB.BINARY, "v["+i+"]");
		y[i] = tModel.addVar(0, M, data.c[i], GRB.CONTINUOUS, "y["+i+"]");
		I[i] = tModel.addVar(0, M, data.h[i], GRB.CONTINUOUS, "I["+i+"]");
		s[i] = tModel.addVar(0, M, data.q[i], GRB.CONTINUOUS, "s["+i+"]");
		for(int j=i; j< data.T; j++){
			a[i][j] = tModel.addVar(0, Double.POSITIVE_INFINITY, 0, GRB.CONTINUOUS, "a["+i+","+j+"]");}
	}

	//Integrate variables
	tModel.update();

	//Add inventory constraints for each time period > 0
	for (int t = 1; t <data.T; t++) {
		GRBLinExpr expr = new GRBLinExpr();
		expr.addTerm(1, y[t]);
		expr.addTerm(1, I[t-1]);
		expr.addTerm(1, s[t]);
		expr.addTerm(-1, I[t]);
		
		tModel.addConstr(expr, GRB.EQUAL, data.demand[t], "c"+t);
	}
	
	//Add inventory constraints for time period  0

	GRBLinExpr expr0 = new GRBLinExpr();
	expr0.addTerm(1, y[0]);
	expr0.addTerm(1, s[0]);
	expr0.addTerm(-1, I[0]);
	tModel.addConstr(expr0, GRB.EQUAL, data.demand[0], "c0");
	
	//Add setup constraints for each time period
	for (int t = 0; t <data.T; t++) {
		GRBLinExpr expr = new GRBLinExpr();
		expr.addTerm(1, y[t]);
		expr.addTerm(-data.cap[t], v[t]);
				
		tModel.addConstr(expr, GRB.LESS_EQUAL, 0, "cs"+t);
	}

	//Add a_ij constraints 1
	for (int t = 0; t <data.T; t++) {
		GRBLinExpr expr = new GRBLinExpr();
		for (int j = t; j < data.T; j++) {
			expr.addTerm(1, a[t][j]);
		}
		expr.addTerm(-1, y[t]);
		tModel.addConstr(expr, GRB.EQUAL, 0, "ca"+t);
	}
	//Add a_ij constraints 2
	for (int t = 0; t <data.T; t++) {
		GRBLinExpr expr = new GRBLinExpr();
		for (int j = 0; j <= t; j++) {
			expr.addTerm(1, a[j][t]);
		}
		expr.addTerm(1, s[t]);
		tModel.addConstr(expr, GRB.EQUAL, data.demand[t], "ca2"+t);
	}
	
	//Integrate constraints		
	tModel.update();
	tModel.optimize();
	
	if(tModel.get(GRB.IntAttr.Status) == GRB.INFEASIBLE){
		System.out.println("INFEASIBLE!!!!!!!!!!!!!!!!!!!!!!!!!!");
	}else{
	
	Solution sol = new Solution(data , Math.round(tModel.get(GRB.DoubleAttr.ObjVal)*100)/100.0);
		
	for(int i=0; i<data.T; i++){
		sol.y[i]=y[i].get(GRB.DoubleAttr.X);
		sol.v[i]=(int)Math.round(v[i].get(GRB.DoubleAttr.X));
		sol.I[i]=I[i].get(GRB.DoubleAttr.X);
		sol.s[i]=s[i].get(GRB.DoubleAttr.X);
	}
	calcM(data,a,sol);
		//sol.print();
	sample.add(sol);
	//System.out.println("SOL ADDED: "+sol.obj);
	}

	
	double obj = tModel.get(GRB.DoubleAttr.ObjVal);
 
	 tModel.reset();
	
	 return Math.round(obj*100)/100.0;		
	
}



}
