package exp;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Random;
import java.util.TreeSet;

import misc.Common;
import misc.ComparableInterval;
import misc.ExtToolsDriver;
import misc.IO;
import misc.SplineInterpolation;
import misc.Time;
import misc.Time.t_res;
import alg.BUp;
import index.CoarsenIndex;
import index.IntervalBounds;
import index.IntervalIndex;
import index.IntervalIndexExactCeiling;
import index.PartitionIndex;
import generator.DynamicModel;
import generator.GraphGenerator;
import graph.Graph;
import graph.ITimeGraph;
import graph.Pattern;
import graph.TimeGraph;
import graph.Tree;
import graph.WeightedTimeGraph;

public class BoundUtility {	
	
	// -------------------  Common -----------------------------------------------------
	
	public static double runNaive(TimeGraph tg, RunMesasurements rm, 
			int s, int e, boolean exact) throws IOException {
		rm.clear();
		// Verification
		int time = e-s+1;
		rm.veri_all = time*(time+1);
		long start = System.currentTimeMillis();
		ComparableInterval max = IntervalBounds.handleNonPruned(tg, s, e, exact);
		rm.veri_t = (System.currentTimeMillis() - start);
		return max.val;
	}
	
	public static void runExhaustive(TimeGraph tg, int topKlb, RunMesasurements rm,
			int time, int s, int e,boolean exact ) throws IOException{
		rm.clear();
		TreeSet<ComparableInterval> notpruned = new TreeSet<ComparableInterval>();
		// NAIVE
		double[][] ubs = new double[time][time];
		double[][] lbs = new double[time][time];
		for(int i=0; i < ubs.length; i++) {
			Arrays.fill(ubs[i], Double.NEGATIVE_INFINITY);
			Arrays.fill(lbs[i], Double.NEGATIVE_INFINITY);
		}
		// Sum+
		long start = System.currentTimeMillis();
		IntervalBounds.sumPositive(tg,s,e,ubs);
		rm.sop_t = (System.currentTimeMillis()-start);
		// Get LB
		start = System.currentTimeMillis();
		rm.best_lb = IntervalBounds.getLBtopKInMatrix(tg, s, e, ubs, topKlb, null, lbs,exact);
		rm.lb_t = (System.currentTimeMillis()-start);
		
//				ExtToolsDriver.plotMatrix(ubs,1.0,lbpp,ubs.length);
		
		// Prune
		rm.ubs_all = time*(time+1)/2 - IntervalBounds.numPruned(ubs, rm.best_lb);
		start = System.currentTimeMillis();
		rm.ubs_n = IntervalBounds.pruneUB(tg, s, e, rm.best_lb, ubs, null, false,1.1,notpruned, rm);
		rm.ub_t = (System.currentTimeMillis() - start);
		
//				ExtToolsDriver.plotMatrix(ubs,1.0,lbpp,ubs.length);
		
		// Verification
		rm.veri_all = notpruned.size();
		start = System.currentTimeMillis();
		rm.veri_n = IntervalBounds.handleNonPruned(tg, s, e, rm, lbs, notpruned, null, exact);
		rm.veri_t = (System.currentTimeMillis() - start);
		
//				ExtToolsDriver.plotMatrix(ubs,1.0,lbpp,ubs.length);
	}
	
