package org.spbu.bdd.samples.schedule;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import org.spbu.bdd.core.Bdd;
import org.spbu.bdd.core.Bdd.BinOp;
import org.spbu.bdd.core.Bdd.Filter;
import org.spbu.bdd.samples.schedule.InstructionDAG.Vert;

public class ScheduleBdd {
	InstructionDAG dag;

	class ContextStorage {

		class ScheduleFilter implements Filter<Integer> {
			int stopVal = InstructionDAG.NOPVAL-1;
			@Override
			public Integer getStopVal() {
				return stopVal;
			}

			@Override
			public boolean isSolution(LinkedList<Integer> lst) {
				return true;
			}

			@Override
			public boolean canBeInSolution(Integer value, int index) {
				return !(stopVal==value);
			}

			@Override
			public void checkFinished() {
			}
		}

		public class condE implements BinOp<Integer,Integer,Integer> {

			@Override
			public Integer apply(Integer op1, Integer op2) {
				return (op1.equals(op2)) ? op1 : filter.getStopVal();
			}
		}
		
		
		// cycle independent conditions ("apply" uses hash table, can't work
		// with parameters changing outside its scope, so we can't just get
		// cycle ## from the addIteration method's "for" and use here)
		public class CommonCond implements BinOp<Integer,Integer,Integer> {

			// We can and WILL schedule something WRONG at current cycle,
			// but during ongoing cycles we will terminate paths where
			// we previously scheduled something wrong.
			
			// here and later finInd=dag.getFinInd()=dag.getSize(), index of
			// imaginable "fin" in the array which supports the DAG
			
			// oldInstrInd is an "index" of some instruction in the DAG,
			// which we scheduled at some earlier cycle, or -1 (for NOP,
			// also scheduled earlier), or >finInd if we tried scheduling a "fin"
			// too early and collected only (oldInstrInd-finInd) instructions
			// instead of (finInd) instructions (see comment for 5-th check)
			
			// newInstrInd is an "index" of some instruction in the DAG,
			// which we are trying to schedule at the current cycle,
			// or >finInd if we are trying to schedule a "fin" and already
			// collected only (oldInstrInd-finInd) instructions instead of
			// (finInd) instructions (see comment for 5-th check). Note,
			// that newInstrInd can't be -1 since NOPs can be scheduled only
			// after all CommonConds are applied - in CycleConds
			
			@Override
			public Integer apply(Integer oldInstrInd, Integer newInstrInd) {
				// Eliminating earlier wrong schedule:
				// can't schedule anything after "fin"
				if (dag.getFinInd()<=oldInstrInd)
					return filter.getStopVal();
				// nop at oldInstrInd doesn't prevent us from scheduling anything at newInstrInd
				if (InstructionDAG.NOPVAL==oldInstrInd)
					return newInstrInd;
				// after this check oldInstrInd is really an index of some instruction
				
				// each instruction must be scheduled only once
				if (newInstrInd.equals(oldInstrInd))
					return filter.getStopVal();
				// newInstrInd==finInd + number of actual, non-NOP, instructions
				// on the path to this "fin". All instructions are scheduled
				// before the "fin" <=> newInstrInd becomes 2*finInd at the end
				// of the "for" in addIteration method, this is used in getResult()
				if (dag.getFinInd()<=newInstrInd)
					return newInstrInd+1;
				// only after this check newInstrInd is really an index of some instruction

				// Eliminating earlier wrong schedule:
				// we must prevent out of order scheduling
				// If we found old.. that does depend on new.., we stop.
				// The mistake (?) occured at earlier cycle,
				// but we can terminate such a solution only now
				if (dag.getInstructions().get(newInstrInd).getSucc().contains(oldInstrInd))
					return filter.getStopVal();
				return newInstrInd;
			}
		}
		
		// cycle dependent conditions (two conditions inserted in CommonCond in
		// the right place). cycleDiff = (#current cycle) - (#cycle when we scheduled
		// instrucion #oldInstrInd)
		public class CycleCond implements BinOp<Integer,Integer,Integer> {

			private int cycleDiff;
			
			public CycleCond(int cycleDiff) {
				this.cycleDiff=cycleDiff;
			}
			
