//
// Processor allocation problem.
// we are given a number of tasks to perform, and for each task a set of task variants
// that can perform that task. Each task variant puts a specific load on a processor and pairs of tasks 
// might need to communicate and generate load on interprocessor connections.
// We have a number of processors, each with a specified capacity. Also, links between processors 
// also have a bandwidth capacity. Problem is then to place task variants onto processors,
// respecting processor and link bandwidths
//
//
import java.util.*;
import java.io.*;
import java.io.File;
import java.io.IOException;
import java.util.Scanner;
import org.chocosolver.solver.*;
import org.chocosolver.solver.variables.*;
import org.chocosolver.solver.constraints.*;
import org.chocosolver.solver.search.strategy.*;
import org.chocosolver.solver.search.loop.monitors.*;

public class AllocationProblem {

    int nTasks;                      // number of tasks
    int nVariants;                   // number of task variants
    int nProcessors;                 // number of processors
    ArrayList[] task;                // task[i] is an array list of task variants
    int[] utilisations;              // utilisation (load) of each task variant
    int[] capacities;                // capacities of each processor, including processor 0
    int[][] links;                   // the communication bandwidth (capacity) between pairs of processors
    int[][] linkId;                  // an integer to identify a link, later used as a value of and index for a constrained integer variable
    int[][] bandwidths;              // the bandwidth between pairs of tasks
    ArrayList[] permittedProcessors; // for each task variant, the processors it may be placed on ... including zero
    int totalUtilisations;           // sum of all utilisations of task variants
    int totalBandwidth;              // sum of bandwidth load between all pairs of tasks
    int[][] interVariantLoad;        // load between variants
    int totalCommunicationsLoad;     // to be allowed on link zero
    Stack<Integer> sameProcessor;    //
    
    Solver solver;                   // the solver
    IntVar[] IVtaskVariant;          // task variants, domains are permitted processors and zero!
    IntVar[] IVprocessor;            // the load placed on a processor, where processor[0] has capacity totalUtilisation
    IntVar[][] IVtaskPair;           // a pair of task variants assigned (possibly) to a pair of processors, i.e. a link
    IntVar[][] IVlink;               // IVlink[i][j] is a bin and is the load on a link between a pair of processors i and j

     public AllocationProblem(String fname) throws IOException {
	 BufferedReader fin = new BufferedReader(new FileReader(fname));
	 StringTokenizer st = null;
	 String b = "";
	 b = fin.readLine();
	 st = new StringTokenizer(b," ");
	 System.out.println(st.nextToken());
	 nTasks = Integer.parseInt(st.nextToken());
	 b = fin.readLine();
	 st = new StringTokenizer(b," ");
	 System.out.println(st.nextToken());
	 nVariants = Integer.parseInt(st.nextToken());
	 b = fin.readLine();
	 st = new StringTokenizer(b," ");
	 System.out.println(st.nextToken());
	 nProcessors = Integer.parseInt(st.nextToken());
	 // task to variants
	 System.out.println(fin.readLine());
	 task = new ArrayList[nTasks];
	 for (int i=0;i<nTasks;i++){
	     task[i] = new ArrayList();
	     b = fin.readLine();
	     st = new StringTokenizer(b," ");
	     while (st.hasMoreTokens()) task[i].add(Integer.parseInt(st.nextToken()));
	     System.out.println(task[i]);
	 }	    
	 // utilisations
	 System.out.println(fin.readLine());
	 utilisations = new int[nVariants];
	 totalUtilisations = 0;
	 b = fin.readLine();
	 st = new StringTokenizer(b," ");
	 for (int i=0;i<nVariants;i++){
	     utilisations[i] = Integer.parseInt(st.nextToken());
	     totalUtilisations = totalUtilisations + utilisations[i];
	 }
	 for (int i=0;i<nVariants;i++) System.out.print(utilisations[i] +" ");
	 System.out.println();
	 // capacities
	 System.out.println(fin.readLine());
	 capacities = new int[nProcessors + 1];
	 b = fin.readLine();
	 st = new StringTokenizer(b," ");
	 for (int i=0;i<nProcessors;i++) capacities[i+1] = Integer.parseInt(st.nextToken());
	 for (int i=0;i<nProcessors;i++) System.out.print(capacities[i+1] +" ");
	 System.out.println();
	 // links
	 System.out.println(fin.readLine());
	 links = new int[nProcessors][nProcessors];
	 for (int i=0;i<nProcessors;i++){
	     b = fin.readLine();
	     st = new StringTokenizer(b," ");
	     for (int j=0;j<nProcessors;j++) links[i][j] = Integer.parseInt(st.nextToken());
	     for (int j=0;j<nProcessors;j++) System.out.print(links[i][j] +" ");
	     System.out.println();
	 }
	 // bandwidths
	 System.out.println(fin.readLine());
	 bandwidths = new int[nTasks][nTasks];
	 totalBandwidth = 0;
	 for (int i=0;i<nTasks;i++){
	     b = fin.readLine();
	     st = new StringTokenizer(b," ,");
	     for (int j=0;j<nTasks;j++){
		 bandwidths[i][j] = Integer.parseInt(st.nextToken());
		 totalBandwidth = totalBandwidth + bandwidths[i][j];
	     }
	     for (int j=0;j<nTasks;j++) System.out.print(bandwidths[i][j] +" ");
	     System.out.println();
	 }
	 // permitted processors
	 System.out.println(fin.readLine());
	 permittedProcessors = new ArrayList[nVariants];
	 for (int i=0;i<nVariants;i++){
	     permittedProcessors[i] = new ArrayList();
	     permittedProcessors[i].add(0);
	     b = fin.readLine();
	     st = new StringTokenizer(b," ,");
	     while (st.hasMoreTokens()) permittedProcessors[i].add(Integer.parseInt(st.nextToken()));
	     System.out.println(permittedProcessors[i]);
	 }
	 // same processor
	 sameProcessor = new Stack<Integer>();
	 System.out.println(fin.readLine());
	 b = fin.readLine();
	 while (b != null){
	     st = new StringTokenizer(b," ,");
	     while (st.hasMoreTokens()) sameProcessor.push(Integer.parseInt(st.nextToken()));
	     b = fin.readLine();
	 }
	 System.out.println(sameProcessor);
	 fin.close();
	 
	 interVariantLoad = new int[nVariants][nVariants];
	 for (int i=0;i<nTasks-1;i++)
	     for (int variant_i : (ArrayList<Integer>)task[i])
		 for (int j=i+1;j<nTasks;j++)
		     for (int variant_j : (ArrayList<Integer>)task[j]){
			 interVariantLoad[variant_i-1][variant_j-1] = interVariantLoad[variant_j-1][variant_i-1] = bandwidths[i][j];
			 totalCommunicationsLoad = totalCommunicationsLoad + bandwidths[i][j];
		     }
	 System.out.println("inter-variant load");
	 for (int i=0;i<nVariants;i++){
	     for (int j=0;j<nVariants;j++)
		     System.out.print(interVariantLoad[i][j] +" ");
	     System.out.println();
	 }
     }