	public static Pattern runShort(ITimeGraph tg, int s, int e, RunMesasurements rm, boolean exact) throws IOException{
		Pattern bptn = null;
		for (int st=s; st <=e; st++) {
			for (int end=st; end <=e; end++) {
				tg.aggregateByTime(st, end);
				BitSet edges = new BitSet(tg.getm());
				if (exact) IntervalBounds.MaximumScoreSubgraph(tg.getGraph(), edges);
				else IntervalBounds.topDownLBFast(tg.getGraph(), edges);
				Pattern pt = new Pattern(st, end, edges, tg.getGraph().getScore(edges));
				if (null == bptn) bptn = pt;
				else if (bptn.score<pt.score) bptn = pt;
			}
		}	
		return bptn;
	}
	
	
	// runs the evaluation of top-1 on the graph
	public static Pattern runCoarse(ITimeGraph tg, int s, int e, int time,
			double alpha, int topKlb, RunMesasurements rm, boolean exact) throws IOException{
		TreeSet<ComparableInterval> notpruned_coarse = new TreeSet<ComparableInterval>();
		rm.clear();
		if (time <=2) {
			return runShort(tg, s, e, rm, exact);
		}
		// OURS
		double[][] coarse = new double[time][time];
		double[][] ubsi = new double[time][time];
		double[][] lbsi = new double[time][time];
		for(int i=0; i < ubsi.length; i++) {
			Arrays.fill(ubsi[i], Double.NEGATIVE_INFINITY);
			Arrays.fill(coarse[i], Double.NEGATIVE_INFINITY);
			Arrays.fill(lbsi[i], Double.NEGATIVE_INFINITY);
		}
		long start = System.currentTimeMillis();
		// 1. INDEX
		// Compute tlog(t) points in the quadratic space of vectors and 
		// index them to be able to reconstruct arbitrary vectors 
		IntervalIndexExactCeiling ind = new IntervalIndexExactCeiling(tg, s, e);
		rm.index_t = (System.currentTimeMillis()-start);
		
		// 2. Group SOP
		start = System.currentTimeMillis();
		IntervalBounds.coarse(tg,s,e,alpha,ind,ubsi,coarse );
		rm.coarsen_t = (System.currentTimeMillis()-start);
		
		// 3. LB
		start = System.currentTimeMillis();
		SplineInterpolation si = new SplineInterpolation(coarse);
		rm.best_lb = IntervalBounds.getLBtopKInMatrix(tg, s, e, si, ubsi.length, topKlb, ind, lbsi, exact);
		
		rm.lb_t = (System.currentTimeMillis()-start+0);
		
		rm.sopcoarse_p = IntervalBounds.numPruned(ubsi, rm.best_lb);
		
		// 4. UB STR
		rm.ubs_all = time*(time+1)/2 - IntervalBounds.numPruned(ubsi, rm.best_lb);
		start = System.currentTimeMillis();
		// TODO(petko): debug pruneUB. for 100 node graph
		// for 73-83 it sets the UB to 218 < 220 the actual. It sets it based
		// on the grouping. debug this
		rm.ubs_n = IntervalBounds.pruneUB(tg, s, e, rm.best_lb, ubsi, ind, false, alpha, notpruned_coarse, rm);
		rm.ub_t = (System.currentTimeMillis() - start);
		
//		for (ComparableInterval ci: notpruned_coarse) {
//			System.err.print((ci.pos+s) + "\t" + (ci.pos+s+ci.size-1) + "\t" +ci.val + "\n");
//		}
		// 5. Verify
		rm.veri_all = notpruned_coarse.size();
		start = System.currentTimeMillis();
		rm.veri_n = IntervalBounds.handleNonPruned(tg, s, e, rm, lbsi, notpruned_coarse, ind, exact);
		rm.veri_t = (System.currentTimeMillis() - start);
//		for (ComparableInterval ci: notpruned_coarse) {
//			System.err.print((ci.pos+s) + "\t" + (ci.pos+s+ci.size-1) + "\t" +ci.act + "(" +ci.val+  ")\n");
//		}
		Pattern pt = null;
		BitSet edges = new BitSet(tg.getm());
		BitSet[] selected  = new BitSet[tg.gett()];
		for(int i= 0; i < lbsi.length; i++) {
			for (int j = 0; j < lbsi.length; j++) {
				if (rm.best_lb == lbsi[i][j]){
					int st = j, en = i+j;
					tg.aggregateByTime(st+s, en+s);
					if (exact) IntervalBounds.MaximumScoreSubgraph(tg.getGraph(), edges);
					else IntervalBounds.topDownLBFast(tg.getGraph(), edges);
					pt = new Pattern(st+s, en+s, edges, tg.getGraph().getScore(edges));
//					System.out.print("n=" + tg.getn() + "\n");
//					System.out.print("T=" + time + "\n");
//					System.out.print("span=[" + (st+s) + "," + (en+s) + "]\n");
//					System.out.print("tuples = {\n");
//					for(int nod = 0; nod < tg.getn(); nod++) {
//						for (int ed = tg.ind[nod] ; ed < tg.ind[nod+1];ed++) {
//							if (edges.get(ed) && nod < tg.endv[ed]) {
//								System.out.print("\t<" + tg.names[nod] + "," + tg.names[tg.endv[ed]] + 
//										           "," + (int)tg.we[ed] + ">\n");
//							}
//						}
//					}
//					System.out.print("};\nscore=" + tg.getScore(edges) + "\n");
					return pt;
					//ExtToolsDriver.showInGoogleEarth(t.names);
					// prepare return
//					for (int t=0; t < tg.gett();t++) {
//						selected[t] = new BitSet(tg.getm());
//						if (t >= st+s && t <=en+s) {
//							selected[t].or(edges);
//						}
//						selected[t].flip(0,tg.getm()-1);
//					}
				}
			}
		}
		return null;
		
//					ExtToolsDriver.plotMatrix(ubsi,1.0,lbpp_interp,ubsi.length);
	}

	
	// ------------------- Increasing interval -----------------------------------------
	
	public static void runIncreasingTimeRandom(boolean isER, int n, int m,
			   double N, double T, double percentNNZ, int[] times, 
			   int trials, double[] alphas, int topKlb,
			   boolean exact ) throws IOException{	
		// generate graph
		Graph g = null;
		if (isER) {
			g = GraphGenerator.generateRandom(n, m);
		} else {
			g = GraphGenerator.generateScaleFree(n);
		}
		assert(g.isConnected());
		
		// Time graph
		
		DynamicModel dm = new DynamicModel();
		dm.PNeighbor = N;
		dm.PNextGivenCurrent = T;
		dm.POne = percentNNZ;
		
		//TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, N, T, EC, g);
		TimeGraph tg = GraphGenerator.generateTimeRWSampling(times[times.length-1]*2, dm, g);
		
		System.err.print(tg.getDynamicsModel() + "\n");
	
		runIncreasingTime(times, trials, tg, "ER_RANDOM", alphas, topKlb, exact);
	}

