package smooth;

import graph.SmoothPattern;
import graph.WeightedTimeGraph;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.TreeSet;

import digraph.AcyclicLP;
import digraph.DirectedEdge;
import digraph.EdgeWeightedDigraph;

public class DAG {
	public HashMap<Integer, Integer> comp2time = new HashMap<Integer, Integer>();
	public ArrayList<BitSet> comps = new ArrayList<BitSet>();
	public ArrayList<Float> scores = new ArrayList<Float>();
	public ArrayList<ArrayList<Integer>> comptimes = new ArrayList<ArrayList<Integer>>();
	public HashMap<Integer, Float> roots;
	public EdgeWeightedDigraph ewdg;
	public WeightedTimeGraph wtg;
	public final int s,e;
	
	public String structureToString() {
		String res = "";
		for (DirectedEdge de: ewdg.edges()) {
			res += de.from() + "(" + (comp2time.get(de.from())+s) + ")\t" +
					de.to() + "(" + (comp2time.get(de.to())+s) + ")\n";
		}
		return res;
	}
	
	public String toString() {
		String res = "";
		for (int t = 0; t < comptimes.size(); t++) {
			res += (t+s) + ": ";
			for (Integer c: comptimes.get(t)) {
				TreeSet<String> s = new TreeSet<String>();
				for (int i = 0; i < wtg.getm(); i++) {
					if (comps.get(c).get(i) && wtg.endv[i] > wtg.getOrigin(i)) {
						s.add(wtg.names[wtg.getOrigin(i)] + "-" + wtg.names[wtg.endv[i]]);
					}
				}
				res += c + ":" +s;
			}
			res += "\n";
		}
		return res;
	}
	
	public String toStringNodeIndices() {
		String res = "";
		for (int t = 0; t < comptimes.size(); t++) {
			res += (t+s) + ": ";
			for (Integer c: comptimes.get(t)) {
				TreeSet<String> ss = new TreeSet<String>();
				for (int i = 0; i < wtg.getm(); i++) {
					if (comps.get(c).get(i) && wtg.endv[i] > wtg.getOrigin(i)) {
						ss.add(wtg.getOrigin(i) + "-" + wtg.endv[i] + "(" + String.format("%.2f", wtg.wsl[t+s][i]) + ")");
					}
				}
				res += c + ":" +ss;
			}
			res += "\n";
		}
		return res;
	}
	
	public String toString(int st, int ed) {
		String res = "";
		for (int t = st-s; t <ed-s; t++) {
			res += (t+s) + ": ";
			for (Integer c: comptimes.get(t)) {
				TreeSet<String> s = new TreeSet<String>();
				for (int i = 0; i < wtg.getm(); i++) {
					if (comps.get(c).get(i) && wtg.endv[i] > wtg.getOrigin(i)) {
						s.add(wtg.names[wtg.getOrigin(i)] + "-" + wtg.names[wtg.endv[i]]);
					}
				}
				res += c + ":" +s;
			}
			res += "\n";
		}
		return res;
	}
	
	public TreeMap<Integer,TreeSet<Integer>> getInvlovedNodes() {
    	TreeMap<Integer,TreeSet<Integer>> res = new TreeMap<Integer, TreeSet<Integer>>();
    	for (int t =0; t < e-s+1; t++) {
    		res.put(t+s, new TreeSet<Integer>());
    	}
    	for (int c =0; c < comps.size(); c++) {
    		int t = comp2time.get(c);
    		for (int i=0;i<wtg.getn();i++) {
    			for (int j = wtg.ind[i]; j < wtg.ind[i+1]; j++){
    				if (comps.get(c).get(j)) {
    					res.get(t+s).add(i);
    					res.get(t+s).add(wtg.endv[j]);
    				}
    			}
    		}
    	}
    	return res;
    }
	
