import java.util.*;


public class CommonFunctions{
    
    //public static double[] rho;
    //public static double[] frequency;

    /* for tests en static */
    static double[] rho = {1.0, 1.1, 1.2, 1.3, 1.4, 1.5};
    static double[] frequency = {0.3, 0.4, 0.4, 0.3, 0.5, 0.9, 0.2}; 	   

    static final int TOP_DOWN_BFS = 1;
    static final int TOP_DOWN_DFS = 2;
    static final int BOTTOM_UP_BFS = 3;
    static final int BOTTOM_UP_DFS = 4;
    static final int RANDOM = 5; 
    static final int RANDOM_SIMPLE = 6;
    //static final int GREEDY = 7;

    static final int FASTEST = 0; /* ohne zuruecklegen */
    static final int NETWORK_CARD = 1;  /* ohne zuruecklegen */
    static final int REMAINING_BW = 2; /* mit zureucklegen */
    static final int REMAINING_CPU = 3; /* mit zuruecklegen */
    
    public static ArrayList<Proc> usedProcs;

    public static void setRhoAndFrequency(double[] rrho, double[] ffrequency) {
	rho = new double[rrho.length];
	frequency = new double[ffrequency.length];

	for(int i = 0; i < rrho.length; i++) {
	    rho[i] = rrho[i];
	    frequency[i] = ffrequency[i];
	}
    }


    public static void traverseTree(Operator root) {
	if(CompileTimeCondition.DEBUG)
	    System.out.println(root.toStringLong());
	for(Operator op : root.operators) {
	    traverseTree(op);
	}
	
    }


    public static boolean isAncestor(Operator op, Operator ancestor) {
	Operator tmp;
	while(op.id <= ancestor.id) {
	    //System.out.println("act: "+op+", ancestor: "+ancestor);
	    if(op.father.equals(ancestor)) return true;
	    else {
		tmp = op.father;
		op = tmp;
	    }
	}
	return false;
    }

    private static Operator getGenOp(Operator actOp) {
	int genOpPos = RunHeuristics.operators.indexOf(actOp);
	return RunHeuristics.operators.get(genOpPos);
    }
    
    private static double getRhoMaxOfOperators(Proc proc) {
	double rhoMax = 0.0;
	
	for(Operator op : proc.assignedOperators) {
	    Operator genOp = getGenOp(op);
	    if(rho[genOp.app] > rhoMax) 
		rhoMax = rho[genOp.app];
	}
	return rhoMax;
    }

    public static void printMapping(Mapping mapping) {
	System.out.println("usedProcs size: "+mapping.usedProcs.size());
	for(Proc proc : mapping.usedProcs) {
	    System.out.println(proc+":");
	    for(Operator op : proc.assignedOperators)
		System.out.println(op+" app"+op.app);
	    System.out.println("");
	}

// 	for(Operator op : RunHeuristics.operators) {
// 	    System.out.println("\n"+op+":");
// 	    for(Proc proc : op.procs)
// 		System.out.print(proc+"\t");
// 	}
	
	System.out.println("");
	for(Proc proc : mapping.usedProcs) {
	    System.out.println(proc+":\nchildren:");
	    for(Operator op : proc.children)
		System.out.println(op+" app"+op.app);
	    
	    System.out.println(proc+":\nfathers:");
	    for(Operator op : proc.fathers)
		System.out.println(op+" app"+op.app);
	    System.out.println("");
	}
	
    }


   private static DownloadObjectAssignment findProcForDownload(BasicObject genOb, Proc actProc) {

	double best = Double.MAX_VALUE;
	Proc bestProc = null;

	for(Proc proc : usedProcs) {
	    if (proc.holds.contains(genOb) && actProc.links[proc.id] < best) {
		bestProc = proc;
		best = actProc.links[proc.id];
	    }		
	}
	for(Proc proc : RunHeuristics.procs) {
	    if (proc.holds.contains(genOb) && actProc.links[proc.id] < best) {
		bestProc = proc;
		best = actProc.links[proc.id];
	    }		
	}
	if(CompileTimeCondition.BIG_OUTPUT)
	    System.out.println(bestProc+" is the best proc for the download of "+genOb);
	DownloadObjectAssignment ass = new DownloadObjectAssignment(genOb, bestProc);
	return ass;
    }
			

    /* verifies if op can be mapped on the child  proc(s), if so, op is mapped (return true), else returns false */
    public static boolean mapOpOnChildProc(Operator actOp, Proc actProc, int heuristic) {
	double rhoMax;
	boolean success = false;
	double successCard = (-1.0);

// 	int opPos = operators.indexOf(actOp);
// 	Operator generalOp = operators.get(opPos);
// 	rhoMax = rho[generalOp.app];	

	Operator generalOp = getGenOp(actOp);
	rhoMax = getRhoMaxOfOperators(actProc);

	double sumCPU = actProc.actSumCPU + (actOp.w/actProc.cpu)*rhoMax;
	

	
	if(sumCPU <= 1) success = true;
	
	/* cpu power is sufficient, continue checking the comms */
	if(success) {
	    successCard = checkNetworkCardCapacity(actOp, actProc, heuristic);
	    if(successCard > 0.0)
		if(CompileTimeCondition.BIG_OUTPUT) 
		System.out.println("network card capacity holds, new usage:"+successCard);
	    else 
		if(CompileTimeCondition.BIG_OUTPUT)
		System.out.println("network card capacity does NOT hold");
	    
	    //System.out.println("network card capacity holds, new usage:"+successCard);
	    // boolean successLinks =  checkLinks(actOp, actProc);
	    //System.out.println("link check: "+successLinks);
	    boolean successParentThroughput =  checkThroughputParents(actOp, actProc, heuristic);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("parent comm throughput: "+successParentThroughput);
	    boolean successChildrenThroughput =  checkThroughputChildren(actOp, actProc, heuristic);
	    if(CompileTimeCondition.DEBUG)
	    System.out.println("children comm throughput: "+successChildrenThroughput);
	    
	    // if(!((successCard > 0)  && successLinks && successParentThroughput && successChildrenThroughput)) {
	    if(!((successCard > 0)  && successParentThroughput && successChildrenThroughput)) {
		success = false;
	    }
	}
	if(success)
	    if(CompileTimeCondition.BIG_OUTPUT)
		System.out.println("ALL tests succeeded, performing the mapping of "+actOp+" on "+actProc);	
	    else
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("tests FAILED, mapping of "+actOp+" on "+actProc+" NOT POSSIBLE");	
	//System.out.println(	
	/* cpu power, network card and comms passed the test */
	if (success) {
	    
	    actOp.isMapped = true;
	    actOp.procs.add(actProc);
	    generalOp.isMapped = true;
	    if(!generalOp.procs.contains(actProc))
		generalOp.procs.add(actProc);
 
	    for(BasicObject ob : actOp.objects) {
		if(!actProc.holds.contains(ob) && actProc.download(ob) == null) { 
		    int genObPos = RunHeuristics.objects.indexOf(ob);
		    BasicObject genOb = RunHeuristics.objects.get(genObPos);
		    DownloadObjectAssignment ass = findProcForDownload(genOb, actProc);
			actProc.downloads.add(ass);
			//if(!usedProcs.contains(ass.proc))
			//   usedProcs.add(ass.proc);
		}
	    }
	    // for(BasicObject ob : actOp.objects) {
// 		if(!actProc.holds.contains(ob) && !actProc.downloads.contains(ob)) {
// 		    actProc.downloads.add(ob);
// 		}
// 	    }
	    
	    actProc.actSumCPU +=  (actOp.w/actProc.cpu)*rhoMax;
	    actProc.bwUsage = successCard;
	    actProc.assignedOperators.add(actOp);

	    actProc.fathers.removeExactly(actOp);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("Removing "+actOp+" from fathersList of "+actProc);
	    

	    // if(actOp.id == 14) System.out.println("I am "+actOp+" and my father is "+actOp.father);
	    if(!actProc.assignedOperators.contains(actOp.father) && actOp.father.id > 0 && !actProc.fathers.containsExactly(actOp.father)) {
		actProc.fathers.add(actOp.father);
		if(CompileTimeCondition.DEBUG)
		    System.out.println("adding father "+actOp.father+" to fathersList of "+actProc);
	    }
	       

		for(Operator child: actOp.operators) 
		    if(!actProc.children.contains(child)) {
			if(actProc.assignedOperators.contains(child)) {
			    if(CompileTimeCondition.DEBUG)
				System.out.println("Normalerweise muss doch jetzt "+child+" nicht hinzugefuegt weden, da "+
						   actProc+" op"+child.id+" schon berechnet. oder nicht?");
			} else {
			    if(actOp.newChildren.contains(child)) {
				int childPos = actOp.newChildren.indexOf(child);
				Operator newChild = actOp.newChildren.get(childPos);
				actProc.children.add(newChild);
				if(CompileTimeCondition.DEBUG)
				    System.out.println("Adding "+newChild+" (the newChild of an added link) to childrensList of "+actProc);
				
			    } else {
				if(CompileTimeCondition.DEBUG)
				    System.out.println("out here");
				actProc.children.add(child);
				if(CompileTimeCondition.DEBUG)
				    System.out.println("Adding "+child+" to childrensList of "+actProc);
			    }
			}
			
		    }
		// }
	}
	
	return success;
    }    
    
