package index;

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

import alg.BUp;

import misc.Common;
import misc.ExtToolsDriver;
import misc.IO;

import graph.Graph;
import graph.TimeGraph;
import generator.GraphGenerator;

public class PartitionIndex {
	
	TimeGraph tg;
	INode root;
	
	public PartitionIndex(TimeGraph _tg, boolean dummy) {
		tg = _tg;
		Random r = new Random();
		ArrayList<String> part = new ArrayList<String>();
		for (int i = 0; i < tg.getn(); i++) {
			if (r.nextBoolean()) part.add("1");
			else part.add("0");
		}
		populateIndexBySplit(part);
	}
	
	// One index on the whole aggregated interval
	// Just a two way partitioning
	public PartitionIndex(TimeGraph _tg) {
		// Create Index
		tg = _tg;
		assert (tg.isUndirected()):"TimeGraph is directed";
		tg.aggregateByTime(0, tg.gett()-1);
		// Lift
		for (int i = 0 ; i < tg.we.length; i++) {
			tg.we[i] += tg.gett();
		}
		// Partition
		ArrayList<String> NodePart = ExtToolsDriver.partitionGraph(tg, 2);
		
		populateIndexBySplit(NodePart);
	}
	
	public PartitionIndex(TimeGraph _tg, int levels) {
		// Create Index
		tg = _tg;
		assert (tg.isUndirected()):"TimeGraph is directed";
		tg.aggregateByTime(0, tg.gett()-1);
		// Lift
		for (int i = 0 ; i < tg.we.length; i++) {
			tg.we[i] += tg.gett();
		}
		// Partition
		ArrayList<String> NodePart = ExtToolsDriver.partitionGraph(tg, 2, levels);
		
		buildMultiLevelIndex(NodePart,levels);
	}
	
	private void populateIndexBySplit(ArrayList<String> NodePart) {
		// Collect sets of edgtes
		HashMap<String, HashSet<Integer>> sets = new HashMap<String,HashSet<Integer>>();
		sets.put("0" + Common.SEP + "1", new HashSet<Integer>());
		sets.put("0" + Common.SEP + "0", new HashSet<Integer>());
		sets.put("1" + Common.SEP + "1", new HashSet<Integer>());
		int n1, n2;
		String key;
		for (int e = 0; e < tg.getm(); e++) {
			n1 = tg.getOrigin(e);
			n2 = tg.endv[e];
			if(n1 > n2) continue; // pick only one direction of the undirected edges
			key = (NodePart.get(n1).compareTo(NodePart.get(n2)) < 0)
				?NodePart.get(n1) + Common.SEP + NodePart.get(n2)
				:NodePart.get(n2) + Common.SEP + NodePart.get(n1);	
			assert(sets.containsKey(key));
			sets.get(key).add(e);
		}
		// Create Index
		INode l = null, r = null;
		if(!sets.get("0" + Common.SEP + "0").isEmpty()) {
			l = new INode(sets.get("0" + Common.SEP + "0"));
		}
		if(!sets.get("1" + Common.SEP + "1").isEmpty()) {
			r = new INode(sets.get("1" + Common.SEP + "1"));
		}
		root = new INode(sets.get("0" + Common.SEP + "1"),l,r);
	}
	
	private void buildMultiLevelIndex(ArrayList<String> NodePart, int levels) {
		// collect cluster paths
		TreeMap<String,INode> index_nodes = new TreeMap<String, INode>();
		TreeMap<String, HashSet<Integer>> sets = new TreeMap<String,HashSet<Integer>>();
		for (int i =0; i < NodePart.size(); i++) {
			assert(NodePart.get(i).split(Common.SEP).length == levels+1);
			if(!index_nodes.containsKey(NodePart.get(i))){
				String k = NodePart.get(i).split(Common.SEP)[0];
				if(!index_nodes.containsKey(k)) {
					index_nodes.put(k, null);
					sets.put(k, new HashSet<Integer>());
				}
				for(int j = 1; j <= levels; j++ ){
					k += Common.SEP + NodePart.get(i).split(Common.SEP)[j];
					if(!index_nodes.containsKey(k))  {
						index_nodes.put(k, null);
						sets.put(k, new HashSet<Integer>());
					}
				}
			}
		}
		
		int n1, n2;
		String key;
		// add a global set added 
		HashSet<Integer> added = new HashSet<Integer>();
		for (int l = levels; l >= 0; l--) {
			for (String k:sets.keySet()) {
				if (k.split(Common.SEP).length != l+1) continue;
				for (int e = 0; e < tg.getm(); e++) {
					n1 = tg.getOrigin(e);
					n2 = tg.endv[e];
					if (n1 > n2) continue;
					if(NodePart.get(n1).startsWith(k) && 
					   NodePart.get(n2).startsWith(k) && 
					   (!added.contains(e))) {
						sets.get(k).add(e);
						added.add(e);
					}
				}
				index_nodes.put(k, new INode(sets.get(k)));
				if (levels == l) {
					index_nodes.get(k).L = null;
					index_nodes.get(k).R = null;
				} else {
					if(null!=index_nodes.get(k + Common.SEP + "0"))
						index_nodes.get(k).L = index_nodes.get(k + Common.SEP + "0");
					if(null!=index_nodes.get(k + Common.SEP + "1"));
						index_nodes.get(k).R = index_nodes.get(k + Common.SEP + "1");
				}
			}
		}
		root = index_nodes.get("0");
	}
	
	// 2. multi-level index
	// 3. Sampling index
	// 4. multi-way split and solve high granularity MST
	// 5. Precompute windows overlay. Hierarchy on intervals -> exact UB[l,r] = exact of the intersecting precomputed parts
	
	
	public double UB(int from, int to) {
		return -1;
		//return root.UB(tg.aggregateEdgeWeights(from, to));
	}
	
	public static void main(String[] args) {			
		long start, end;
		int n = 400, m = 300, t = 100;
		double Pn = 0.005, 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);
		
		PartitionIndex ind_l2 = new PartitionIndex(tg,1);
		PartitionIndex ind_l3 = new PartitionIndex(tg,4);
		PartitionIndex ind_rand = new PartitionIndex(tg,false);
		BUp solver;
		double ub2, ub3,actual, ubstar;
		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.computeOptimalLMSM();
				actual = solver.getBestClusterGraph().getScore();
				end = System.currentTimeMillis();
				tac = end - start;
				// ub
				start = System.currentTimeMillis();
				ub2 = ind_l2.UB(i, j);
				ub3 = ind_l3.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" + (ub2 -actual) + "\t" + (ub3 -actual) + ((ub3<ub2)?"*":"") +"\t" + ubstar + "\t" + tac + "\t" + tub + "\n");
				//System.out.print("[" +i+ "," + j + "]:\t" + ((actual*1.0)/(ub*1.0)*100)  + "\t" + ((actual*1.0)/(ub_rand*1.0)*100)  + "\t" + tac + "\t" + tub + "\n");
			}
		}
		
	}
}
