package graph;

import generator.DynamicModel;
import generator.GraphGenerator;
import misc.Common;
import misc.Distribution;
import misc.ExtToolsDriver;
import misc.IO;
import misc.Time.t_res;

import index.IntervalBounds;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;

public class TimeGraph extends Graph implements ITimeGraph{
	public BitSet[] slices;
	public int[][] values;
	public long[] pivots;
	public double[][] opt_intervals;
	
	public double[][] nodespeeds;
	public double[][] nodescores;
	public double[][] original_nodespeeds;
	private HashMap<Integer, HashMap<Integer, Double>> values_sparse;
	
	// -----------------------------Create--------------------- 
	// A list of time edges in format name1, name2 time
	public TimeGraph(Graph g, 
				ArrayList<String> edges, int num_slices) {
		super(g);
		slices = new BitSet[num_slices];
		for (BitSet bs:slices) bs.clear();
		String[] elems;	;
		int t, j;
		for (String e: edges) {
			elems = e.split(Common.SEP);
			t = Integer.parseInt(elems[2]);
			j = getEdgeIndex(getNodeIndex(elems[0]),
							 getNodeIndex(elems[1]));
			slices[t].set(j);
		}
	}
	
	public TimeGraph(Graph g, BitSet[] sl) {
		super(g);
		slices = sl;
	}
	
	public TimeGraph(Graph g, int[][] vals) {
		super(g);
		values = vals;
		slices = new BitSet[vals.length];
	}
	
	public TimeGraph(Graph g, double[][] _nodespeeds) {
		super(g);
		original_nodespeeds = _nodespeeds;
		slices = null;
	}
	
	// sparse representation of the edge histories
	public TimeGraph(Graph g, 
		   HashMap<Integer, HashMap<Integer, Double>> vals,
		   int t) {
		super(g);
		values_sparse  = vals;
		slices = new BitSet[t];
	}

	public void aggregateCoarsen(int times) {
		int newt = (int)Math.ceil((1.0*original_nodespeeds[0].length)/times);
		nodespeeds = new double[getn()][newt];
		for(int i = 0; i < newt; i++) {
			int s = i*times, e = Math.min((i+1)*times, original_nodespeeds[0].length);
			for (int j = 0; j < getn(); j++) {
				for (int k=s; k < e; k++) {
					nodespeeds[j][i] += original_nodespeeds[j][k];
				}
				nodespeeds[j][i] /= 1.0*(e-s);
			}
		}
	}
	
	// -----------------------------Tresholding--------------------- 
	public void thresholdFractionLessThan(double frac) {
		int[] allvals = new int[values.length*values[0].length];
		for(int i = 0; i < values.length; i++) {
			for (int j = 0; j < values[0].length; j++) {
				allvals[i*values[0].length + j] = values[i][j];
			}
		}
		Arrays.sort(allvals);
		slices = new BitSet[values.length];
		int t = allvals[(int)(allvals.length*frac)];
		for (int i = 0; i < values.length; i++) {
			slices[i] = new BitSet(getm());
			slices[i].clear();
			for (int j = 0; j < getm(); j++) {
				if(values[i][j] < t) slices[i].set(j);
			}
		}
	}
	
	// anything strictly greater than val will be set to 1 
	public void thresholdGTValue(int val) {
		slices = new BitSet[values.length];
		for (int i = 0; i < values.length; i++) {
			slices[i] = new BitSet(getm());
			slices[i].clear();
			for (int j = 0; j < getm(); j++) {
				if(values[i][j] > val) slices[i].set(j);
			}
		}
	}
	
	// anything strictly greater than val will be set to 1 
	public double thresholdSparseGTValue(double val) {
		assert(slices != null);
		int cnt = 0, cnt_above = 0;
		for (int i = 0; i < slices.length; i++) {
			slices[i] = new BitSet(getm());
			slices[i].clear();
			for (int j = 0; j < getm(); j++) {
				if (!values_sparse.containsKey(j)) continue;
				if(values_sparse.get(j).containsKey(i)) {
					cnt++;
					if(values_sparse.get(j).get(i) > val){
						cnt_above++;
						slices[i].set(j);
					    slices[i].set(getReverseEdgeIndex(j));
					}
				}
			}
		}
		return 1.0*cnt_above/cnt;
	}

