package smooth;

import index.IntervalBounds;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;

import exp.BoundUtility;
import exp.RunMesasurements;

import misc.ComparableIndexedValue;
import misc.ComparableFix;
import misc.IO;

import generator.GraphGenerator;
import graph.Pattern;
import graph.SmoothPattern;
import graph.WeightedTimeGraph;

public class Greedy {
	public static boolean DEBUG = false; 
	public static boolean SMOOTH_DEBUG = false; 
	
	// heuristic SMOOTHEN
	// returns a smoothed pattern 
	
	public static SmoothPattern smoothen(WeightedTimeGraph tg, 
			SmoothPattern sp, 
			int maxsmooth, 
			boolean split){
		// everything is allowed
		TreeMap<Integer,BitSet> allowed = new TreeMap<Integer, BitSet>();
		for (int t=0; t < tg.gett(); t++) {
			allowed.put(t, new BitSet(tg.getm())) ;
			allowed.get(t).set(0, tg.getm());
		}
		return smoothen(tg, sp, maxsmooth, allowed, split);
	}
	
	public static SmoothPattern smoothen(WeightedTimeGraph tg, 
													SmoothPattern sp, 
													int maxsmooth, 
													TreeMap<Integer,BitSet> allowed,
													boolean split){		
		// in case someone calls this for one slice :)
		if (sp.edges.size()==1) return sp;
		// save the original pattern
		ArrayList<BitSet> pattern = new ArrayList<BitSet>();
		BitSet prev = new BitSet(tg.getm());
		prev.set(0,tg.getm());
		for(Integer t:sp.edges.keySet()) {
			pattern.add(new BitSet(sp.edges.get(t).size()));
			pattern.get(pattern.size()-1).or(sp.edges.get(t));
			prev.and(sp.edges.get(t));
			// Time-Disconnected pattern
			if(prev.cardinality() < 1) return null;
			prev.clear();
			prev.or(sp.edges.get(t));
		}
		
		ArrayList<Float> slicescores = getSliceScores(tg,sp.s,pattern);
		if (sp.hasNegativeSlice()) return null;
		
		// get all violations only shaving removals! (i.e. those that do not disconnect the graph in the slice)
		TreeSet<ComparableFix> fixes = new TreeSet<ComparableFix>();
		HashSet<String> done = new HashSet<String>();
		int numv = computeViolationFixes(tg,sp.s,pattern, maxsmooth, fixes, allowed, slicescores);
		while (numv > 0) {
			// if in debug mode
			if (SMOOTH_DEBUG) {
				for (ComparableFix cf: fixes) {
					int eidx = tg.getEdgeIndex(cf.srcnd, cf.dstnd);
					for(int t=cf.tstart;t<=cf.tend;t++) {
						assert(cf.add!=pattern.get(t).get(eidx)):
							"Fix is " + (cf.add?"adding ":"removing ") + cf.srcnd + " - " + cf.dstnd + 
							" at time " + t + ", but the edge is " + (cf.add?" in ":" not in ") + "the pattern " + 
							pattern.toString() + "\n";
						if(slicescores.get(t) + (cf.add?1:-1)*tg.wsl[sp.s+t][eidx] < 0) {
							System.out.print("Negative slice when " + (cf.add?"adding ":"removing ") + 
									cf.srcnd + " - " + cf.dstnd + " at time " + t + ".\n");
							numv = computeViolationFixes(tg, sp.s, pattern, maxsmooth, fixes, allowed, slicescores);
							assert(0==1);
						}
					}
				}
			}
			
			// find a fix that involves an edge that have not been changed
			if (fixes.isEmpty()) {
				// TODO: verify if this is a case in which every fix is infeasible
				// because it disconnects the graphs
				return null;
			}
			ComparableFix cf = fixes.last();
			while (done.contains(cf.getIndexTime())) {
				fixes.remove(fixes.last());
				if (fixes.size() == 0) {
					cf = null;
					break;
				}
				cf = fixes.last();
			}
			
			BitSet empty = new BitSet();
			BitSet disconnect = new BitSet();
			// Fix a violation
			if (cf.add) {
				if(SMOOTH_DEBUG) System.err.print("adding " + cf.toString());
				for(int t=cf.tstart;t<=cf.tend;t++) {
					pattern.get(t).set(cf.index);
					pattern.get(t).set(tg.getReverseEdgeIndex(cf.index));
					slicescores.set(t, slicescores.get(t) + tg.wsl[sp.s+t][cf.index]);
				}
			} else {
				if(SMOOTH_DEBUG) System.err.print("removing " + cf.toString());
				for(int t=cf.tstart;t<=cf.tend;t++) {
					pattern.get(t).clear(cf.index);
					pattern.get(t).clear(tg.getReverseEdgeIndex(cf.index));
					slicescores.set(t, slicescores.get(t) - tg.wsl[sp.s+t][cf.index]);
					if (slicescores.get(t) < 0) empty.set(t);
				}
				// check for disconnections
				for (int t=Math.max(0, cf.tstart-1); t < Math.min(pattern.size()-1, cf.tend); t++) {
					BitSet bs = new BitSet();
					bs.or(pattern.get(t));
					bs.and(pattern.get(t+1));
					if (bs.cardinality() == 0) disconnect.set(t);
				}
			}
			if (SMOOTH_DEBUG) {
				ArrayList<Float> ss = getSliceScores(tg,sp.s,pattern);
				for (int i=0;i<ss.size();i++) 
					assert(Math.abs(ss.get(i)-slicescores.get(i)) < 0.00001);
			}
			// SPLIT
			// If any of the affected slices is empty -> split
			// invoke in all three parts recursively
			if (empty.cardinality() > 0 || disconnect.cardinality() >0 ){
				SmoothPattern res = null;
				if (!split) return res;
				if(sp.s==sp.e) return null;
				if(DEBUG) System.err.print("\nSplit:" + cf.toString() + "\n");
				assert(null==res);
				SmoothPattern before = null;
				if (cf.tstart > 0) {
					before = smoothen(tg,slice(sp.s,sp.s+cf.tstart-1,sp,tg),maxsmooth,allowed,split);
					res = before;
				}
				SmoothPattern after = null;
				if (cf.tend < pattern.size()-1) {
					after = smoothen(tg,slice(sp.s+cf.tend+1,sp.e,sp,tg),maxsmooth,allowed,split);
					if (null==res) res = after;
					else if (res.score < after.score) res = after;
				}
				if(res == null) {
//					System.out.println("breaking does not spit\n");
//					System.out.println(sp.toString());
					return null;
				}
				SmoothPattern now = 
					smoothen(tg,slice(sp.s+cf.tstart,sp.s+cf.tend,sp,tg),maxsmooth,allowed,split);
				if (now == null) 
					return res;
				if (now.score > res.score) res = now; 
				return res;
			}
			done.add(cf.getIndexTime());
			//viz(tg,pattern);
			numv = computeViolationFixes(tg, sp.s,pattern, maxsmooth, fixes, allowed, slicescores);
			if(false) System.err.print("\t" + numv + "\n");
		}
		// smoothened, now convert pattern into a SmoothPattern
		
		TreeMap<Integer,BitSet> edg = new TreeMap<Integer,BitSet>();
		for(int i=0;i<pattern.size();i++) edg.put(i+sp.s,pattern.get(i));
		SmoothPattern res = new SmoothPattern(tg, edg, maxsmooth);
		
		// TODO: apply post-processing to improve score 
		
		return res;
	}
	
