import java.util.*;

public class TopDownBFS{

    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 */
    
    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; /* with reuse */
    static final int RANDOM_SIMPLE = 6; /* no reuse */
   
//        private  static int actInternalNumber = 0;

//     private static int getNextInternalNum() {
// 	return actInternalNumber++;
//     }
    

    public static Mapping topDownBFS(ArrayList<Operator> rootList, int strategy, ArrayList<Proc> procs) {
	Proc actProc;
	boolean possible = false;
	boolean mapped = false;

	CommonFunctions.usedProcs = new ArrayList<Proc>();

	switch(strategy) {
	    
	case FASTEST: 
	    QuickSorter.sortFastest(procs);
	    break;
	case NETWORK_CARD:
	    QuickSorter.sortCard(procs);
	    break;
	default:
	    
	}
	while(!rootList.isEmpty()) {
	//	for(int i=0; i<10; i++) {
	    mapped = false;
	    if(CompileTimeCondition.DEBUG)
		System.out.println("\nRoot List:");
	    if(CompileTimeCondition.DEBUG)
		for(Operator op : rootList) {
		    System.out.println(op);
		}
	    
	    
	    Operator actOp = rootList.get(0);
	    if(CompileTimeCondition.BIG_OUTPUT)
		System.out.println("\nact Op: "+actOp+" app"+actOp.app);
	    
	    rootList.remove(actOp);
	    int listPos = RunHeuristics.operators.indexOf(actOp);
	    Operator generalOp = RunHeuristics.operators.get(listPos);
	    if(CompileTimeCondition.DEBUG) 
		System.out.println("general Op: "+actOp);
	    
	    
	    
	    /* operator not yet mapped on a proc */
	    if(!generalOp.isMapped) {
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("generalOp not mapped yet");
		
		if(actOp.father.id != -1 && actOp.father.isMapped) {
		    if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("father already mapped: "+actOp.father);
		    
		    int fatherPos =  RunHeuristics.operators.indexOf(actOp.father);
		    Operator father = RunHeuristics.operators.get(fatherPos);
		    int pos = 0;
		    possible = false;

		    if(CompileTimeCondition.DEBUG)
			System.out.println("\n Procs of father "+father+":");
		    if(CompileTimeCondition.BIG_OUTPUT)
			for(Proc p : father.procs) 
			    System.out.println(p);
		    
		    while(pos < father.procs.size() && !possible) {
			actProc = father.procs.get(pos);
			possible = CommonFunctions.mapOpOnFatherProc(actOp, actProc,  TOP_DOWN_BFS);
			if (possible) {
			    /* operator is mapped on father proc */
			  //   generalOp.procs.add(actProc);
// 			    generalOp.isMapped = true;
// 			    actOp.isMapped = true;
// 			    actOp.procs.add(actProc);
			    mapped = true;
			   
			} else if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("mapping was not possible: "+actOp+" on "+actProc);
			pos++;
		    }
		    
		//     if(mapped) {
// 			/* adding the children for BFS treatment in rootList */
// 			for(Operator actChild : actOp.operators) {
// 			    rootList.add(actChild);
// 			}
// 		    }
		    if(mapped) {
		    /* adding the children for BFS treatment in rootList */
			Proc proc = actOp.procs.get(0);	
			if(CompileTimeCondition.DEBUG)				    
			    System.out.println("Proc of actOp: "+proc);
			if(CompileTimeCondition.BIG_OUTPUT)
			    for(Operator o : proc.assignedOperators) 
				System.out.println(o);
			for(Operator actChild : actOp.operators) {
			    if(!proc.assignedOperators.contains(actChild)) {
				rootList.add(actChild);
				if(CompileTimeCondition.BIG_OUTPUT)
				    System.out.println("adding "+actChild+" to rootList");
			    } else {
				System.out.println(proc+" already calculates "+actChild);
				proc.children.removeExactly(actChild);
				if(CompileTimeCondition.DEBUG)
				    System.out.println("removing "+actChild+"from children list");
			    }
			}
		    }
		} else 
		    if(CompileTimeCondition.DEBUG)
			System.out.println("father not mapped yet");
	    } else {
		/* operator is already  mapped on at least one proc */
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("operator is already  mapped on at least one proc, trying to add link ...");
		if(actOp.father.id != -1) {
		    
		    int fatherPos =  RunHeuristics.operators.indexOf(actOp.father);
		    Operator father = RunHeuristics.operators.get(fatherPos);
		   
		
		    possible = CommonFunctions.addLink(actOp.father, generalOp, actOp, TOP_DOWN_BFS);
		    if(possible) {
			//if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("\n*******link between "+father+" app"+father.app+"  and "+actOp+" app"+actOp.app+", father "+actOp.father+" added.(outside)*******\n");
			actOp.isMapped = true;
			mapped = true;
		    } else 
			if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("link could not be added");
		    //return false;
		}
	    }
	    
	    if(!mapped) {
		/* operator could not be mapped on father proc  or the */
		/* the additional communication could not be added     */
		/* chosing a new proc depending on strategy            */
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println(actOp+" still not mapped yet, chosing a new proc for strategy "+strategy);
		
		int pos = 0;
		possible = false;
		
		if(procs.size() == 0) { 
		    System.out.println(" no further proc available.");
		    return (new Mapping());
		}
		
		switch(strategy) {
		    
		case REMAINING_BW:
		    QuickSorter.sortRemainingBw(procs);
		    break;
		    
		case REMAINING_CPU: 
		    QuickSorter.sortRemainingCPU(procs);
		    break;
		    default:
		}
		
		while (pos < procs.size() && !possible) {
		    if(CompileTimeCondition.DEBUG)
			System.out.println("procs.size: "+procs.size());
		    
		    actProc = CommonFunctions.getNextProc(strategy,actOp,procs,pos);
		    if(actProc == null) return  (new Mapping()); 
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("Proc where to map on: "+actProc);
		    
		    possible = CommonFunctions.mapOpOnProc(actOp,actProc, TOP_DOWN_BFS);
		    System.out.println("mapping was successful on "+actProc+": "+possible);
		    /* operator is mapped on proc */
		    if(possible) {
			if(!CommonFunctions.usedProcs.contains(actProc)) CommonFunctions.usedProcs.add(actProc);
			if(strategy == FASTEST || strategy == NETWORK_CARD)
			    procs.remove(actProc);
			
		    
			/* adding the children for BFS treatment in rootList */
			Proc proc = actOp.procs.get(0);	
			if(CompileTimeCondition.DEBUG)
			    System.out.println("Proc of actOp: "+proc);		

			for(Operator actChild : actOp.operators) {
			    if(!proc.assignedOperators.contains(actChild))
				rootList.add(actChild);
			    else {
				System.out.println(proc+" already calculates "+actChild);
				proc.children.removeExactly(actChild);
				System.out.println("removing "+actChild+"from children list");
			    }
			}
			mapped = true;
			//  break;
		    } //else return possible
		    pos++;
		}
	    }
	    if(!mapped) return  (new Mapping());
	    for(Operator child : actOp.operators) {
		if(rootList.contains(child))
		    if(CompileTimeCondition.DEBUG)
			System.out.println("rootList contains "+child);
		else 
		    if(CompileTimeCondition.DEBUG)
			System.out.println("rootList does NOT contain "+child);
	    }
	}
	Mapping mapping = new Mapping(possible, CommonFunctions.usedProcs);
	return mapping;
    }

}