    void build(){
	solver = new Solver("Any Scale Task Allocation");
	System.out.println("BUILD");

	//////////////////////////////////////
	//                                  //
	//    Respect processor capacities  //
	//                                  //
	//////////////////////////////////////

	//
	// create IVtaskVariant variables, where each variable represents a task variant
	// and has to be assigned to a processor, possibly the virtual processor 0
	// IVtask[i] is a set of task variants that can perform task[i], but only one must be executed
	//
	IVtaskVariant = new IntVar[nVariants];
	IntVar[][] IVtask = new IntVar[nTasks][]; // IVtask[i] is set of variants for task i
	for (int i=0;i<nTasks;i++){
	    IVtask[i] = new IntVar[task[i].size()]; // set of task variants for this task, as an array
	    int k = 0;
	    for (int variant : (ArrayList<Integer>)task[i]){
		int n = permittedProcessors[variant-1].size();
		int[] domain = new int[n];
		for (int j=0;j<n;j++) domain[j] = (int)permittedProcessors[variant-1].get(j);
		IVtaskVariant[variant-1] = VF.enumerated("variant_"+ variant,domain,solver);
		IVtask[i][k++] = IVtaskVariant[variant-1];
	    }
	}
	IVprocessor = new IntVar[nProcessors+1]; // allow processor[0]
	capacities[0] = totalUtilisations;
	for (int i=0;i<nProcessors+1;i++)
	    IVprocessor[i] = VF.bounded("processor_"+i,0,capacities[i],solver);

	// for a task i, all but one task variant must be allocated to processor zero
	for (int i=0;i<nTasks;i++)
	    solver.post(ICF.count(0,IVtask[i],VF.fixed(task[i].size()-1,solver)));

	// viewing a processor as a bin, pack task variants onto that bin
	//for (int i=0;i<=nProcessors;i++)
	solver.post(ICF.bin_packing(IVtaskVariant,utilisations,IVprocessor,0));
	
	////////////////////////////////////
	//                                //
	//    Respect network bandwidth   //
	//                                //
	////////////////////////////////////

	//
	// how many task variant pairs are there?
	//
	int nTaskVariantPairs = 0;
	for (int i=0;i<nTasks-1;i++)
	    for (int j=i+1;j<nTasks;j++)
		nTaskVariantPairs = nTaskVariantPairs + task[i].size() * task[j].size();
	//System.out.println("number of task/variants pairs: "+ nTaskVariantPairs);
	//
	// for all task variant pairs and all pairs of processors that they may be placed on
	// post a constratint that if task variants i and j are on processors p and q
	// then taskPair[i][j] = linkId[p][q], i.e they load up on the link between p and q
	//
	int numberOfLinks = (nProcessors * (nProcessors-1))/2;
	linkId = new int[nProcessors+1][nProcessors+1];
	for (int i=1,k=1;i<nProcessors;i++)
	    for (int j=i+1;j<=nProcessors;j++,k++)
		linkId[i][j] = linkId[j][i] = k;
	IVtaskPair = new IntVar[nVariants+1][nVariants+1];
	for (int i=0;i<nTasks-1;i++)
	    for (int variant_i : (ArrayList<Integer>)task[i])
		for (int j=i+1;j<nTasks;j++)
		    for (int variant_j : (ArrayList<Integer>)task[j]){
			IVtaskPair[variant_i-1][variant_j-1] = VF.bounded("taskPair_"+ variant_i +","+ variant_j,0,numberOfLinks,solver);
			for (int processor_i : (ArrayList<Integer>)permittedProcessors[variant_i-1])
			    for (int processor_j : (ArrayList<Integer>)permittedProcessors[variant_j-1]){
				//System.out.println("("+ variant_i +"/"+ processor_i +","+ 
				//		   variant_j +"/"+ processor_j +") = linkId: "+
				//		   linkId[processor_i][processor_j]);
				Constraint c1 = ICF.arithm(IVtaskVariant[variant_i-1],"=",processor_i);
				Constraint c2 = ICF.arithm(IVtaskVariant[variant_j-1],"=",processor_j);
				Constraint c3 = ICF.arithm(IVtaskPair[variant_i-1][variant_j-1],"=",linkId[processor_i][processor_j]);
				LCF.ifThen(LCF.and(new Constraint[]{c1,c2}),c3);
			    }
		    }
	//
	//
	//
	IVlink = new IntVar[nProcessors+1][nProcessors+1]; // bandwidth between pairs of processors
	for (int i=1;i<nProcessors;i++)
	    for (int j=i+1;j<nProcessors+1;j++)
		IVlink[i][j] = IVlink[j][i] = VF.bounded("link_"+ i +","+ j,0,links[i-1][j-1],solver);
	//for (int i=0;i<nProcessors;i++)
	//   for (int j=i+1;j<nProcessors+1;j++)
	//	System.out.println("linkId: "+ linkId[i][j] +" ("+ i +","+ j +") = "+ IVlink[i][j]);
	// flatten IVlink for packing
	IntVar[] IVflatLink = new IntVar[numberOfLinks+1];
	IVflatLink[0] = VF.bounded("linkInf",0,totalCommunicationsLoad,solver); //link with unbounded bandwidth
	for (int i=1,k=1;i<nProcessors;i++)
	    for (int j=i+1;j<=nProcessors;j++)
		IVflatLink[k++] = IVlink[i][j];
	IntVar[] IVflatTaskPair = new IntVar[nTaskVariantPairs];
	int[] flatLoad = new int[nTaskVariantPairs];
	for (int i=0,k=0;i<nTasks-1;i++)
	    for (int variant_i : (ArrayList<Integer>)task[i])
		for (int j=i+1;j<nTasks;j++)
		    for (int variant_j : (ArrayList<Integer>)task[j])
			if (IVtaskPair[variant_i-1][variant_j-1] != null){
			    //System.out.println("("+ i +"-"+ variant_i +","+ j +"-"+ variant_j +")");
			    IVflatTaskPair[k] = IVtaskPair[variant_i-1][variant_j-1];
			    flatLoad[k] = interVariantLoad[variant_i-1][variant_j-1]; //bandwidths[i][j];
			    k++;
			}

        //for (int i=0;i<flatLoad.length;i++)
	//    System.out.println(IVflatTaskPair[i] +" load: "+ flatLoad[i]);

	//for (int i=0;i<IVflatLink.length;i++)
	//    System.out.println(IVflatLink[i]);

	solver.post(ICF.bin_packing(IVflatTaskPair,flatLoad,IVflatLink,0));

	////////////////////////////////////
	//                                //
	//         same processors        //
	//                                //
	////////////////////////////////////
	while (!sameProcessor.isEmpty()){
	    int task_i = sameProcessor.pop();
	    int task_j = sameProcessor.pop();
	    for (int i : (ArrayList<Integer>)task[task_i-1])
		for (int j : (ArrayList<Integer>)task[task_j-1]){
		    Constraint c1 = ICF.arithm(IVtaskVariant[i-1],"!=",0);
		    Constraint c2 = ICF.arithm(IVtaskVariant[j-1],"!=",0);
		    Constraint c3 = ICF.arithm(IVtaskVariant[i-1],"=",IVtaskVariant[j-1]);
		    LCF.ifThen(LCF.and(new Constraint[]{c1,c2}),c3);
		    //System.out.println(c1 +" and "+ c2 +" -> "+ c3);
		}
	}
    }

    public static void main(String[] args)  throws IOException {
	AllocationProblem p = new AllocationProblem(args[0]);
	p.build();
	p.solver.findSolution();
	// 
	// NOTE: variable ordering over decision variables wich will be IVtaskVariant
	//       also deliver run time statistics
	//
	for (IntVar variant : p.IVtaskVariant) System.out.println(variant);
    }
}