package graph;

import java.io.IOException;
import java.text.DecimalFormat;
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 misc.ExtToolsDriver;
import misc.IO;
import cluster.Common;

public class SmoothPattern implements Comparable {
	WeightedTimeGraph tg;
	public TreeMap<Integer,BitSet> edges;
	public int smoothness;
	public Double score;
	public double fillratio;
	public int s;
	public int e;
	public HashMap<String,String> nnames = null;
	
	public SmoothPattern(WeightedTimeGraph _tg, TreeMap<Integer,BitSet> _edges, int _smoothness) {
		score = 0.0;
		tg = _tg;
		edges = _edges;
		smoothness = _smoothness;
		s = edges.firstKey();
		e = edges.lastKey();
		BitSet eu = new BitSet();
		int numsel = 0;
		for(int t=s; t <= e; t++) {
			numsel += edges.get(t).cardinality();
			eu.or(edges.get(t));
			for(int i=0; i < tg.getm(); i++) {
				if (edges.get(t).get(i))
					score += tg.wsl[t][i]/2.0;
			}
		}
		fillratio = numsel*1.0/(eu.cardinality()*(e-s+1));
		smoothness = getMaxDiffSlices(_edges,_edges.firstKey(),_edges.lastKey());
	}
	
	public SmoothPattern(SmoothPattern pat, int st, int en) {
		score = 0.0;
		tg = pat.tg;
		edges = new TreeMap<Integer, BitSet>();
		s = st;
		e = en;
		smoothness = pat.smoothness;
		BitSet eu = new BitSet();
		int numsel = 0;
		for(int t=s; t <= e; t++) {
			edges.put(t, pat.edges.get(t));
			numsel += edges.get(t).cardinality();
			eu.or(edges.get(t));
			for(int i=0; i < tg.getm(); i++) {
				if (edges.get(t).get(i))
					score += tg.wsl[t][i]/2.0;
			}
		}
		fillratio = numsel*1.0/(eu.cardinality()*(e-s+1));
		smoothness = getMaxDiffSlices(edges,edges.firstKey(),edges.lastKey());
	}
	
	public SmoothPattern(WeightedTimeGraph _tg, int _s, int _e, ArrayList<BitSet> edg) {
		score = 0.0;
		tg = _tg;
		s = _s;
		e = _e;
		edges = new TreeMap<Integer, BitSet>();
		BitSet eu = new BitSet();
		int numsel = 0;
		for(int t=0; t < edg.size(); t++) {
			numsel += edg.get(t).cardinality();
			eu.or(edg.get(t));
			BitSet b = new BitSet();
			b.or(edg.get(t));
			edges.put(_s+t, b);
			for(int i=0; i < tg.getm(); i++) {
				if (edg.get(t).get(i))
					score += tg.wsl[t+_s][i]/2.0;
			}
		}
		fillratio = numsel*1.0/(eu.cardinality()*(_e-_s+1));
		smoothness = getMaxDiffSlices(edges,_s,_e);
	}
	
	
	public SmoothPattern(WeightedTimeGraph _tg, int _s, int _e, BitSet edg) {
		tg = _tg;
		score = 0.0;
		edges = new TreeMap<Integer,BitSet>();
		for (int i=_s; i <= _e; i++) {
			edges.put(i, edg);
		}
		smoothness = 0;
		s = edges.firstKey();
		e = edges.lastKey();
		BitSet eu = new BitSet();
		int numsel = 0;
		for(int t=s; t <= e; t++) {
			numsel += edges.get(t).cardinality();
			eu.or(edges.get(t));
			for(int i=0; i < tg.getm(); i++) {
				if (edges.get(t).get(i))
					score += tg.wsl[t][i]/2.0;
			}
		}
		fillratio = numsel*1.0/(eu.cardinality()*(e-s+1));
		smoothness = getMaxDiffSlices(edges,_s,_e);
	}
	
	public int getMaxDiffSlices(TreeMap<Integer,BitSet> edg, int ss, int ee) {
		int max = 0;
		BitSet bs = new BitSet();
		for (int t = ss; t < ee; t++) {
			bs.clear();
			bs.or(edg.get(t));
			bs.xor(edg.get(t+1));
			if (max < bs.cardinality()/2.0) max = (int)(bs.cardinality()/2.0);
		}
		return max;
	}
	
	public boolean isSmooth(int smooth) {
		return (smoothness <= smooth);
	}
	
	public boolean isConnectedInTime() {
		BitSet bs = new BitSet();
		for (int t = s; t < e; t++) {
			bs.clear();
			bs.or(edges.get(t));
			bs.and(edges.get(t+1));
			if (bs.cardinality()==0) return false;
		}
		return true;
	}
	
