package index;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.TreeMap;

import alg.BUp;
import alg.SAClusterer;

import misc.Common;
import misc.ExtToolsDriver;
import generator.GraphGenerator;
import graph.Graph;
import graph.TimeGraph;

public class CoarsenIndex {
	TimeGraph tg;
	// there is a bucket for every size
	// in each bucket the entries are ordered by origin
	TreeMap<Integer,TreeMap<Integer,CoarseIndexEntry>> index = 
		new TreeMap<Integer,TreeMap<Integer,CoarseIndexEntry>>();
	int nparts;
	
	
	
	// partitioning in every window of size 2,4,8,16..... O(nlogn)
	public CoarsenIndex(TimeGraph _tg, int _nparts, int smallest_size, boolean signedPartion) {
		tg = _tg;
		nparts = _nparts;
		Graph g = null;
		CoarseIndexEntry entry = null;
		assert(smallest_size>=0) : "Requested interval too coarse";
		int size = 0, pow = smallest_size;
		while (Math.pow(2,pow) < tg.gett()) {
			size = (int)Math.pow(2,pow);
			index.put(size, new TreeMap<Integer, CoarseIndexEntry>());
			for (int i = 0; i < tg.gett()-size; i++) {
				entry = createEntry(signedPartion, i, i+size-1);
				index.get(size).put(entry.s, entry);
			}
			// increase the size
			pow++;
		}
		entry = createEntry(signedPartion, 0, tg.gett()-1);
		index.put(tg.gett(), new TreeMap<Integer,CoarseIndexEntry>());
		index.get(tg.gett()).put(entry.s,entry);
	}

	private CoarseIndexEntry createEntry(boolean signedPartion, int from, int to) {
		Graph g;
		CoarseIndexEntry entry;
		if (!signedPartion) {
			makePartitionableGraph(from,to);
			entry = new CoarseIndexEntry(from,to);
			entry.partition = ExtToolsDriver.partitionHyperGraph(tg, nparts);
			computeJoints(entry);
		} else {
			 tg.aggregateByTime(from,to);
			 entry = new CoarseIndexEntry(from,to);
			 entry.partition = new HashMap<Integer, Integer>();
			 entry.joints = new HashMap<String, String>();
			 int[] node_partitions = (new SAClusterer(tg, nparts)).cluster();
			 for (int j=0; j < tg.getn(); j++) {
				 for (int e=tg.ind[j]; e < tg.ind[j+1]; e++) {
					 // even if the edge is across clusters it does not matter
					 // which partition we will add it to for the UB
					 entry.partition.put(e, node_partitions[j]);
					 if(node_partitions[tg.endv[e]] != node_partitions[j]) {
						 entry.joints.put(""+e, Math.min(node_partitions[tg.endv[e]],node_partitions[j]) + 
								   Common.SEP + Math.max(node_partitions[tg.endv[e]],node_partitions[j]));
					 }
				 }
			 }
		}
		return entry;
	}
	
	// original partitioning considering the whole timespan
	public CoarsenIndex(TimeGraph _tg, int _nparts) {
		tg = _tg;
		nparts = _nparts;
		makePartitionableGraph(0, tg.gett()-1);
		CoarseIndexEntry entry = new CoarseIndexEntry(0, tg.gett()-1);
		entry.partition = ExtToolsDriver.partitionHyperGraph(tg, nparts);
		computeJoints(entry);
		index.put(tg.gett(), new TreeMap<Integer,CoarseIndexEntry>());
		index.get(tg.gett()).put(entry.s,entry);
	}
	
	// Random partitioning
	public CoarsenIndex(TimeGraph _tg, int _nparts, boolean random) {
		tg = _tg;
		nparts = _nparts;
		
		// Random partition
		Random r = new Random();
		CoarseIndexEntry entry = new CoarseIndexEntry(0, tg.gett()-1);
		entry.partition = new HashMap<Integer, Integer>();
		for (int i = 0; i < tg.getm(); i++) {
			if (tg.getOrigin(i) > tg.endv[i]) continue;
			int part = r.nextInt(nparts); 
			entry.partition.put(i, part);
			entry.partition.put(tg.getReverseEdgeIndex(i), part);
		}
		computeJoints(entry);
		index.put(tg.gett(), new TreeMap<Integer,CoarseIndexEntry>());
		index.get(tg.gett()).put(entry.s,entry);
	}