	private static ArrayList<Float> getSliceScores(WeightedTimeGraph tg,
			int s, ArrayList<BitSet> pattern) {
		// compute score in every slice
		ArrayList<Float> slicescores = new ArrayList<Float>();
		for(int t=0; t < pattern.size(); t++) {
			float score = 0;
			for(int i=pattern.get(t).nextSetBit(0); i >=0 && i < tg.getm(); 
			    i = pattern.get(t).nextSetBit(i+1)) {
				if (pattern.get(t).get(i))
					score += tg.wsl[t+s][i]/2.0;
			}
			slicescores.add(score);
		}
		return slicescores;
	}
	
	private static SmoothPattern slice(int from, int to, SmoothPattern sp, WeightedTimeGraph tg) {
		TreeMap<Integer,BitSet> edg = new TreeMap<Integer,BitSet>();
		for(int i=from;i<=to;i++) edg.put(i, sp.edges.get(i));
		SmoothPattern res = new SmoothPattern(tg, edg, (from==to?0:Integer.MAX_VALUE) );
		return res;
	}
	
	// gets all violations and orders them by cost to fix greedily
	private static int computeViolationFixes(
			WeightedTimeGraph tg, int start, 
			ArrayList<BitSet> pattern, int maxsmooth,
			TreeSet<ComparableFix> fixes,
			TreeMap<Integer,BitSet> allowed,
			ArrayList<Float> slicescores) {
		int numv = 0;
		fixes.clear();
		
		// count all violations a every transition
		BitSet[] incons = new BitSet[pattern.size()-1];
		for (int t = 0; t < pattern.size()-1; t++) {
			incons[t] = new BitSet();
			incons[t].or(pattern.get(t));
			incons[t].xor(pattern.get(t+1));
		}

		for (int t = 0; t < pattern.size()-1; t++) {
			// if too many violations (add fixes)
			if(incons[t].cardinality()/2 > maxsmooth) {
				for(int i=incons[t].nextSetBit(0); i>=0; i=incons[t].nextSetBit(i+1)) {
					if (tg.endv[i] > tg.getOrigin(i)) {
						// first case: inconsistency is incl(t),excl(t+1)
						if(pattern.get(t).get(i)) {
							// Fill a hole in the future
							int to = t+1;
							float cost = 0;
							
							// this loop rotates until there another inconsistent edge is hit or until 
							// one slice before the end of the pattern
							// alternatively it might break due to inability to add the edge at some time to
							// or if adding it might make a slice negative
							while (to < pattern.size()-1 && !incons[to].get(i) && canAdd(i,pattern.get(to),tg) &&
									slicescores.get(to) + tg.wsl[to+start][i] >= 0 && allowed.get(to+start).get(i) ) {
								cost += tg.wsl[to+start][i];
								to++;
							}
							// check if the edge can be added at time to
							// to might be either a time in which the addition failed (in this case a fix is not added), 
							// or the end of the whole in which case the cost is updated and the fix is added
							if (canAdd(i,pattern.get(to),tg) && allowed.get(to+start).get(i) &&
								 slicescores.get(to) + tg.wsl[to+start][i] >= 0) {
								cost += tg.wsl[to+start][i];
								fixes.add(new ComparableFix(t+1, to, i, cost, true, tg.getOrigin(i), tg.endv[i]));
							}
							
							// Shave a bump in the past
							int from = t-1;
							cost = 0;
							if (canRemove(i,pattern.get(t),tg) && 
								slicescores.get(t) - tg.wsl[t+start][i] >= 0) {
								cost -= tg.wsl[t+start][i];
								while (from >=0 ) {
									if(!incons[from].get(i) && canRemove(i,pattern.get(from),tg) && 
										slicescores.get(from) - tg.wsl[from+start][i] >= 0) {
										cost -= tg.wsl[from+start][i];
										from--;
									} else {
										break;
									}
								}
								// if we reached the beginning 
								if (from < 0) {
									fixes.add(new ComparableFix(from+1, t, i, cost, false, tg.getOrigin(i), tg.endv[i]));
								} else if (incons[from].get(i)) { // or to another inconsistency we can shave
									fixes.add(new ComparableFix(from+1, t, i, cost, false, tg.getOrigin(i), tg.endv[i]));
								}
							}
						} else { // second case: inconsistency is excl(t),incl(t+1)
							// Shave a bump in the future
							int to = t+1;
							float cost = 0;
							while (to < pattern.size()-1 && !incons[to].get(i) && canRemove(i, pattern.get(to), tg) &&
									slicescores.get(to) - tg.wsl[to+start][i] >= 0) {
								cost -= tg.wsl[to+start][i];
								to++;
							}
							if (canRemove(i, pattern.get(to), tg) &&
								slicescores.get(to) - tg.wsl[to+start][i] >= 0) { // reached to another violation to solve
								cost -= tg.wsl[to+start][i];
								fixes.add(new ComparableFix(t+1, to, i, cost, false, tg.getOrigin(i), tg.endv[i]));
							}
							
							// Fill a hole in the past
							if (canAdd(i, pattern.get(t), tg) && allowed.get(t+start).get(i) &&
								 slicescores.get(t) + tg.wsl[t+start][i] >= 0) {
								cost += tg.wsl[t+start][i];
								int from = t-1;
								while(from>=0 ) {
									if(!incons[from].get(i) && canAdd(i, pattern.get(from), tg) &&
										slicescores.get(from) + tg.wsl[from+start][i] >= 0 && allowed.get(from+start).get(i)) {
										cost += tg.wsl[from+start][i];
										from--;
									} else {
										break;
									}
								}
								if (from < 0) { // fill to the beginning
									fixes.add(new ComparableFix(from+1, t, i, cost, true, tg.getOrigin(i), tg.endv[i]));
								} else if (incons[from].get(i)) { // fill to from excluding 
									fixes.add(new ComparableFix(from+1, t, i, cost, true, tg.getOrigin(i), tg.endv[i]));
								}
							}
						}
					}
				}
				numv+= incons[t].cardinality()/2 - maxsmooth;
			}
		}
		return numv;
	}
	
