import java.util.*;

public class RandomIntelligent {
    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++;
//     }
    
    private static void traverseTree(Operator root, MyArrayList<Operator> operatorList) {
	operatorList.add(root);
	for(Operator op : root.operators)
	    traverseTree(op, operatorList);
    }
    
 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.DEBUG)
	    System.out.println("Proc where to map on: "+actProc);
	    double cardUsage;
	    cardUsage = CommonFunctions.tryToMapOpOnProc(actOp,actProc, RANDOM);
	    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;
	
    }
    
    private static void deleteSubtreeFromList(Operator root, MyArrayList list) {
	Proc proc = null;

	for(Operator op : root.operators) {
	    int listPos = RunHeuristics.operators.indexOf(op);
	    Operator genOp = RunHeuristics.operators.get(listPos);

	    if(!op.isMapped) 
		if(genOp.isMapped) 
		    if(root.procs.size() > 0) {
			proc = root.procs.get(0);
			//System.out.println("NEW: root.procs.size():"+root.procs.size());
			if(!proc.children.containsExactly(op)) 
			    deleteSubtreeFromList(op, list);
		    } else 
			deleteSubtreeFromList(op, list);
		else {
		    if(CompileTimeCondition.DEBUG){
			System.out.println(op+" is not mapped yet, but gen neither, stopping delete of this branch here");
		    }
		}
	    else{
		if(CompileTimeCondition.DEBUG)
		    System.out.println(op+" is already mapped, stopping delete of this branch here");
	 	if(!op.father.isMapped) {
		    proc = op.procs.get(0);
		    proc.fathers.removeExactly(root);
		    if(CompileTimeCondition.DEBUG)
			System.out.println("Removing "+root+" from fatherList of "+proc+"(for "+op+", as "+root+" will be deleted.");
	 	} else {
		    if(CompileTimeCondition.DEBUG)
			System.out.println("No remove of "+root+" from fatherList of "+proc+"(for "+op+") as "+root+" is already mapped.");
 		}
	    }
	    
	}
	list.removeExactly(root);
    }

    /* picks randomly an operator and trys to map it, but application after application */
    /* this allows us maybe to save some computations in the later mapped applications */
    public static Mapping randomIntelligent(MyArrayList<Operator> rootList, int strategy, ArrayList<Proc> procs, Random rand) {
	Proc actProc;
	boolean possible = false;
	boolean mapped = false;
	int actPos;

	CommonFunctions.usedProcs = new ArrayList<Proc>();	
	
	for(Operator root: rootList) {
	    MyArrayList<Operator> untreatedOperators = new MyArrayList<Operator>();
	    
	    traverseTree(root, untreatedOperators);
	    
	    
	    switch(strategy) {
		
	    case FASTEST: 
		QuickSorter.sortFastest(procs);
		break;
	    case NETWORK_CARD:
		if(CompileTimeCondition.DEBUG)
		    System.out.println("NUMBER of procs :"+procs.size());
		QuickSorter.sortCard(procs);
		break;
	    default:
		
	    }
	    if(CompileTimeCondition.BIG_OUTPUT){
		System.out.println("\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^");
		System.out.println("^^ Treating application "+untreatedOperators.get(0).app+": ^^");
		System.out.println("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^");
	    }
	    
	    while(!untreatedOperators.isEmpty()) {
		mapped = false;
		
		actPos = rand.nextInt(untreatedOperators.size());
		Operator actOp = untreatedOperators.get(actPos);
		System.out.println("\nact Op: "+actOp+" app"+actOp.app);
		
		untreatedOperators.removeExactly(actOp);
		int listPos = RunHeuristics.operators.indexOf(actOp);
		Operator genOp = RunHeuristics.operators.get(listPos);
		if(CompileTimeCondition.DEBUG)
		System.out.println("general Op: "+actOp);
		
	    /* operator not yet mapped on proc */
		if(!genOp.isMapped) {
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("generalOp not mapped yet");
		    
		    /* father is already mapped, try to add to father proc */
		    if(actOp.father.isMapped) {
			if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("father "+actOp.father+" is already mapped, try to map "+actOp+" on father proc");
			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+":");
			    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 */
				mapped = true;
			    } else 
				if(CompileTimeCondition.BIG_OUTPUT)
				    System.out.println("mapping was not possible: "+actOp+" on "+actProc);
			    pos++;
			}
		    }
		    
		    if(!mapped) {
			if(!actOp.father.isMapped)
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("father "+actOp.father+" not yet mapped"); 
			
			int pos = 0;
			
			while(!mapped && pos < actOp.operators.size()) {
			    Operator child = actOp.operators.get(pos);
			    
			    /* child is already mapped -> try to map on child proc */
			    if(child.isMapped && child.procs.size() > 0) {
				if(CompileTimeCondition.BIG_OUTPUT)
				    System.out.println("child "+child+" is already mapped -> try to map on child proc"); 
				actProc = child.procs.get(0);
				possible = CommonFunctions.mapOpOnChildProc(actOp, actProc, BOTTOM_UP_DFS);
				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) {
			    /* actOp could not be mapped onto a child proc */
			    pos = 0;
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println(actOp+" could not be mapped onto a child proc");
			    
			    while(!mapped && pos < actOp.operators.size()) {
				Operator child = actOp.operators.get(pos);
				
				int genOpPosChild = RunHeuristics.operators.indexOf(child);
				Operator genChild = RunHeuristics.operators.get(genOpPosChild);  
				
				/* genchild is already mapped, map op on proc and add link */
				if(genChild.isMapped) {
				    Proc proc = tryToFindAProcForOp(actOp, strategy, procs);
				    if(proc != null) {
					if(CompileTimeCondition.BIG_OUTPUT)
					    System.out.println("trying to add Link(1) between "+actOp+" and "+genChild); 
					
					possible = CommonFunctions.addLinkAndMapFather(actOp, proc, genChild, child, RANDOM);
				    } else possible = false;
				    if (possible) {
					/* operator is mapped on child proc */
					mapped = true;
					if(CompileTimeCondition.BIG_OUTPUT)
					    System.out.println("added Link with SUCCESS");
					
					/* delete child rooted subtree from untreatedOperator list */
					deleteSubtreeFromList(child, untreatedOperators);
					if(CompileTimeCondition.BIG_OUTPUT)
					    System.out.println("Deleted subtree rooted by "+child);
					
				    } else 
					if(CompileTimeCondition.BIG_OUTPUT)
					    System.out.println("mapping was not possible: "+actOp+" on "+proc);
				}
				pos++;
			    }	
			}
		    }
		} else {
		    /* operator already mapped on a proc */
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println("genOp already mapped on a proc");
		    if(actOp.father.isMapped && !actOp.father.procs.isEmpty()) {
			possible = CommonFunctions.addLink(actOp.father, genOp, actOp, RANDOM);
			if(possible) {
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("\n*******link added.(outside)*******\n");
			    actOp.isMapped = true;
			    mapped = true;	
			    
			    /* delete child rooted subtree from untreatedOperator list */
			    deleteSubtreeFromList(actOp, untreatedOperators);
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("Deleted subtree rooted by "+actOp);
			    
			} else 
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("link could not be added");
		    } else { 
			if(actOp.father.id > 0 && untreatedOperators.containsExactly(actOp.father)) {
			    /* father not mapped yet (genOp may be mapped!) */
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("father not mapped yet (genOp may be mapped!)");
			    Proc proc = tryToFindAProcForOp(actOp.father, strategy, procs);
			    if(proc != null) {
				if(CompileTimeCondition.BIG_OUTPUT)
				    System.out.println("trying to add Link(1) between "+actOp.father+" and "+genOp); 
				possible = CommonFunctions.addLinkAndMapFather(actOp.father, proc, genOp, actOp, RANDOM);
			    } else possible = false;
			    if(possible) {
				if(CompileTimeCondition.DEBUG)
				    System.out.println("Deleting father "+actOp.father+" from untreatedOp list");
				untreatedOperators.removeExactly(actOp.father);
				if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("added Link with SUCCESS");
				mapped  = true;
				
				/* delete child rooted subtree from untreatedOperator list */
				deleteSubtreeFromList(actOp, untreatedOperators);
				if(CompileTimeCondition.DEBUG)
				    System.out.println("Deleted subtree rooted by "+actOp);
				
			    } else 
				if(CompileTimeCondition.BIG_OUTPUT)
				    System.out.println("link NOT ADDED(1)");			
			} else {
			    System.out.println("father not mapped yet, but already deleted from untreatedOp list.");
			}
		    }
		    
		}
		
		if(!mapped){
		    /* operator either could not be mapped yet or no neighbour (father or child) is mapped */
		    /* looking for a proc */
		    if(CompileTimeCondition.BIG_OUTPUT)
			System.out.println(actOp+" still not mapped, trying to find a proc");
		    
		    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.DEBUG)
			    System.out.println("Proc where to map on: "+actProc);
			
			possible = CommonFunctions.mapOpOnProc(actOp,actProc, RANDOM);
			if(CompileTimeCondition.DEBUG)
			    System.out.println("mapping was successful on "+actProc+": "+possible);
			/* operator is mapped on proc */
			if(possible) {
			    System.out.println("mapping was SUCCESSFULL on "+actProc);
			    if(!CommonFunctions.usedProcs.contains(actProc)) CommonFunctions.usedProcs.add(actProc);
			    if(strategy == FASTEST || strategy == NETWORK_CARD)
				procs.remove(actProc);
			    
			    
			    
			
			    mapped = true;
			    
			} else 
			    if(CompileTimeCondition.BIG_OUTPUT)
				System.out.println("mapping was NOT successfull on "+actProc);
			
			pos++;
		    }
		}
		if(!mapped) return  (new Mapping());
		
	    } // end while(!untreatedOpertor.isEmpty())
	} // end for(root)  (each application)	
	
	Mapping mapping = new Mapping(possible, CommonFunctions.usedProcs);
	return mapping;
    }
 
   
}