	public SmoothPattern getMaxNonNegativeSS() {
		TreeMap<Integer,Float> scores = getScoresPerSlice();
		int ms=0, me=0;
		double max_score = 0.0;
		
		int en = 0;
		int st = scores.firstKey();
		while(scores.get(st)<0) {
			if (st == scores.lastKey()) break;
			st++;
		}
		while(st <=scores.lastKey()) {
			en = st;
			double sum = 0.0;
			while (scores.get(en) >=0) {
				sum +=scores.get(en);
				en++; 
				if  (en > scores.lastKey()) break;
			}
			en--;
			if (sum > max_score) {
				max_score = sum;
				ms = st; me = en;
			}
			st = en + 1;
			if (st <= scores.lastKey()) {
				while(scores.get(st)<0) {
					if (st == scores.lastKey()) break;
					st++;
				}
			}
		}
		
		return new SmoothPattern(this, ms, me);
	}
	
	public boolean hasNegativeSlice() {
		TreeMap<Integer,Float> scores = getScoresPerSlice();
		for (Integer t:scores.keySet()) {
			if (scores.get(t) < 0) {
				return true;
			}
		}
		return false;
	}
	
	public TreeMap<Integer,Float> getScoresPerSlice() {
		TreeMap<Integer,Float> scores = new TreeMap<Integer, Float>();
		for (Integer t: edges.keySet()) {
			float sum = 0;
			for(int i=0; i < tg.getm(); i++) {
				if (edges.get(t).get(i))
					sum += tg.wsl[t][i]/2.0;
			}
			scores.put(t, sum);
		}
		return scores;
	}	
	
	public SmoothPattern copy() {
		TreeMap<Integer, BitSet> edg = new TreeMap<Integer, BitSet>();
		for (Integer t: edges.keySet()) {
			BitSet bs = new BitSet();
			bs.or(edges.get(t));
			edg.put(t,bs);
		}
		return new SmoothPattern(tg, edg, smoothness);
		
	}
	
	public String toString() {
		String res = "[" + s + "," + e + "]" + score + "\n";
		for (Integer t:edges.keySet()) {
			//res += t + "(edge ids):" + edges.get(t).toString() + "\n";
			String edg = "";
			double sc = 0;
			for (int i =0 ; i < tg.getn(); i++) {
				for (int j = tg.ind[i]; j < tg.ind[i+1]; j++) {
					if(edges.get(t).get(j) && i < tg.endv(j)) { 
						res += " " + i + "-" + tg.endv[j] + "(" + String.format("%.2f", tg.wsl[t][j]) + ")";
						sc += tg.wsl[t][j];
					}
				}
			}
			res += "("+t+"," +String.format("%.2f",sc) + "){" + edg + "}\n";
		}
		return res;
	}
	
	public String toStringNodeNames() {
		String res = "[" + s + "," + e + "]" + score + "\n";
		for (Integer t:edges.keySet()) {
			//res += t + "(edge ids):" + edges.get(t).toString() + "\n";
			String edg = "";
			double sc = 0;
			for (int i =0 ; i < tg.getn(); i++) {
				for (int j = tg.ind[i]; j < tg.ind[i+1]; j++) {
					if(edges.get(t).get(j) && i < tg.endv(j)){ 
						edg += " " + tg.names[i] + "-" + tg.names[tg.endv[j]] + "(" + String.format("%.2f", tg.wsl[t][j]) + ")";
						sc += tg.wsl[t][j];
					}
				}
			}
			res += "("+t+"," +String.format("%.2f",sc) + "){" + edg + "}\n";
		}
		return res;
	}
	
	public String stats() {
		DecimalFormat df = new DecimalFormat("###.###");
		int numedges = 0;
		for (Integer t:edges.keySet())
			numedges += edges.get(t).cardinality();
		String res = "Score: " + df.format(score) + "\tLength="+(e-s)+"[" + s + "," + e + "]" + 
					"\t|E|=" + numedges/2 + "\tFillR=" + df.format(fillratio);
		return res;
	}
	
