package misc;
import index.IntervalBounds;
import index.IntervalIndexExactCeiling;

import java.util.Arrays;
import java.util.TreeSet;

import flanagan.interpolation.*;
import generator.DynamicModel;
import generator.GraphGenerator;
import graph.Graph;
import graph.TimeGraph;
public class SplineInterpolation {
	private BiCubicSplineFast bcs;
	public double[][] m;
	// takes a matrix similar to our lower/ upper bounds and interpolates it
	public SplineInterpolation(double[][] _m) {
		m = _m;
		int cnt=0;
		for (int i = 0 ; i < m.length; i ++) if (m[i][0] != Double.NEGATIVE_INFINITY) cnt++;
		double[] sz = new double[cnt];
		double[] pos = new double[m.length];
		int indx = 0;
		for (int i = 0 ; i < m.length; i ++) {
			if (m[i][0] != Double.NEGATIVE_INFINITY) {
				sz[indx++] = i; 
			}
			pos[i] = i;
		}
		
		double[][] data = new double[sz.length][pos.length];
		Double neginf = Double.NEGATIVE_INFINITY;
		for(int i=0;i<data.length; i++) Arrays.fill(data[i], Double.NEGATIVE_INFINITY);
		for (int s = 0; s < sz.length; s++) {
			for (int p = 0; p < pos.length - sz[s]; p++ ) {
				data[s][p+(int)(((int)sz[s])/2)] = m[(int)sz[s]][(int)pos[p]]; 
			}
			for(int p=0; p < pos.length; p++) {
				if (p < (int)(((int)sz[s])/2) && neginf.equals(data[s][p])) {
					data[s][p] = m[(int)sz[s]][0];
				} else if (neginf.equals(data[s][p])) {
					data[s][p] =  m[(int)sz[s]][m.length-(int)sz[s]-1];
				}
			}
		}
		
//		for (int i=0; i < data.length; i++) {
//			for(int j = 0; j < data[i].length; j++) {
//				System.err.print(data[i][j] + " ");
//			}
//			System.err.print("\n");
//		}
		
		// Create an instance of BiCubicSpline
	    bcs = new BiCubicSplineFast(sz, pos, data);
	}
	
	public void getInterpolatedNeighborsGreaterThan(ComparableInterval ci, TreeSet<ComparableInterval> topk,
			TreeSet<ComparableInterval> newtopk) {
		double v = 0;
		if(topk.size() == 1) {
			newtopk.clear();
			newtopk.add(topk.first());
			return;
		}
		int k = topk.size();
		if (ci.size > 0) {
			if (m[ci.size-1][0] < 0) { // add neighbors only if they need interpolation
				int sz = ci.size-1;
				for(int pos=Math.max(0, ci.pos-1);pos < Math.min(m.length-sz,ci.pos + 2); pos++) {
					boolean intopk = false;
					for (ComparableInterval cii: topk){
						if(cii.sameInterval(sz, pos)){
							intopk = true;
							break;
						}
					}
					if (intopk) continue;
					v = interpolate(sz, pos);
					if (v - topk.first().val <= 0.1) continue;
					if(newtopk.size() < k || v > newtopk.first().val) {
						ComparableInterval intvl = new ComparableInterval(pos,sz,v);
						newtopk.add(intvl);
						if (newtopk.size()>k) newtopk.remove(newtopk.first());
					}
				}
			}
		}
		if (ci.size < m.length-1) {
			if (m[ci.size+1][0] < 0) { // add neighbors only if they need interpolation
				int sz = ci.size+1;
				for(int pos=Math.max(0, ci.pos-1);pos < Math.min(m.length-sz,ci.pos + 1); pos++) {
					boolean intopk = false;
					for (ComparableInterval cii: topk){
						if(cii.sameInterval(sz, pos)){
							intopk = true;
							break;
						}
					}
					if (intopk) continue;
					v = interpolate(sz, pos);
					if (v - topk.first().val <= 0.1) continue;
					if(newtopk.size() < k || v > newtopk.first().val) {
						ComparableInterval intvl = new ComparableInterval(pos,sz,v);
						newtopk.add(intvl);
						if (newtopk.size()>k) newtopk.remove(newtopk.first());
					}
				}
			}
		}
		
	}
	
	
	public double interpolate(int sz, int pos) {
		if (m[sz][pos] == Double.NEGATIVE_INFINITY)
			return bcs.interpolate(sz,pos+sz/2);
		else
			return m[sz][pos];
	}
	
	public void checkInterpolation(double[][] mp) {
	    for (int s=0; s < mp.length; s++) {
			for (int p = 0; p  < mp.length - s; p++) {
				mp[s][p] = interpolate(s,p);
			}
		}
	}
	
	public static void main(String[] args) {
		Graph g =  GraphGenerator.generateRandom(500, 1500);
		DynamicModel dm = new DynamicModel();
		dm.PNeighbor = 0.4;
		dm.PNextGivenCurrent = 0.92;
		dm.POne = 0.05;
		int[] times = {40,50,100,200,500,1000};
		double[] alphas = {0.5,0.6,0.7,0.8,0.9};
		for (int j=0 ; j < times.length; j++) {
			int time = times[j];
			TimeGraph tg = GraphGenerator.generateTimeRWSampling(time, dm, g);
			
			for (int alphi = 0; alphi < alphas.length; alphi++) {
				// NAIVE
				double[][] posit = new double[time][time];
				double[][] posit_coarse = new double[time][time];
				double[][] posit_ube = new double[time][time];
				for(int i=0; i < posit.length; i++) {
					Arrays.fill(posit[i], Double.NEGATIVE_INFINITY);
					Arrays.fill(posit_coarse[i], Double.NEGATIVE_INFINITY);
					Arrays.fill(posit_ube[i], Double.NEGATIVE_INFINITY);
				}
				IntervalBounds.sumPositive(tg,0,time-1,posit);
				IntervalIndexExactCeiling ind = new IntervalIndexExactCeiling(tg, 0, time-1);
				IntervalBounds.coarse(tg,0,time-1,alphas[alphi],ind, posit_ube, posit_coarse);
				
				SplineInterpolation si = new SplineInterpolation(posit_coarse);
				si.checkInterpolation(posit_coarse);
				
//				ExtToolsDriver.plotMatrix(posit, 1, 0, posit.length);
//				ExtToolsDriver.plotMatrix(posit_coarse, 1, 0, posit_coarse.length);
				
				
				for (int k = 20; k < 30; k+=10 ) {
					long start = System.currentTimeMillis();
					TreeSet<ComparableInterval> tkact = IntervalBounds.getTopKIntervals(posit, k);
					long tact = System.currentTimeMillis() - start;
					
					start = System.currentTimeMillis();
					TreeSet<ComparableInterval> tkapx = IntervalBounds.getTopKIntervals(posit_coarse, k);
					long tapx = System.currentTimeMillis() - start;
					
					int cnt = 0;
					for(ComparableInterval ci: tkact) {
						for(ComparableInterval cci: tkapx) {
							if (ci.pos == cci.pos && ci.size == cci.size) {
								cnt++;
								break;
							}
						}
					}
					System.err.print("TIME: " + time + "\n");
					System.err.print("Time: alpha" + alphas[alphi] + " :" + tapx + "\tact:" + tact + "\n");
					System.err.print("Accuracy " + k + " :" + (1.0*cnt / k)  + "\n");
				}
				
				ExtToolsDriver.kill("gnuplot");
			}
		}
		
	}

	
}
