package index;

import graph.ITimeGraph;
import graph.TimeGraph;
import graph.WeightedTimeGraph;

import java.util.ArrayList;
import java.util.Arrays;

import misc.Common;

public class IntervalIndexExactCeiling {
	// aggregate vectors
	private ArrayList<double[][]> pvs;
	// ceiling vectors
	private ArrayList<double[][]> cvs;
	private ArrayList<IntervalTreeNodeExactCeiling> topnodes;
	private int size;
	
	// computes tlogt vectors : t of size 1, t/2 of size 2 ...
	public IntervalIndexExactCeiling(ITimeGraph tg, int s,int e) {
		size =  e-s+1;
		// compute tlogt vectors
		pvs = new ArrayList<double[][]>();
		cvs = new ArrayList<double[][]>();
		topnodes = new ArrayList<IntervalTreeNodeExactCeiling>();
		
		ArrayList<IntervalTreeNodeExactCeiling> nodes = new ArrayList<IntervalTreeNodeExactCeiling>();
		ArrayList<IntervalTreeNodeExactCeiling> prevnodes = new ArrayList<IntervalTreeNodeExactCeiling>();
		for (int pow = 0; Math.pow(2, pow) <= size; pow++) {
			int len = (int)Math.pow(2, pow);
			double[][] ps = new double[size/len + ((size%len > 0)?1:0)][tg.getm()];
			double[][] cs = new double[size/len + ((size%len > 0)?1:0)][tg.getm()];
			for (int pos = 0; pos + len  <= size; pos += len) {
				if (len == 1) {
					tg.aggregateByTime(s+pos, s+pos+len-1,ps[pos/len]);
					cs[pos/len] = Arrays.copyOf(ps[pos/len], ps[pos/len].length);
					nodes.add(new IntervalTreeNodeExactCeiling(pos, pos+len-1,ps[pos/len],ps[pos/len]));
				}
				else {
					// aggregate the agg vectors of constituents
					Common.sum(pvs.get(pow-1)[pos/(int)Math.pow(2, pow-1)], 
							 pvs.get(pow-1)[pos/(int)Math.pow(2, pow-1) + 1],
							 ps[pos/len]);
					// c = v_left + c_right 
					Common.sum(pvs.get(pow-1)[pos/(int)Math.pow(2, pow-1)],
							cvs.get(pow-1)[pos/(int)Math.pow(2, pow-1) + 1],
							cs[pos/len]);
					// c = ceil(v_left + c_right, c_left)
					Common.max(cs[pos/len],cvs.get(pow -1)[pos/(int)Math.pow(2, pow-1)],cs[pos/len]);
					nodes.add(new IntervalTreeNodeExactCeiling(pos, pos+len-1, ps[pos/len], cs[pos/len]));
					nodes.get(nodes.size()-1).L = prevnodes.get(pos/(int)Math.pow(2, pow-1));
					nodes.get(nodes.size()-1).R = prevnodes.get(pos/(int)Math.pow(2, pow-1) + 1);
				}
			}
			if( (prevnodes.size()%2) > 0) 
				topnodes.add(0, prevnodes.get(prevnodes.size()-1));
			prevnodes.clear();
			prevnodes.addAll(nodes);
			nodes.clear();
			pvs.add(ps);
			cvs.add(cs);
		}
		topnodes.add(0,prevnodes.get(0));
	}
	
	public void getCeiling(int start_fixed, int end_fixed, int end, double[] v) {
		assert (start_fixed >= 0 && start_fixed <= end_fixed && end_fixed <= end && end < size);
		double[] vec = new double[v.length];
		double[] ceil = new double[v.length];
		aggregate(start_fixed,end_fixed,vec);
		ceilingLeft(end_fixed+1, end, ceil);
		Common.sum(vec,ceil,v);
	}
	
	public void getAggregate(int s, int e, double[] v) {
		assert (s >= 0 && s <= e && e < size):
			"Start = " + s + " End = " + e + "\n";
		Arrays.fill(v, 0);
		aggregate(s,e,v);
	}

	private void aggregate(int s, int e, double[] v) {
		//System.err.print("***********************\nQuery [" + s + "," + e + "]\n");
		if (s > e || s < 0 || e < 0) return;
		for (IntervalTreeNodeExactCeiling n: topnodes ) {
			n.aggregate(s,e,v);
		}
	}
	private void ceilingLeft(int s, int e, double[] c) {
		//System.err.print("***********************\nQuery [" + s + "," + e + "]\n");
		if (s > e || s < 0 || e < 0) return;
		double[] v = new double[c.length];
		for (IntervalTreeNodeExactCeiling n: topnodes ) {
			n.ceilingLeft(s,e,v,c);
		}
	}
}