	private void computeJoints(CoarseIndexEntry entry) {
		entry.joints = new HashMap<String, String>();
		
		// compute joints
		HashSet<String> edges = new HashSet<String>();
		int e1, e2;
		for (int i=0; i < tg.getn(); i++) {
			for (int j = tg.ind[i]; j < tg.ind[i+1]; j++) {
				if (null == entry.partition.get(j)) e1 = tg.getReverseEdgeIndex(j);
				else e1 = j;
				for (int jj = j+1; jj < tg.ind[i+1]; jj++) {
					if (null == entry.partition.get(jj)) e2 = tg.getReverseEdgeIndex(jj);
					else e2 = jj;
					if(entry.partition.get(e1) != entry.partition.get(e2)){
						entry.joints.put(e1 + Common.SEP + e2, 
								   Math.min(entry.partition.get(e1),entry.partition.get(e2)) + 
								   Common.SEP + Math.max(entry.partition.get(e1),entry.partition.get(e2)));
						edges.add(entry.partition.get(e1) + Common.SEP + entry.partition.get(e2));
						edges.add(entry.partition.get(e2) + Common.SEP + entry.partition.get(e1));
					} 
				}
			}
		}
		
		// now compute a graph structure for the entry to reuse
		
		// nodes will be twice the number of partitions to add the additional "dummy" cluster edges
		String[] nodes = new String[nparts*2];
		for(int i=0; i < nparts; i++) {
			nodes[2*i] = "" + i;
			nodes[2*i+1] = "_" + i; // dummy this is the guy for the dummy edge
			edges.add("" + i + Common.SEP + "_" + i);
			edges.add("_" + i + Common.SEP + "" + i);
		}
		
		String[] edges_sequence = new String[edges.size()*2];
		int i=0;
		for (String s: edges) {
			edges_sequence[i++] = s.split(Common.SEP)[0];
			edges_sequence[i++] = s.split(Common.SEP)[1];
		}
		entry.g = new Graph(edges_sequence, nodes);
	}
	
	private void makePartitionableGraph(int s, int e) {
		tg.aggregateByTime(s, e);
		// Lift
		for (int j = 0 ; j < tg.we.length; j++) {
			tg.we[j] += e-s+1;
		}
	}
	
	// bounding
	public double UB(int from, int to) {
		assert(from >= 0 && to >= from && tg.gett() > to):"Bad interval:" + from + "-" + to ;
		double[] ew = new double[tg.getm()]; 
		tg.aggregateEdgeWeights(from, to,ew);
		int e1, e2;
		HashMap<String,Double> edges = new HashMap<String, Double>();
		
		// select an entry
		CoarseIndexEntry entry = selectBestInterval(from, to);
		
		for (String s: entry.joints.keySet()) {
			if (s.contains(Common.SEP)) {
				e1 = Integer.parseInt(s.split(Common.SEP)[0]);
				e2 = Integer.parseInt(s.split(Common.SEP)[1]);
				if (!edges.containsKey(entry.joints.get(s))) edges.put(entry.joints.get(s), Math.min(0, ew[e1] + ew[e2]));
				else if (Math.min(0, ew[e1] + ew[e2]) > edges.get(entry.joints.get(s)) ) {
					edges.put(entry.joints.get(s), Math.min(0, ew[e1] + ew[e2]));
				}
			} else {
				e1 = Integer.parseInt(s);
				if (!edges.containsKey(entry.joints.get(s))) edges.put(entry.joints.get(s), Math.min(0, ew[e1]));
				else if (Math.min(0, ew[e1]) > edges.get(entry.joints.get(s)) ) {
					edges.put(entry.joints.get(s), Math.min(0, ew[e1]));
				}
			}
		}
		Graph g = new Graph(nparts, edges.size()*2);
		
		Arrays.fill(g.wn, 0);
		for (int i:entry.partition.keySet()) {
			if (ew[i] > 0) g.wn[entry.partition.get(i)] += ew[i];
		}
		for (int i = 0; i < g.getn(); i++) g.names[i] = "" + i;
		
		
		int p1, p2;
		int eidx = 0;
		g.ind[0]=0;
		for (int i = 0; i < g.getn(); i++){
			g.ind[i+1] = g.ind[i];
			for (String e: edges.keySet()) {
				p1 = Integer.parseInt(e.split(Common.SEP)[0]);
				p2 = Integer.parseInt(e.split(Common.SEP)[1]);
				if (p1 == i) {
					g.ind[i+1]++;
					g.endv[eidx] = p2;
					g.we[eidx] = edges.get(e);
					if (g.we[eidx] < 0) g.we[eidx] *= -1;
					eidx++;
				} else if (p2 == i) {
					g.ind[i+1]++;
					g.endv[eidx] = p1;
					g.we[eidx] = edges.get(e);
					if (g.we[eidx] < 0) g.we[eidx] *= -1;
					eidx++;
				}
			}
		}
		
		// now build the graph
		BUp b = new BUp(g);
		b.computeOptimalLMSM();
		return b.getBestClusterGraph().getScore();
	}
	
