package org.spbu.bdd.samples.schedule;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class InstructionDAG {
	
	public class Vert {
		private HashSet<Integer> pred;
		private HashSet<Integer> succ;
		private Instruction instr;
		private int index;
		
		public int getIndex() {
			return index;
		}
		
		public HashSet<Integer> getPred() {
			return pred;
		}

		public HashSet<Integer> getSucc() {
			return succ;
		}

		public Instruction getInstr() {
			return instr;
		}

		public Vert(Instruction instr, int index) {
			this.instr = instr;
			this.index = index;
			pred = new HashSet<Integer>();
			succ = new HashSet<Integer>();
		}
		
		public void addSucc(int index) {
			succ.add(index);
		}
		
		public void addPred(int index) {
			pred.add(index);
		}
		
		public void addPred(HashSet<Integer> other) {
			pred.addAll(other);
		}
		
		public void addSucc(HashSet<Integer> other) {
			succ.addAll(other);
		}

		private boolean isRoot() {
			return pred.isEmpty();
		}
		
		public boolean isLeaf() {
			return succ.isEmpty();
		}
	}
	
	public static final int NOPVAL = -1; // must be < 0, NOPVAL-1 will be used for stopVal
	
	private ArrayList<Vert> instructions = new ArrayList();
	private ArrayList<Integer> roots = new ArrayList();
	private ArrayList<Integer> leaves = new ArrayList();
	// "all" is just [0,1,..,n] for fetching to insertNewList
	private ArrayList<Integer> all;
	private int stalls = 0;
	// maximum latency of instructions present in this DAG
	private int maxLatency = 0;
	// index of imaginary instruction "fin" in "instructions"
	private int finInd;
	private LinkedList<Integer> initialSchedule = new LinkedList();

	public ArrayList<Vert> getInstructions() {
		return instructions;
	}	
	
	public List<Integer> getRoots() {
		return roots;
	}

	public ArrayList<Integer> getLeaves() {
		return leaves;
	}
	
	public List<Integer> getAll() {
		return all;
	}

	public int getStalls() {
		return stalls;
	}

	public int getMaxLatency() {
		return maxLatency;
	}
	
	public int getFinInd() {
		return finInd;
	}

	public LinkedList<Integer> getInitialSchedule() {
		return initialSchedule;
	}
	
	public int getSize() {
		return instructions.size();
	}

	public int getLength() {
		return initialSchedule.size();
	}
	
	private int commonFunc(Vert v, int ind, int i, int maxdelta){
		// #ind and #i instructions are dependent by data
		v.addPred(ind);
		instructions.get(ind).addSucc(i);
		// this dependence may produce nops...
		int lat = instructions.get(ind).getInstr().getLatency();
		// use positions of instruction indices in initial schedule
		// rather than just instruction indices!!
		return Math.max(maxdelta, initialSchedule.indexOf(ind)+lat-initialSchedule.size());
	}
	
	// no nops & fins allowed
	public void parse(InputStream is) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(is));
		HashMap<String,Integer> lastWritten = new HashMap();
		HashMap<String,Integer> lastRead = new HashMap();
		int i=0;
		Vert v;
		for (String line = reader.readLine(); line != null; line = reader.readLine()) {
			line = line.trim();
			if (line.equals("") || line.startsWith("#")) continue;
			v = new Vert(new Instruction(line),i);
			this.maxLatency=Math.max(v.getInstr().getLatency(),this.maxLatency);
			
			int maxDelta = 0;
			// are there any RW dependencies?
			String vWrites = v.getInstr().getMem()[0]; // assuming no nops & fins here!
			if (lastRead.containsKey(vWrites))
				maxDelta = commonFunc(v,lastRead.get(vWrites),i,maxDelta);
			// are there any WW dependencies?
			if (lastWritten.containsKey(vWrites))
				maxDelta = commonFunc(v,lastWritten.get(vWrites),i,maxDelta);
			// *R dependencies
			int size = v.getInstr().getMem().length;
			String[] vReads = new String[size-1];
			for (int j=0; j<size-1; j++) {
				vReads[j] = v.getInstr().getMem()[j+1];
				// are there any RR dependencies?
				if (lastRead.containsKey(vReads[j]))
					maxDelta = commonFunc(v,lastRead.get(vReads[j]),i,maxDelta);
				// are there any WR dependencies?
				if (lastWritten.containsKey(vReads[j]))
					maxDelta = commonFunc(v,lastWritten.get(vReads[j]),i,maxDelta);
			}
			// update last access information for later use for
			// parsing other instructions
			lastWritten.put(vWrites, i);
			for (int j=0; j<size-1; j++) lastRead.put(vReads[j], i);

			stalls+=maxDelta;
			// adding nops to initialSchedule
			for (int j=0; j<maxDelta; j++)
				initialSchedule.add(NOPVAL);

			// adding current Vert to initialSchedule
			initialSchedule.add(i);
			if (v.isRoot()) roots.add(i);
			// adding current Vert to instructions
			instructions.add(v);

			i++;
		}
		
		v = new Vert(new Instruction("fin"),i);
		// "fin" depends on all the leaves
		int j = 0;
		int maxDelta = 0; // for adding nops before "fin"
		for (Vert v1 : instructions) {
			if (v1.isLeaf()) {
				maxDelta=Math.max(maxDelta, j+v1.getInstr().getLatency()-i);
				v1.addSucc(i);
				leaves.add(j);
				v.addPred(j);
			}
			j++;
		}
		stalls+=maxDelta;
		// adding nops to initialSchedule
		for (j=0; j<maxDelta; j++)
			initialSchedule.add(NOPVAL);
		
		// scheduling "fin" means we've scheduled everything
		initialSchedule.add(i);
		instructions.add(v);
		finInd=i;

		all = new ArrayList<Integer>(i);
		for (j=0; j<i; j++)	all.add(j);
	}
	
	// makes "succ" transitive
	public void doClosure() {
		for (Integer i : leaves)
			_doClosure(i);
	}
	
	private void _doClosure(Integer lower) {
		// for each parent...
		for (Integer upper : instructions.get(lower).getPred()) {
			// add its grandsons to its sons
			instructions.get(upper).addSucc(instructions.get(lower).getSucc());
			// proceed to DAG roots
			_doClosure(upper);
		}
		// notice that "pred"s are unchanged!
	}
	
	public String scheduleToString(List<Integer> lst) {
		String res="";
		if (lst==null) return res;
		for (int i : lst) {
			if (i==NOPVAL) res += "nop\n";
			else if (i>=finInd) res += "fin\n"; // need this in ScheduleBdd...*Cond
			else res += instructions.get(i).getInstr().getStr()+"\n";
		}
		return res;
	}

	public String toString() {
		String res="";
		int i = 0;
		for (Vert v : instructions) {
			res += "[" + (i++) +"] " +v.getInstr().getStr() +
				"\n   pred: " + v.getPred().toString() +
				"\n   succ: " + v.getSucc().toString() + "\n";
		}
		return res;
	}
}