    /* verifies if op can be mapped on the (or one of the) father proc(s), if so, op is mapped (return true), else returns false */
    public static boolean mapOpOnFatherProc(Operator actOp, Proc actProc, int heuristic) {
	double rhoMax;
	boolean success = false;
	double successCard = (-1.0);

// 	int opPos = operators.indexOf(actOp);
// 	Operator generalOp = operators.get(opPos);
// 	rhoMax = rho[generalOp.app];	

	Operator generalOp = getGenOp(actOp);
	rhoMax = getRhoMaxOfOperators(actProc);

	double sumCPU = actProc.actSumCPU + (actOp.w/actProc.cpu)*rhoMax;
	

	
	if(sumCPU <= 1) success = true;
	
	/* cpu power is sufficient, continue checking the comms */
	if(success) {
	    successCard = checkNetworkCardCapacity(actOp, actProc, heuristic);
	    if(successCard > 0.0) 
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("network card capacity holds, new usage:"+successCard);
	    else 
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("network card capacity does NOT hold");
	    
	    //System.out.println("network card capacity holds, new usage:"+successCard);
	    // boolean successLinks =  checkLinks(actOp, actProc);
	    //System.out.println("link check: "+successLinks);
	    //boolean successParentThroughput =  checkThroughputParents(actOp, actProc);
	    //System.out.println("parent comm throughput: "+successParentThroughput);
	    boolean successChildrenThroughput =  checkThroughputChildren(actOp, actProc, heuristic);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("children comm throughput: "+successChildrenThroughput);
	    
	    // if(!((successCard > 0)  && successLinks && successParentThroughput && successChildrenThroughput)) {
	    if(!((successCard > 0)  && successChildrenThroughput)) {
		success = false;
	    }
	}

  	if(success)
	    if(CompileTimeCondition.BIG_OUTPUT)
		System.out.println("ALL tests secceeded, performing the mapping of "+actOp+" on "+actProc);	
	    else
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("tests FAILED, mapping of "+actOp+" on "+actProc+" NOT POSSIBLE");	
	
	/* cpu power, network card and comms passed the test */
	if (success) {
	    
	    actOp.isMapped = true;
	    actOp.procs.add(actProc);
	    generalOp.isMapped = true;
	    if(!generalOp.procs.contains(actProc))
		generalOp.procs.add(actProc);
 
	    for(BasicObject ob : actOp.objects) {
		if(!actProc.holds.contains(ob) && actProc.download(ob) == null) { 
		    int genObPos = RunHeuristics.objects.indexOf(ob);
		    BasicObject genOb = RunHeuristics.objects.get(genObPos);
		    DownloadObjectAssignment ass = findProcForDownload(genOb, actProc);
			actProc.downloads.add(ass);
			//if(!usedProcs.contains(ass.proc))
			//   usedProcs.add(ass.proc);
		}
	    }
	    // for(BasicObject ob : actOp.objects) {
// 		if(!actProc.holds.contains(ob) && !actProc.downloads.contains(ob)) {
// 		    actProc.downloads.add(ob);
// 		}
// 	    }
	    
	    actProc.actSumCPU +=  (actOp.w/actProc.cpu)*rhoMax;
	    actProc.bwUsage = successCard;
	    actProc.assignedOperators.add(actOp);

	    actProc.children.removeExactly(actOp);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("Removing "+actOp+" from childrensList of "+actProc);
	    
	    for(Operator child: actOp.operators) 
		if(!actProc.children.contains(child)) {
		    if(actProc.assignedOperators.contains(child)) {
			if(CompileTimeCondition.DEBUG)
			    System.out.println("Normalerweise muss doch jetzt "+child+" nicht hinzugefuegt weden, da "+
					       actProc+" op"+child.id+" schon berechnet. oder nicht?");
		    } else {
			actProc.children.add(child);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("Adding "+child+" to childrensList of "+actProc);
		    }
		    
		}
	}
	
	return success;
    }    
 


