/*
 * Created on 09.11.2003 20:56:46
 *
 * Multimediale Algorithmen und Datenstrukturen Assessments
 */
package mauda.plugin.fibheap;

import mauda.*;
import mauda.operation.*;
import mauda.plugin.*;

import java.util.*;

/**
 * The analyzer-class for automatic generation of FibHeap-
 * Exercises.
 * 
 * @author Markus Krebs
 */
public class FibHeapAnalyse implements Analysable {
	
	/**
	 * Creates a FibHeap-Analyzer
	 */
	public FibHeapAnalyse() {
		// EMPTY
	}

	/* (non-Javadoc)
	 * @see mauda.plugin.Analysable#getOperations(java.lang.Object)
	 */
	public OperationQueue getOperations(Object o) {
		FibHeapDSExt fibHeap = null;
		if(o instanceof FibHeapExt) {
			fibHeap = (FibHeapDSExt)((FibHeapExt)o).copyDS();
		} 
		else if(o instanceof FibHeapDSExt) {
			fibHeap = (FibHeapDSExt)((FibHeapDSExt)o).clone();
		}
		
		//long millis = System.currentTimeMillis();
		Vector presentKeys = getPresentKeys(fibHeap);
		Vector randomKeys = getRandomKeysFromIntervalls(fibHeap, presentKeys);

		//printOut("Present Keys:", presentKeys);
		//printOut("Random Insertion-Keys:", randomKeys);

		OperationQueue v = new OperationQueue();
		v.addAll(genInserts(randomKeys));
		v.addAll(genDeletemin(presentKeys));
		v.addAll(genDeletes(presentKeys));
		v.addAll(genDecreasekeys(presentKeys, randomKeys));

		calcOperations(fibHeap, v);

		//millis = System.currentTimeMillis()-millis;
		//System.out.println("TIME to calculate: "+millis+"ms ("+v.size()+" Operations)");
		//GeneralAnalyst.calcTime = millis;
		//GeneralAnalyst.calcCount = v.length();
		//GeneralAnalyst.keysCount = presentKeys.size();
		return v;
	}
	// Operationenfolge mit einem bestimmten Schwierigkeitsgrad zurückgeben
	private OperationQueue getInstanceWithDifficulty(OperationQueue givenOQ, int difficulty, FibHeapDSExt fibHeap) {
		int overallRating = 0;
		OperationQueue operationQueueToReturn = new OperationQueue();
		for(int i=0; i<givenOQ.length(); i++) {
			// mögliche Operationen holen
			OperationQueue oq = getOperations(fibHeap);
						
			Operation[] op = oq.toArray();
			
			Operation.setSort(Operation.SORT_BY_RATING);
			Arrays.sort(op);
			
			/*
			String msg = "SHOULD BE SORTED BY RATING\n";
			for(int j=0; j<op.length; j++) {
				msg += j+". "+op[j]+"\n";
			}
			javax.swing.JOptionPane.showMessageDialog(MAUDA.getApplicationMainFrame(), msg);
			*/
			

			String actOp = givenOQ.get(i).getID();

			Operation opToExecute = null;

			if(actOp.equals("DELETE_MIN")) {
				if(fibHeap.getHeapSize()>0)
					opToExecute = new Operation("DELETE_MIN", Operation.NULL, Operation.NULL, Operation.NULL);
			}
			else {
				// Grenzen der in Frage kommenden Ratings
				int min = op[0].getRating();
				int max = op[op.length-1].getRating();
				float delta = (max-min)/Difficulties.DIFFICULTY_LEVELS;
				int dmin = min+Math.round(delta*(float)difficulty);	// Grenzen für in Frage kommende Operationsratings
				int dmax = max-Math.round(delta*(float)(Difficulties.DIFFICULTY_LEVELS-difficulty-1));
				//if(difficulty==DIFFICULTY_LEVELS-1) dmax = max;
				int minIndex = 0;
				int maxIndex = op.length;
				for(int j=op.length-2; j>=0; j--) if(op[j].getRating()<dmin) { minIndex = j+1; break; }
				for(int j=0; j<op.length; j++) if(op[j].getRating()>dmax) { maxIndex = j; break; }	

				// Alle Operation herausfiltern, die der aktuellen entsprechen
				Vector vec = new Vector();
				for(int j=minIndex; j<maxIndex; j++) {
					if(op[j].getID().equals(actOp)) vec.add(op[j]);
				}
				// Falls es in dem Bereich keine solche Operation gibt dann
				if(vec.size()==0) {
					// nach unten abgrasen
					int j=minIndex;
					while(j>=0&&!op[j].getID().equals(actOp)) j--;
					// nacht oben abgrasen wenn unten nichts gefunden wurde
					if(j<0) {
						j=maxIndex;
						while(j<op.length-1&&!op[j].getID().equals(actOp)) j++;
					}
					if(j>=0&&j<op.length) opToExecute = op[j];
				}
				else {
					int sel = (int)(Math.random()*(double)vec.size());
					opToExecute = (Operation)vec.elementAt(sel);
				}
			}
			if(opToExecute!=null) {
				opToExecute.execute(fibHeap);
				overallRating+=opToExecute.getRating();
				/*
				javax.swing.JOptionPane.showMessageDialog(MAUDA.getApplicationMainFrame(),
													"min = "+min+"\n"+
													"max = "+max+"\n"+
													"dmin = "+dmin+"\n"+
													"dmax = "+dmax+"\n"+
													"minIndex = "+minIndex+"\n"+
													"maxIndex = "+maxIndex+"\n"+
													"#Ops = "+op.length+"\n"+
													"Op = "+opToExecute);
				System.out.println("SCRAMBLE: "+opToExecute);*/			
				operationQueueToReturn.add(opToExecute);
			}
		}
		operationQueueToReturn.setRating(overallRating);
		return operationQueueToReturn;
	}