	public String getStats() {
		
		HashMap<String,Integer> ecs = new HashMap<String, Integer>();
		for (DirectedEdge de: ewdg.edges()) {
			String key = comp2time.get(de.from()) + "_" +  comp2time.get(de.to());
			if(!ecs.containsKey(key)) ecs.put(key, 1);
			else ecs.put(key, ecs.get(key)+1);
		}
		
		String res = "\tNodes\tEdges\n";
		for (int t=0; t < comptimes.size();t++) {
			String key = t + "_" + t;
			res += t + "\t" + comptimes.get(t).size() + "\t" + (ecs.containsKey(key)?ecs.get(key):0) + "\n";
		}
		
		res += "\tCross Slice Edges";
		for (int t=0; t < comptimes.size()-1;t++) {
			String key = t + "_" + (t+1);
			res += key + "\t" + (ecs.containsKey(key)?ecs.get(key):0) + "\n";
		}
		
		res += "\tAverage JCC in slice";
		for (int t=0; t < comptimes.size();t++) {
			double avg = 0.0;
			int cnt = comptimes.get(t).size();
			for (int i=0; i < cnt-1; i++) {
				for (int j = i+1; j < cnt; j++) {
					BitSet in = new BitSet();
					in.or(comps.get(comptimes.get(t).get(i)));
					in.and(comps.get(comptimes.get(t).get(j)));
					BitSet un = new BitSet();
					un.or(comps.get(comptimes.get(t).get(i)));
					un.or(comps.get(comptimes.get(t).get(j)));
					avg += in.cardinality()*1.0/un.cardinality();
				}
			}
			res += t + "\t" + (1.0*avg/(0.5*cnt*(cnt-1))) + "\n";
		}
		return res;
	}
	
	public DAG( WeightedTimeGraph _wtg, TreeMap<Integer,BitSet> allowed, boolean usePCST, int st, int en) {
		wtg = _wtg;
		s = st;
		e = en;
		computeComponents(allowed, _wtg, usePCST);
		buildDAG();
		
	}
	
	public DAG( WeightedTimeGraph _wtg, 
				HashMap<Integer,HashSet<HashMap<String,HashSet<String>>>> components,
				int st,int en) {
		wtg = _wtg;
		s = st;
		e = en;
		transformComponents(_wtg, components);
		buildDAG();
	}

	public void buildDAG() {
		// Create a DAG
		roots = new HashMap<Integer, Float>();
		ewdg = new EdgeWeightedDigraph(comps.size());
		BitSet bs = new BitSet();
		for (int t = 0; t <= e-s; t++) {
			if(t==0) {
				for (int i=0; i < comptimes.get(t).size(); i++) {
					roots.put(comptimes.get(t).get(i), scores.get(comptimes.get(t).get(i)));
				}
			} else {
				// for every component, look back to connect it to previous
				for (int i=0; i < comptimes.get(t).size(); i++) {
					boolean isroot = true;
					for (int j = 0; j < comptimes.get(t-1).size(); j++) {
						bs.clear();
						bs.or(comps.get(comptimes.get(t).get(i)));
						bs.and(comps.get(comptimes.get(t-1).get(j)));
						if (bs.cardinality() > 0) {
							isroot = false;
							// add an edge from j(t-1) to i(t)
							// weight is the weight of the receiver i(t)
							ewdg.addEdge(new DirectedEdge(comptimes.get(t-1).get(j), 
														  comptimes.get(t).get(i), 
														  (double)scores.get(comptimes.get(t).get(i))
														  )
										);
										
						}
					}
					if (isroot) 
						roots.put(comptimes.get(t).get(i),scores.get(comptimes.get(t).get(i)));
				}
			}
		}
	}
	
	public DAG( WeightedTimeGraph _wtg, HashMap<Integer, Integer> _comp2time, ArrayList<BitSet> _comps, 
			HashMap<Integer, Float> _roots, HashMap<String,Double> edges, int st, int en) {
		wtg = _wtg;
		comp2time = _comp2time;
		comptimes = new ArrayList<ArrayList<Integer>>();
		for (int i=0; i < en-st+1; i++) comptimes.add(new ArrayList<Integer>());
		for (Integer c: _comp2time.keySet()) {
			comptimes.get(_comp2time.get(c)).add(c);
		}
		comps = _comps;
		roots = _roots;
		s = st;
		e = en;
		buildDAG(edges);
	}
	
	public void buildDAG(HashMap<String,Double> edges) {
		ewdg = new EdgeWeightedDigraph(comps.size());
		int v1=-1, v2 =-1;
		for(String s: edges.keySet()) {
			v1 = Integer.parseInt(s.split("_")[0]);
			v2 = Integer.parseInt(s.split("_")[1]);
			ewdg.addEdge(new DirectedEdge(v1, v2, edges.get(s)));
		}
	}