    /* verifies if op can be mapped on proc, if so, op is mapped (return true), else returns false */
    public static boolean mapOpOnProc(Operator actOp, Proc actProc, int heuristic) {
	double rhoMax;
	boolean success = false;
	double successCard = (-1.0);

// 	int opPos = operators.indexOf(actOp);
// 	Operator generalOp = operators.get(opPos);
	Operator generalOp = getGenOp(actOp);
	if(CompileTimeCondition.DEBUG)
	    System.out.println("app of genOp: "+generalOp.app); 
	rhoMax = rho[generalOp.app];	

	if(actProc.assignedOperators.contains(actOp) && heuristic != RANDOM_SIMPLE) {
	    
		
		System.out.println("@@@@@@@@@@@@@@ ALERT @@@@@@@@@");
		System.out.println(actProc+" contains already an op"+actOp.id);
		System.out.println("no need to continue with this proc");
		//System.out.println("trying to add the additional communications !!!!!!!!!!! TODO !!!!!!!!!!!!!!!!!!!!");
		//succes s= addAdditionalComm(actOp, actProc, heuristic);
		success = false;
	  
	  
	} else {
	
	    double sumCPU;
	    
	    if(actProc.assignedOperators.contains(actOp))
		/* heuristic: RANDOM_SIMPLE */
		/* in this case, op can be remapped on a proc, cpu remains unchangend, comms not */
		sumCPU = 0.0;
	    else 
		sumCPU = actProc.actSumCPU + (actOp.w/actProc.cpu)*rhoMax;	
	    
	    
	    if(sumCPU <= 1) success = true;
	    
	    /* cpu power is sufficient, continue checking the comms */
	    if(success) {
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("cpu check was successful, sumCPU: "+ sumCPU);
		successCard = checkNetworkCardCapacity(actOp, actProc, heuristic);
		if(successCard > 0.0) { 
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("network card capacity holds, new usage:"+successCard);
		    boolean successLinks =  checkLinks(actOp, actProc, heuristic);
		    if(successLinks) {
			if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("link check was SUCCESSFUL");
			boolean successParentThroughput =  checkThroughputParents(actOp, actProc, heuristic);
			if(successParentThroughput) {
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("parent comm throughput HOLDS");
			    boolean successChildrenThroughput =  checkThroughputChildren(actOp, actProc, heuristic);
			    if(successChildrenThroughput) {
				if(CompileTimeCondition.BIG_OUTPUT)
				    System.out.println("children comm throughput HOLDS");
			    } else {
				if(CompileTimeCondition.BIG_OUTPUT)
				    System.out.println("children comm throughput does NOT hold");
				success = false;
			    }		    
			} else {
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("parent throughput does NOT hold");
			    success = false;
			}
		    } else {
			if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("link check FAILED");
		    	success = false;
		    }
		} else { 
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("network card capacity does NOT hold");
		    success = false;
		}
	    }
	    if(success)
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("ALL tests secceeded, performing the mapping of "+actOp+" on "+actProc);	
		else 
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("tests FAILED, mapping of "+actOp+" on "+actProc+" NOT POSSIBLE");	
	    
	    /* cpu power, network card and comms passed the test */
	    if (success) {
		
		actOp.isMapped = true;
		actOp.procs.add(actProc);
		generalOp.isMapped = true;
		if(!generalOp.procs.contains(actProc))
		    generalOp.procs.add(actProc);
		
		for(BasicObject ob : actOp.objects) {
		    if(!actProc.holds.contains(ob) && actProc.download(ob) == null) { 
			int genObPos = RunHeuristics.objects.indexOf(ob);
			BasicObject genOb =  RunHeuristics.objects.get(genObPos);
			DownloadObjectAssignment ass = findProcForDownload(genOb, actProc);
			actProc.downloads.add(ass);
		
		    }
		}
		actProc.bwUsage = successCard;
		if(!actProc.assignedOperators.contains(actOp))	
		    actProc.actSumCPU +=  (actOp.w/actProc.cpu)*rhoMax;
		
		actProc.assignedOperators.add(actOp);
		

		if(actProc.children.contains(actOp)) {
		    actProc.children.removeExactly(actOp);
		    if(CompileTimeCondition.DEBUG)		    
			System.out.println("Removing "+actOp+" from childrensList of "+actProc);
		}
		
		if(!actProc.assignedOperators.contains(actOp)) {
		    for(Operator op : actOp.operators) 
			if(!actProc.children.contains(op)) { 
			    //    actProc.children.add(op);
			    //System.out.println("Adding "+op+" to childrensList of "+actProc);
			    if(actProc.assignedOperators.contains(op)) {
				if(CompileTimeCondition.DEBUG)
				    System.out.println("Normalerweise muss doch jetzt "+op+" nicht hinzugefuegt weden, da "+
						       actProc+" op"+op.id+" schon berechnet. oder nicht?");
			    } else {
				if(actOp.newChildren.contains(op)) {
				    int childPos = actOp.newChildren.indexOf(op);
				    Operator newChild = actOp.newChildren.get(childPos);
				    actProc.children.add(newChild);
				    if(CompileTimeCondition.DEBUG)
					System.out.println("Adding "+newChild+" (the newChild of an added link) to childrensList of "+actProc);
				    
				} else {	
				    actProc.children.add(op);
				    if(CompileTimeCondition.DEBUG)
					System.out.println("Adding "+op+" to childrensList of "+actProc);
				}
			    }
			}
		    if(!actProc.fathers.contains(actOp.father) && actOp.father.id >= 0){
			actProc.fathers.add(actOp.father);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("adding "+actOp.father+" to fathersList of "+actProc);
		    }
		} else {
		    for(Operator op : actOp.operators) 
			if(!actProc.children.contains(op)) { 
			    //    actProc.children.add(op);
			    //System.out.println("Adding "+op+" to childrensList of "+actProc);
			    if(actProc.assignedOperators.containsExactly(op)) {
				if(CompileTimeCondition.DEBUG)				
				    System.out.println("Normalerweise muss doch jetzt "+op+" nicht hinzugefuegt weden, da "+
						       actProc+" op"+op.id+" schon berechnet. oder nicht?");
			    } else {	
				if(actOp.newChildren.contains(op)) {
				    int childPos = actOp.newChildren.indexOf(op);
				    Operator newChild = actOp.newChildren.get(childPos);
				    actProc.children.add(newChild);
				    if(CompileTimeCondition.DEBUG)
					System.out.println("Adding "+newChild+" (the newChild of an added link) to childrensList of "+actProc);
				} else {
				    actProc.children.add(op);
				    if(CompileTimeCondition.DEBUG)
					System.out.println("Adding "+op+" to childrensList of "+actProc);
				}
			    }
			}
		    if(!actProc.fathers.containsExactly(actOp.father) && actOp.father.id >= 0){
			actProc.fathers.add(actOp.father);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("adding "+actOp.father+" to fathersList of "+actProc);
		    }
		}
		
	    } /* end else: proc does not contain act op && !RANDOM_SIMPLE */
	}
	return success;
    }    
    
    /* verifies if op can be mapped on proc, but does not do the mapping!!! this is used for adding a fatherlink */
    /* returns the new cardUsage, if op would be mapped on proc, negative value if not possible */
    public static double tryToMapOpOnProc(Operator actOp, Proc actProc, int heuristic) {
	double rhoMax;
	boolean success = false;
	double successCard = (-1.0);
	
	Operator generalOp = getGenOp(actOp);
	if(CompileTimeCondition.DEBUG)
	    System.out.println("app of genOp: "+generalOp.app); 
	rhoMax = rho[generalOp.app];	

	double sumCPU = actProc.actSumCPU + (actOp.w/actProc.cpu)*rhoMax;	

	
	if(sumCPU <= 1) success = true;
	
	/* cpu power is sufficient, continue checking the comms */
	if(success) {
	    if(CompileTimeCondition.BIG_OUTPUT)
		System.out.println("cpu check was successful, sumCPU: "+ sumCPU);
	    successCard = checkNetworkCardCapacity(actOp, actProc, heuristic);
	    if(successCard > 0.0) { 
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("network card capacity holds, new usage:"+successCard);
		boolean successLinks =  checkLinks(actOp, actProc, heuristic);
		if(successLinks) {
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("link check was SUCCESSFUL");
		    boolean successParentThroughput =  checkThroughputParents(actOp, actProc, heuristic);
		    if(successParentThroughput) {
			if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("parent comm throughput HOLDS");
			boolean successChildrenThroughput =  checkThroughputChildren(actOp, actProc, heuristic);
			if(successChildrenThroughput) {
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("children comm throughput HOLDS");
			} else {
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("children comm throughput does NOT hold");
			    success = false;
			}		    
		    } else {
			if(CompileTimeCondition.BIG_OUTPUT)			    
			    System.out.println("parent throughput does NOT hold");
			success = false;
		    }
		} else {
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("link check FAILED");
		    success = false;
		}
	    } else { 
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("network card capacity does NOT hold");
		success = false;
	    }
	}
	// 	if(!((successCard > 0)  && successLinks && successParentThroughput && successChildrenThroughput)) {
// 	    success = false;
// 	}
	
	if(success)
	    if(CompileTimeCondition.BIG_OUTPUT)
		System.out.println("ALL tests secceeded, mapping of "+actOp+" on "+actProc+" IS POSSIBLE");	
	    else
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("tests FAILED, mapping of "+actOp+" on "+actProc+" NOT POSSIBLE");	
	
	if(success)	
	    return successCard;
	
	
	return (-1.0);
	
    }    
    