	public static void runIncreasingTime(int[] times, int ntrials, 
			TimeGraph tg, String name, double[] alphas, int topKlb,boolean exact ) throws IOException{
		
		double[][] elapsed = new double[times.length][1+alphas.length];
		double[][] breakdown_t = new double[times.length][5];
		double[][][] pruning = new double[alphas.length][times.length][5];
		RunMesasurements rm = new RunMesasurements();
		
		for(int tindex = 0 ; tindex < times.length; tindex++) {
			for (int trials = 0; trials < ntrials; trials++) {
				int time = times[tindex];
				int s = Common.rand.nextInt(tg.gett()-time-1);
				int e = s+time-1;
				System.err.print("TIME:"+ time + "[" + s + "-" + e + "] ###################\n" );
				
//				runNaive(tg, rm, s, e);
//				System.err.print("------ NAIVE ------------ :\n");
//				System.err.print(rm.toString());
//				System.err.print("Total:" + rm.sumTime() + "\n");
//				elapsed[tindex][0] += rm.sumTime() / (1000.0*ntrials);
				
//				runExhaustive(tg, topKlb, rm, time, s, e);
				
				//ExtToolsDriver.plotMatrix(posit,1.0,lbpp,posit.length);
				System.err.print("------ Sum+ ------------ :\n");
				System.err.print(rm.toString());
				System.err.print("Total:" + rm.sumTime() + "\n");
				elapsed[tindex][0] += rm.sumTime() / (1000.0*ntrials);
				
				for (int alphi = 0;  alphi < alphas.length; alphi++) { 
					double alpha = alphas[alphi];
					
					runCoarse(tg, s, e, time, alpha, topKlb, rm, exact);
					
					System.err.print("------ Interpolate ({/Symbol a}="+ Common.oneDigitFormat.format(alpha) + ") ------------ :\n");
					System.err.print(rm.toString());
					System.err.print("Total:" + (rm.sumTime()) + "\n");
					elapsed[tindex][1+alphi] += (rm.sumTime()) / (1000.0*ntrials);
					if (alphi == 0) {
						breakdown_t[tindex][0] += rm.index_t / (1000.0*ntrials);
						breakdown_t[tindex][1] += rm.coarsen_t / (1000.0*ntrials);
						breakdown_t[tindex][2] += rm.lb_t / (1000.0*ntrials);
						breakdown_t[tindex][3] += rm.ub_t / (1000.0*ntrials);
						breakdown_t[tindex][4] += rm.veri_t / (1000.0*ntrials);
					} 
					pruning[alphi][tindex][0] += rm.sopcoarse_p*100.0 / (ntrials);
					pruning[alphi][tindex][1] += rm.ubcoarse_p*100.0 / (ntrials);
					pruning[alphi][tindex][2] += rm.sop_p*100.0 / (ntrials);
					pruning[alphi][tindex][3] += rm.ub_p*100.0 / (ntrials);
					pruning[alphi][tindex][4] += rm.veri_p*100.0 / (ntrials);
				}
				ExtToolsDriver.kill("gnuplot");
			}
		}
		
		String[] x = new String[times.length]; for (int i=0;i<times.length; i++) x[i] = "" + (int)times[i];
		
		for (int alphi = 0;  alphi < alphas.length; alphi++) { 
			String[] component_names = {"CSOP", "CUB", "SOP", "UB", "VER"};
			ExtToolsDriver.plotStacks(x,component_names, pruning[alphi], "Interval Size", "Pruning %", 
						name + "_inctsize_pruning." + Common.oneDigitFormat.format(alphas[alphi]) + ".t", true);
		}
		
		
		String[] time_curve_names = new String[1+alphas.length]; 
		time_curve_names[0] = "Exhaustive";
		for(int i=0;i<alphas.length;i++) time_curve_names[i+1] = "HDS({/Symbol a}=" + Common.oneDigitFormat.format(alphas[i]) + ")";
		
		ExtToolsDriver.plotCurves(x,time_curve_names, elapsed, "Interval Size", "Time (s)", name + "_inctsize.t");
		
		String[] component_names = {"Index", "Coarsen", "Estimate", "UB+UBE", "Verify"};
		ExtToolsDriver.plotStacks(x,component_names, breakdown_t, "Interval Size", "Time (s)", name + "_inctsize_breakdown.t");
	}
	
	public static void runAllIncreasingInterval(boolean exact) throws IOException {
		TimeGraph tg = null;
		int n = 500;
		int m = 1000;
		double N = 0.3;
		double T = 0.9;
		double nz = 0.1;
		//int trials = 50;
		int trials = 10;
		int k = 10;
		int times[] = {100,500,1000,1500,2000};
		double[] alphas = {0.5, 0.7, 0.9};
		
		// RANDOM
		//runIncreasingTimeRandom(true, n, m, N, T, nz, times, trials, alphas, k);
		
		int enrontimes[] = {100};
		runIncreasingTime(enrontimes, trials, IO.getEnronGraph(t_res.W, 10), "ENRON", alphas, k, exact);
		//System.exit(0);
		//TWITTER
		int timestwitter[] = {50,100,150,200};
		tg = IO.getTwitterGraph(Common.DATA_DIR + "twitter/music/music.rt.graph.lcc.timegraph.final",
				        0.00037);
		System.err.print(tg.getDynamicsModel() + "\n");
		runIncreasingTime(timestwitter, trials, tg,"TWITTER", alphas, k, exact);
		
		// TRAFFIC
		tg = IO.readTGraphPems(Common.DATA_DIR + "PeMS/d07_stations_2010_08_18.graph", 
		   Common.DATA_DIR + "PeMS/d07_text_station_5min_2011_04.txt.timeseries");
		//nz = tg.scoreEdgesLTSpeed(20);
		tg.aggregateCoarsen(4);
		nz = tg.scoreEdgesLTPercOfAvg(0.4);
		k = 10;
		runIncreasingTime(times,trials,tg, "TRAFFIC", alphas, k, exact);
	}
	
	
	public static void runIncreasingTimeRandomNaive(boolean isER, int n, int m,
			   double N, double T, double percentNNZ, int[] times, int trials, 
			   boolean exact) throws IOException {	
		// generate graph
		Graph g = null;
		if (isER) {
			g = GraphGenerator.generateRandom(n, m);
		} else {
			g = GraphGenerator.generateScaleFree(n);
		}
		assert(g.isConnected());
		
		// Time graph
		
		DynamicModel dm = new DynamicModel();
		dm.PNeighbor = N;
		dm.PNextGivenCurrent = T;
		dm.POne = percentNNZ;
		
		//TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, N, T, EC, g);
		TimeGraph tg = GraphGenerator.generateTimeRWSampling(times[times.length-1]*2, dm, g);
		
		System.err.print(tg.getDynamicsModel() + "\n");
	
		runIncreasingTimeNaive(times, trials, tg, "ER_RANDOM_NAIVE", exact);
	}

