package gsearch;

import java.util.BitSet;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeSet;

import misc.ComparableIndexedValue;
import misc.ComparableLabeledValue;
import misc.Visualizer;
import graph.CompositeGraph;
import graph.Graph;

public class Sparsifier {
	
	public enum Functions {EXP,FRAC};
	public static Functions FUNC_K = Functions.FRAC; 
	
	/* orders edges based on weighted 
	 * Jaccard coefficient of neighbors selects top k %
	 */
	public static BitSet sparsifyJCGlobal(double pc, Graph g) {
		TreeSet<ComparableIndexedValue> edges = new TreeSet<ComparableIndexedValue>(Collections.reverseOrder());
		for (int n=0; n<g.getn(); n++) {
			for (int e = g.ind[n]; e < g.ind[n+1]; e++) {
				if (n < g.endv[e]) {
					edges.add(new ComparableIndexedValue(e,wjs(e,g)));
				}
			}
		}
		BitSet retained = new BitSet(g.getm());
		for(ComparableIndexedValue ed: edges) {
			if (retained.cardinality()*1.0/g.getm() > pc) break;
			retained.set(ed.ind);
			retained.set(g.getReverseEdgeIndex(ed.ind));
		}
		return retained;
	}

	public static BitSet sparsifyJCLocal(double pc, Graph g) {	
		BitSet retg = null;
		// first search for eps
		int error = (int) Math.round((1-pc)*g.getm());
		double imax = 1.0, imin = 0.0;
		// fix
		int cnt = 0;
		do {
//			System.err.print("[" + imin + " - "  + imax  + "" + "\t");
			retg = sparsifyJCLocalEps(imin + (imax - imin)/2.0, g);
			if (retg.cardinality() > pc*g.getm()) imax = imin + (imax - imin)/2.0;
			else imin = imin + (imax - imin)/2.0;
			error = (int) Math.round(retg.cardinality() - pc*g.getm());
//			System.err.print(retg.cardinality()*1.0/g.getm() + "\t" +retg.cardinality() +  "\n");
			cnt++;
		} while (Math.abs(error) > 50 && cnt < 30);
		return retg;
	}
	
	/* Orders edges adjacent to nodes i 
	 * based on weighted Jaccard coefficient of neighbors 
	 * selects top d_i^{eps} edges (eps is a local sparsification param)
	 */
	public static BitSet sparsifyJCLocalEps(double eps, Graph g) {	
		
		TreeSet<ComparableIndexedValue> edges;
		HashSet<Integer> keep = new HashSet<Integer>();
		for (int n=0; n<g.getn(); n++) {
			edges = new TreeSet<ComparableIndexedValue>(Collections.reverseOrder());
			for (int e = g.ind[n]; e < g.ind[n+1]; e++) {
				edges.add(new ComparableIndexedValue(e,wjs(e,g)));
			}
			int cnt = 0;
			for(ComparableIndexedValue ed: edges) {
				if (cnt+1 >= ((Double)((Math.pow((g.ind(n+1)-g.ind(n)) , eps)))).intValue()) 
					break;
				keep.add(ed.ind);
				keep.add(g.getReverseEdgeIndex(ed.ind));
				cnt++;
			}
		}
		
		BitSet retained = new BitSet(g.getm());
		for (Integer ed: keep) retained.set(ed);
		
		return retained;
	}
	
	private static Double wjs(int e, Graph g) {
		int n1 = g.getOrigin(e);
		int n2 = g.endv(e);
		
		double inters = 0.0;
		HashSet<Integer> common = new HashSet<Integer>();
		for (int j= g.ind(n1); j < g.ind(n1+1); j++) {
			for (int jj = g.ind(n2); jj < g.ind(n2+1); jj++) {
				if (g.endv(j)==g.endv(jj)) {
					common.add(g.endv(j));
					inters += Math.max(g.we(j), g.we(jj));
				}
			}
		}
		
		double union = inters;
		for (int j= g.ind(n1); j < g.ind(n1+1); j++) {
			if (g.endv(j) != n2 && !common.contains(g.endv(j))) {
				union += g.we(j); 
			}
		}
		for (int j= g.ind(n2); j < g.ind(n2+1); j++) {
			if (g.endv(j) != n1 && !common.contains(g.endv(j))) {
				union += g.we(j); 
			}
		}
		
		return g.we(e)*inters/union;
	}

