import java.util.*;


public class BottomUpBFS{
        
    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 */
    
    public static int internalNum = 0;
    
  //   public static int getNextInternalNum() {
// 	return internalNum++;
//     }

    public static Operator getGenOp(Operator op) {
	int genOpPos = RunHeuristics.operators.indexOf(op);
	return RunHeuristics.operators.get(genOpPos);
    }



    public static Proc tryToFindAProcForOp(Operator actOp, int strategy, ArrayList<Proc> procs) {
	int pos = 0;
	boolean possible = false;
	Proc actProc = null;
	if(CompileTimeCondition.DEBUG)
	    System.out.println("** trying to find a new proc for "+actOp);
	if(procs.size() == 0) { 
	    System.out.println(" no further proc available.");
	    return null;
	}
	
	switch(strategy) {
	    
	case REMAINING_BW:
	    QuickSorter.sortRemainingBw(procs);
	    break;
	    
	case REMAINING_CPU: 
	    QuickSorter.sortRemainingCPU(procs);
	    break;
	default:
	}
	
	while (pos < procs.size() && !possible) {	
	    
	    actProc = CommonFunctions.getNextProc(strategy,actOp,procs,pos);
	    if(actProc == null) return actProc;; 
	    if(CompileTimeCondition.BIG_OUTPUT)
		System.out.println("Proc where to map on: "+actProc);
	    double cardUsage;
	    cardUsage = CommonFunctions.tryToMapOpOnProc(actOp,actProc,BOTTOM_UP_BFS);
	    if(cardUsage > 0.0) 
		possible = true;
	    if(possible)
		if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("mapping is POSSIBLE on "+actProc);
		else
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("mapping is NOT POSSIBLE on "+actProc);
	    
	    pos++;	
	}  
	return actProc;
	
    }
    
    public static Mapping bottomUpBFS(MyArrayList<Operator> applications, int strategy, ArrayList<Proc> procs){
	Proc actProc;
	boolean possible = false;
	boolean mapped = false;
	boolean mapWithFather = false;
	
	CommonFunctions.usedProcs = new ArrayList<Proc>();

	MyArrayList<Operator> application = new MyArrayList<Operator>(); 
	
	for(Operator root : applications) {
	    possible = false;
	    mapped = false;
	    
	    createApplicationList(root, application);
	    
 // 	    System.out.println("\napplication:");
//  	    for(Operator op: application)
//  		System.out.println(op);
	    
	    QuickSorter.sortOpId(application);
	    //  System.out.println("\napplication (app"+application.get(0).app+") sorted by id:");
	    // for(Operator op: application)
	    //	System.out.println(op);
	}

	    /* mapping all operators of the act application list */
	    while(!application.isEmpty()) {

		if(CompileTimeCondition.DEBUG)
		    System.out.println("\napplications:");
		if(CompileTimeCondition.DEBUG)
		    for(Operator op: application)
			System.out.println(op+" app"+op.app);
		
		possible = false;
		mapped = false;
		Operator actOp = application.get(0);
		application.remove(actOp);
	
		System.out.println("\nactOp: "+actOp);
		
		int genOpPos = RunHeuristics.operators.indexOf(actOp);
		Operator genOp =  RunHeuristics.operators.get(genOpPos);
		
		if(genOp.isMapped && actOp.father.id < 0) {
		    mapped = false;
		    System.out.println("father of "+ actOp+"(app"+actOp.app+") is null, have to find a proc for "+
				       actOp+". Jumping to find a proc....");
		} else if(genOp.isMapped && actOp.father.id > 0) {
		    System.out.println("General op is already mappend on a proc and act Op is at bottom");
		    System.out.println("try to add comm link to additional father");
		    mapped = CommonFunctions.addFatherLink(actOp, genOp, BOTTOM_UP_BFS);

		
		
		} else {
		    /* general operator is not mapped yet */
		    /* or biological children of actOp are mapped and shortcut of mappedGenop is not possible*/
		    if(!genOp.isMapped)
			System.out.println("general Op not mapped yet");

			
		    if(!actOp.operators.isEmpty()) {
			/* operator has other operators as children -> no al-op */
			/* in theory: all operator children are already mapped */
			    System.out.println("act op is no al-op");
			    
			    //actOp.operators vorher sortieren ?
			    //for(Operator child : actOp.operators) {
			    for(int i = 0; i< actOp.operators.size(); i++) {
				Operator child = actOp.operators.get(i);
				
				int genOpPosChild = RunHeuristics.operators.indexOf(child);
				Operator genChild = RunHeuristics.operators.get(genOpPosChild);  
				
				int pos = 0;
				possible = false;
				while(pos < genChild.procs.size() && !possible) {
				    actProc = genChild.procs.get(pos);
				    possible = CommonFunctions.mapOpOnChildProc(actOp, actProc, BOTTOM_UP_BFS);
				    if (possible) {
					/* operator is mapped on child proc */
					mapped = true;
					
					
				    } else 
					if(CompileTimeCondition.BIG_OUTPUT)				    
					    System.out.println("mapping was not possible: "+actOp+" on "+actProc);
				    pos++;
				}
				if(mapped)
				    i=actOp.operators.size(); //to break!!
			    }
			    
		    } else { 
			/* actOp has only objects as children -> bottom */
			if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("actOp has only objects as children -> bottom");
		    }
		}
		
		if(!mapped) {
		    /* operator could not be mapped on child proc  or the  */
		    /* the additional communication could not be added     */
		    /* or act op has only object children (al-op)          */
		    /* 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(possible, CommonFunctions.usedProcs));
		    }
		    
		    switch(strategy) {
			
		    case REMAINING_BW:
			QuickSorter.sortRemainingBw(procs);
			break;
			
		    case REMAINING_CPU: 
			QuickSorter.sortRemainingCPU(procs);
			break;
		    default:
		    }
		    
		    while (pos < procs.size() && !possible) {	
			
			actProc = CommonFunctions.getNextProc(strategy,actOp,procs,pos);
			if(actProc == null) return  (new Mapping(possible, CommonFunctions.usedProcs)); 
			if(CompileTimeCondition.BIG_OUTPUT)
			    System.out.println("Proc where to map on: "+actProc);
			
			possible = CommonFunctions.mapOpOnProc(actOp,actProc,BOTTOM_UP_BFS);
			if(possible) {
			    System.out.println("mapping  of "+actOp+" was SUCCESSFUL on "+actProc);
			    mapped = true;
			} else 
			    if(CompileTimeCondition.DEBUG)
				System.out.println("mapping of "+actOp+" was NOT POSSIBLE on "+actProc);
			
			/* operator is mapped on proc */
			if(possible) {
			    if(!CommonFunctions.usedProcs.contains(actProc)) {
				CommonFunctions.usedProcs.add(actProc);
				if(CompileTimeCondition.DEBUG)
				    System.out.println("*** added "+actProc+" to usedProcs ** "); 
			    }
			    if(strategy == FASTEST || strategy == NETWORK_CARD)
				procs.remove(actProc);
			}
			pos++;	
		    }
		}
		
		if(!mapped) {
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("a node could not be mapped, breaking....");
		    Mapping mapping = new Mapping(possible, CommonFunctions.usedProcs);
		    return mapping;
		}
	    }/*end while*/
	    //}/*end for application */
	    Mapping mapping = new Mapping(possible, CommonFunctions.usedProcs);
	    return mapping;
    }
    
    public static void createApplicationList(Operator root, MyArrayList<Operator> list) {
	list.add(root);
	for(Operator child : root.operators) {
	    createApplicationList(child,list);
	}
    }


   
}