	/* (non-Javadoc)
	 * @see mauda.plugin.Analysable#init(java.lang.Object, mauda.operation.OperationQueue, int, int)
	 */
	// Instanz zu gegebener Menge von Initial-Operationen berechnen
	// Bemerkung: difficulty wird hier nicht benötigt
	// ---> Momentan ist diese Routine relativ kompatibel zu anderen Aufgaben (da dsObject)
	public OperationQueue init(Object o, OperationQueue givenOperations, int difficulty, int mode) {
		// Init-FaultMode (im Moment bei allen Modi gleich)
		//if(mode == ExerciseMode.FAULT) return null;
		Object dsObject = null;
		if(o instanceof FibHeapExt) {
			//FibHeapExt fibHeap = (FibHeapExt)o;
			FibHeapDSExt fibHeapCopy = (FibHeapDSExt)((FibHeapExt)o).copyDS();
			dsObject = fibHeapCopy;
		} else if(o instanceof FibHeapDSExt) {
			dsObject = (FibHeapDSExt)((FibHeapDSExt)o).clone();
		}
		OperationQueue oq = new OperationQueue();
		if(dsObject!=null) {
			int[] keys = new int[GeneralAnalyst.maxKey];
			Arrays.fill(keys, -1);
			keys[0]=0;	// 0-Schlüssel nicht erlauben
			oq = new OperationQueue();
			Enumeration en = givenOperations.toVector().elements();
			while(en.hasMoreElements()) {
				Operation op = (Operation)en.nextElement();
				Operation todoOp = null;
				if(op.getID().equals("INSERT")) {
					int value = -1;
					do { value = (int)(Math.round(Math.random()*(double)99));
					} while(keys[value]!=-1);
					keys[value] = 1;
					todoOp = new Operation("INSERT",
											value,
											Operation.NULL,
											Operation.NULL);
				} else if(op.getID().equals("DELETE_MIN")) {
					boolean empty=true;
					for(int i=0; i<keys.length; i++)
						if(keys[i] == 1) { empty = false; break; }
					if(!empty)
						todoOp = new Operation("DELETE_MIN");
				}
				if(todoOp!=null) {
					todoOp.execute(dsObject);
					oq.add(todoOp);
				}
			}
		} 
		return oq;
	}
	/* (non-Javadoc)
	 * @see mauda.plugin.Analysable#scramble(java.lang.Object, mauda.operation.OperationQueue, int, int)
	 */
	// Durcheinander-Operationen-Berechnung
	public OperationQueue scramble(Object o, OperationQueue givenOperations, int difficulty, int mode) {
		// Scramble-FaultMode (im Moment bei allen Modi gleich)
		//if(mode == ExerciseMode.FAULT) return null;
		// NEU
		Object dsObject = null;
		if(o instanceof FibHeapExt) {
			//FibHeapExt fibHeap = (FibHeapExt)o;
			FibHeapDSExt fibHeapCopy = (FibHeapDSExt)((FibHeapExt)o).copyDS();
			dsObject = fibHeapCopy;
		} else if(o instanceof FibHeapDSExt) {
			dsObject = o;
		}
		FibHeapDSExt fibHeap = (FibHeapDSExt)dsObject;
		// ALT
		//FibHeapDSExt fibHeap = (FibHeapDSExt)o;
		
		givenOperations.shuffleDelmin();
		FibHeapDSExt fibHeapCopy = (FibHeapDSExt)fibHeap.clone();
		OperationQueue oq =
			getInstanceWithDifficulty(givenOperations, difficulty, fibHeapCopy);

		return oq;
	}
	