    public static void mapOpWithoutCheck(Operator actOp, Proc actProc, int heuristic) {
	Operator generalOp = getGenOp(actOp);
	double rhoMax = rho[generalOp.app];	
	
	actOp.isMapped = true;
	actOp.procs.add(actProc);
	generalOp.isMapped = true;
	if(!generalOp.procs.contains(actProc))
	    generalOp.procs.add(actProc);
	
	
	for(BasicObject ob : actOp.objects) {
	    if(!actProc.holds.contains(ob) && actProc.download(ob) == null) { 
		int genObPos = RunHeuristics.objects.indexOf(ob);
		BasicObject genOb =  RunHeuristics.objects.get(genObPos);
		DownloadObjectAssignment ass = findProcForDownload(genOb, actProc);
		actProc.downloads.add(ass);
	    }
	}
	if(!actProc.assignedOperators.contains(actOp)){
	    actProc.actSumCPU +=  (actOp.w/actProc.cpu)*rhoMax;
	    actProc.bwUsage =  checkNetworkCardCapacity(actOp, actProc, heuristic);//successCard;
	    actProc.assignedOperators.add(actOp);
	} else {
	    System.out.println("ATTENTION! "+actOp+" is already computed on "+actProc);
	}
	
	if(actProc.children.contains(actOp)) {
	    actProc.children.removeExactly(actOp);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("Removing "+actOp+" from childrensList of "+actProc);
	}
	
	for(Operator op : actOp.operators) 
	    if(!actProc.children.contains(op)) { 
		//    actProc.children.add(op);
		//System.out.println("Adding "+op+" to childrensList of "+actProc);
		if(actProc.assignedOperators.contains(op)) {
		    if(CompileTimeCondition.DEBUG)		
			System.out.println("Normalerweise muss doch jetzt "+op+" nicht hinzugefuegt weden, da "+
					   actProc+" op"+op.id+" schon berechnet. oder nicht?");
		} else {
		    actProc.children.add(op);
		    if(CompileTimeCondition.DEBUG)
			System.out.println("Adding "+op+" to childrensList of "+actProc);
		}
	    }
	if(!actProc.fathers.contains(actOp.father) && actOp.father.id >= 0){
	    actProc.fathers.add(actOp.father);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("adding "+actOp.father+" to fathersList of "+actProc);
	}
	
	if(!usedProcs.contains(actProc)){
	    if(CompileTimeCondition.DEBUG)
		System.out.println("adding "+actProc+" to usedProcs");
	    usedProcs.add(actProc);
	}
    }


    /* returns the new bwUsage if Network card capacity holds, a negative value otherwise */
    public static double checkNetworkCardCapacity (Operator actOp, Proc actProc, int heuristic) {
	double capacity = actProc.bwUsage;

	if(CompileTimeCondition.BIG_OUTPUT)
	    System.out.println("checking the network card capacity for "+actProc+" when adding "+actOp+":");
	if(CompileTimeCondition.DEBUG)
	    System.out.println("- bw used before test: "+actProc.bwUsage);


	/* ich glaube man muss doch alle operators die auf actProc gemapped sind neu berechnen, */
	/* weil sonst die downloads von den anderen procs evtl. doppelt hinzugefuegt werden, */
	/* weil man nicht weiss, welche neu hinzugekommen sind und welche nicht */
	

	/* downloads of actProc */
	for(DownloadObjectAssignment ass : actProc.downloads) {
	    int genObPos = RunHeuristics.objects.indexOf(ass.object);
	    BasicObject genOb = RunHeuristics.objects.get(genObPos);
	    capacity += genOb.getRate();
	    if(CompileTimeCondition.DEBUG)
		System.out.println("- "+actProc+" downloads "+ass.object+" with rate "+genOb.getRate()); 
       	}
	
	/* downloads of other procs on actProc*/
	//System.out.println(actProc.holds.size());
	for(BasicObject obj : actProc.holds) {
	    for(Proc proc : usedProcs) {
		if(proc.download(obj) != null && actProc.equals(proc.download(obj))) {  
		    if(CompileTimeCondition.DEBUG)
			System.out.print("- "+proc+" downloads "+obj);
		    int genObPos = RunHeuristics.objects.indexOf(obj);
		    BasicObject genOb = RunHeuristics.objects.get(genObPos);
		    capacity += genOb.getRate();
		    if(CompileTimeCondition.DEBUG)
			System.out.println("with rate "+genOb.getRate()); 
		}
	    }
	}
	
	/* comm with fathers */
	for(Operator father: actProc.fathers) {
	    for(Operator child : father.operators) {
		if(actProc.assignedOperators.contains(child)) {
		    Operator genChild = getGenOp(child);
		    capacity += (child.delta*rho[genChild.app]);
		    if(father.newChildren.contains(child)) {
			int newPos = father.newChildren.indexOf(child);
			Operator newChild = father.newChildren.get(newPos);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("- comm between "+newChild+"(NEW link) and "+father+
					       " takes "+(newChild.delta*rho[genChild.app]));
		    } else {
			if(CompileTimeCondition.DEBUG)
			    System.out.println("- comm between "+child+" and "+father+
					       " takes "+(child.delta*rho[genChild.app]));
		    }
		}
	    }
	}

	/* comm with children */
	for(Operator child : actProc.children) {
	    Operator genChild = getGenOp(child);
	    capacity += (child.delta*rho[genChild.app]);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("- comm between "+child+" and "+child.father+
				   " takes "+(child.delta*rho[genChild.app]));
	   
	}


	/* downloads of actOp*/
	for(BasicObject ob : actOp.objects) {
	    if(!actProc.holds.contains(ob) && actProc.download(ob) == null) {
		if(CompileTimeCondition.DEBUG)
		    System.out.print("- "+actProc+" downloads "+ob);
		int genObPos = RunHeuristics.objects.indexOf(ob);
		BasicObject genOb = RunHeuristics.objects.get(genObPos);
		capacity += genOb.getRate();
		if(CompileTimeCondition.DEBUG)
		    System.out.println("with rate "+genOb.getRate()); 
	    }
	}
	
	/* comm with children of actOp*/
	if(actProc.children.contains(actOp)) {
	    Operator genOp = getGenOp(actOp);
	    capacity -= (actOp.delta*rho[genOp.app]);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("- actOp "+actOp+" is child of "+actProc+". this comm is not needed anymore.");
	}
	for(Operator child : actOp.operators) {
	    if(!actProc.children.contains(child)) {
		if(!actProc.assignedOperators.contains(child)) {
		    Operator genOp = getGenOp(child);
		    capacity += (child.delta*rho[genOp.app]);
		    if(CompileTimeCondition.DEBUG)
			System.out.println("- comm with "+child+" takes "+(child.delta*rho[genOp.app])); 
		}
	    }
	}
	
	/* comm with father of actOp */
	if(actOp.father.id >= 0) {
	    if(actProc.fathers.containsExactly(actOp)) { 
		for(Operator child : actOp.operators) {
		    if(actProc.assignedOperators.contains(child)) {
			Operator genOp = getGenOp(child);
			capacity -= (child.delta*rho[genOp.app]);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("- actOp "+actOp+" is father of "+actProc+". this comm is not needed anymore.");
		    }
		}
	    } //else {
	    if(!actProc.assignedOperators.containsExactly(actOp.father)) {
		Operator genOp = getGenOp(actOp);
		capacity += (actOp.delta*rho[genOp.app]);
		if(CompileTimeCondition.DEBUG)		
		    System.out.println("- comm with father "+actOp.father+" of actOp "+actOp+" takes "+(actOp.delta*rho[genOp.app]));
	    }
	    //}
	} else {
	    if(CompileTimeCondition.DEBUG)
		System.out.println("- actOp is root, no additional father comm");
	}
	if(CompileTimeCondition.DEBUG)
	    System.out.print("- bw used after test: "+capacity);
	if(CompileTimeCondition.DEBUG)
	    System.out.println(" vs networkCard: "+actProc.bw);
	if(capacity <= actProc.bw)
	    return capacity;
	else 
	    return (-1.0);
    }
    

    