	// PeMS transportation network
	public double scoreEdgesLTSpeed(double thresh) {
		return scoreEdgesLTSpeed(thresh, 0, gett()-1);
	}
	
	public double scoreEdgesLTSpeed(double thresh, int s, int e) {
		if (null==nodespeeds) nodespeeds = original_nodespeeds;
		slices = new BitSet[e-s+1];
		long nset = 0;
		for (int i = s; i <= e; i++) {
			slices[i-s] = new BitSet(getm());
			slices[i].clear();
			for( int n = 0; n < getn(); n++) {
				for (int j = ind[n]; j < ind[n+1]; j++) {
					if((nodespeeds[n][i] + nodespeeds[endv[j]][i]) / 2.0 < thresh) 
						slices[i-s].set(j);
				}
			}
			nset += slices[i-s].cardinality();
		}
		return nset*1.0/((e-s+1)*getm()*1.0);
	}
	
	public double scoreEdgesLTPercOfAvg(double perc) {
		return scoreEdgesLTPercOfAvg(perc, 0, gett()-1);
	}
	
	public double scoreEdgesLTPercOfAvg(double perc, int s, int e) {
		if (null==nodespeeds) nodespeeds = original_nodespeeds;
		slices = new BitSet[e-s+1];
		long nset = 0;
		
		double[] avg = new double[getn()];
		for (int i=0; i < getn(); i++) {
			for(int j =s; j <=e; j++ ) {
				avg[i] += nodespeeds[i][j];
			}
			avg[i] /= 1.0*(e-s+1);
		}
		
		for (int i = s; i <= e; i++) {
			slices[i-s] = new BitSet(getm());
			slices[i].clear();
			for( int n = 0; n < getn(); n++) {
				for (int j = ind[n]; j < ind[n+1]; j++) {
					if((nodespeeds[n][i] + nodespeeds[endv[j]][i])/2.0 < perc*(avg[n] + avg[endv[j]])/2.0) 
						slices[i-s].set(j);
				}
			}
			nset += slices[i-s].cardinality();
		}
		return nset*1.0/((e-s+1)*getm()*1.0);
	}
	
	
	public double scoreEdgesPvalueTODDOW(double logodsnorm, 
										 int nbins) {
		
		if (null==nodespeeds) nodespeeds = original_nodespeeds;
	
		int day_length = 288;
		int week_length = 288*7;
		assert(day_length % nbins == 0):"288 should be a multiple of the number of bins.";
		int bin_length = day_length / nbins;
		
		Distribution dist = new Distribution();
		nodescores = new double[nodespeeds.length][nodespeeds[0].length]; 
		
		for (int i=0; i < getn(); i++) { // nodes
			dist.clean();
			// Build distributions
			for (int bin = 0; bin < nbins; bin++) { // bins
				for (int dow = 0; dow < 7; dow++) { // days of week
					for (int w = 0; w*week_length + dow*day_length < nodespeeds[0].length; w++) { // weeks
						int tss = w*week_length + dow*day_length + bin*bin_length;
						int tse = tss + bin_length;
						for(int ts = tss; ts < tse; ts++) {
							dist.add(nodespeeds[i][ts]);
						}
					}
					// Now score the edges in this day of week and bin
					for (int w = 0; w*week_length + dow*day_length < nodespeeds[0].length; w++) { // weeks
						int tss = w*week_length + dow*day_length + bin*bin_length;
						int tse = tss + bin_length;
						for(int ts = tss; ts < tse; ts++) {
							nodescores[i][ts] = dist.score(nodespeeds[i][ts],logodsnorm);
						}
					}
				}
			}
		}
		
		
		int s = 0, e = gett()-1;
		slices = new BitSet[e-s+1];
		long nset = 0;
		for (int i = 0; i <= e; i++) {
			slices[i-s] = new BitSet(getm());
			slices[i].clear();
			for( int n = 0; n < getn(); n++) {
				for (int j = ind[n]; j < ind[n+1]; j++) {
					if((nodescores[n][i] + nodescores[endv[j]][i])/2.0 > 0) 
						slices[i-s].set(j);
				}
			}
			nset += slices[i-s].cardinality();
		}
		return nset*1.0/((e-s+1)*getm()*1.0);
	}
	