	public static void runIncreasingTimeNaive(int[] times, 
			int ntrials, TimeGraph tg, String name, boolean exact) throws IOException {
		double[] elapsed = new double[times.length];
		RunMesasurements rm = new RunMesasurements();
		
		for(int tindex = 0 ; tindex < times.length; tindex++) {
			for (int trials = 0; trials < ntrials; trials++) {
				int time = times[tindex];
				int s = Common.rand.nextInt(tg.gett()-time);
				int e = s+time-1;
				System.err.print("TIME:"+ time + "[" + s + "-" + e + "] ###################\n" );
				runNaive(tg, rm, s, e, exact);
				System.err.print("------ NAIVE ------------ :\n");
				System.err.print("Total:" + rm.sumTime() + "\n");
				elapsed[tindex] += rm.sumTime() / (1000.0*ntrials);
			}
		}
		
		String[] x = new String[times.length]; for (int i=0;i<times.length; i++) x[i] = "" + (int)times[i];
		try {
			IO.writeSingleCurve(x, elapsed, Common.RES_DIR + name + "_inctsize.t");
		} catch (Exception e) {
			
		}
	}
	
	public static void runAllIncreasingIntervalNaive(boolean exact ) throws IOException {
		TimeGraph tg = null;
		int n = 500;
		int m = 1000;
		double N = 0.3;
		double T = 0.9;
		double nz = 0.1;
		//int trials = 50;
		int trials = 1;
		int times[] = {100,250};
		
		// RANDOM
//		runIncreasingTimeRandomNaive(true, n, m, N, T, nz, times, trials);
		
		int enrontimes[] = {50, 70};
		runIncreasingTimeNaive(enrontimes, trials, IO.getEnronGraph(t_res.D, 0), "ENRON_NAIVE", exact);
		//System.exit(0);
		//TWITTER
		int timestwitter[] = {20,30};
		tg = IO.getTwitterGraph(Common.DATA_DIR + "twitter/music/music.rt.graph.lcc.timegraph.final",
				        0.00037);
		System.err.print(tg.getDynamicsModel() + "\n");
//		runIncreasingTimeNaive(timestwitter, trials, tg,"TWITTER_NAIVE");
		
		// TRAFFIC
		int timestr[] = {100, 200};
		tg = IO.readTGraphPems(Common.DATA_DIR + "PeMS/d07_stations_2010_08_18.graph", 
		   Common.DATA_DIR + "PeMS/d07_text_station_5min_2011_04.txt.timeseries");
		//nz = tg.scoreEdgesLTSpeed(20);
		tg.aggregateCoarsen(4);
		nz = tg.scoreEdgesLTPercOfAvg(0.4);
		runIncreasingTimeNaive(timestr,trials,tg, "TRAFFIC_NAIVE", exact);
	}
	
	// ------------------- Increasing graph size -----------------------------------------
	
	public static void runIncreasingGraphSize(boolean isER, int[] n, int[] m,
			   double N, double T, double percentNNZ, int time, 
			   int ntrials, int topKlb, double[] alphas, boolean exact ) throws IOException{	
		double[][] elapsed = new double[n.length][1+alphas.length];
		double[][] breakdown_t = new double[n.length][5];
		RunMesasurements rm = new RunMesasurements();
		
		Graph g = null;
		for (int trial = 0; trial < ntrials; trial++) {
			for (int sind = 0; sind < n.length; sind++) {
				// generate graph
				if (isER) {
					g = GraphGenerator.generateRandom(n[sind], m[sind]);
				} else {
					g = GraphGenerator.generateScaleFree(n[sind]);
				}
				assert(g.isConnected());
				
				// Time graph
				DynamicModel dm = new DynamicModel();
				dm.PNeighbor = N;
				dm.PNextGivenCurrent = T;
				dm.POne = percentNNZ;
				
				//TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, N, T, EC, g);
				TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, dm, g);
			
				System.err.print(tg.getDynamicsModel() + "\n");
				int s = 0;
				int e = time-1;
				
				runExhaustive(tg, topKlb, rm, time, s, e, exact);
				
				System.err.print("SIZE:G("+ n[sind] +","+ m[sind] + ") [" + s + "-" + e + "] ###################\n" );
				System.err.print("------ Sum+ ------------ :\n");
				System.err.print(rm.toString());
				System.err.print("Total:" + rm.sumTime() + "\n");
				elapsed[sind][0] += (rm.sumTime()) / (1000.0*ntrials);
				
				
				for (int alphi = 0;  alphi < alphas.length ; alphi++) { 
					double alpha = alphas[alphi];
					
					runCoarse(tg, s, e, time, alpha, topKlb, rm, exact);
					
					System.err.print("------ Interpolate ({/Symbol a}="+ Common.oneDigitFormat.format(alpha) + ") ------------ :\n");
					System.err.print(rm.toString());
					
					System.err.print("Total:" + (rm.sumTime()) + "\n");
					elapsed[sind][1+alphi] += (rm.sumTime()) / (1000.0*ntrials);
					if (alphi == 0) {
						breakdown_t[sind][0] += rm.index_t / (1000.0*ntrials);
						breakdown_t[sind][1] += rm.coarsen_t / (1000.0*ntrials);
						breakdown_t[sind][2] += rm.lb_t / (1000.0*ntrials);
						breakdown_t[sind][3] += rm.ub_t / (1000.0*ntrials);
						breakdown_t[sind][4] += rm.veri_t / (1000.0*ntrials);
					}
				}	
				ExtToolsDriver.kill("gnuplot");
			}
		}
		String[] x = new String[n.length]; for (int i=0;i<n.length; i++) x[i] = ((int)(m[i]/100.0))*0.1 + "k";
		