	static public BitSet sparsifyEItopK(double pc, Graph g, int k, double r) {
		TopK qp = new TopK(new CompositeGraph(g));
		double[] edgcnt = new double[g.getm()]; 
		
		HashMap<Integer,Double> ns = new HashMap<Integer, Double>();
		for (int j=0; j < g.getn(); j++) {
			ns.clear();
			ns.put(j, 1.0);
			ComparableLabeledValue[] tm = qp.getActualEI(ns, r, null);
			HashSet<Integer> nodes = new HashSet<Integer>();
			for (int i = 0; i < k; i++) nodes.add(g.getNodeIndex(tm[i].l)); 
			HashSet<Integer> edg = g.getEdgesAmong(nodes);
//			Visualizer.visualize(g, edg);
			for (Integer e: edg) edgcnt[e]++;
		}
		
		TreeSet<ComparableIndexedValue> edges = new TreeSet<ComparableIndexedValue>(Collections.reverseOrder());
		for (int i = 0; i < edgcnt.length; i++) {
			edges.add(new ComparableIndexedValue(i, edgcnt[i]));
		}
		BitSet retained = new BitSet(g.getm());
		for (ComparableIndexedValue ed: edges) {
			retained.set(ed.ind);
			retained.set(g.getReverseEdgeIndex(ed.ind));
			if (retained.cardinality()>=pc*g.getm()) break;
		}
		
		return retained;
	}
	
	static public BitSet sparsifyDynamicK(double pc, Graph g, double r, boolean ei) {
		TopK qp = new TopK(new CompositeGraph(g));
		double[] edgcnt = new double[g.getm()]; 
		long s = System.currentTimeMillis();
		
		HashMap<Integer,Double> ns = new HashMap<Integer, Double>();
		for (int j=0; j < g.getn(); j++) {
			ns.clear();
			ns.put(j, 1.0);
			ComparableLabeledValue[] tm = null;
			if (ei) tm = qp.getActualEI(ns, r, null);
			else tm = qp.getActualRW(ns, r, null);
			HashSet<Integer> nodes = new HashSet<Integer>();
			for (int i = 0; i < getk(g.ind[j+1]-g.ind[j],pc); i++) 
				nodes.add(g.getNodeIndex(tm[i].l)); 
			HashSet<Integer> edg = g.getEdgesAmong(nodes);
//			Visualizer.visualize(g, edg);
			for (Integer e: edg) edgcnt[e] += g.we(e);
			if (j%1000==0 && j > 0) 
				System.out.print("[" + (System.currentTimeMillis() - s)/1000.0 + 
								"] Done with " + j + "nodes\n" );
		}
		
		TreeSet<ComparableIndexedValue> edges = new TreeSet<ComparableIndexedValue>(Collections.reverseOrder());
		for (int i = 0; i < edgcnt.length; i++) {
			edges.add(new ComparableIndexedValue(i, edgcnt[i]));
		}
		BitSet retained = new BitSet(g.getm());
		for (ComparableIndexedValue ed: edges) {
			retained.set(ed.ind);
			retained.set(g.getReverseEdgeIndex(ed.ind));
			if (retained.cardinality()>=pc*g.getm()) break;
		}
		
		return retained;
	}

	private static double getk(int deg, double pc) {
		if (FUNC_K == Functions.EXP) return Math.pow(deg,pc);
		else if (FUNC_K == Functions.FRAC) return deg*pc;
		return Math.pow(deg,pc); 
	}
	
	
}