	// checks if an edge is connected to the pattern (AT LEAST ONE end is in b (excluding e))
	private static boolean canAdd(int e, BitSet b,
			WeightedTimeGraph tg) {
		int src = tg.getOrigin(e);
		int dest = tg.endv(e);
		boolean srcin = false, destin = false;
		for(int i=tg.ind[src]; i < tg.ind[src+1]; i++) {
			if (i==e || i==tg.getReverseEdgeIndex(e)) continue; // skip the same edge
			if (b.get(i)) {
				srcin = true;
				break;
			}
		}
		for(int i=tg.ind[dest]; i < tg.ind[dest+1]; i++) {
			if (i==e || i==tg.getReverseEdgeIndex(e)) continue; // skip the same edge
			if (b.get(i)) {
				destin = true;
				break;
			}
		}
		// it is connected if AT LEAST one of src and dest is in the rest of the pattern b
		return ((srcin || destin));
	}
	
	// checks if an edge is connected to the pattern (AT LEAST ONE end is in b (excluding e))
	private static boolean canRemove(int e, BitSet b,
			WeightedTimeGraph tg) {
		// sanity check
		assert(b.get(e)):"trying to remove an edge that is not part of the pattern";
		if (b.cardinality()==2) return true;
		assert(canAdd(e, b, tg)):"Tryingt to remove a disconnected edge!";
		// first check if it is a whisker
		if (isWhiskerEdge(e, b, tg)) return true;
		// Both ends are attached. Check if it disconnects the pattern
		int src = tg.getOrigin(e);
		int dest = tg.endv(e);
		// do a BFS from src using b's edges excluding e and check if we reach dest
		HashSet<Integer> explored = new HashSet<Integer>();
		PriorityQueue<Integer> next = new PriorityQueue<Integer>();
		next.add(src); explored.add(src);
		Integer nd = null;
		while ((nd = next.poll())!=null) {
			for (int i = tg.ind[nd]; i < tg.ind[nd+1];i++) {
				if (i!=e && b.get(i)) {
					if (tg.endv[i]==dest) return true;
					else if (!explored.contains(tg.endv[i])) {
						next.add(tg.endv[i]); 
						explored.add(tg.endv[i]);
					}
				}
			}
		}
		return false;
	}

