/**
 * 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 backwardSampling;

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

import java.util.ArrayList;

import DIKBD.DIKBD;
import DIKBD.DIKBD_Graph;
import DIKBD.DIKBD_Vertex;
import sampling.DukqstraDist;
import sampling.DukqstraTime;
import sampling.FinalNode;
import sampling.PulseGraph;
import sampling.ShortestPathTask;


public class AlgorithmHandler {

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

	int zbar; 								// Best upper bound
	int perDamage;							// Damaged perceived
	int 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<Integer> wListRealDamage; 	// Waiting list real damage
	double epsilon;							// Control for the waiting list
	
	public static long sampleTime;			//Sample time 
	public static int sTimeLimit;			//Sample time limit
	public static boolean continueSampling;	//Sample boolean
		
	boolean masterFeasible;				 	// If the fortification problem is feasible
	boolean globalStop;						// Stopping criterion for the backward sampling	
		
	static public ArrayList<ArrayList<Integer>> sample;		// Current sample
	static public ArrayList<Integer> sampleObj;				// Sample objectives
	static public int sampleSizeLimit;						
	public static int arcLimit;

	PulseGraph network;										// The network
	
	GRBEnv env;												// Gurobi Environment
	GRBModel dModel;										// Gurobi defender's model
	GRBModel aModel;										// Gurobi attacker's model
	
	DIKBD_Graph G;											// SP Network
	
	// Some performance measures
	long hatTime;
	long maxMinTime;
	int maxMinIter;
	int wHatEval;
	int aborted;
	
	
	public AlgorithmHandler(DataHandler data) throws GRBException, InterruptedException {
		
		w=new int[data.numArcs];
		x=new int[data.numArcs];
		zbar = 999999999;
		perDamage = (int) Double.POSITIVE_INFINITY;
		realDamage = 0;
		masterFeasible = true;
		globalStop = false;
		sample = new ArrayList<ArrayList<Integer>>();
		sampleObj = new ArrayList<Integer>();
		cutPool = new ArrayList<int[]>();
		guessCutPool = new ArrayList<int[]>();
		waitingList = new ArrayList<int[]>();
		wListRealDamage = new ArrayList<Integer>();
		
		env = new GRBEnv(null);
		env.set(GRB.IntParam.OutputFlag, 0);
		env.set(GRB.DoubleParam.MIPGap, 10E-12);
		
		sampleSizeLimit = 100;
		arcLimit = 20;
		sTimeLimit = 1;
		
		epsilon = 0.1;
		
		hatTime = 0;
		maxMinTime = 0;
		maxMinIter = 0;
		wHatEval = 0;
		aborted = 0;
		
		// Sampling initialization
		// Create the network 					 
		network = data.getGd();
		network.setPrimalBound((int) Double.POSITIVE_INFINITY);
		network.setWidth(1.01);
		// Create two threads for the initialization		
		Thread tTime = new Thread();
		Thread tDist = new Thread();
		// Reverse the network and run SP for distance and time 
		DukqstraDist spDist = new DukqstraDist(network, data.lastNode);
		DukqstraTime spTime = new DukqstraTime(network, data.lastNode);
		tDist = new Thread(new ShortestPathTask(1, spDist, null));
		tTime = new Thread(new ShortestPathTask(0, null,  spTime));
		tDist.start();
		tTime.start();
		tDist.join();
		tTime.join();
		
	}



	public void solveDefenderProblem(DataHandler data) throws GRBException {
		long auxT = System.currentTimeMillis();
		dModel = new GRBModel(env);
		dModel.reset();
		masterFeasible=true;
		
		GRBVar[] wt = new GRBVar[data.numArcs];
		//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.numArcs; 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.numArcs; 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.numArcs; 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.numArcs; i++){
		    	w[i]=(int) wt[i].get(GRB.DoubleAttr.X);
		     }
		//	printw(data);
		
		}

	}

	public void printw(DataHandler data) {
		System.out.println("		Defense: ");
		for(int j=0; j<data.numArcs; j++){
			 if(w[j]>0)
			 System.out.println("		w"+j+": "+w[j]);
		 }	
	}	
public int solveAux(DataHandler data) throws GRBException {
		long auxT = System.currentTimeMillis();
		
		aModel = new GRBModel(env);
		
		GRBVar[] xt = new GRBVar[data.numArcs];
		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 path in the sample
		for (int j = 0; j <AlgorithmHandler.sample.size(); j++) {
			GRBLinExpr expr = new GRBLinExpr();
				for (int i = 0; i < AlgorithmHandler.sample.get(j).size(); i++) {
					int boundedDelay =Math.min(data.delay[AlgorithmHandler.sample.get(j).get(i)], (zbar+1-AlgorithmHandler.sampleObj.get(j)));
					boundedDelay = Math.max(boundedDelay, 0);
					expr.addTerm(boundedDelay, xt[AlgorithmHandler.sample.get(j).get(i)]);
				}
				expr.addTerm(-1, z);
			
			aModel.addConstr(expr, GRB.GREATER_EQUAL, -AlgorithmHandler.sampleObj.get(j), "c"+j);
		}
		
		//Add budget constraint
		GRBLinExpr budgetExpr = new GRBLinExpr();
		
		for (int j = 0; j <data.numArcs; 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);
		aModel.addConstr(boundExpr, GRB.LESS_EQUAL, (zbar+1), "cbound");
		
		//Integrate constraints		
		aModel.update();
		
		aModel.optimize();
		
		maxMinIter++;
		maxMinTime+=(System.currentTimeMillis() - auxT);

		//Update attack plan
		for(int i=0; i<data.numArcs; i++){
	    	x[i]=(int) Math.round(xt[i].get(GRB.DoubleAttr.X));
	     }
				
		double auxObj = (-1)*aModel.get(GRB.DoubleAttr.ObjVal);
		
		int obj = (int) Math.round(auxObj);
		
		// Print results
		/* System.out.println("		Aux obj:"+(-1)*aModel.get(GRB.DoubleAttr.ObjVal));
		 	 for(int i=0; i<data.numArcs; 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.numArcs; j++){
				 if(wstar[j]>0)
				 System.out.println("		w"+j+": "+wstar[j]);
			 }	
			System.out.println("		Optimal attack: ");
			for(int j=0; j<data.numArcs; j++){
				 if(xstar[j]>0)
				 System.out.println("		x"+j+": "+xstar[j]);
			 }
	
	
	}
	
	public void sample(DataHandler data) throws InterruptedException {
		
		sampleTime = System.currentTimeMillis();
		continueSampling = true;
		
		// Set the first primal bound
		network.setObj(zbar);
		// Reset network
		network.resetNetwork();
		
		
///////////////////////////////////// PULSE SAMPLE /////////////////////////////////////////////////////////////
		
		// Create an empty path
		ArrayList<Integer> path = new ArrayList<Integer>();
		// Create an empty path
		ArrayList<Integer> pathArcs = new ArrayList<Integer>();
		// Pulse the origin node
		network.getVertexByID(data.source).pulse(0, 0, path,pathArcs);
		if(sample.size() == 0){System.out.println("NOOOO FATAL ERROR SAMPLE IS EMPTY!");}
		
	//	System.out.println("SAMPLE SIZE: "+sample.size());
		
		
	/*	for (int i = 0; i < sample.size(); i++) {
			System.out.println(sample.get(i)+" Cost: "+sampleObj.get(i));
		}
	*/
	}


	private void updateSample(DataHandler data) {

		for (int i = 0; i < sample.size(); i++) {
			if(sampleObj.get(i)>zbar){
				for (int j = 0; j < sample.get(i).size(); j++) {
					data.arcCount[sample.get(i).get(j)]--;
				}
								
				sampleObj.remove(i);
				sample.remove(i);
				i--;
			}
		}
						
	}


	public int shortestPath(DataHandler data, int[] xcut) {
		
		// SP Initialization
		G = new DIKBD_Graph(data.numNodes);

		//Adding vertexes
		for (int i = 0; i < data.numNodes; i++) {
			G.addVertex(new DIKBD_Vertex(i) );
		}
		//Adding Edges
		for (int i = 0; i < data.numArcs; i++) {
			if(Math.round(xcut[i])==0){
			G.addWeightedEdge( G.getVertexByID(data.arcs[i][0]), G.getVertexByID(data.arcs[i][1]),data.cost[i], i);
			}
			else{
			G.addWeightedEdge( G.getVertexByID(data.arcs[i][0]), G.getVertexByID(data.arcs[i][1]),data.cost[i]+data.delay[i], i);
			}
		}
		
	
		
		//Run SP algorithm
		DIKBD spDist = new DIKBD(G, data.source);
		spDist.runAlgDist();
		
		//ArrayList<Integer> path = new ArrayList<Integer>();
		//System.out.println("Shortest Path: "+G.getPath(data.lastNode, path)+" Cost: "+G.getVertexByID(data.lastNode).getMinDist());
		
		ArrayList<Integer> pathArcs = new ArrayList<Integer>();
		pathArcs = G.getPathArcs(data.lastNode, pathArcs); 
		
		int interdictedCost = G.getVertexByID(data.lastNode).getMinDist();
		
		int uninterdictedCost = 0;
		for (int i = 0; i < pathArcs.size(); i++) {
			uninterdictedCost=uninterdictedCost+data.cost[pathArcs.get(i)];
		}
		
		addSample(pathArcs, uninterdictedCost);
		
		//System.out.println("SP COST: "+cost);
		
		return interdictedCost;
	}