	/* (non-Javadoc)
	 * @see mauda.plugin.Analysable#autoGen(java.lang.Object, mauda.operation.OperationQueue, int, int)
	 */
	// Aufgabenstellungs-Operationen-Berechnung
	public OperationQueue autoGen(Object o, OperationQueue givenOperations, int difficulty, int mode) {
		// AutoGen-FaultMode (im Moment bei allen Modi gleich)
		//if(mode == ExerciseMode.FAULT) return null;
		// NEU
		Object dsObject = null;
		if(o instanceof FibHeapExt) {
			FibHeapDSExt fibHeapCopy = (FibHeapDSExt)((FibHeapExt)o).copyDS();
			dsObject = fibHeapCopy;
		} else if(o instanceof FibHeapDSExt) {
			dsObject = o;
		}
		FibHeapDSExt fibHeap = (FibHeapDSExt)dsObject;
		// ALT
		//FibHeapDSExt fibHeap = (FibHeapDSExt)o;
		
		OperationQueue retOQ = new OperationQueue();
		int permSize = 4;
		FibHeapDSExt work = (FibHeapDSExt)fibHeap.clone();			
		givenOperations.shuffle();
		OperationQueue temp = (OperationQueue)givenOperations.clone();
		do {
			OperationQueue oqInput = (OperationQueue)temp.clone();
			while(oqInput.length()>permSize) oqInput.remove(permSize);
			
			OperationQueue[] oqs = calcPermutations(work, oqInput, difficulty);
			//OperationQueue[] oqs = FibHeapAnalyse.calcPermutations((FibHeapOperations)o);
			OperationQueue oq = null;
			switch(difficulty) {
				case Difficulties.EASY	: oq = oqs[0]; break;
				case Difficulties.MEDIUM	: oq = oqs[Math.round(oqs.length/2)]; break;
				case Difficulties.HARD	: oq = oqs[oqs.length-1]; break; 
			}
			//javax.swing.JOptionPane.showMessageDialog(MAUDA.getApplicationMainFrame(), oq);
			if(oq!=null) {
				retOQ.addAll(oq);
				java.util.Enumeration en = oq.toVector().elements();
				while(en.hasMoreElements()) {
					Operation op = (Operation)en.nextElement();
					op.execute(work);
				}
			} 
			int l = temp.length()>permSize?permSize:temp.length();
			for(int i=0; i<l; i++) temp.remove(0);
		} while(temp.length()>0);
		return retOQ;
	}
	
	/* (non-Javadoc)
	 * @see mauda.plugin.Analysable#fullAutomatic(java.lang.Object, mauda.operation.OperationQueue, mauda.operation.OperationQueue, mauda.operation.OperationQueue, int, int)
	 */
	public OperationQueue[] fullAutomatic(Object o,
					OperationQueue initOQ,
					OperationQueue scrambleOQ,
					OperationQueue autoGenOQ,
					int difficulty,
					int mode) {
		if(mode == ExerciseMode.FAULT) return null;
		Object dsObject = null;
		if(o instanceof FibHeapExt) {
			FibHeapDSExt fibHeap = (FibHeapDSExt)((FibHeapExt)o).copyDS();
			dsObject = fibHeap;
		} else if(o instanceof FibHeapDSExt) {
			dsObject = (FibHeapDSExt)((FibHeapDSExt)o).clone();
		}
		if(dsObject==null) return null;

		OperationQueue[] mainOQ = new OperationQueue[2];
		mainOQ[0] = new OperationQueue();
		mainOQ[1] = new OperationQueue();
		OperationQueue oq;
		// Init
		oq = init(dsObject, initOQ, difficulty, mode);
		oq.execute(dsObject);
		mainOQ[0].addAll(oq);
		// Scramble
		oq = scramble(dsObject, scrambleOQ, difficulty, mode);
		oq.execute(dsObject);
		mainOQ[0].addAll(oq);
		// AutoGen
		oq = autoGen(dsObject, autoGenOQ, difficulty, mode);
		oq.execute(dsObject);
		mainOQ[1].addAll(oq);
		return mainOQ;
	}
	
	
	// Alle möglichen Permutationen einer Operationshäufigkeitsvorgabe berechnen
	private OperationQueue[] calcPermutations(FibHeapDSExt fibHeap, OperationQueue givenOperations, int difficulty) {
		long millis = System.currentTimeMillis();
				
		// Permutationsberechnung
		OperationQueue[] permutations = givenOperations.getPermutations();
		
		FibHeapDSExt fibHeapOriginal = (FibHeapDSExt)fibHeap.clone();
		for(int i=0; i<permutations.length; i++) {
			FibHeapDSExt fibHeapCopy = (FibHeapDSExt)fibHeapOriginal.clone();
			permutations[i] =
				getInstanceWithDifficulty(permutations[i], difficulty, fibHeapCopy);
		}
		//-----------------------------------------------------
		
		Arrays.sort(permutations);
		
		millis = System.currentTimeMillis()-millis;
		
		// Ausgabe
		/*
		String s = "PERMUTATIONEN: (Time: "+millis+"ms)\n\n";
		for(int i=0; i<permutations.length; i++) {
			s += (i+1)+": "+permutations[i]+"\n";
		}
		javax.swing.JOptionPane.showMessageDialog(MAUDA.getApplicationMainFrame(), s);
		*/

		// Alle Permutationen zurückgeben
		return permutations;	
	}