	public void scoreNodesPvalue(int nbins) {

		if (null==nodespeeds) nodespeeds = original_nodespeeds;
		
		int day_length = 288;
		int week_length = 288*7;
		assert(day_length % nbins == 0):"288 should be a multiple of the number of bins.";
		int bin_length = day_length / nbins;
		
		Distribution dist = new Distribution();
		nodescores = new double[nodespeeds.length][nodespeeds[0].length]; 
		
		for (int i=0; i < getn(); i++) { // nodes
			dist.clean();
			// Build distributions
			for (int bin = 0; bin < nbins; bin++) { // bins
				for (int dow = 0; dow < 7; dow++) { // days of week
					for (int w = 0; w*week_length + dow*day_length < nodespeeds[0].length; w++) { // weeks
						int tss = w*week_length + dow*day_length + bin*bin_length;
						int tse = tss + bin_length;
						for(int ts = tss; ts < tse; ts++) {
							dist.add(nodespeeds[i][ts]);
						}
					}
					// Now score the edges in this day of week and bin
					for (int w = 0; w*week_length + dow*day_length < nodespeeds[0].length; w++) { // weeks
						int tss = w*week_length + dow*day_length + bin*bin_length;
						int tse = tss + bin_length;
						for(int ts = tss; ts < tse; ts++) {
							nodescores[i][ts] = dist.pvalue_lt(nodespeeds[i][ts]);
						}
					}
				}
			}
		}
	}

// -----------------------------Accessors--------------------- 
	
	// -----------------------------Accessors--------------------- 
	public int gett() {
		if (null!=slices) 
			return slices.length;
		else return nodespeeds[0].length;
	}
	
	public int getTimeAt(long ts) {
		int res = 0;
		while(pivots[res]<ts){
			res++;
			if (res==pivots.length) break;
		}
		return res-1;
	}
	
	// returns the ts at the beginnign of this interval
	public long getActualTime(int i) {
		if (null==pivots || i < 0 || i > gett()) return -1;
		return pivots[i];
	}
	
	// -----------------------------toString--------------------- 
	public String toStringTime() {
		String res = "";
		for (int i=0; i<slices.length; i++) {
			for(int j=0;j<getm(); j++) {
				res += slices[i].get(j)?"1":"0";
			}
			res += "\n";
		}
		return res;
	}
	
	public String toStringTime(int s, int e) {
		String res = "";
		for (int i=s; i<=e; i++) {
			for(int j=0;j<getm(); j++) {
				res += slices[i].get(j)?"1":"0";
			}
			res += "\n";
		}
		return res;
	}
	
	public String toStringTimeFirstK(int k) {
		assert(k < getm());
		String res = "";
		for (int i=0; i<slices.length; i++) {
			int cnt = 0;
			for (int n=0; n < getn(); n++){
				for(int j=ind[n];j<ind[n+1]; j++) {
					if (n<endv[j]) {
						res += slices[i].get(j)?"1":"0";
						cnt++;
					}
					if (cnt==k) break;
				}
				if (cnt==k) break;
			}
			
			res += "\n";
		}
		return res;
	}
	
	// -----------------Print-----------------------------
	public void printStringTime(int s, int e) {
		for (int i=s; i<=e; i++) {
			System.err.print(i + "\t");
			for(int j=0;j<getm(); j++) {
				System.err.print(slices[i].get(j)?"1":"0");
			}
			System.err.print("\n");
		}
	}
	