			@Override
			public Integer apply(Integer oldInstrInd, Integer newInstrInd) {
				// Eliminating earlier wrong schedule:
				// can't schedule anything after "fin"
				if (dag.getFinInd()<=oldInstrInd)
					return filter.getStopVal();
				// nops at "new.." can occur only after earlier CycleConds, preserve them
				if (InstructionDAG.NOPVAL==newInstrInd)
					return newInstrInd;
				// nop at oldInstrInd doesn't prevent us from scheduling anything at newInstrInd
				if (InstructionDAG.NOPVAL==oldInstrInd)
					return newInstrInd;
				// after this check oldInstrInd is really an index of some instruction
				
				// each instruction must be scheduled only once
				if (newInstrInd.equals(oldInstrInd))
					return filter.getStopVal();
				
				// we can't schedule a dependent instruction in case of a stall
				int i = (newInstrInd>dag.getFinInd()) ? dag.getFinInd() : newInstrInd;
				Vert v = dag.getInstructions().get(oldInstrInd);
				if (v.getSucc().contains(i))         // "new.." depends on "old.."
					if (v.getInstr().getLatency()>cycleDiff)   // a stall occurs
						return InstructionDAG.NOPVAL;
				// newInstrInd==finInd + number of actual, non-NOP, instructions
				// on the path to this "fin". All instructions are scheduled
				// before the "fin" <=> newInstrInd becomes 2*finInd at the end
				// of the "for" in addIteration method, this is used in getResult()
				if (dag.getFinInd()<=newInstrInd)
					return newInstrInd+1;
				// only after this check newInstrInd is really an index of some instruction

				// Eliminating earlier wrong schedule:
				// we must prevent out of order scheduling
				// If we found old.. that does depend on new.., we stop.
				// The mistake (?) occured at earlier cycle,
				// but we can terminate such a solution only now
				if (dag.getInstructions().get(newInstrInd).getSucc().contains(oldInstrInd))
					return filter.getStopVal();
				return newInstrInd;
			}
		}
		
		// ROBDD for the schedule
		LinkedList<Bdd<Integer>> cycles;
		// Simple filter for use in Bdd.getSolution.
		// It was not that simple during the development ;)
		ScheduleFilter filter;
		// Object for applying a common operation
		// on two instruction indices
		CommonCond commonCond;
		// Object for applying cycle dependent operations
		// on two instruction indices
		CycleCond[] cycleCond;
		// Objects for filtering correct "fin" scheduling
		condE CondE;
		Bdd<Integer> finTerm;
		// just for conversion of LinkedList to array
		Bdd<Integer>[] tmp = new Bdd[0];

		public ContextStorage() {
			filter = new ScheduleFilter();
			commonCond = new CommonCond();
			CondE = new condE();
			cycleCond = new CycleCond[dag.getMaxLatency()];
			for (int i=0; i<dag.getMaxLatency(); i++)
				cycleCond[i] = new CycleCond(i+1);
			Bdd.Init(1000000, 1009, filter, 2000000, 20000);
			finTerm = Bdd.makeConst(2*dag.getFinInd());
			cycles = new LinkedList();
			cycles.add(Bdd.makeConst(filter.getStopVal()).insertNewList(dag.getRoots()));
			// we don't know for sure how much cycles do we need, hence
			// all other additions are made when really needed
		}

		
		public void addIteration(int cycleDiff) {
			List<Integer> lst = dag.getAll();
			// from now on we can potentially schedule "fin"
			if (cycleDiff>=dag.getSize()-1) lst.add(dag.getFinInd());
			Bdd<Integer> elem = Bdd.makeConst(filter.getStopVal()).insertNewList(lst);
			//System.out.println(elem.toString());
			for (Bdd<Integer> cycle : cycles) {
				if (cycleDiff>dag.getMaxLatency())
					// early instructions latencies' influence is already over...
					elem = Bdd.apply(cycle, elem, commonCond);
				else
					// ...but last chosen instructions still may produce nops
					elem = Bdd.apply(cycle, elem, cycleCond[cycleDiff-1]);
				cycleDiff--;
			}
			cycles.add(elem);
		}

		public LinkedList<Integer> getResult(int cycle) {
			Bdd<Integer> restricted = Bdd.apply(cycles.getLast(), finTerm, CondE);
			// "restricted" contains only "stopVal" and "2*dag.getFinInd()" among leaves
			if (restricted.isConst() && !restricted.equals(finTerm))
				return null;
			cycles.removeLast();
			cycles.addLast(restricted);
			//Set<LinkedList<Integer>> temp = Bdd.getResult(cycles.toArray(tmp)); //exponential =(
			return Bdd.getSolution(cycles.toArray(tmp));
		}
	}

	LinkedList<Integer> solution = null;

	public LinkedList<Integer> reschedule(InstructionDAG g) {
		if (g.getStalls()==0) return g.getInitialSchedule();
		
		dag = g;

		ContextStorage s = new ContextStorage();
		
		// A schedule can't take less than g.getSize() cycles
		// since we disallow nops in original "schedule".
		// So we must do at least this much iterations before
		// first check for a solution
		int cycle = 1;
		for (; cycle < g.getSize()-1; cycle++)
			s.addIteration(cycle);
		
		// check for solution after each new addIteration
		do {
			s.addIteration(cycle);
			solution = s.getResult(cycle++);
		} while (solution==null);

		return solution;
	}
}
