import java.util.*;


public class BottomUpDFS{
    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;
	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_DFS);
	    if(cardUsage > 0.0) 
		possible = true;
	    if(possible)
		System.out.println("mapping is POSSIBLE on "+actProc);
	    else
		if(CompileTimeCondition.DEBUG)
		    System.out.println("mapping is NOT POSSIBLE on "+actProc);
	    
	    pos++;	
	}  
	return actProc;
	
    }
    
    public static Mapping bottomUpDFS(MyArrayList<Operator> applications, int strategy, ArrayList<Proc> procs){
	Proc actProc;
	boolean possible = false;
	boolean mapped = false;
	boolean mapWithFather = false;
	
	CommonFunctions.usedProcs = new ArrayList<Proc>();

	for(Operator root : applications) {
	    possible = false;
	    mapped = false;
	    
	    MyArrayList<Operator> application = new MyArrayList<Operator>(); 
	    createApplicationList(root, application);
	    
 // 	    System.out.println("\napplication:");
//  	    for(Operator op: application)
//  		System.out.println(op);
	    
	    QuickSorter.sortOpId(application);
	    if(CompileTimeCondition.DEBUG)
		System.out.println("\napplication (app"+application.get(0).app+") sorted by id:");
	    if(CompileTimeCondition.DEBUG)
		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("\napplication ("+application.get(0).app+"):");
		if(CompileTimeCondition.DEBUG)
		    for(Operator op: application)
			System.out.println(op);
		
		possible = false;
		mapped = false;
		Operator actOp = application.get(0);
		application.remove(actOp);
	
		System.out.println("\nactOp: "+actOp);
		if(!actOp.isMapped){
		int genOpPos = RunHeuristics.operators.indexOf(actOp);
		Operator genOp =  RunHeuristics.operators.get(genOpPos);
		
		boolean biologicalChildrenAreMapped = false;
		for(Operator op : actOp.operators) {
		    if(op.isMapped) biologicalChildrenAreMapped = true;
		}
		if(actOp.operators.isEmpty()) biologicalChildrenAreMapped = true;
		//if(actOp.operators == null) biologicalChildrenAreMapped = true;
		
		if(genOp.isMapped && actOp.father.id < 0) {
		    mapped = false;
		    if(CompileTimeCondition.BIG_OUTPUT)
			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.operators.isEmpty() && actOp.father.id > 0 && (!actOp.father.isMapped)) {
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("General op is already mappend on a proc and act Op is at bottom");
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("try to add comm link to additional father");
		    mapped = CommonFunctions.addFatherLinkForLeaf(actOp, genOp, BOTTOM_UP_DFS);
		    
		} else if(genOp.isMapped && !biologicalChildrenAreMapped && actOp.father.id > 0) {
		    /* general Op is already mapped on a proc */
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("General op is already mappend on a proc and actOPs biological children not");
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("NEED to map not-mapped father on a proc and add link");
		    
		    //  Operator fatherOp = actOp.father;
		    Operator genFatherOp = getGenOp(actOp.father);
		    MyArrayList<Operator> alreadyMapped = new MyArrayList<Operator>();
		    Operator tmpActOp,  genChildOp; Operator child = null;

		   			
		    if( genFatherOp.isMapped ){ //&& !biologicalChildrenAreMapped) {
			/* father (gen) of actOp is already mapped on a proc (and none of actOp's biological children), going up in the tree*/
			
			tmpActOp = actOp.father;
			child = actOp;
			
			application.removeExactly(tmpActOp);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("1 RRemoving "+tmpActOp+" from application list");			

			alreadyMapped.add(child);
			alreadyMapped.add(tmpActOp);
			mapWithFather = false;
			while(getGenOp(tmpActOp).isMapped) { //&& !tmpActOp.isMapped) { // && !biologicalChildrenAreMapped) {
			    if(CompileTimeCondition.DEBUG)
			    System.out.println(tmpActOp+" (genOp) is mapped and biological children not");
			    
			    //if(tmpActOp.isMapped) System.out.println("HIER IST WAS ZU AENDERM?????, tmpActOP "+tmpActOp+" is already mapped");
			    child = tmpActOp;
			    tmpActOp = child.father;
			    if(tmpActOp.id < 0) break;
			    if(tmpActOp.isMapped) { 
				mapWithFather = true;
				break;
			    }
			    alreadyMapped.add(tmpActOp);
			    application.removeExactly(tmpActOp);
			    if(CompileTimeCondition.DEBUG)
				System.out.println("2 RRemoving "+tmpActOp+" from application list");
			 
		}
			
			genChildOp = getGenOp(child);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("child: "+child+"_app"+child.app+" father: "+tmpActOp+"_app"+tmpActOp.app);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("genOp of child: "+genChildOp+"_app");
			
		    } else {
			/* genOp is mapped, but father not */
			alreadyMapped.add(actOp);
			if(actOp.father.id > 0) {
			    alreadyMapped.add(actOp.father);
			    application.remove(actOp.father);
			    if(CompileTimeCondition.DEBUG)
				System.out.println("removing "+actOp.father+" from application list");
			    if(CompileTimeCondition.BIG_OUTPUT)			    
				System.out.println("father "+actOp.father+" not mapped yet, adding "+actOp+" and "+actOp.father+" to alreadyMappedList");
			 
			}
		    }
		    while(!possible && alreadyMapped.size()>2 ) {
			for(Operator op : alreadyMapped)
			    System.out.print(op+" ");
			child = alreadyMapped.get(alreadyMapped.size()-2);
			tmpActOp = alreadyMapped.get(alreadyMapped.size()-1);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("\n# tmpActOp (father) "+tmpActOp+" and child "+child); 
			if(child.isMapped) {
			    /* the child is already mapped because of a added link in the past */
			    /* trying first to add tmpActOp on the proc of child */
			    System.out.println("attention!!! the child in the application is "+
					       "already mapped, do NOT NEED to add link, but first try to add on childProc"); 
			    Proc proc = CommonFunctions.getProcOfOp(child);
			    possible = CommonFunctions.mapOpOnChildProc(tmpActOp, proc, BOTTOM_UP_DFS);
			    if(possible) 
				if(CompileTimeCondition.DEBUG)
				    System.out.println("tmpActOp "+tmpActOp+" has been mapped on child proc "
						   +proc+" of child "+child);
				else
				    if(CompileTimeCondition.DEBUG)
					System.out.println("the mapping was not possible, try to add a link now");
			    
			} //else {
			if(!possible) {
			    boolean success = false;
			    if(mapWithFather) {
				if(CompileTimeCondition.DEBUG)
				    System.out.println("* Trying to add link between genOp of "+tmpActOp+" and the father "+tmpActOp.father+":");
				/* try to add Link between genOp of tmpActOp and tmpActOp.father */
				/* this is due to the fact, that the father is already mapped of this application and he needs */
				/* the informations of tmpActOp, which is already mapped in another application, but no information */
				/* is sent to this application. so as in top down, we simply try to add a link between 2 procs */
				success = CommonFunctions.addLink(tmpActOp.father, getGenOp(tmpActOp), tmpActOp, BOTTOM_UP_DFS);
				possible = success;
				if(success)
				    System.out.println("Link between genOp of "+tmpActOp+" and the father "+tmpActOp.father+" was added");
				else 
				    if(CompileTimeCondition.BIG_OUTPUT)
					System.out.println("Link between genOp of "+tmpActOp+" and the father "+tmpActOp.father+" COULD NOT BE ADDED!!");
			    }
			    if(!success) {
				/* try to add Link between genOp of child and tmpActOp */ 
				Proc proc = tryToFindAProcForOp(tmpActOp, strategy, procs);
				if(proc != null) {
				    if(CompileTimeCondition.BIG_OUTPUT)
					System.out.println("trying to add Link(1) between "+tmpActOp+" and "+child); 
				    genChildOp = getGenOp(child);
				    possible = CommonFunctions.addLinkAndMapFather(tmpActOp, proc, genChildOp, child, BOTTOM_UP_DFS);
				} else possible = false;
				if(possible)
				    if(CompileTimeCondition.BIG_OUTPUT)
				    System.out.println("added Link with SUCCESS");
				else {
				    if(CompileTimeCondition.BIG_OUTPUT)
					System.out.println("link NOT ADDED(1)");
				    alreadyMapped.remove(tmpActOp);
				    application.add(tmpActOp);
				    if(CompileTimeCondition.DEBUG)
					System.out.println("adding "+tmpActOp+" back to application list");
				}
			    }
			}
		    }
		    
		    if(possible && application.size() > 0) {
			mapped = true;
			if(CompileTimeCondition.DEBUG)
			    System.out.println(child+" > "+application.get(0));
			int pos = 0;
			while(pos < application.size() && application.get(pos).id < child.id){
			    Operator tmp = application.get(pos);
			    if(CommonFunctions.isAncestor(tmp,child)){
				if(CompileTimeCondition.DEBUG)
				    System.out.println("removing "+application.get(pos)+" from application");
				application.remove(pos);
			    } else pos++;
			}
		    }
		     if(application.size() >1)
			QuickSorter.sortOpId(application);
		    
		    
			
		} else {
		    /* general operator is not mapped yet */
		    /* or biological children of actOp are mapped and shortcut of mappedGenop is not possible*/
		    if(!genOp.isMapped)
			if(CompileTimeCondition.DEBUG)
			    System.out.println("general Op not mapped yet");
		    if(biologicalChildrenAreMapped)
			if(CompileTimeCondition.DEBUG)
			    System.out.println("biological children of actOp are mapped and shortcut of mappedGenop is not possible");
		    
		    if(!actOp.operators.isEmpty()) {
			/* operator has other operators as children -> no al-op */
			/* in theory: all operator children are already mapped */
			if(CompileTimeCondition.DEBUG)
			    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_DFS);
				if (possible) {
				    /* operator is mapped on child proc */
				    mapped = true;
				    
				} else 
				    if(CompileTimeCondition.DEBUG)
				    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.DEBUG)
			    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_DFS);
			if(possible) {
			    System.out.println("mapping  of "+actOp+" was SUCCESSFUL on "+actProc);
			    mapped = true;
			} else 
			    if(CompileTimeCondition.BIG_OUTPUT)
				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++;	
		    }   
		}
		} else {
		    if(CompileTimeCondition.BIG_OUTPUT)
		    System.out.println("actOP "+actOp+" is already Mapped, nothing to do for this node");
		    mapped = true;
		}
		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);
	}
    }


}