package cluster;

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

import misc.ComparableIndexedValue;

import generator.GraphGenerator;
import graph.APSP;
import graph.DistanceMeasure;
import graph.Graph;
import graph.NodeWeightedTimeGraph;
import cluster.Common;
import cluster.Common.COMPRESS;
import cluster.Common.GDIST;

//Greedy Incremental Clustering
public class GreedyClustering {
	
	public static void cluster(NodeWeightedTimeGraph tg, int k, int lag, 
							   GDIST gd, COMPRESS cm, float alpha) {
		// First precompute ptp distance
		DistanceMeasure dm = null;
		if (GDIST.SP == gd) {
			dm = new APSP(tg,true);
		}
		
		ArrayList<HashSet<Integer>> cl = new ArrayList<HashSet<Integer>>();
		for (int i=0; i<k; i++) cl.add(new HashSet<Integer>());
		
		
		// compute the clusterings  
		for (int t = lag-1; t < tg.gett(); t++) {
			clusterSlice(tg, k, lag, cm, alpha, dm, cl, t);
		}
		
	}

	private static void clusterSlice(NodeWeightedTimeGraph tg, 
			int k, int lag, COMPRESS cm, float alpha, 
			DistanceMeasure dm, ArrayList<HashSet<Integer>> cl, int t) {
		
		HashSet<Integer> from = new HashSet<Integer>();
		HashSet<Integer> clustered = new HashSet<Integer>();
		ComparableIndexedValue nd = null;
		
		// clear previous clustering
		for (int c=0; c<k; c++) cl.get(c).clear();
		clustered.clear();
		
		// find furthest k nodes 
		// (one can bootstrap with the centers of previous clusters)
		from.clear();
		from.add(0);
		nd = findFurthest(tg,t,lag,from,dm,cm,alpha,clustered);
		cl.get(0).add(nd.ind);
		from.clear();
		from.add(nd.ind); 
		clustered.add(nd.ind);
		for (int c = 1; c < k; c++) {
			nd = findFurthest(tg,t,lag,from,dm,cm,alpha,clustered);
			cl.get(c).add(nd.ind);
			from.add(nd.ind);
			clustered.add(nd.ind);
		}
		
		// Start adding nodes to clusters greedily from adjacent nodes 
		float min_dist = Float.POSITIVE_INFINITY;
		int clust = -1 , node = -1;
		 
		while (clustered.size() < tg.getn()) {
			min_dist = Float.POSITIVE_INFINITY;
			clust = -1;
			node = -1;
			
			for (int c = 0; c < k; c++) {
				nd = findClosestAdjacent(tg,t,lag,cl.get(c),dm,cm,alpha,clustered);
				if (null == nd) continue;
				if (min_dist > nd.v) {
					min_dist = nd.v.floatValue();
					clust = c;
					node = nd.ind;
				}
			}
			cl.get(clust).add(node);
			clustered.add(node);
		}
		System.err.print(cl.toString()+ "\n");
	}

	private static ComparableIndexedValue findClosestAdjacent(NodeWeightedTimeGraph tg,
			int t, int lag, HashSet<Integer> from, DistanceMeasure dm,
			COMPRESS cm, float alpha, HashSet<Integer> taken) {
			
		ComparableIndexedValue closest = null, tmp = null;
		HashSet<Integer> checked = new HashSet<Integer>();
		int nbr = -1;
		
		for (Integer n: from) {
			for (int j=tg.ind[n]; j < tg.ind[n+1]; j++) {
				nbr = tg.endv[j];
				if (!(taken.contains(nbr)) && !(checked.contains(nbr))) {
					tmp = getDistance(tg,t,lag,from,nbr,dm,cm,alpha);
					checked.add(nbr);
					if(closest==null) 
						closest = tmp;
					else if (tmp.compareTo(closest)<0) 
						closest = tmp;
				}
			}
		}
		return closest;
	}

	private static ComparableIndexedValue findFurthest(NodeWeightedTimeGraph tg, int t, int lag,
			HashSet<Integer> from, DistanceMeasure dm, COMPRESS cm, float alpha, HashSet<Integer> taken) {
		ComparableIndexedValue furthest = null, tmp = null;
		for (int nbr=0; nbr < tg.getn(); nbr++) {
			if (!taken.contains(nbr) && !from.contains(nbr)){
				tmp = getDistance(tg,t,lag,from,nbr,dm,cm,alpha);
				if(furthest==null) 
					furthest = tmp;
				else if (tmp.compareTo(furthest)>0) 
					furthest = tmp;
			}
		}
		return furthest;
	}
	
	private static ComparableIndexedValue getDistance(NodeWeightedTimeGraph tg, int t, int lag,
			HashSet<Integer> from, int nbr, DistanceMeasure dm, COMPRESS cm,
			float alpha) {
		double compression_decay = Common.getCompressionDecay(tg,t,lag,from,nbr,cm);
		compression_decay /= lag;
		double mind_dist = Common.getMinDist(dm, from, nbr)/dm.max();
		assert(mind_dist>=0 && compression_decay >=0):"Negative compresion decay of distance"; 
		return new ComparableIndexedValue(nbr, alpha*mind_dist + (1-alpha)*compression_decay);
	}

	public static void main(String[] args) {
		Graph gr = GraphGenerator.getTestGraph();	
		double[][] cl = {{1.0,1.0,0.0,0.0,0.0,0.0,1.0},
						 {0.0,0.0,1.0,1.0,1.0,1.0,0.0}};
		
		NodeWeightedTimeGraph ntg = 
			GraphGenerator.generateRandomNWSoftClusters(8000, gr, cl, 10, 0.9, 10, 0.5 );
		Arrays.fill(ntg.we,1.0);
		
		int numclusters = 2;
		int tlag = 5;
		float alpha = 0.0f;
		
		cluster(ntg, numclusters, tlag, 
				GDIST.SP, COMPRESS.AVGL2, 
				alpha);
	}
	
}