	public String diffToStringNodeNames(SmoothPattern o) {
		String res = "[" + s + "," + e + "]" + score + "-->" +"[" + o.s + "," + o.e + "]" + o.score + " \n";
		if (o.s>e || s>o.e) return res += "Non-overlapping intervals!";
		int t = Math.min(s, o.s);
		if (s < o.s) {
			while (t < o.s) {
				String edg = "";
				double sc = 0;
				for (int i =0 ; i < tg.getn(); i++) {
					for (int j = tg.ind[i]; j < tg.ind[i+1]; j++) {
						if(edges.get(t).get(j) && i < tg.endv(j)){ 
							edg += " " + tg.names[i] + "-" + tg.names[tg.endv[j]] + "(" + String.format("%.2f", tg.wsl[t][j]) + ")";
							sc += tg.wsl[t][j];
						}
					}
				}
				res += "[-]\t("+t+"," +String.format("%.2f",sc) + "){" + edg + "}\n";
				t++;
			}
		} else if (o.s < s) {
			while (t < s) {
				String edg = "";
				double sc = 0;
				for (int i =0 ; i < tg.getn(); i++) {
					for (int j = tg.ind[i]; j < tg.ind[i+1]; j++) {
						if(o.edges.get(t).get(j) && i < tg.endv(j)) {
							edg += " " + tg.names[i] + "-" + tg.names[tg.endv[j]] + "(" + String.format("%.2f", tg.wsl[t][j]) + ")";
							sc += tg.wsl[t][j];
						}
					}
				}
				res += "[+]\t("+t+"," +String.format("%.2f",sc) + "){" + edg + "}\n";
				t++;
			}
		}
		while (t <= Math.min(e, o.e)) {
			String edg = "";
			double sc = 0;
			for (int i =0 ; i < tg.getn(); i++) {
				for (int j = tg.ind[i]; j < tg.ind[i+1]; j++) {
					// added
					if(o.edges.get(t).get(j) && !edges.get(t).get(j) && i < tg.endv(j)) {
						edg += " [+]" + tg.names[i] + "-" + tg.names[tg.endv[j]] + "(" + String.format("%.2f", tg.wsl[t][j]) + ")";
						sc += tg.wsl[t][j];
					// removed
					} else if (!o.edges.get(t).get(j) && edges.get(t).get(j)  && i < tg.endv(j)) {
						edg += " [-]" + tg.names[i] + "-" + tg.names[tg.endv[j]] + "(" + String.format("%.2f", tg.wsl[t][j]) + ")";
						sc -= tg.wsl[t][j];
					}
				}
			}
			res += "\t("+t+"," +String.format("%.2f",sc) + "){" + edg + "}\n";
			t++;
		}
		while (e>=t) {
			String edg = "";
			double sc = 0;
			for (int i =0 ; i < tg.getn(); i++) {
				for (int j = tg.ind[i]; j < tg.ind[i+1]; j++) {
					if(edges.get(t).get(j) && i < tg.endv(j)) {
						edg += " " + tg.names[i] + "-" + tg.names[tg.endv[j]] + "(" + String.format("%.2f", tg.wsl[t][j]) + ")";
						sc -= tg.wsl[t][j];
					}
				}
			}
			res += "[-]\t("+t+"," +String.format("%.2f",sc) + "){" + edg + "}\n";
			t++;
		} 
		while (o.e>t) {
			String edg = "";
			double sc = 0;
			for (int i =0 ; i < tg.getn(); i++) {
				for (int j = tg.ind[i]; j < tg.ind[i+1]; j++) {
					if(o.edges.get(t).get(j) && i < tg.endv(j)) {
						edg += " " + tg.names[i] + "-" + tg.names[tg.endv[j]] + "(" + String.format("%.2f", tg.wsl[t][j]) + ")";
						sc += tg.wsl[t][j];
					}
				}
			}
			res += "[+]\t("+t+"," +String.format("%.2f",sc) + "){" + edg + "}\n";
			t++;
		}
		return res;
	}
	
	// GraphViz visualization
	
	public void saveGraphViz(String fn) {
		ExtToolsDriver.saveGraphViz(toGraphViz(),fn);
	}
	
	public void saveGraphVizNoLabels(String fn) {
		ExtToolsDriver.saveGraphViz(toGraphVizNoWeights(),fn);
	}
	
	
	public void showGraphViz(String fn) {
		ExtToolsDriver.showGraphViz(fn);
	}
	
	
	public void visualize() {
		ExtToolsDriver.saveGraphViz(toGraphViz());
		ExtToolsDriver.showGraphViz();
	}
	
	public void visualize(ArrayList<Integer> centers) {
		ExtToolsDriver.saveGraphViz(toGraphViz(centers));
		ExtToolsDriver.showGraphViz();
	}

	public void visualizeHighwayGraph() {
		ExtToolsDriver.saveGraphViz(toGraphVizHW());
		ExtToolsDriver.showGraphViz();
	}
	
	public void visualizeNoLabels() {
		ExtToolsDriver.saveGraphViz(toGraphVizNoWeights());
		ExtToolsDriver.showGraphViz();
	}
	