	public void printStringTimeFirstK(int s, int e, int k) {
		assert(k < getm());
		for (int i=s; i<=e; i++) {
			System.err.print(i + "\t");
			for(int j=0;j<k; j++) {
				System.err.print(slices[i].get(j)?"1":"0");
			}
			System.err.print("\n");
		}
	}
	
	
	@Override
	public String toString() {
		String res = "Nodes:\n";
		for (int i=0;i<names.length;i++) {
			res += names[i] + "(" + wn[i] + "),";
		}
		res += "\nEdges:\n";
		if (getn()==1) return res;
		for(int i=0;i<ind.length-1;i++) {
			for (int j=ind[i];j<ind[i+1];j++) {
				res += j+ ":" + names[i] + "\t" + names[endv[j]] + "\t" + we[j] + "\t";
				for (int t=0; t<gett(); t++) res+= ((slices[t].get(j))?"1":"0");
				res += "\n";
			}
		}
		return res;
	}
	
	public String toStringStruct() {
		return "TimeGraph n=" + getn() + " e=" + getm() + " t=" + slices.length +   
			   "\n[structure=\n" +  super.toStringStruct() + 
			   "\n" + toStringTime() + "\n";
	}
	
	// -----------------------------Edge weighting--------------------- 
	public void aggregateByTime(int s, int e) {
		assert(s<=e && s >= 0 && e < gett()):"Incorrect interval" + s + " " + e;
		//Graph g = getStructure();
		Arrays.fill(we, 0.0);
		for (int i = s; i <=e; i++) {
			for(int j = 0; j < getm(); j++) {
				if (slices[i].get(j)) we[j] +=1;
				else we[j] -=1;
			}
		}
	}
	
	public void aggregateByTime(int s, int e, double[] weights) {
		assert(s<=e && s >= 0 && e < gett()):"Incorrect interval" + s + " " + e;
		Arrays.fill(weights, 0.0);
		for (int i = s; i <=e; i++) {
			for(int j = 0; j < getm(); j++) {
				if (slices[i].get(j)) weights[j] +=1;
				else weights[j] -=1;
			}
		}
	}
	
	// Computes the ceiling for all subintervals
	public double[] getBestTimeLapsedEdges(int s, int e, int sz) {
		assert(e-s+1 >= sz);
		double[] res = new double[getm()];
		Arrays.fill(res, Double.NEGATIVE_INFINITY);
		double[] tmp = new double[getm()];
		for (int i=s; i <= e-sz+1; i++) {
			Arrays.fill(tmp, 0);
			for (int j=i; j < i+sz; j++) {
				for (int m = 0; m < getm(); m++) {
					tmp[m] += (slices[j].get(m)?1.0:(-1.0));
				}
			}
			for (int m = 0; m < getm(); m++) {
				res[m] = Math.max(tmp[m], res[m]);
			}
		}
		return res;
	}
	
	// Computes the ceiling for all intervals starting from s and ending before and including e
	public void getBestTimeLapsedEdgesLeftAligned(int s, int e, double[] res) {
		assert(s <= e);
		Arrays.fill(res, Double.NEGATIVE_INFINITY);
		double[] tmp = new double[getm()];
		for (int i=s; i <= e; i++) {
			for (int m = 0; m < getm(); m++) {
				tmp[m] += (slices[i].get(m)?1.0:(-1.0));
			}
			for (int m = 0; m < getm(); m++) {
				res[m] = Math.max(tmp[m], res[m]);
			}
		}
	}
	
	// Computes the ceiling for all intervals starting with prefix ps - pe and ending before and including e
	public void getBestTimeLapsedEdgesLeftAligned(int ps, int pe, int e, double[] res) {
		assert(ps <= pe && pe <= e);
		Arrays.fill(res, Double.NEGATIVE_INFINITY);
		double[] tmp = new double[getm()];
		for (int i=ps; i <= e; i++) {
			for (int m = 0; m < getm(); m++) {
				tmp[m] += (slices[i].get(m)?1.0:(-1.0));
			}
			if (i >= pe) {
				for (int m = 0; m < getm(); m++) {
					res[m] = Math.max(tmp[m], res[m]);
				}
			}
		}
	}
	
	
	