	public void computeComponents(TreeMap<Integer,BitSet> allowed, WeightedTimeGraph wtg, boolean usePCST) {
		// Compute + components in every slice
		for (int t = 0; t <=e-s; t++) comptimes.add(new ArrayList<Integer>());
		for (int t = 0; t <=e-s; t++) {
			if (allowed.get(t+s).cardinality() == 0) continue;
			wtg.aggregateByTime(t+s, t+s);
			ArrayList<BitSet> cps = new ArrayList<BitSet>();
			if (!usePCST) {
				cps = wtg.getRestrictedPositiveEdgeComponents(allowed.get(t+s));
			} else {
				cps = wtg.getRestrictedPCSTComponents(allowed.get(t+s));
			}
			
			for (int i=0; i < cps.size(); i++) {
				comps.add(cps.get(i));
				// edges are not counted twice in this score
				scores.add((float)wtg.getScore(cps.get(i)));
				comptimes.get(t).add(comps.size()-1);
				comp2time.put(comps.size()-1, t);
			}
		}
	}
	
	
	public void transformComponents(WeightedTimeGraph tg, 
			HashMap<Integer,HashSet<HashMap<String,HashSet<String>>>> components ) {
		// Compute + components in every slice
		for (int t = 0; t <= e-s; t++) comptimes.add(new ArrayList<Integer>());
		for (Integer t: components.keySet()) {
			if (t < s || t > e ) {
				System.err.print("components passed to DAG " +
						"are not within the time interval [" + s + "," + e +"]\n");
				System.exit(1);
			}
			if(null == components.get(t)) continue;
			if (components.get(t).size()==0) continue;
			wtg.aggregateByTime(t+s, t+s);
			// we have components at this time
			for(HashMap<String,HashSet<String>> comp :components.get(t)) {
				BitSet compedges = new BitSet(tg.getm()); 
				for (String src: comp.keySet()) {
					int srcind = tg.getNodeIndex(src);
					for (String dst: comp.get(src)) {
						int ei = tg.getEdgeIndex(srcind, tg.getNodeIndex(dst));
						compedges.set(ei);
						compedges.set(tg.getReverseEdgeIndex(ei));
					}
				}
				comps.add(compedges);
				scores.add((float)wtg.getScore(compedges));
				comptimes.get(t).add(comps.size()-1);
				comp2time.put(comps.size()-1, t);
			}
		}
	}

	public void getLongestPathEveryRoot(TreeSet<SmoothPattern> pats) {
		// get all paths from every root and add it to pats
		for (Integer r: roots.keySet()) {
			AcyclicLP lp = new AcyclicLP(ewdg, r);
			int maxv = r; 
			float maxd = 0.0F;
			for (int v = 0; v < ewdg.V(); v++) {
				if (lp.distTo(v) > maxd) {
					maxd = (float)lp.distTo(v);
					maxv = v;
				}
			}
			// maxv is our guy
			TreeMap<Integer, BitSet> edges = new TreeMap<Integer, BitSet>();
			edges.put(comp2time.get(r)+s, comps.get(r));
			for (DirectedEdge e : lp.pathTo(maxv)) {
                edges.put(comp2time.get(e.to())+s, comps.get(e.to()));
            }
			SmoothPattern sp = new SmoothPattern(wtg, edges, Integer.MAX_VALUE);
			//sp.visualizeNoLabels();
			pats.add(sp);
		}
	}
	
	public void getAllLongestPaths(TreeSet<SmoothPattern> pats) {
		// TODO: this can be done faster if needed
		HashSet<String> added = new HashSet<String>();
		for (int src = 0; src < ewdg.V(); src+=2) {
			AcyclicLP lp = new AcyclicLP(ewdg, src);
			for (int dest = 1; dest < ewdg.V(); dest+=2) {
				if (lp.hasPathTo(dest) && !added.contains(src + "_" + dest)) {
					added.add(src + "_" + dest);
					TreeMap<Integer, BitSet> edges = new TreeMap<Integer, BitSet>();
					edges.put(comp2time.get(src)+s, comps.get(src));
					for (DirectedEdge e : lp.pathTo(dest)) {
		                edges.put(comp2time.get(e.to())+s, comps.get(e.to()));
		            }
					SmoothPattern sp = new SmoothPattern(wtg, edges, Integer.MAX_VALUE);
					pats.add(sp);
				}
			}
		}
	}
	
	
	

}