	// Berechnung der Ratings der Operationen durch Ausführung auf Kopie
	private void calcOperations(FibHeapDSExt fibHeap, OperationQueue operations) {
		FibHeapDSExt fibHeapCopy;
		for(int i=0; i<operations.length(); i++) {
			Operation op = operations.get(i);
			fibHeapCopy = (FibHeapDSExt)fibHeap.clone();
			op.execute(fibHeapCopy);
		}
	}

	// decrease-keys
	private OperationQueue genDecreasekeys(Vector pKeys, Vector rKeys) {
		OperationQueue vec = new OperationQueue();
		Enumeration en = pKeys.elements();
		while(en.hasMoreElements()) {
			int k = ((Integer)en.nextElement()).intValue();
			Enumeration en2 = rKeys.elements();
			while(en2.hasMoreElements()) {
				int newKey = ((Integer)en2.nextElement()).intValue();
				if(newKey<k) {
					Operation op = new Operation(	"DECREASE_KEY",
													k,
													newKey,
													Operation.NULL);
					vec.add(op);
				}
			}
		}
		return vec;
	}

	// delets
	private OperationQueue genDeletes(Vector keysVec) {
		OperationQueue vec = new OperationQueue();
		Enumeration en = keysVec.elements();
		while(en.hasMoreElements()) {
			int k = ((Integer)en.nextElement()).intValue();
			Operation op = new Operation(	"DELETE",
											k,
											Operation.NULL,
											Operation.NULL);
			vec.add(op);
		}
		return vec;
	}

	// Delete-Min
	private OperationQueue genDeletemin(Vector keysVec) {
		OperationQueue vec = new OperationQueue();
		if(keysVec.size()==0) return vec;
		Operation op = new Operation(	"DELETE_MIN",
										Operation.NULL,
										Operation.NULL,
										Operation.NULL);
		vec.add(op);
		return vec;
	}

	// mögliche Inserts
	private OperationQueue genInserts(Vector keys) {
		OperationQueue vec = new OperationQueue();
		Enumeration en = keys.elements();
		while(en.hasMoreElements()) {
			int k = ((Integer)en.nextElement()).intValue();
			Operation op = new Operation(	"INSERT",
											k,
											Operation.NULL,
											Operation.NULL);
			vec.add(op);
		}
		return vec;
	}

	// Ausgabe eines Vectors mit Titel
	private void printOut(String s, Vector v) {
		System.out.print(s+"  ");
		Enumeration en = v.elements();
		while(en.hasMoreElements()) {
			int k = ((Integer)en.nextElement()).intValue();
			System.out.print(k+" ");
		}
		System.out.println();
	}

	// Alle belegten Schlüssel
	private Vector getPresentKeys(FibHeapDSExt fibHeap) {
		FibNodeDS[] keys = fibHeap.getAllNodes();
		Vector vec = new Vector();
		for(int i=0; i<keys.length; i++)
			if(keys[i]!=null) vec.add(new Integer(i));
		return vec;
	}
	// Berechung von zufälligen Zwischenwerten aus den Intervallen, die durch die bereits
	// vorhandenen Schlüssel definiert werden.
	private Vector getRandomKeysFromIntervalls(FibHeapDSExt fibHeap, Vector presentKeys) {
		FibNodeDS[] keys = fibHeap.getAllNodes();
		int maxKey = keys.length;
		Vector vec = new Vector();
		int start=1;	// keine Werte kleiner als 1 erlauben (0 ausschliessen)
		int end=1;
		do {
			while(start<maxKey&&keys[start]!=null) start++;
			end=start;
			while(end<maxKey&&keys[end]==null) end++;
			int width = end-start;
			if(width>0) {
				int r = (int)(Math.random()*(double)width);
				vec.add(new Integer(start+r));
				//System.out.print(start+"-"+(end-1)+"  ");
			}
			start=end;
		} while(start<maxKey&&end<maxKey);
		//System.out.println();
		return vec;
	}
}