    /* checks if the communication links have enough bandwidth, 
       when mapping actOp on actProc 
    */
    public static boolean checkLinks(Operator actOp, Proc actProc, int heuristic) {
 	double actBW;
	//if(CompileTimeCondition.DEBUG)
	if(CompileTimeCondition.BIG_OUTPUT)
	    System.out.println("Checking all communication links if bandwidth holds ...");	
	for(Proc proc : usedProcs) {
 	    actBW = actProc.links[proc.id];
 	    double capacity= 0.0;
	    
	    
	    /* check downloads */
	    for(DownloadObjectAssignment ass : actProc.downloads) {
		if(proc.equals(ass.proc)) {
		    capacity += ass.object.getRate();
		    if(CompileTimeCondition.DEBUG)
			System.out.println("- "+actProc+" downloads "+ass.object+" from "+proc+": "+ ass.object.getRate());
		}
	    }
	    
	    
	    /* downloads of other procs */
	    for(DownloadObjectAssignment ass : proc.downloads) {
		//System.out.println(ass);
		if(actProc.equals(ass.proc)) {
		    capacity += ass.object.getRate();
		    if(CompileTimeCondition.DEBUG)		    
			System.out.println("- "+ass.proc+" downloads "+ass.object+" from "+actProc+": "+ass.object.getRate());
		}
	    }
	    
	    /*comm with children */
	    for(Operator child : actProc.children) {
		if( proc.assignedOperators.containsExactly(child)) {
		    Operator genOp = getGenOp(child);
		    capacity += child.delta *rho[genOp.app];
		    if(CompileTimeCondition.DEBUG)
			System.out.println("Comm with "+proc+" for child "+child+" takes "+child.delta *rho[genOp.app]);
		}
	    }
	    // /* comm with children of actOp that are already mapped */
	    // 	    for(Operator child : actOp.operators){
// 		if(child.isMapped && getProcOfOp)
// 		    }
   
	    /* comm with father */
	    for(Operator father : actProc.fathers) {
		if(proc.assignedOperators.containsExactly(father)) {
		    Operator genOp = getGenOp(father);
		    for(Operator op : father.operators) {
			if(actProc.assignedOperators.contains(op)) {
			    capacity += op.delta *rho[genOp.app];
			    if(CompileTimeCondition.DEBUG)
				System.out.println("Comm with "+proc+" for father "+father+" takes"+op.delta *rho[genOp.app]);	
			}
		    }
		}
	    }
	    //System.out.println("cap: "+capacity+", actBW: "+actBW);
 	    if(capacity > actBW) return false;
 	}
	return true;
    }


    public static boolean checkThroughputParents(Operator actOp, Proc actProc, int heuristic) {
	if(CompileTimeCondition.BIG_OUTPUT)
	    System.out.println("Checking if the throughput for parent comms holds ...");
	
	initMeanCommForFather(actProc, actOp);
	
	// 	if(usedProcs.isEmpty()) {
	// 	    double sum = actOp.meanComm;
	// 	    System.out.println("- mean comm to the father of "+actOp+": "+actOp.meanComm);
	// 	    if(sum > 1) return false;    
// 	}
	
	double sum  = 0.0;
	boolean firstTime = true;
	for(Proc proc : usedProcs) {
	    //double sum  = 0.0;    	    
	    
	    /* father comms of already mapped ops */
	    for(Operator father : actProc.fathers) {
		
		if(proc.assignedOperators.containsExactly(father)) {
		    for(Operator child: father.operators) {
			if(actProc.assignedOperators.contains(child)) {
			    Operator genOp = getGenOp(child);
			    sum += rho[genOp.app] * (child.delta/actProc.links[proc.id]);
			    if(CompileTimeCondition.DEBUG)
				System.out.println("- comm of "+child+" with father "+father+" on "+proc+" takes "
						   + rho[genOp.app] * (child.delta/actProc.links[proc.id]));
			}
		    }
		}
		if(firstTime && !father.isMapped && !father.equals(actOp)){
		    for(Operator child: father.operators) {
			if(actProc.assignedOperators.containsExactly(child)) {
			    sum += child.meanCommFather;
			    if(CompileTimeCondition.DEBUG)
				System.out.println("- mean comm with father "+father+" of "+child+" takes "
						   +child.meanCommFather);
			}
		    }
		}
	    }
	    firstTime = false;
	    
	    
	    if(actOp.father.isMapped && proc.assignedOperators.containsExactly(actOp.father)) {
		Operator genOp = getGenOp(actOp); 
		sum += rho[genOp.app] * (actOp.delta/actProc.links[proc.id]);
		if(CompileTimeCondition.DEBUG)
		    System.out.println("- comm with father "+actOp.father+" on "+proc+" takes "
				       +rho[genOp.app] * (actOp.delta/actProc.links[proc.id]));
	    }
	}
	if(!actOp.father.isMapped && actOp.father.id > 0) {
	    sum += actOp.meanCommFather;
	    if(CompileTimeCondition.DEBUG)
		System.out.println("- mean comm with father "+actOp.father+" takes "+ actOp.meanCommFather);
	}

	    
	if(sum > 1) return false;    
	
   
	
	return true;
    }
    
    

    public static boolean checkThroughputChildren(Operator actOp, Proc actProc, int heuristic) {
	if(CompileTimeCondition.BIG_OUTPUT)
	    System.out.println("Checking if the throughput with children comms holds ...");
	initMeanCommForChildren(actProc, actOp);
	double sum = 0.0;
	boolean firstTime = true;
	
	for(Proc proc : usedProcs) {
	    //sum = 0.0;
	    //System.out.println("- adding constraints for "+proc);
	    
	    for(Operator child : actProc.children) {
		if(proc.assignedOperators.contains(child) ) {//&& 
		    Operator genOp = getGenOp(child);
		    sum += rho[genOp.app] * (child.delta/actProc.links[proc.id]);
		    //System.out.println("- child "+child+"rho: "+ rho[genOp.app]+" delta: "+child.delta+"link bw:"+actProc.links[proc.id]);
		    if(CompileTimeCondition.DEBUG)
			System.out.println("- comm with "+child+" on "+proc+" takes "
					   +rho[genOp.app] * (child.delta/actProc.links[proc.id]));
		} else {
		    if(firstTime && !child.isMapped && !child.equals(actOp)) {
			sum += child.meanComm;
			if(CompileTimeCondition.DEBUG)
			    System.out.println("- mean comm of child "+child+" takes "+child.meanComm);
		    }
		}
	    }		
	    firstTime = false;
	    for(Operator child : actOp.operators) {
		if(!actProc.children.contains(child) && child.isMapped) {
		    if(proc.assignedOperators.contains(child) && !proc.equals(actProc)) { 
			Operator genOp = getGenOp(child);
			sum += rho[genOp.app] * (child.delta/actProc.links[proc.id]);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("- comm for child "+child+" on proc "+proc+" takes "
					       + rho[genOp.app] * (child.delta/actProc.links[proc.id]));
		    } 
		}
	    }
	}
	for(Operator child : actOp.operators) {
	    if(!child.isMapped && !actProc.children.contains(child)) {
		sum += child.meanComm;
		if(CompileTimeCondition.DEBUG)
		    System.out.println("- mean comm for child "+child+" takes "+ child.meanComm);
	    } 
	}
	
	
	if(sum > 1) return false;    
	
	return true;
    }
    

    
    public static Proc getProcOfOp(Operator actOp) {
	for(Proc proc : usedProcs) {
	    for (Operator op : proc.assignedOperators) { 
		if(op.equalFather(actOp)) return proc;
	    }
	}
	return null;
    }

 
  