	private String toGraphViz(ArrayList<Integer> centers) {
		// HELLO->World [color = red, label = \"aaa\"]; HELLO [style=filled, color = blue]
		String res = "digraph G { \n";
		res += edgesToGraphViz(s);
		for (int t = s+1; t <= e; t++) {
//			common.clear();
//			common.or(edges.get(t-1));
//			common.and(edges.get(t));
//			res += timeEdgesToGraphViz(t-1,common);
			res += edgesToGraphViz(t);
		}
		for (int i =0; i < centers.size(); i++) {
			res += "\"" + tg.names[centers.get(i)] + "(" + i +  ")\" [style=filled, color = red]" + ";\n";
		}
		
		res += "overlap=false \n " +
		"label=\"Start=" + s + 
		"\tEnd=" + e + 
		"\tScore=" + String.format("%.4f", score) + 
		"\tFill=" + String.format("%.4f", fillratio) + "\"fontsize=18;\n";
		
		res += "}";
		return res;
	}

	private String toGraphViz() {
		BitSet common = new BitSet();
		// HELLO->World [color = red, label = \"aaa\"]; HELLO [style=filled, color = blue]
		String res = "digraph G { \n";
		res += edgesToGraphViz(s);
		for (int t = s+1; t <= e; t++) {
//			common.clear();
//			common.or(edges.get(t-1));
//			common.and(edges.get(t));
//			res += timeEdgesToGraphViz(t-1,common);
			res += edgesToGraphViz(t);
		}
		
		
		res += "overlap=false \n " +
		"label=\"Start=" + s + 
		"\tEnd=" + e + 
		"\tScore=" + String.format("%.4f", score) + 
		"\tFill=" + String.format("%.4f", fillratio) + "\"fontsize=18;\n";
		
		res += "}";
		return res;
	}
	
	private String toGraphVizHW() {
		BitSet common = new BitSet();
		// HELLO->World [color = red, label = \"aaa\"]; HELLO [style=filled, color = blue]
		String res = "graph G { \n";
		res += edgesToGraphVizHW(s);
		for (int t = s+1; t <= e; t++) {
//			common.clear();
//			common.or(edges.get(t-1));
//			common.and(edges.get(t));
//			res += timeEdgesToGraphViz(t-1,common);
			res += edgesToGraphVizHW(t);
		}
		
		
		res += "overlap=false \n " +
		"label=\"Start=" + s + 
		"\tEnd=" + e + 
		"\tScore=" + String.format("%.4f", score) + 
		"\tFill=" + String.format("%.4f", fillratio) + "\"fontsize=18;\n";
		
		res += "}";
		return res;
	}
	
	private String toGraphVizNoWeights() {
		BitSet common = new BitSet();
		// HELLO->World [color = red, label = \"aaa\"]; HELLO [style=filled, color = blue]
		String res = "digraph G { \n";
		
		if(fillratio>=0.99) {
			res += edgesToGraphVizNoWeightsNoTime(s);
		} else {
			res += edgesToGraphViz(s);
			for (int t = s+1; t <= e; t++) {
	//			common.clear();
	//			common.or(edges.get(t-1));
	//			common.and(edges.get(t));
	//			res += timeEdgesToGraphViz(t-1,common);
				res += edgesToGraphViz(t);
			}
		}
		
		
		res += "overlap=false \n " +
		"label=\"Start=" + s + 
		"\tEnd=" + e + 
		"\tScore=" + String.format("%.4f", score) + 
		"\tFill=" + String.format("%.4f", fillratio) + "\"fontsize=18;\n";
		
		res += "}";
		return res;
	}
	
	private String timeEdgesToGraphViz(int first, BitSet CommonEdges) {
		String res = "";
		HashSet<Integer> nodes = new HashSet<Integer>();
		for (int i=0; i < tg.getn(); i++) {
			for (int j = tg.ind[i]; j < tg.ind[i+1]; j++){
				if (CommonEdges.get(j)) {
					nodes.add(i);
					nodes.add(tg.endv(j));
				}
			}
		}
		for (Integer i: nodes) {
			res += "\"" +tg.names[i] + "(" + (first-s) + ")\" -> \"" + tg.names[i] + "(" + (first+1-s) + ")\";\n";
		}
		return res;
	}
	