	// checks of an edge is a whisker (only one end is in b (excluding e))
	private static boolean isWhiskerEdge(int e, BitSet b,
			WeightedTimeGraph tg) {
		int src = tg.getOrigin(e);
		int dest = tg.endv(e);
		boolean srcin = false, destin = false;
		for(int i=tg.ind[src]; i < tg.ind[src+1]; i++) {
			if (i==e || i==tg.getReverseEdgeIndex(e)) continue; // skip the same edge
			if (b.get(i)) {
				srcin = true;
				break;
			}
		}
		for(int i=tg.ind[dest]; i < tg.ind[dest+1]; i++) {
			if (i==e || i==tg.getReverseEdgeIndex(e)) continue; // skip the same edge
			if (b.get(i)) {
				destin = true;
				break;
			}
		}
		// it is a whisker if only one of src and dest is in the rest of the pattern b
		return (srcin && !destin) || (!srcin && destin);
	}

	// Heuristic EXTEND
	public static TreeMap<Integer,BitSet> extend(WeightedTimeGraph tg, int t, int maxsmooth, int s, int e) {
		TreeMap<Integer, BitSet> pattern = new TreeMap<Integer, BitSet>();
		BitSet bs = new BitSet();
		
		tg.aggregateByTime(t, t);
		IntervalBounds.topDownLBFast(tg, bs);
		
		if (bs.cardinality()==0) return null;
		
		pattern.put(t, bs);
		
		// Extend forward
		int next = t+1;
		if (next < e) {
			bs = extendPattern(tg, next, pattern.get(next-1), maxsmooth);
			while (bs.cardinality() > 0) {
				pattern.put(next,bs);
				next++;  if(next == e) break;
				bs = extendPattern(tg, next, pattern.get(next-1), maxsmooth);
			}
		}
		
		// Extend backward
		next = t-1;
		if (next >= s){
			bs = extendPattern(tg, next, pattern.get(next+1), maxsmooth);
			while (bs.cardinality() > 0) {
				pattern.put(next,bs);
				next--; if(next < s) break;
				bs = extendPattern(tg, next, pattern.get(next+1), maxsmooth);
			}
		}
		
		return pattern; 
	}