	public double UB_inside(int from, int to, TimeGraph _tg) {
		int e1, e2;
		HashMap<String,Double> edges = new HashMap<String, Double>();
		
		// select an entry
		CoarseIndexEntry entry = selectBestInterval(from, to);
		for (int i=0; i < _tg.getm(); i++) assert(_tg.we[i]==tg.we[i]);
		Arrays.fill(entry.g.we,0);
		
		for (String s: entry.joints.keySet()) {
			if (s.contains(Common.SEP)) {
				e1 = Integer.parseInt(s.split(Common.SEP)[0]);
				e2 = Integer.parseInt(s.split(Common.SEP)[1]);
				if (!edges.containsKey(entry.joints.get(s))) edges.put(entry.joints.get(s), Math.min(0, _tg.we[e1] + _tg.we[e2]));
				else if (Math.min(0, _tg.we[e1] + _tg.we[e2]) > edges.get(entry.joints.get(s)) ) {
					edges.put(entry.joints.get(s), Math.min(0, _tg.we[e1] + _tg.we[e2]));
				}
			} else {
				e1 = Integer.parseInt(s);
				if (!edges.containsKey(entry.joints.get(s))) edges.put(entry.joints.get(s), Math.min(0, _tg.we[e1]));
				else if (Math.min(0, _tg.we[e1]) > edges.get(entry.joints.get(s)) ) {
					edges.put(entry.joints.get(s), Math.min(0,_tg.we[e1]));
				}
			}
		}
		
		Graph gp;
		int v1, v2;
		for (int i:entry.getPartSets(_tg).keySet()) {
			gp = _tg.subgraph(entry.getPartSets(_tg).get(i));
			v1 = entry.g.getNodeIndex("" + i);
			v2 = entry.g.getNodeIndex("_" + i);
			entry.g.we[entry.g.getEdgeIndex(v1, v2)] = IntervalBounds.getUB(gp);
			entry.g.we[entry.g.getEdgeIndex(v2, v1)] = entry.g.we[entry.g.getEdgeIndex(v1, v2)];
		}

		for (String e: edges.keySet()) {
			v1 = entry.g.getNodeIndex(e.split(Common.SEP)[0]);
			v2 = entry.g.getNodeIndex(e.split(Common.SEP)[1]);
			entry.g.we[entry.g.getEdgeIndex(v1, v2)] = edges.get(e);
			entry.g.we[entry.g.getEdgeIndex(v2, v1)] = edges.get(e);
		}
//		for (int i=0; i < g.we.length; i++) g.we[i] *= -1;
		return IntervalBounds.getUB(entry.g);
		
		// now build the graph
//		BUp b = new BUp(g);
//		b.computeOptimalLMSM();
//		return b.getBestClusterScore();
	}
	
	private CoarseIndexEntry selectBestInterval(int from, int to) {
		// figure out the size
		Integer s = index.ceilingKey(to-from+1);
		assert (s!=null);
		return index.get(s).get(index.get(s).floorKey(from));
	}

	@Override
	public String toString() {
		return toString(0,tg.gett()-1);
	}
	
	public String toString(int from, int to) {
		CoarseIndexEntry entry = selectBestInterval(from, to);
		String res = "Partitions: " + nparts + "\n";
		for (int i = 0; i < nparts; i++) {
			res += i + "{";
			for (int j: entry.partition.keySet()) {
				if (entry.partition.get(j) == i) {
					res += tg.names[tg.getOrigin(j)] + "-" + tg.names[tg.endv[j]] + ",";
				}
			}
			res += "}\n";
		}
		String tmp;
		res += "Connections: \n";
		for (int i = 0; i < nparts; i++) {
			for (int j = i+1; j < nparts; j++) {
				tmp = i + " " + j + "{\n";
				for (String s:entry.joints.keySet()) {
					if (entry.joints.get(s).equals(i + Common.SEP + j)) {
						tmp += tg.names[tg.getOrigin(Integer.parseInt(s.split(Common.SEP)[0]))] + "-" +
						                tg.names[tg.endv[Integer.parseInt(s.split(Common.SEP)[0])]] + " --- " +
						                tg.getOrigin(Integer.parseInt(s.split(Common.SEP)[1])) + "-" +
						                tg.names[tg.endv[Integer.parseInt(s.split(Common.SEP)[1])]] + "\n";
					}
				}
				tmp += "}\n";
				if(tmp.equals(i + " " + j + "{\n" + "}\n")) continue;
				else res += tmp;
			}
		}
		return res;
	}