  public static void sort(double[] array, int[] permutation, int elements) {
      int i, j, pos; 
      double temp;
      i = 0;
      
      while( i < (elements-1) ) {
	  j = i + 1;
	  while( j < elements ) {
	      if( array[i] > array[j] ) {
		  temp = array[i];
		  array[i] = array[j];
		  array[j] = temp;
		  pos = permutation[i];
		  permutation[i] = permutation[j];
		  permutation[j] = pos;
	      }
	      j++; 
	  }
	  i++; 
      }
  }
  
  public static Proc getNextProc(int strategy, Operator actOp, ArrayList<Proc> procs, int pos) {
      Proc nextProc = null;
      if(!RunHeuristics.procs.isEmpty())
	  switch(strategy) {
	      
	    case FASTEST:
		//System.out.println("Position: "+pos);
		nextProc = RunHeuristics.procs.get(pos); 
		break;  
	    case NETWORK_CARD:
		nextProc = RunHeuristics.procs.get(pos);
		break;
	  
		
	    case REMAINING_BW:
		//QuickSorter.sortRemainingBw(procs);
		nextProc = RunHeuristics.procs.get(pos);
		break;
		
	    case REMAINING_CPU: 
		//QuickSorter.sortRemainingCPU(procs);
		nextProc = RunHeuristics.procs.get(pos);
		break;


	    default:
		nextProc = RunHeuristics.procs.get(pos); 
	    }
	
	return nextProc;
    }
    
 


    /* father: the father of actOp, child: gen op of actOp, actOp: actOp*/
    public static boolean addLink(Operator father, Operator child, Operator actOp, int heuristic) {
	//private static boolean addLink(Operator father, Operator child, Operator actOp) {
	boolean success;
	double sum = 0.0;
	double actBW;

	//	for(Proc fatherProc : father.procs) {
	//  for(Proc childProc : child.procs) {
	//	actBW = fatherProc.links[childProc.id];
	//sum = 0.0;
	/* cpu keeps the same, by adding a comm link, so no check necessary */
	
	    

	success = false;
	
	
	Proc fatherProc = father.procs.get(0);
	Proc childProc = null;
	//	for(int i = 0; i< father.procs.size(); i++) {
	    for(int j = 0; j<child.procs.size(); j++) {
		/* act father-child pair */
		//	fatherProc = father.procs.get(i);
		childProc = child.procs.get(j);
		
		if(CompileTimeCondition.DEBUG)
		    System.out.println("act fatherProc: "+fatherProc+", act childProc: "+childProc);
		
		if(fatherProc.equals(childProc)) {
		    if(CompileTimeCondition.DEBUG)
			System.out.println(fatherProc+" has already mapped an "+actOp+". No need for further mapping.");
		    fatherProc.children.removeExactly(actOp);
		    if(CompileTimeCondition.DEBUG)
			System.out.println("Removing "+actOp+" from children list of "+fatherProc);
		    return true;
		}
		
		if(heuristic == RANDOM ) {
		    if(CompileTimeCondition.DEBUG)
			System.out.println("RANDOM");
		    if(fatherProc.assignedOperators.containsExactly(actOp.father)) {
			//			if( fatherProc.children.contains(child)) {
			//  System.out.println(fatherProc+" already contains an operator "+child+". no need to recompute.");
			if(CompileTimeCondition.DEBUG)
			    System.out.println("^^^^^^ "+fatherProc+" treats the real father "+actOp.father+" of actOp "+actOp+" ^^^^^^^");
			
			if(fatherProc.children.containsAnother(actOp)) {
			    if(CompileTimeCondition.DEBUG)			    
				System.out.println("no mapping necessary for this op, fatherproc already downloads another op with id "+actOp.id);
			    fatherProc.children.removeExactly(actOp);
			    return true;
			}
		    }
		}
		
		/* check comm link */
		success = checkLink(fatherProc,childProc);
		
		if(success) { 
		    /* check network card */
		    success = checkNetworkCards(fatherProc,childProc,child);
		    
		    if(success) {
			/* father comm throughput for childProc */
			boolean throuParent = checkThroughputParents(actOp, childProc, heuristic);

			/* child comm throughput for childProc */
			boolean throuChild = checkThroughputChildren(actOp, fatherProc, heuristic);


			success = throuParent & throuChild;
		       
			if(success) {
			    int newFatherPos = fatherProc.assignedOperators.indexOf(father);
			    Operator newFather = fatherProc.assignedOperators.get(newFatherPos);
			    int childPos = childProc.assignedOperators.indexOf(child);
			    Operator realChild = childProc.assignedOperators.get(childPos);

			    //    System.out.println("act fatherProc: "+fatherProc+", act childProc: "+childProc);
			    //if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("\n*******link between "+newFather+" app"+newFather.app+"  and "+realChild+" app"+realChild.app+", father "+actOp.father+" added.*******\n");
			    
			    fatherProc.children.removeExactly(actOp);
			    if(CompileTimeCondition.DEBUG)
				System.out.println("removing "+actOp+" from childrensList of fatherProc "+ fatherProc);
			    if(!fatherProc.children.containsExactly(realChild)) {
				fatherProc.children.add(realChild);
				if(CompileTimeCondition.DEBUG)
				    System.out.println("NEW");
				if(CompileTimeCondition.DEBUG)
				    System.out.println("Adding "+realChild+" to childrensList of fatherProc "+fatherProc);
			    }
			    
			    if(!childProc.fathers.containsExactly(father)){
				childProc.fathers.add(father);
				if(CompileTimeCondition.DEBUG)
				    System.out.println("Adding "+father+" to fathersList of chhildProc "+childProc);
			    }
			    return success;
			}
		    }
		}
		//  }
	}
	
	// 	if(success) {
// 	    success = checkNetworkCards(fatherProc, childProc);

		// }
	//}
	
	return success;
    }
     /* father of actOp not mapped yet!!! */
    /* this method is only used in BottomUpBFS, whose genOp is already mapped, and we try to add the additional fatherLink to the proc*/
    public static boolean addFatherLink (Operator actOp, Operator genOp, int heuristic) {
	boolean success;
	double sum = 0.0;
	double actBW;
	//System.out.println("values when entering:\nfather: "+father+"\nchild: "+child+"\nactOp: "+actOp);
	/* cpu keeps the same, by adding a comm link, so no check necessary */
	
	success = false;
	
	Proc proc = null;
	//	for(int i = 0; i< father.procs.size(); i++) {
	for(int j = 0; j<genOp.procs.size(); j++) {
	    /* act father-child pair */
	    
	    
	    proc = genOp.procs.get(j);
	    initMeanCommForFather(proc, actOp);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("act proc: "+proc);
	    
	    
	    /* check comm link not possible, father proc not known yet */
	    double successCard = 0.0;
	    
	    
	    if(successCard >= 0.0) {
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("* network card test successful");
		/* father comm throughput for childProc */
		boolean throuParent = checkThroughputParents(actOp, proc, heuristic);
		
		success = throuParent;
		
		if(success) {
		    System.out.println("* throughput test successful");
		    /* add the link to the father of act Op to proc! */
		    
		    actOp.isMapped = true;
		    if(!proc.fathers.containsExactly(actOp.father) && actOp.father.id > 0) {
			proc.fathers.add(actOp.father);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("adding "+actOp.father+" to fatherList of "+proc);
		    }
		    
		    for(Operator op : actOp.newChildren) {
			Proc childProc = getProcOfOp(op);
			    boolean done = childProc.fathers.removeExactly(actOp);
			    if(CompileTimeCondition.DEBUG)
				System.out.println("removing "+actOp+" from fatherList of "+childProc+"("+done+"). this link is not needed anymore");
		    }			
		    
		    for(Operator op : actOp.operators) {
			Proc childProc = getProcOfOp(op);
			if(childProc != null) {
			    boolean done = childProc.fathers.removeExactly(actOp);
			    if(CompileTimeCondition.DEBUG)
				System.out.println("removing "+actOp+" from fatherList of "+childProc+"("+done+",realChild). this link is not needed anymore");
			}			
		    }			
		    
		    
		    int pos = proc.assignedOperators.indexOf(genOp);
		    Operator newChild = proc.assignedOperators.get(pos);
		    actOp.father.newChildren.add(newChild);
		    if(CompileTimeCondition.DEBUG)
			System.out.println("new child for father "+actOp.father+" of "+actOp+": "+newChild);
		    
		    
		    //actOp.procs.add(proc);
		    if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("******link to father "+actOp.father+" added.");
		    
		    
		    return success;
		} else 	
		    if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("* throughput test FAILED");
	    } else {
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("* network card does NOT hold");
	    }
	}
	return false;
    }
    