	public void updateBestTimeLapsedEdges( int s, int e, int sz,
										   double[] weights, int[] pos) {
		assert(e-s+1 >= sz);
		if (e-s+1 == sz) {
			aggregateEdgeWeights(s, e, weights);
			Arrays.fill(pos, s);
		} else {
			for (int m = 0; m < getm(); m++) {
				// if edge can be updated do it
				if (!slices[e].get(m)) {
					weights[m] = weights[m] + 1;
				} else if(!slices[s].get(m) && slices[e].get(m)) {
					weights[m] = weights[m] + 1;
					pos[m]++;
				} else if (slices[s].get(m) && slices[e].get(m)) { // both ends are +1, then recompute
					double tmp = 0;
					weights[m] = Double.NEGATIVE_INFINITY;
					pos[m] = -1;
					for (int p=s; p <= e; p++) {
						if(p-s+1 < sz) {
							tmp += (slices[p].get(m)?1.0:(-1.0));
						} else if (p-s+1 == sz) {
							tmp += (slices[p].get(m)?1.0:(-1.0));
							weights[m] = tmp;
							pos[m] = p-sz+1;
						} else {
							tmp -= (slices[p-sz].get(m)?1.0:(-1.0));
							tmp += (slices[p].get(m)?1.0:(-1.0));
							if (tmp > weights[m]) {
								weights[m] = tmp;
								pos[m] = p-sz+1;
							}
						}
					}
				}
			}
			
		}
		System.currentTimeMillis();
	}
	
	
	public double[] aggregateEdgeWeights(int s, int e, double[] ew) {
		assert(s<=e && s >= 0 && e < gett()):"Incorrect interval" + s + " " + e;
		Arrays.fill(ew, 0);
		for (int i = s; i <=e; i++) {
			for(int j = 0; j < getm(); j++) {
				if (slices[i].get(j)) ew[j] +=1;
				else ew[j] -=1;
			}
		}
		return ew;
	}
	
	public void computeOptimalIntervalsPerEdge() {
		opt_intervals = new double[getm()][50];
		double[] be;
		for (int size =0; size < 50; size++) {
			be = getBestTimeLapsedEdges(0, gett()-1, size+1);
			for (int i = 0; i < getm(); i++) {
				opt_intervals[i][size] = be[i];
			}
			we = be;
			System.err.print(IntervalBounds.getUB(this) + "\n");
		}
		
		for (int i = 0 ;i < getm(); i++) {
			ExtToolsDriver.plotVector(opt_intervals[i]);
			ExtToolsDriver.kill("gnuplot");
		}
		
	}
	
	//-----------------------------Stats--------------------
	public DynamicModel getDynamicsModel() {
		DynamicModel m = new DynamicModel();
		BitSet curr = new BitSet();
		int pppairs = 0, pmpairs = 0;
		for (int t = 0; t < gett(); t++) {
			m.POne += slices[t].cardinality();
			for (int n = 0; n < getn(); n++) {
				int ones = slices[t].get(ind[n], ind[n+1]).cardinality();
				pppairs += ones*(ones-1)/2;
				if(ones > 0) { pmpairs += ones*(ind[n+1] - ind[n] - ones);}
			}
			curr.clear();
			curr.or(slices[t]);
			if (t < gett()-1) {
				curr.and(slices[t+1]);
				m.PNextGivenCurrent += curr.cardinality();
			}
		}
		m.PNextGivenCurrent /= m.POne;
		m.PNeighbor = pppairs*1.0/(pppairs +pmpairs);
		m.POne /= gett()*getm();
		return m;
	}
	
	
	// -----------------------------Subgraphs--------------------- 
	@Override
	public TimeGraph getLargestConnectedComponent() {
		Graph g = super.getLargestConnectedComponent();
		int[] edgemap = new int[g.getm()];
		for (int i=0;i<g.getm();i++) {
			edgemap[i] = getEdgeIndex(getNodeIndex(g.names[g.getOrigin(i)]), 
									  getNodeIndex(g.names[g.endv[i]]));
		}
		BitSet[] bs = null;
		if (null != slices[0]) {
			bs = new BitSet[gett()];
			for (int i=0;i<gett(); i++) {
				bs[i] = new BitSet(g.getm());
				for (int j = 0; j < g.getm(); j++) 
					if (slices[i].get(edgemap[j])) 
						bs[i].set(i);
			} 
		}
		int[][] vs = null;
		if (null != values) {
			vs = new int[gett()][g.getm()];
			for (int i = 0; i < gett(); i++) {
				for (int j = 0; j < g.getm(); j++) {
					vs[i][j] = values[i][edgemap[j]];
				}
			}
		}
		TimeGraph tg = null;
		if (null != values) {
			tg = new TimeGraph(g, vs);
			tg.slices = bs;
		} else {
			tg = new TimeGraph(g, bs);
		}
		return tg;
	}