	private static BitSet extendPattern(WeightedTimeGraph tg, int t,
		BitSet prevbs, int maxsmooth) {
		
		// get nodes adjacent to selected edges
		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 (prevbs.get(j)) {
					nodes.add(i);
					nodes.add(tg.endv(j));
				}
			}
		}
		
		// rank order insertion and deletion of edges (in one direction only)
		tg.aggregateByTime(t, t);
		PriorityQueue<ComparableIndexedValue> q = 
			new PriorityQueue<ComparableIndexedValue>(prevbs.cardinality()*2,Collections.reverseOrder());
		for (Integer i: nodes) {
			for(int j=tg.ind[i]; j < tg.ind[i+1]; j++) {
				if (i > tg.endv[j]) continue;
				if (!prevbs.get(j)) q.add(new ComparableIndexedValue(j, tg.we[j]));
				else q.add(new ComparableIndexedValue(j, -1.0*tg.we[j]));
			}
		}
		
		BitSet res = new BitSet(prevbs.size());
		res.or(prevbs);
		// Update the pattern
		int changes = 0;
		while (changes < maxsmooth && res.cardinality() > 0 && q.size() > 0) {
			ComparableIndexedValue ed = q.poll();
			if(ed.v<0) break;
			// If we have removed edges and disconnected this edge's anchor skip
			if(!nodes.contains(tg.getOrigin(ed.ind)) || !nodes.contains(tg.endv(ed.ind)))
				continue;
			if (res.get(ed.ind)){
				// remove the edge
				HashSet<Integer> splitnodes = tg.nodesInSmallerComponent(res,ed.ind); 
				if (splitnodes.size() <= 1) {
					// if there is an external node remove it from nodes
					nodes.removeAll(splitnodes);
					// remove the edge
					res.clear(ed.ind);
					res.clear(tg.getReverseEdgeIndex(ed.ind));
					changes++;
				}
			} else {
				// add an edge
				nodes.add(tg.getOrigin(ed.ind));
				nodes.add(tg.endv(ed.ind));
				res.set(ed.ind);
				res.set(tg.getReverseEdgeIndex(ed.ind));
				changes++;
			}
			
		}
		
		double sum = 0;
		for (int i =0; i < tg.getn(); i++) {
			for (int j= tg.ind[i]; j < tg.ind[i+1]; j++) {
				if(res.get(j) && i < tg.endv[j]) {
					sum += tg.we[j];
				}
			}
		}
		
		if (sum < 0) res.clear();
		
		return res;
	}
	
	// LOWER BOUNDS
	
	public static float lowerBound(WeightedTimeGraph tg, int s, int e, 
			int maxsmooth, TreeSet<SmoothPattern> pats, int numsamples) {
		Random r = new Random();
		// First compute sum of positive CDF for every slice
		double[] sop = new double[e-s+1];
		for (int t =0; t < sop.length; t++) {
			for (int i = 0; i < tg.getm(); i++) {
				if (tg.wsl[t+s][i] > 0) { 
					sop[t] += tg.wsl[t+s][i];
				}
			}
			if (t > 0) sop[t] += sop[t-1];
		}
		
		for (int t =0; t < sop.length; t++) sop[t] /= sop[sop.length-1];
		
		pats.clear();
		double bestscore = 0;
		HashSet<Integer> sampled = new HashSet<Integer>();
		// now sample slices biased towards high SOP
		int cnt = 0;
		while (cnt < numsamples) {
			cnt++;
			double prob = r.nextDouble();
			int t = Arrays.binarySearch(sop, prob);
			if (t < 0) t = t*(-1);
			t = t-1;
			if (sampled.contains(t)) continue;
			else sampled.add(t);
			TreeMap<Integer, BitSet> edges = extend(tg, t+s, maxsmooth, s,e);
			if (null!=edges) {
				SmoothPattern sp = new SmoothPattern(tg, edges, maxsmooth);
				pats.add(sp);
				//if(DEBUG) System.err.print("time " + t + " score " + sp.score + "\n");
				if (sp.score > bestscore) {
					bestscore = sp.score;
				}
			}
		}
		return (float)(bestscore);
	}
	
	public static float lowerBoundExhaustive(WeightedTimeGraph tg, int s, int e, 
			int maxsmooth, TreeSet<SmoothPattern> pats) {
		pats.clear();
		double bestscore = Float.NEGATIVE_INFINITY;
		// now sample slices biased towards high SOP
		for (int t = s; t <= e; t++){
			TreeMap<Integer, BitSet> edges = extend(tg, t, maxsmooth, s, e);
			if (null!=edges) {
				SmoothPattern sp = new SmoothPattern(tg, edges, maxsmooth);
				pats.add(sp);
				if(DEBUG) System.err.print("time " + t + " score " + sp.score + "\n");
				if (sp.score > bestscore) {
					bestscore = sp.score;
				}
			}
		}
		return (float)(bestscore);
	}
	
	// VERIFICATION
	public static SmoothPattern verifyDAG(int maxsmooth, WeightedTimeGraph wtg,
			boolean allPaths, boolean split, TreeMap<Integer,BitSet> allowed, 
			DAG d, double lb) {
		TreeSet<SmoothPattern> pats = new TreeSet<SmoothPattern>();
		long s = System.currentTimeMillis();
		if (allPaths) {
			d.getAllLongestPaths(pats);
		} else {
			d.getLongestPathEveryRoot(pats);
		}
		
		if (DEBUG ) {
			// summarize paths
			TreeMap<String,Integer> interv_counts = new TreeMap<String, Integer>();
			HashSet<String> uniq_intervals = new HashSet<String>();
			for (SmoothPattern sp: pats.descendingSet()) {
				uniq_intervals.add(sp.toString());
				if (!interv_counts.containsKey(sp.s + "\t" + sp.e)) interv_counts.put(sp.s + "\t" + sp.e, 0);
				interv_counts.put(sp.s + "\t" + sp.e, interv_counts.get(sp.s + "\t" + sp.e) + 1);
			}
			
//			for (String ic: interv_counts.keySet()) {
//				System.err.print(ic + "\t" + interv_counts.get(ic) + "\n");
//			}
			System.out.println("TIME TO CONSTRUCT PATHS:" + (System.currentTimeMillis()-s)/1000.0);
			System.out.println("DAG candidate paths:" + pats.size());
		}
		//System.out.println("MAX Path Score:" + pats.last().score);
		TreeSet<SmoothPattern> res = new TreeSet<SmoothPattern>();
		int cnt = 0, nullcnt=0;
		HashSet<String> uniq_res = null;
		TreeMap<String,String> S = null;
		if(DEBUG) {
			uniq_res = new HashSet<String>();
			S = new TreeMap<String, String>();
		}
		
		for (SmoothPattern sp: pats.descendingSet()) {
			assert(!sp.hasNegativeSlice());
			SmoothPattern newsp = Greedy.smoothen(wtg,sp,maxsmooth,allowed,split);
			if(null!=newsp) {
				assert(!newsp.hasNegativeSlice());
				if (DEBUG) {
					S.put(sp.toString(), newsp.toString());
					uniq_res.add(newsp.toString());
				}
				res.add(newsp);
			} else {
				nullcnt++;
			}
			cnt++;
			if ((cnt % 1000)==0 && DEBUG) 
				System.out.println("Verified " + cnt + "paths");
		}
		if (DEBUG )System.out.println("VERIFIED TOTAL:" + cnt);
		if (res.size()==0) return null;
		else return res.last();
	}
	
	
	/// ------------------------------ API CALLS -------------------------------------------
	
	/* PARAMETERS
	 
	maxsmooth - max number of changes
	
	numsamples - number of time slice samples when running fast lower bound heuristic
	
	wtg - is the Weighted time graph (similar to when calling the lower bound)
	
	lowerbound - is the computed lowerbound value

	upperBound[time][node] is the node upper bounds. the indices of the nodes are according to their order in wtg.names
	If you have a string node name NODE. just call   wtg.getNodeIndex(NODE) to get its index

	allPaths - if set enumerates all pairs longest paths in the DAG

	split - if set does splits in smoothening (if allPaths is set, better leave split=false)

	HashMap<Integer,HashSet<HashMap<String,HashSet<String>>>> components contains the components as a set of adjacency lists for every time stamp
	This is the meaning of the values in the nested structure  above:
	HashMap<Time,HashSet<HashMap<SourceNode,HashSet<DestinationNode>>>> 
	
	*/
	
	// Sampling Extend
	public static float calcLowerBound(int maxsmooth, int numsamples, WeightedTimeGraph tg) {
		TreeSet<SmoothPattern> pats = new TreeSet<SmoothPattern>();
		return lowerBound(tg, 0, tg.gett()-1, maxsmooth, pats, numsamples);
	}
	// Exhaustive Extend
	public static float calcLowerBound(int maxsmooth, WeightedTimeGraph tg) {
		TreeSet<SmoothPattern> pats = new TreeSet<SmoothPattern>();
		return lowerBoundExhaustive(tg, 0, tg.gett()-1, maxsmooth, pats);
	}

	public static SmoothPattern verifyComponents(int maxsmooth, WeightedTimeGraph wtg, 
			Vector<HashSet<Integer>> validNodes, 
			TreeMap<Integer, HashSet<Integer>> region, boolean doSplits){
		TreeMap<Integer,BitSet> allowed = transformAllowed(validNodes, region.firstKey(), region.lastKey(), wtg);
		TreeMap<Integer, BitSet> edg = new TreeMap<Integer, BitSet>();
		int edgescnt = 0;
		for (Integer t:region.keySet()) {
			edg.put(t, allowedNodes2allowedEdges(wtg, region.get(t)));
			edgescnt+= edg.get(t).cardinality()/2;
		}
		if (edgescnt == 0) {
			System.err.print("Empty region passed");
		}
		SmoothPattern sporig = new SmoothPattern(wtg, edg, -1);
		SmoothPattern res =smoothen(wtg, sporig, maxsmooth, allowed, doSplits);
		if (null == res) {
			System.err.print("Null after smoothing");
		}
		return res;
	}
	
	public static TreeMap<Integer,BitSet> transformAllowed(
			Vector<HashSet<Integer>> validNodes, Integer s,
			Integer e, WeightedTimeGraph wtg) {
		TreeMap<Integer,BitSet> allowed = new TreeMap<Integer, BitSet>();
		for (int t = s; t <=e; t++) {
			allowed.put(t,allowedNodes2allowedEdges(wtg, validNodes.get(t)));
		}
		return allowed;
	}
	
	public static BitSet allowedNodes2allowedEdges(WeightedTimeGraph wtg, HashSet<Integer> nodes) {
		BitSet allowed = new BitSet(wtg.getm());
		for (Integer i: nodes) {
			for(int j = wtg.ind[i]; j < wtg.ind[i+1]; j++) {
				if(nodes.contains(wtg.endv[j]))
					allowed.set(j);
			}
		}
		return allowed;
	}
	
    // MEDEN
	public static SmoothPattern meden(WeightedTimeGraph tg, int s, int e, 
									  int maxsmooth, boolean roughen) throws Exception {
		Pattern pt = BoundUtility.runCoarse(tg, s, e, e-s+1, 0.4, 10, new RunMesasurements(), false);
		SmoothPattern sp = new SmoothPattern(tg, pt.s,pt.e,pt.edges);
		if (sp.hasNegativeSlice()) 
			sp = sp.getMaxNonNegativeSS();
		//System.out.println("Meden original score:" + sp.score);
		if (!roughen) return sp;
		else {
			SmoothPattern newsp = improveMedenSolution(sp,tg,maxsmooth);
			if (newsp.hasNegativeSlice()) 
				return newsp.getMaxNonNegativeSS();
			else 
				return newsp;
		}
	}
	
	public static void testGrid() {
		
		WeightedTimeGraph wtg = GraphGenerator.getGridLineSweep(3, 4);
		//WeightedTimeGraph wtg = GraphGenerator.getGridLineSweepWeakMiddle(3, 4);
		ArrayList<BitSet> pattern = new ArrayList<BitSet>();
		// prepare edge list of positive
		for(int t=0; t < wtg.gett(); t++) {
			BitSet bs = new BitSet(wtg.getm());
			for (int j = 0; j < wtg.getm(); j++) {
				if(wtg.wsl[t][j] >= 0) bs.set(j);
			}
			pattern.add(bs);
		}
		
		int smoothness = 5;
		
		//viz(wtg,pattern,0);
		
 		TreeMap<Integer,BitSet> allowed = new TreeMap<Integer, BitSet>();
 		for (int i =0; i < wtg.gett(); i++) {
 			allowed.put(i,new BitSet());
 			allowed.get(i).set(0, wtg.getm());
 		}
 		
 		TreeMap<Integer,BitSet> edg = new TreeMap<Integer,BitSet>();
		for(int i=0;i<pattern.size();i++) edg.put(i, pattern.get(i));
		SmoothPattern sp = new SmoothPattern(wtg, edg, Integer.MAX_VALUE);
		SmoothPattern res = smoothen(wtg, sp, smoothness, allowed,true);
		
		res.visualizeNoLabels();
		System.err.print("Done");
		
	}

	
	public static void viz(WeightedTimeGraph wtg, ArrayList<BitSet> pattern, int start) {
		TreeMap<Integer,BitSet> edges = new TreeMap<Integer, BitSet>();
		for(int t = 0; t < pattern.size(); t++) edges.put(t+start, pattern.get(t));
		SmoothPattern before = new SmoothPattern(wtg, edges, Integer.MAX_VALUE);
		before.visualizeNoLabels();
	}

	public static SmoothPattern improveMedenSolution(SmoothPattern spp,
			WeightedTimeGraph tg, int maxsmooth) {
		TreeMap<Integer, Integer> violations = new TreeMap<Integer, Integer>();
		ArrayList<BitSet> sp = new ArrayList<BitSet>();
		for (Integer t:spp.edges.keySet()) {
			violations.put(t-spp.s, 0);
			sp.add(new BitSet());
			sp.get(sp.size()-1).or(spp.edges.get(t));
		}
		
		HashSet<String> edgetimeaction = new HashSet<String>();
		double score = spp.score;
		boolean changed = true;
		while (changed) {
			changed = false;
			for (int t = 0; t < sp.size(); t++) {
				for (int i=0; i < tg.getn(); i++) {
					for (int j = tg.ind[i]; j < tg.ind[i+1]; j++) {
						if(sp.get(t).get(j) && tg.wsl[t+spp.s][j] < 0 && sp.get(t).cardinality() > 2 && canRemove(j, sp.get(t), tg)) { 
							boolean violates_prev = false;
							if (t>0) {
								if (sp.get(t-1).get(j)) {
									violates_prev = true;
								}
							}
							boolean violates_this = false;
							if (t<sp.size()-1) {
								if (sp.get(t+1).get(j)) {
									violates_this = true;
								}
							}
							if (violates_prev)
								if (violations.get(t-1) == maxsmooth) 
									continue;
							if (violates_this)
								if (violations.get(t) == maxsmooth) 
									continue;
							// we can remove
							if(edgetimeaction.contains(j + "_"+ t + "_r" )) 
								continue;
							edgetimeaction.add(j + "_"+ t + "_r");
							score -= tg.wsl[t+spp.s][j];
							sp.get(t).clear(j);
							sp.get(t).clear(tg.getReverseEdgeIndex(j));
							if (DEBUG) System.err.print("Removing " + j + " at time " + t + 
									" score " +tg.wsl[t+spp.s][j]+ "\n");
							if (violates_prev) 
								violations.put(t-1, 1+violations.get(t-1));
							if (violates_this) 
								violations.put(t, 1+violations.get(t));
							changed = true;
						} else if (!sp.get(t).get(j) && tg.wsl[t+spp.s][j] >= 0 && canAdd(j, sp.get(t), tg)) { // try to add
							boolean violates_prev = false;
							if (t>0) {
								if (!sp.get(t-1).get(j)) 
									violates_prev = true;
							}
							boolean violates_this = false;
							if (t<sp.size()-1) {
								if (!sp.get(t+1).get(j)) {
									violates_this = true;
								}
							}
							if (violates_prev)
								if (violations.get(t-1) == maxsmooth) 
									continue;
							if (violates_this)
								if (violations.get(t) == maxsmooth) 
									continue;
							// we can add
							if(edgetimeaction.contains(j + "_"+ t + "_a" )) 
								continue;
							edgetimeaction.add(j + "_"+ t + "_a");
							score += tg.wsl[t+spp.s][j];
							sp.get(t).set(j);
							sp.get(t).set(tg.getReverseEdgeIndex(j));
							if (DEBUG) System.err.print("Adding " + j + " at time " + t + 
									" score " +tg.wsl[t][j]+ "\n");
							if (violates_prev) 
								violations.put(t-1, 1+violations.get(t-1));
							if (violates_this) 
								violations.put(t, 1+violations.get(t));
							changed = true;
						}
					}
				}
			}
		}
		return new SmoothPattern(tg, spp.s,spp.e, sp);
	}
	
	public static void main(String[] args) throws IOException{
//		String fn = "/home/petko/data/seine/15_traffic/preprocessed/100nodes.uniq";
//		HashMap<String,String> nnames = IO.readHashMap("/home/petko/data/seine/03_wikipedia/preprocessed/gregress/6934.nds.names.990.8");
		
		//testGrid();
		System.exit(0);
		
		String fn =  "/home/petko/data/seine/03_wikipedia/preprocessed/gregress/6934.graph.5000.8.ewpval.quadruples";
		HashMap<String,String> nnames = IO.readHashMap("/home/petko/data/seine/03_wikipedia/preprocessed/gregress/6934.nds.names.5000.8");
		
		
		
		float mu = 0.01F; 
		long st = System.currentTimeMillis();
		WeightedTimeGraph tg = IO.readTGraphQuadruplesPvalues(fn, mu);
		
//		System.out.print("Loading took:\t" + 
//				(System.currentTimeMillis()-st) + "ms\n");
//		float a = calcLowerBound(20, 10, tg);
//		System.err.print(a + "\n");	
	}

}