    /* father of actOp not mapped yet!!! */
    /* this method is only used for leaves, whose genOp is already mapped, and we try to add the additional fatherLink to the proc*/
    public static boolean addFatherLinkForLeaf (Operator actOp, Operator genOp, int heuristic) {
	boolean success;
	double sum = 0.0;
	double actBW;
	//System.out.println("values when entering:\nfather: "+father+"\nchild: "+child+"\nactOp: "+actOp);
	/* cpu keeps the same, by adding a comm link, so no check necessary */
	
	success = false;
	
	Proc proc = null;
	//	for(int i = 0; i< father.procs.size(); i++) {
	for(int j = 0; j<genOp.procs.size(); j++) {
	    /* act father-child pair */
	    
	    
	    proc = genOp.procs.get(j);
	    initMeanCommForFather(proc, actOp);

	    if(CompileTimeCondition.BIG_OUTPUT);	 
		System.out.println("act proc: "+proc);
	    
	    
	    /* check comm link not possible, father proc not known yet */
	    double successCard = 0.0;
	    
	    if(heuristic != BOTTOM_UP_BFS) 
		successCard = checkNetworkCardCapacity(actOp, proc, heuristic);
	    
	    if(successCard >= 0.0) {
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("* network card test successful");
		/* father comm throughput for childProc */
		boolean throuParent = checkThroughputParents(actOp, proc, heuristic);
		
		success = throuParent;
		
		if(success) {
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("* throughput test successful");
		    /* add the link to the father of act Op to proc! */
		    
		    actOp.isMapped = true;
		    if(!proc.fathers.containsExactly(actOp.father) && actOp.father.id > 0) {
			proc.fathers.add(actOp.father);
			if(CompileTimeCondition.DEBUG)
				    System.out.println("Adding "+actOp.father+" to fathersList of proc "+proc);
		    
		    }
		    actOp.procs.add(proc);
		    
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("******actOp "+actOp+" mapped on "+proc+", link to father "+actOp.father+" added.");
		    
		    
		    return success;
		} else 	
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("* throughput test FAILED");
	    } else {
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("* network card does NOT hold");
	    }
	}
	return false;
    }
    
    /* father: the father of actOp, child: gen op of actOp, actOp: actOp*, fatherProc: father not mapped yet!!! */
    public static boolean addLinkAndMapFather(Operator father, Proc fatherProc, Operator child, Operator actOp, int heuristic) {
	//private static boolean addLink(Operator father, Operator child, Operator actOp) {
	boolean success;
	double sum = 0.0;
	double actBW;
	if(CompileTimeCondition.DEBUG)
	    System.out.println("values when entering:\nfather: "+father+"\nchild: "+child+"\nactOp: "+actOp);
	/* cpu keeps the same, by adding a comm link, so no check necessary */
	
	success = false;
	
	
	//Proc fatherProc = father.procs.get(0);
	Proc childProc = null;
	//	for(int i = 0; i< father.procs.size(); i++) {
	for(int j = 0; j<child.procs.size(); j++) {
	    /* act father-child pair */
	    
	    childProc = child.procs.get(j);
		
	    if(CompileTimeCondition.DEBUG)
		System.out.println("act fatherProc: "+fatherProc+", act childProc: "+childProc);
	    
	    
	    /* check comm link */
	    success = checkLinkForFather(fatherProc,childProc,father);
	    
	    if(success) { 
		if(CompileTimeCondition.BIG_OUTPUT)	
		    System.out.println("* link check successful");
		/* check network card */
		success = checkNetworkCardsForFather(fatherProc,childProc,child,father,heuristic);
		
		if(success) {
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("* network card test successful");
		    /* father comm throughput for childProc */
		    boolean throuParent = checkThroughputParents(actOp, childProc, heuristic);
		    
		    /* child comm throughput for childProc */
		    boolean throuChild = checkThroughputChildren(actOp, fatherProc, heuristic);
		    //System.out.println("throughput with children can not be tested, father not yet mapped");
		    
		    success = throuParent & throuChild;
		    
		    if(success) {
			if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("* throughput test successful");
			/* map father on fahter Proc and add the link! */
			mapOpWithoutCheck(father, fatherProc, heuristic);
			if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("******father "+father+" mapped on "+fatherProc);
			
			
			int newFatherPos = fatherProc.assignedOperators.indexOf(father);
			Operator newFather = fatherProc.assignedOperators.get(newFatherPos);
			int childPos = childProc.assignedOperators.indexOf(child);
			Operator realChild = childProc.assignedOperators.get(childPos);

			// 			       System.out.println("act fatherProc: "+fatherProc+", act childProc: "+childProc);
			//if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("\n*******link between "+newFather+" app"+newFather.app+"  and "
					       +realChild+" app"+realChild.app+", father "+actOp.father+" added.*******\n");
			
			fatherProc.children.removeExactly(actOp);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("removing "+actOp+" from childrenList, adding "+realChild);
			if(fatherProc.fathers.containsExactly(father)) {
			    fatherProc.fathers.removeExactly(father);
			    if(CompileTimeCondition.DEBUG)
				System.out.println("removing "+father+" from fathersList of fatherProc "+fatherProc );
			}
			fatherProc.children.add(realChild);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("Adding "+realChild+" to childrensList of fatherProc "+fatherProc);

			if(!childProc.fathers.containsExactly(father)){
			    childProc.fathers.add(father);
			    if(CompileTimeCondition.DEBUG)
				System.out.println("Adding "+father+" to fathersList of childProc "+childProc);
			}
			
			return success;
		    } else if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("* throughput test FAILED");
		} else if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("* network card test FAILED");
	    } else if(CompileTimeCondition.BIG_OUTPUT)
		System.out.println("* link check FAILED");
	    //  }
	}
	
	// 	if(success) {
	// 	    success = checkNetworkCards(fatherProc, childProc);
	
	// }
	//}
	