		String[] time_curve_names = new String[1+alphas.length]; 
		time_curve_names[0] = "Exhaustive";
		for(int i=0;i<alphas.length;i++) time_curve_names[i+1] = "HDS({/Symbol a}=" + Common.oneDigitFormat.format(alphas[i]) + ")";
		ExtToolsDriver.plotCurves(x,time_curve_names, elapsed, "Graph Size |E|", "Time (s)", "incgsize.t");
		
		String[] component_names = {"Index", "Coarsen", "Estimate", "UB+UBE", "Verify"};
		ExtToolsDriver.plotStacks(x,component_names, breakdown_t, "Graph Size |E|", "Time (s)", "incgsize_breakdown.t");
	}
	
	// ------------------- Increasing density --------------------------------------------
	
	public static void runIncreasingDensity(boolean isER, int n, int m,
			   double N, double T, double[] percentNNZs, int time, 
			   int ntrials, int topKlb, double[] alphas,boolean exact ) throws IOException{	
		double[][] elapsed = new double[percentNNZs.length][1+alphas.length];
		double[][] breakdown_t = new double[percentNNZs.length][5];
		RunMesasurements rm = new RunMesasurements();
		
		Graph g = null;
		for (int trial = 0; trial < ntrials; trial++) {
			// generate graph
			if (isER) {
				g = GraphGenerator.generateRandom(n, m);
			} else {
				g = GraphGenerator.generateScaleFree(n);
			}
			assert(g.isConnected());
			
			// Time graph
			DynamicModel dm = new DynamicModel();
			dm.PNeighbor = N;
			dm.PNextGivenCurrent = T;
			for (int dind = 0; dind < percentNNZs.length; dind++) {
				dm.POne = percentNNZs[dind];
				
				//TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, N, T, EC, g);
				TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, dm, g);
			
				System.err.print(tg.getDynamicsModel() + "\n");
				int s = 0;
				int e = time-1;
				
				
				runExhaustive(tg, topKlb, rm, time, s, e, exact);
				
				System.err.print("DENSITY:"+ dm.POne + " [" + s + "-" + e + "] ###################\n" );
				System.err.print(rm.toString());
				System.err.print("Total:" + (rm.sumTime()) + "\n");
				elapsed[dind][0] += (rm.sumTime()) / (1000.0*ntrials);
				
				for (int alphi = 0;  alphi < alphas.length; alphi++) { 
					double alpha = alphas[alphi];
					
					runCoarse(tg, s, e, time, alpha, topKlb, rm, exact);
					
					System.err.print("------ Interpolate ({/Symbol a}="+ Common.oneDigitFormat.format(alpha) + ") ------------ :\n");
					System.err.print(rm.toString());
					System.err.print("Total:" + (rm.sumTime()) + "\n");
					elapsed[dind][1+alphi] += (rm.sumTime()) / (1000.0*ntrials);
					if (alphi == 1) {
						breakdown_t[dind][0] += rm.index_t / (1000.0*ntrials);
						breakdown_t[dind][1] += rm.coarsen_t / (1000.0*ntrials);
						breakdown_t[dind][2] += rm.lb_t / (1000.0*ntrials);
						breakdown_t[dind][3] += rm.ub_t / (1000.0*ntrials);
						breakdown_t[dind][4] += rm.veri_t / (1000.0*ntrials);
					} 
				}	
				ExtToolsDriver.kill("gnuplot"); // comment
			}
		}
		String[] x = new String[percentNNZs.length]; for (int i=0;i<percentNNZs.length; i++) x[i] = "" + percentNNZs[i];
		String[] time_curve_names = new String[1+alphas.length];
		time_curve_names[0] = "Exhaustive";
		for(int i=0;i<alphas.length;i++) time_curve_names[i+1] = "HDS({/Symbol a}=" + Common.oneDigitFormat.format(alphas[i]) + ")";
		
		ExtToolsDriver.plotCurves(x,time_curve_names, elapsed, "Percentage of Active Edges", "Time (s)", "incdensity.t");
		
		String[] component_names = {"Index", "Coarsen", "Estimate", "UB+UBE", "Verify"};
		ExtToolsDriver.plotStacks(x,component_names, breakdown_t, "Percentage of Active Edges", "Time (s)", "incdensity_breakdown.t");
	}
	
	// ------------------- Increasing correlation ----------------------------------------
	private static void runIncreasingCorrelation(boolean isER, int n, int m,
			double[] params, double nz, int time, int ntrials, int topKlb,
			double[] alphas, boolean exact ) throws IOException{
		
		double[][] elapsed = new double[params.length][1+alphas.length];
		double[][] breakdown_t = new double[params.length][6]; 
		RunMesasurements rm = new RunMesasurements();
		
		Graph g = null;
		for (int trial = 0; trial < ntrials; trial++) {
			// generate graph
			if (isER) {
				g = GraphGenerator.generateRandom(n, m);
			} else {
				g = GraphGenerator.generateScaleFree(n);
			}
			assert(g.isConnected());
			
			// Time graph
			DynamicModel dm = new DynamicModel();
			dm.POne = nz;
			
			for (int dind = 0; dind < params.length ; dind++) {
				dm.PNeighbor = params[dind];
				dm.PNextGivenCurrent = Math.min(params[dind]*2.5, 0.98);
				//TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, N, T, EC, g);
				TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, dm, g);
			
				System.err.print(tg.getDynamicsModel() + "\n");
				int s = 0;
				int e = time-1;
				
				
				runExhaustive(tg, topKlb, rm, time, s, e, exact);
				
				System.err.print("N:"+ dm.PNeighbor + " [" + s + "-" + e + "] ###################\n" );
				System.err.print(rm.toString());
				System.err.print("Total:" + (rm.sumTime()) + "\n");
				elapsed[dind][0] += (rm.sumTime()) / (1000.0*ntrials);
				
				for (int alphi = 0;  alphi < alphas.length; alphi++) { 
					double alpha = alphas[alphi];
					
					runCoarse(tg, s, e, time, alpha, topKlb, rm, exact);
					
					System.err.print("------ Interpolate({/Symbol a}="+ Common.oneDigitFormat.format(alpha) + ") ------------ :\n");
					System.err.print(rm.toString());
					System.err.print("Total:" + (rm.sumTime()) + "\n");
					elapsed[dind][1+alphi] += (rm.sumTime()) / (1000.0*ntrials);
					if (alphi == 0) {
						breakdown_t[dind][0] += rm.index_t / (1000.0*ntrials);
						breakdown_t[dind][1] += rm.coarsen_t / (1000.0*ntrials);
						breakdown_t[dind][2] += rm.lb_t / (1000.0*ntrials);
						breakdown_t[dind][3] += rm.ub_t / (1000.0*ntrials);
						breakdown_t[dind][4] += rm.veri_t / (1000.0*ntrials);
					}
				}	
				ExtToolsDriver.kill("gnuplot");
			}
		}
		String[] x = new String[params.length]; for (int i=0;i < params.length ; i++) x[i] = "" + Common.oneDigitFormat.format(params[i]);
		String[] time_curve_names = new String[1+alphas.length];
		time_curve_names[0] = "Exhaustive";
		for(int i=0;i<alphas.length;i++) time_curve_names[i+1] = "HDS({/Symbol a}=" + Common.oneDigitFormat.format(alphas[i]) + ")";
		
		ExtToolsDriver.plotCurves(x,time_curve_names, elapsed, "Correlation of Neighboring Edges", "Time (s)", "inccorrelation.t");
		
		String[] component_names = {"Index", "Coarsen", "Estimate", "UB+UBE", "Verify"};
		ExtToolsDriver.plotStacks(x,component_names, breakdown_t, "Correlation of Neighboring Edges", "Time (s)", "inccorelation_breakdown.t");
	}
	
	// ------------------- Increasing Alpha ----------------------------------------
	private static void runIncreasingAlpha(double nz, int ntrials, int topKlb,boolean exact ) throws IOException{

		double[][] elapsed = new double[9][4];
		RunMesasurements rm = new RunMesasurements();
		Graph g = null;
		int time = 0;

			for (int gtype=0; gtype <1; gtype++) {
				TimeGraph tg = null;
				try {
					if (gtype==0){
						System.err.print("Traffic\n");
						tg = IO.readTGraphPems(Common.DATA_DIR + "PeMS/d07_stations_2010_08_18.graph", 
								   Common.DATA_DIR + "PeMS/d07_text_station_5min_2011_04.txt.timeseries");
						//nz = tg.scoreEdgesLTSpeed(20);
						tg.aggregateCoarsen(4);
						nz = tg.scoreEdgesLTPercOfAvg(0.3);
						time = 100;
					} else if (1==gtype) {
						System.err.print("Enron\n");
						tg = IO.getEnronGraph(t_res.D,0);
						time = 200;
					} else if (2==gtype) {
						System.err.print("Twitter\n");
						tg = IO.getTwitterGraph(Common.DATA_DIR + "twitter/music/music.rt.graph.lcc.timegraph.final",
						        0.00036);
						time = 80;
					} else {
						System.err.print("Synthetic\n");
						g = GraphGenerator.generateRandom(500, 1200);
						// Time graph
						DynamicModel dm = new DynamicModel();
						dm.POne = nz;
						dm.PNeighbor = 0.4;
						dm.PNextGivenCurrent = 0.97;
						//TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, N, T, EC, g);
						time = 200;
						tg = GraphGenerator.generateTimeRWSampling(time, dm, g);
						assert(g.isConnected());
						
					}
				} catch (Exception e) {
					
				}
				
				System.err.print(tg.getDynamicsModel() + "\n");
				int s = Common.rand.nextInt(tg.gett()-time-1);
				int e = s+time-1;
				for (int trial = 0; trial < ntrials; trial++) {
					for (int aind = 0; aind < 9 ; aind++) {
						double alpha = (1+aind)*0.1;
						runCoarse(tg, s, e, time, alpha, topKlb, rm, exact);
						System.err.print("------ Interpolate({/Symbol a}="+ Common.oneDigitFormat.format(alpha) + ") ------------ :\n");
						System.err.print(rm.toString());
						System.err.print("Total:" + (rm.sumTime()) + "\n");
						elapsed[aind][gtype] += (rm.sumTime()) / (1000.0*ntrials);	
					}	
					ExtToolsDriver.kill("gnuplot");
				}
		}
		String[] x = new String[9]; for (int i=0; i < 9 ; i++) x[i] = "" + Common.oneDigitFormat.format((1+i)*0.1);
		String[] time_curve_names = new String[4];
		time_curve_names[0] = "Traffic";
		time_curve_names[1] = "Enron";
		time_curve_names[2] = "Twitter";
		time_curve_names[3] = "Synthetic";
		
		ExtToolsDriver.plotCurves(x,time_curve_names, elapsed, "{/Symbol a}", "Time (s)", "incalpha.t");
	}
	
	public static void measureCeilVsUB(boolean isER,
			   double N, double T, int EC, int[] sizes){
		int ntrials = 1;
		Random r = new Random();
		
		if (isER) System.err.print("Random\n");
		else System.err.print("Power Law\n");
		for(int szindex = 0 ; szindex < sizes.length; szindex++) {
			for (int trials = 0; trials < ntrials; trials++) {
				// generate graph
				Graph g = null;
				if (isER) {
					g = GraphGenerator.generateRandom(sizes[szindex], sizes[szindex]*2);
				} else {
					g = GraphGenerator.generateScaleFree(sizes[szindex]);
				}
				double[] u = new double[g.getm()];
				double[] v = new double[g.getm()];
				int time = 20;
				assert(g.isConnected());
				DynamicModel dm = new DynamicModel();
				dm.PNeighbor = N;
				dm.PNextGivenCurrent = T;
				dm.POne = 0.1;
				
				TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, dm, g);
				int cnt_ub = 0;
				double tub=0.0, tceil=0.0;
				
				for(int sz = 0; sz < time; sz++) {
					for (int j = 0; j < time-sz; j++) {
						tg.aggregateByTime(j, j+sz);
						long start = System.currentTimeMillis();
						IntervalBounds.getUB(tg); 
						tub+= (System.currentTimeMillis() -start);
						cnt_ub++;
					}
				}
				int numcnt = cnt_ub*10;
				for (int n = 0; n < numcnt; n++) {
					for (int i = 0; i < tg.we.length; i++) {
						u[i] = r.nextDouble();
						v[i] = r.nextDouble();
					}
					
					long start = System.currentTimeMillis();
					for (int i = 0; i < tg.we.length; i++) 
						tg.we[i] = Math.max(u[i], v[i]);
					tceil += (System.currentTimeMillis() -start);
				}
				
				System.err.print((tg.getm()/2) + "\t" + tub/cnt_ub + "\t" +  tceil/numcnt + "\n"); 
			}
		}
	}
	
	//------------------------Estimation Accuracy-------------------------------------------
	public static void estimationAccuracy(boolean exact) throws IOException {
		TimeGraph tg = null;
		int n = 500;
		int m = 1000;
		double N = 0.3;
		double T = 0.96;
		double nz = 0.01;
		//int trials = 50;
		int ntrials = 2;
		int[] ks = {5,10,15,20,25,30,35,40};
		int time = 100;
		double alpha = 0.5;
		
		double[][] accuracy = new double[ks.length][5];
		RunMesasurements rm = new RunMesasurements();
		
		for (int gtrials = 0; gtrials < ntrials; gtrials++){
			Graph g = null;
			g = GraphGenerator.generateRandom(n, m);
			
			// Time graph
			
			DynamicModel dm = new DynamicModel();
			dm.PNeighbor = N;
			dm.PNextGivenCurrent = T;
			dm.POne = nz;
			
			//TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, N, T, EC, g);
			tg = GraphGenerator.generateTimeRWSampling(time*5, dm, g);
			
			System.err.print(tg.getDynamicsModel() + "\n");
		
			for (int trials = 0; trials < ntrials; trials++) {
				int s = Common.rand.nextInt(tg.gett()-time);
				int e = s+time-1;
				double score = 1;
				score = runNaive(tg, rm, s, e, exact);
				System.err.print("actual:"+ score + "\n" );
				
				for(int kindex = 0 ; kindex < ks.length; kindex++) {
					int k = ks[kindex];
					System.err.print("K:"+ ks[kindex] + "[" + s + "-" + e + "] ###################\n" );
					double[][] coarse = new double[time][time];
					double[][] ubsi = new double[time][time];
					double[][] lbsi = new double[time][time];
					for(int i=0; i < coarse.length; i++) {
						Arrays.fill(coarse[i], Double.NEGATIVE_INFINITY);
						Arrays.fill(ubsi[i], Double.NEGATIVE_INFINITY);
						Arrays.fill(lbsi[i], Double.NEGATIVE_INFINITY);
					}
			
					// Compute tlog(t) points in the quadratic space of vectors and 
					// index them to be able to reconstruct arbitrary vectors 
					IntervalIndexExactCeiling ind = new IntervalIndexExactCeiling(tg, s, e);
					
					long start = System.currentTimeMillis();
					IntervalBounds.coarse(tg,s,e,alpha,ind,ubsi,coarse );
					long elapsed_coarse = (System.currentTimeMillis()-start+0);
					
					start = System.currentTimeMillis();
					SplineInterpolation si = new SplineInterpolation(coarse);
					accuracy[kindex][2] += IntervalBounds.getLBtopKInMatrix(tg, s, e, si, ubsi.length, k, ind, lbsi, exact) /(score*ntrials*ntrials);
					long elapsed = (System.currentTimeMillis()-start+0);
					
					accuracy[kindex][1] += IntervalBounds.getLBGreedy(tg, s, e, time, k, ind, coarse, elapsed, exact) /(score*ntrials*ntrials);
					
					accuracy[kindex][0] += IntervalBounds.getLBRandomSampling(tg, s, e, time,ind,elapsed+elapsed_coarse, exact)/(score*ntrials*ntrials);
					
					System.err.print(k + "\t" + accuracy[kindex][0]*(score*ntrials*ntrials) + "\t" + 
							 accuracy[kindex][1]*(score*ntrials*ntrials) + "\t" + accuracy[kindex][2]*(score*ntrials*ntrials) + "\n");
				}
				
			}
		}
		
		String[] x = new String[ks.length]; for (int i=0;i<ks.length; i++) x[i] = "" + (int)ks[i];
		
		String[] time_curve_names = new String[3]; 
		time_curve_names[1] = "Greedy";
		time_curve_names[0] = "Sampling";
		time_curve_names[2] = "Spline";
		
		ExtToolsDriver.plotCurves(x,time_curve_names, accuracy, "k", "Accuracy", "lbcomparison.t");
//		
//		String[] component_names = {"Index", "Coarsen", "Estimate", "UB+UBE", "Verify"};
//		ExtToolsDriver.plotStacks(x,component_names, breakdown_t, "Interval Size", "Time (s)", name + "_inctsize_breakdown.t");
	}
	
	
	public static void CompareMetrics() throws IOException {
		int[] times = {1,3,5,7,9,11,13,15};
		double[][] elapsed = new double[times.length][1];
		int time = 0;
		int trials = 100;
		
		System.err.print("Traffic\n");
		TimeGraph tg = IO.readTGraphPems(Common.DATA_DIR + "PeMS/d07_stations_2010_08_18.graph", 
				   Common.DATA_DIR + "PeMS/d07_text_station_5min_2011_04.txt.timeseries");
		tg.aggregateCoarsen(4);
		double nz = tg.scoreEdgesLTPercOfAvg(0.4);
		tg.aggregateCoarsen(4);
		for (int i = 0; i < times.length; i++) {
			double avg = 0;
			for (int j = 0; j < 100; j++) {
				int s = Common.rand.nextInt(tg.gett()-times[i] -1);
				int e = s + times[i] -1;
				tg.aggregateByTime(s, e);
				BitSet edges = new BitSet(tg.getm());
				IntervalBounds.topDownLBFast(tg, edges);
				double d = tg.getScore(edges);
				
				BUp b = new BUp(tg.getAggNodeWeighted());
				double gw = b.getBestClusterScore();
				
				elapsed[i][0] += (d/(gw*trials));
			}
		}
		
		String[] x = new String[9]; for (int i=0; i < 9 ; i++) x[i] = "" + times[i];
		String[] time_curve_names = new String[1];
		time_curve_names[0] = "Traffic";
		
		ExtToolsDriver.plotCurves(x,time_curve_names, elapsed, "{/Symbol a}", "Time (s)", "compheu_incalpha.t");
	}
	
	public static void main(String[] args) throws IOException{
		
//		runAllIncreasingIntervalNaive();
//		if (true) System.exit(0);
//		estimationAccuracy();
		
		// increasing time
		runAllIncreasingInterval(false);
		//int[] m = {1000,5000,10000,15000,20000};
		int[] m = {1000,5000,10000,15000,20000};
		int[] n = new int[m.length];
		for (int i = 0 ; i < n.length; i++) {
			n[i] =  (int)(m[i] / 2.4);
		}
		
		double N = 0.3;
		double T = 0.96;
		double nz = 0.05;
		//int trials = 10;
		int trials = 2;
		int k  = 5;
		int time = 1000;
		double[] alphas = {0.6};
//		runIncreasingGraphSize(true, n, m, N, T, nz, time, trials, k, alphas);
		
		//trials = 50;
		trials = 5;
		int nn = 1000;
		int mm = 2400;
		time = 1000;
		k = 20;
		double[] alphasd = {0.6, 0.7, 0.8};
		double[] density = {0.01, 0.1, 0.2, 0.3};
//		runIncreasingDensity(true, nn, mm, N, T, density, time, trials, k, alphasd);
		
		//trials = 50;
		trials = 1;
		nz = 0.1;
		time = 1000;
		double[] params = {0, 0.1, 0.2, 0.3, 0.5};
//		runIncreasingCorrelation(true, nn, mm, params, nz, time, trials, k, alphasd);
		
		trials=3; time = 200; k = 10;
//		runIncreasingAlpha(nz, trials, k);
	//	CompareMetrics();
	}

	

	
}