	public TimeGraph getBFSSubgraph(int seed, int size, int s , int e) {
		Graph gg = super.getBFSSubgraph(seed, size);
		HashMap<Integer,Integer> edge_map = new HashMap<Integer, Integer>();
		gg.buildN2I();
		for (int i = 0; i < gg.getn(); i++) {
			for (int j = gg.ind[i]; j < gg.ind[i+1]; j++) {
				int v1 = getNodeIndex(gg.names[i]);
				int v2 = getNodeIndex(gg.names[gg.endv[j]]);
				int ed = getEdgeIndex(v1,v2);
				if (ed == -1) {
					System.err.print("negative");
				}
				edge_map.put(j, ed);
			}
		}
		BitSet[] nslices = new BitSet[e-s+1];
		for (int t = s; t <= e; t++) {
			nslices[t-s] = new BitSet(gg.getm());
			for (int i = 0; i < gg.getm(); i++) {
				if (slices[t].get(edge_map.get(i))) {
					nslices[t-s].set(i); 
				}
			}
		}
		
		TimeGraph tg = new TimeGraph(gg, nslices);
		if (null != nodescores) {
			double[][] ns = new double[tg.getn()][tg.gett()];
			for (int n=0; n < tg.getn(); n++) {
				int idx = getNodeIndex(tg.names[n]);
				for (int t = 0; t < tg.gett(); t++) {
					ns[n][t] = nodescores[idx][t];
				}
			}
			tg.nodescores = ns;
		}
		
		return tg;
	}
	
	public double getBestScore(int s, int e, boolean exact) throws IOException {
		Arrays.fill(we,0);
		aggregateByTime(s, e);
		BitSet edges = new BitSet(getm());
		if (exact) IntervalBounds.MaximumScoreSubgraph(this, edges);
		else IntervalBounds.topDownLBFast(this,edges);
		return getScore(edges);
	}
	
	public Graph getGraph() {
		return this;
	}
	
	@Override
	public float[][] getTimeseries() {
		float[][] res = new float[slices.length][getm()];
		for (int t = 0; t < gett(); t++) {
			for (int i = 0; i < getm(); i++) {
				res[t][i] = (slices[t].get(i)?1:-1);
			}
		}
		return res;
	}

	public float[][] getEdgePvalues() {
		//not supposed to be asking for this
		return null;
	}

	public static void main(String[] argv) {
		
//		System.err.print("orig:\t" +  tg.getDynamicsModel().toString() + "\n");
//		tgcopy = GraphGenerator.generateTimeRWSampling(tg.gett(), tg.getDynamicsModel(), tg);
//		//tgcopy = GraphGenerator.generateTimeNonClustered(tg.gett(), tg.getDynamicsModel(), tg);
//		System.err.print("copy:\t" +  tgcopy.getDynamicsModel().toString() + "\n");
		//tg = tgcopy;
		
		
		// first probability is persist, second seed
//		Graph g = GraphGenerator.generateRandom(10, 13);
//		TimeGraph tg = GraphGenerator.generateTimeGraphLocalized(60, 0.01, 0.1, 0.01, g);
		TimeGraph tg = null;
		try{
			 tg = IO.readTGraphEvents("/home/petko/data/temporal/enron/events",
					 t_res.W, 2, "pete.davis@enron.com no.address@enron.com enron.announcements@enron.com ");
		} catch (IOException e) {
			
		}
		//System.err.print(tg.toStringTime());
		tg.computeOptimalIntervalsPerEdge();
		
		
		tg.aggregateByTime(10, 33);
		System.err.print("[10,14]\n" + tg.toStringStruct());
	}
	
}