	return success;
    }
    

    private static boolean checkNetworkCards(Proc fatherProc, Proc childProc, Operator genOp) {
	if(CompileTimeCondition.BIG_OUTPUT)
	    System.out.println("check Network Cards of "+fatherProc+" and "+childProc+":");
	double fatherCardUsage = fatherProc.bwUsage + genOp.delta * rho[genOp.app];
	if(CompileTimeCondition.BIG_OUTPUT)
	    System.out.println("fatherCardUsage: "+fatherCardUsage+", NetworkCard: "+fatherProc.bw);
	if(fatherProc.bw < fatherCardUsage) return false;
	
	double childCardUsage = childProc.bwUsage + genOp.delta * rho[genOp.app];
	if(CompileTimeCondition.BIG_OUTPUT)
	    System.out.println("childCardUsage: "+childCardUsage+", NetworkCard: "+childProc.bw);
	if(childProc.bw < childCardUsage) return false;
	
	return true;
 
    }

    private static boolean checkNetworkCardsForFather(Proc fatherProc, Proc childProc, Operator genOp, Operator father, int heuristic) {
	if(CompileTimeCondition.BIG_OUTPUT)
	    System.out.println("check Network Cards of "+fatherProc+" and "+childProc+":");
	//double fatherCardUsage = fatherProc.bwUsage + genOp.delta * rho[genOp.app];
	double fatherCardUsage = checkNetworkCardCapacity(father, fatherProc, heuristic);
	if(CompileTimeCondition.DEBUG)
	    System.out.println("fatherCardUsage: "+fatherCardUsage+", NetworkCard: "+fatherProc.bw);
	if(fatherCardUsage < 0.0) return false;
	else {
	    fatherCardUsage += genOp.delta * rho[genOp.app];
	    if(fatherProc.bw < fatherCardUsage) return false;
	}
	
	double childCardUsage = childProc.bwUsage + genOp.delta * rho[genOp.app];
	if(CompileTimeCondition.DEBUG)
	    System.out.println("childCardUsage: "+childCardUsage+", NetworkCard: "+childProc.bw);
	if(childProc.bw < childCardUsage) return false;
	
	return true;
 
    }
   
  private static boolean checkLink(Proc fatherProc, Proc childProc) {
	double actBW = fatherProc.links[childProc.id];
	double sum = 0.0;

	/* downloads fatherproc -> childproc */
	for(DownloadObjectAssignment ass : fatherProc.downloads) {
	    if(childProc.equals(ass.proc)) {
		sum += ass.object.getRate();
		//System.out.println(fatherProc+" downloads "+ass.object+" from "+childProc);
		
	    }
	}
	    
	/* downloads childproc -> fatherproc */
	for(DownloadObjectAssignment ass : childProc.downloads) {
	    if(fatherProc.equals(ass.proc)) {
		sum += ass.object.getRate();
		//System.out.println(childProc+" downloads "+ass.object+" from "+fatherProc);
	    }
	}
	
	/* comm fatherproc -> childproc */
	for(Operator op : fatherProc.fathers) {
	    if(childProc.assignedOperators.contains(op)) {
		//int genOpPos = operators.indexOf(op);
		Operator genOp = getGenOp(op);
		for(Operator opp : op.operators) {
		    if(fatherProc.assignedOperators.contains(opp)) {
			sum += opp.delta *rho[genOp.app];
			//System.out.println("Comm fatherproc-childproc");	
		    }
		}
	    }
	}
	
	/* comm childproc -> fatherproc */
	for(Operator op : fatherProc.children) {
	    if(childProc.assignedOperators.contains(op)) {
		//int genOpPos = operators.indexOf(op);
		Operator genOp = getGenOp(op);
		sum += op.delta *rho[genOp.app];
		
		//System.out.println("Comm child proc-fatherproc");
	    }
	}
	if(CompileTimeCondition.DEBUG)
	    System.out.println("bw used on link: "+sum+", actBW: "+actBW);
	if(sum > actBW) return false;
	//System.out.println("returning true");
	return true;
    }


    private static boolean checkLinkForFather(Proc fatherProc, Proc childProc, Operator father) {
	double actBW = fatherProc.links[childProc.id];
	double sum = 0.0;
	
	/* downloads fatherproc -> childproc */
	for(DownloadObjectAssignment ass : fatherProc.downloads) {
	    if(childProc.equals(ass.proc)) {
		sum += ass.object.getRate();
		//System.out.println(fatherProc+" downloads "+ass.object+" from "+childProc);
		
	    }
	}
	/* the basic objects of the father that are not downloaded yet */
	for(BasicObject obj : father.objects) {
	    boolean toBeAdded = true;
	    for(DownloadObjectAssignment ass : fatherProc.downloads) {
		if(obj.equals(ass.object)) toBeAdded = false;
	    }
	    if(toBeAdded && !fatherProc.holds.contains(obj)) {
		int genObjPos = RunHeuristics.objects.indexOf(obj);
		BasicObject genObj = RunHeuristics.objects.get(genObjPos);
		sum += genObj.getRate();
	    }
	}
	
	/* downloads childproc -> fatherproc */
	for(DownloadObjectAssignment ass : childProc.downloads) {
	    if(fatherProc.equals(ass.proc)) {
		sum += ass.object.getRate();
		//System.out.println(childProc+" downloads "+ass.object+" from "+fatherProc);
	    }
	}
	
	/* comm fatherproc -> childproc */
	for(Operator op : fatherProc.fathers) {
	    if(childProc.assignedOperators.contains(op)) {
		//int genOpPos = operators.indexOf(op);
		Operator genOp = getGenOp(op);
		for(Operator opp : op.operators) {
		    if(fatherProc.assignedOperators.contains(opp)) {
			sum += opp.delta *rho[genOp.app];
			//System.out.println("Comm fatherproc-childproc");	
		    }
		}
	    }
	}
	if(!fatherProc.assignedOperators.contains(father.father) && 
	   childProc.assignedOperators.contains(father.father)) {
	    Operator genOp = getGenOp(father);
	    sum += father.delta *rho[genOp.app];
	}
	
	/* comm childproc -> fatherproc */
	for(Operator op : fatherProc.children) {
	    if(childProc.assignedOperators.contains(op)) {
		//int genOpPos = operators.indexOf(op);
		Operator genOp = getGenOp(op);
		sum += op.delta *rho[genOp.app];
		
		//System.out.println("Comm child proc-fatherproc");
	    }
	}
	for(Operator op : father.operators) {
	    if(childProc.assignedOperators.contains(op) && !fatherProc.assignedOperators.contains(op)) {
		Operator genOp = getGenOp(op);
		sum += op.delta *rho[genOp.app];
	    }
	}
	if(CompileTimeCondition.DEBUG)
	    System.out.println("bw used on link: "+sum+", actBW: "+actBW);
	if(sum > actBW) return false;
	//System.out.println("returning true");
	return true;
    }
  
    
    private static double getMaxRho(Operator op) {
	//int genOpPos = operators.indexOf(op);
	Operator genOp = getGenOp(op);
	//System.out.println(" gen op "+genOp+" app "+genOp.app);
	return rho[genOp.app];	
    }
	
    private static void initMeanCommForChildren(Proc proc, Operator op) {
	for(Operator child : op.operators) {
	    if(!child.isMapped) {
		double sum = 0.0;
		double meanBW = 1.0;
		
		for(int i = 0; i<proc.links.length; i++) {
		    sum += proc.links[i];
		    // System.out.println("proc link : "+proc.links[i]);
		}
		//	System.out.println(proc.links.length+" max rho : "+ getMaxRho(child));
		if(proc.links.length > 1) meanBW = sum/(double)(proc.links.length-1);
		child.meanComm = getMaxRho(child) * (child.delta / meanBW);
		//System.out.println(child+" mean comm : "+child.meanComm);
	    }
	}
    }
	
    private static void initMeanCommForFather(Proc proc, Operator op) {
	if(!op.father.isMapped) {
	    double sum = 0.0;
	    double meanBW = 1.0;
	    
	    for(int i = 0; i<proc.links.length; i++) {
		sum += proc.links[i];
		//System.out.println("proc link : "+proc.links[i]);
	    }
	    //System.out.println(proc.links.length+" max rho : "+ getMaxRho(op)+", sum: "+sum+", delta: "+op.delta);
	    if(proc.links.length > 1) meanBW = sum/(double)(proc.links.length-1);
	    op.meanCommFather = getMaxRho(op) * (op.delta / meanBW);
	    //System.out.println(op+" mean comm father : "+op.meanCommFather);
	    
	}
    }
    
    public static int computeMappingCost() {
	int cost =0;
	for(Proc proc : usedProcs) {
	    cost += proc.cost;
	}

	return cost;
    }

}