	public static void main(String[] args) {	
		System.out.print("");
		
		long start, end;
		int n = 100, m = 300, t = 100;
		double Pn = 0.05, Pp = 0.05, Ps = 0.001; // settings
		Graph gbase = GraphGenerator.getTestGraphWithStarFurtherMerge();
		//Graph gbase = GraphGenerator.generateScaleFree(n);
		//Graph gbase = GraphGenerator.generateRandom(n,(int)(1.2*n));
		TimeGraph tg = GraphGenerator.generateTimeGraphLocalized(t, Pn, Pp, Ps, gbase);
		
		Arrays.fill(tg.wn, 0);
		CoarsenIndex citest = new CoarsenIndex(tg, 4);
		
		double a = citest.UB_inside(0, 4,tg);
		
		
		PartitionIndex pi = new PartitionIndex(tg,1);
		CoarsenIndex ci2 = new CoarsenIndex(tg, 2);
		CoarsenIndex ci4 = new CoarsenIndex(tg, 4);
		CoarsenIndex ci8 = new CoarsenIndex(tg, 8);
		CoarsenIndex ci16 = new CoarsenIndex(tg, 16);
		CoarsenIndex ci32 = new CoarsenIndex(tg, 32);
		CoarsenIndex ci64 = new CoarsenIndex(tg, 64);
		CoarsenIndex ci128 = new CoarsenIndex(tg, 128);
		CoarsenIndex ci64r = new CoarsenIndex(tg, 64,true);
		
		BUp solver;
		double ubp, ubc2, ubc4, ubc8, ubc16, ubc32, ubc64, ubc128, actual, ubstar, ubc64r;
		long tub, tac;
		for (int i=0; i < t; i++) {
			for (int j=i; j < t; j++ ) {
				// solve
				start = System.currentTimeMillis();
				tg.aggregateByTime(i, j);
				solver = new BUp(tg.getAggNodeWeighted());
				//solver.computeOptimalLookAheadGrow();
				solver.computeOptimalLM();
				actual = solver.getBestClusterGraph().getScore();
				end = System.currentTimeMillis();
				tac = end - start;
				// ub
				start = System.currentTimeMillis();
				ubp = pi.UB(i, j);
				ubc2 = ci2.UB(i, j);
				ubc4 = ci4.UB(i, j);
				ubc8 = ci8.UB(i, j);
				ubc16 = ci16.UB(i, j);
				ubc32 = ci32.UB(i, j);
				ubc64 = ci64.UB(i, j);
				ubc128 = ci128.UB(i, j);
				ubc64r = ci64r.UB(i, j);
				ubstar = 0;
				for (int z=0; z < tg.getm(); z++) {
					if(tg.getOrigin(z) < tg.endv[z] && tg.we[z] > 0)
						ubstar += tg.we[z];
				}
				end = System.currentTimeMillis();
				tub = end - start;
				if (actual == 0) continue;
				//System.out.print("[" +i+ "," + j + "]:\t" + actual + "\t"+ ubp + "\t"+ ubc2 + "\t" + ubstar + "\t" + tac + "\t" + tub + "\n");
				System.out.print("[" +i+ "," + j + "]:\t" + actual + "\t"+ 
									Common.perc(actual,ubstar) + "\t"+
									Common.perc(actual,ubp) + "\t|\t"+
									Common.perc(actual,ubc2) + "\t"+
									Common.perc(actual,ubc4) + "\t"+
									Common.perc(actual,ubc4) + "\t"+
									Common.perc(actual,ubc16) + "\t"+
									Common.perc(actual,ubc32) + "\t"+
									Common.perc(actual,ubc64) + "\t"+
									Common.perc(actual,ubc128) +
									"\t|\t"+
									Common.perc(actual,ubc64r) + "\t| \t"+
									
									tac + "\t" + tub + "\n");
				
				
			}
		}
	}
}