public void addSample(ArrayList<Integer> pathArcs, int obj) {
	
	for (int i = 0; i < pathArcs.size(); i++) {
		DataHandler.arcCount[pathArcs.get(i)]++;
	}
	
		AlgorithmHandler.sample.add(copy(pathArcs));
		AlgorithmHandler.sampleObj.add(obj);
			
				
}

private ArrayList<Integer> copy(ArrayList<Integer> pathArcs) {
	
	ArrayList<Integer> copy = new ArrayList<Integer>();
	copy.addAll(pathArcs);
	return copy;
}


// 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 = (int) Double.POSITIVE_INFINITY;
		realDamage = 0;
//	System.out.println("**********************************************************************************************");
		while(realDamage < zbar && (System.nanoTime()-Atime)/1000000000<timeLimit){
			// Get the perceived damage
			perDamage = solveAux(data);
			// Get the real damage
			realDamage = shortestPath(data, x);	//new path is added to sample inside this method
			//			System.out.println("P: "+perDamage+" R: "+realDamage+" ZBAR: "+zbar);
			// Update zbar and the sample
			if (perDamage < zbar) {
				zbar = perDamage;
				realDamage = 0;
				updateSample(data);
				sample(data);
			}
			// 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++;
			}
		}
	}
}


// This method revisits the solutions stored in the waiting list
public void evaluateGuessPool(DataHandler data , double Atime) throws GRBException, InterruptedException {
	double originalEpsilon = this.epsilon;
	masterFeasible = true;
	epsilon = -1;
	
	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));
			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--;
	} 
	
	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.numArcs; j++) {
					sum+=cutPool.get(i)[j]*w_hat[j];
				}
				if (sum < 1){
					return false;
				}
				
			}
	
	return true;
}






}