	private String edgesToGraphViz(int t) {
		String res = "";
		for (int i=0; i < tg.getn(); i++) {
			for (int j = tg.ind[i]; j < tg.ind[i+1]; j++){
				if (edges.get(t).get(j) && i < tg.endv[j]) {
					if (nnames==null) {
						res += "\"" + tg.names[i] + "(" + (t-s) +  ")\" -> \"" + 
								tg.names[tg.endv[j]] + "(" + (t-s) +
								")\" [ label = " + String.format("%.4f", tg.wsl[t][j]) +  "];\n";
					} else {
						res += "\"" + nnames.get(tg.names[i]) + "(" + (t-s) +  ")\" -> \"" + 
								nnames.get(tg.names[tg.endv[j]]) + "(" + (t-s) +
								")\" [ label = " + String.format("%.4f", tg.wsl[t][j]) +  "];\n";
					}
				}
			}
		}
		return res;
	}
	
	private String edgesToGraphVizHW(int t) {
		String res = "";
		
		HashMap<String,String> namesmap = new HashMap<String, String>();
		HashMap<String,Double> hwmin = new HashMap<String, Double>();
		HashMap<String,Double> hwmax = new HashMap<String, Double>();
		HashSet<String> edg = new HashSet<String>();
		
		for (int i=0; i < tg.getn(); i++) {
			for (int j = tg.ind[i]; j < tg.ind[i+1]; j++){
				if (edges.get(t).get(j) && i < tg.endv(j)) {
					String src = nnames.get(tg.names[i]);
					String dst = nnames.get(tg.names[tg.endv[j]]);
					String srchw = src.split("-")[0];
					Double srcmiles = Double.parseDouble(src.split("-")[1]);
					String dsthw = dst.split("-")[0];
					Double dstmiles = Double.parseDouble(dst.split("-")[1]);
					namesmap.put(src, srchw);
					namesmap.put(dst, dsthw);
					
					if (!hwmin.containsKey(srchw)) hwmin.put(srchw,srcmiles);
					else hwmin.put(srchw,Math.min(srcmiles, hwmin.get(srchw)));
					if (!hwmax.containsKey(srchw)) hwmax.put(srchw,srcmiles);
					else hwmax.put(srchw,Math.max(srcmiles, hwmax.get(srchw)));
					
					if (!hwmin.containsKey(dsthw)) hwmin.put(dsthw,dstmiles);
					else hwmin.put(dsthw,Math.min(dstmiles, hwmin.get(dsthw)));
					if (!hwmax.containsKey(dsthw)) hwmax.put(dsthw,dstmiles);
					else hwmax.put(dsthw,Math.max(dstmiles, hwmax.get(dsthw)));
					
					if(!srchw.equals(dsthw)) {
						if(srchw.compareTo(dsthw)<0) {
							edg.add(srchw + "\t" + dsthw);
						} else {
							edg.add(dsthw + "\t" + srchw);
						}
					}
					
				}
			}
		}
		
		for (String e:edg) {
			String src = e.split("\t")[0];
			String dst = e.split("\t")[1];
			res += "\"" + src +"["+ hwmin.get(src) +"-"+ hwmax.get(src) +"](" + t +")" + "\" -- \"" + 
						dst +"["+ hwmin.get(dst) +"-"+ hwmax.get(dst) +"](" + t +")" + "\";\n";
		}
		
		return res;
	}
	
	private String edgesToGraphVizNoWeightsNoTime(int t) {
		String res = "";
		for (int i=0; i < tg.getn(); i++) {
			for (int j = tg.ind[i]; j < tg.ind[i+1]; j++){
				if (edges.get(t).get(j) && i < tg.endv[j]) {
					if (tg.names[i].endsWith("_") || tg.names[tg.endv[j]].endsWith("_")) continue;
					if (nnames==null) {
						res += "\"" + tg.names[i] + "\" -> \"" + 
								tg.names[tg.endv[j]] + "\";\n";
					} else {
						res += "\"" + nnames.get(tg.names[i]) + "\" -> \"" + 
								nnames.get(tg.names[tg.endv[j]]) + "\";\n";
					}
				}
			}
		}
		return res;
	}

	@Override
	public int compareTo(Object o) {
		SmoothPattern osp = (SmoothPattern)o;
		if(score.compareTo(osp.score) == 0) {
			return toString().compareTo(osp.toString());
		} else {
			return score.compareTo(osp.score);
		}
	}

	public double percOverlap(SmoothPattern sp) {
		int cnt=0, overlapped=0;
		for (Integer t: edges.keySet()) {
			BitSet bs = new BitSet();
			cnt += edges.get(t).cardinality();
			bs.or(edges.get(t));
			if (sp.edges.containsKey(t)) {
				bs.and(sp.edges.get(t));
				overlapped += bs.cardinality();
			}
		}
		return overlapped*1.0/cnt;
	}
}
