package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeSet;

import graph.Graph;
import generator.GraphGenerator;

public class APSP implements DistanceMeasure {

	// contains distances d and paths sp for pairs of nodes
	// indices are computed using getind(index_v1, index_v2)
	private double[] d;
	private ArrayList<ArrayList<Integer>> sp;
	private double maximum = Double.NEGATIVE_INFINITY;
	@Override public double max() {return maximum;}
	private double minimum = Double.POSITIVE_INFINITY;
	@Override public double min() {return minimum;}
	private double average = 0;
	@Override public double avg() {return average;}
	@Override public int numelems() { return g.getn();}
	
	public double[] centrality() {
		double[] res = new double[g.getn()];
		for (int i= 0; i < sp.size();i++) {
			for (int j = 0; j < sp.get(i).size();j++) {
				res[sp.get(i).get(j)] += 1.0/sp.size(); 
			}
		}
		return res;
	}
	
	Graph g;
	
	public int getind(int v1,int v2){
		assert(v2!=v1);
		return v1*(g.getn()-1) + ((v2>v1)?(v2-1):v2);
	}
	
	public double getD(int v1,int v2) {
		if (v1==v2) return 0.0;
		else return d[getind(v1,v2)];
	}
	
	public ArrayList<Integer> getSPath(int v1,int v2) {
		return sp.get(getind(v1,v2));
	}
	
	public APSP(Graph _g) {
		assert(_g.isUndirected());
		g = _g;
		d = new double[g.getn()*(g.getn()-1)];
		Arrays.fill(d,Double.MAX_VALUE);
		sp = new ArrayList<ArrayList<Integer>>();
		for (int i=0; i < g.getn()*(g.getn()-1); i++){ 
			sp.add(new ArrayList<Integer>());
		}		
	}
	
	public APSP(Graph _g, boolean computeFW) {
		assert(_g.isUndirected());
		g = _g;
		d = new double[g.getn()*(g.getn()-1)];
		Arrays.fill(d,Double.MAX_VALUE);
		sp = new ArrayList<ArrayList<Integer>>();
		for (int i=0; i < g.getn()*(g.getn()-1); i++){ 
			sp.add(new ArrayList<Integer>());
		}		
		if (computeFW) computeFloydWarshall();
	}
	
	public void computeFloydWarshall() {
		Arrays.fill(d, Double.MAX_VALUE);
		for (int i=0; i < sp.size(); i++) sp.get(i).clear();
		// initialize with edges
		for (int i = 0; i < g.getn(); i++) {
			for (int j=g.ind[i]; j < g.ind[i+1]; j++) {
				d[getind(i,g.endv[j])] = g.we[j];
				sp.get(getind(i,g.endv[j])).add(i);
				sp.get(getind(i,g.endv[j])).add(g.endv[j]);
			}
		}
		
		// Triple loop
		for (int k=0; k<g.getn(); k++){
		    for (int i=0; i<g.getn(); i++){
		        for (int j=0; j<g.getn(); j++){
		        	if (i==j || i==k || k == j) continue;
		            if (d[getind(i, j)] > d[getind(i, k)] + d[getind(k, j)]) {
		            	d[getind(i, j)] = d[getind(i, k)] + d[getind(k, j)];
		            	sp.get(getind(i,j)).clear();
		            	sp.get(getind(i,j)).addAll(sp.get(getind(i,k)));
		            	sp.get(getind(i,j)).remove(sp.get(getind(i,j)).size()-1);
		            	sp.get(getind(i,j)).addAll(sp.get(getind(k,j)));
		            }
		        }
		    }
		}
		// get min and max and average too
		for(double dist: d) {
			if (minimum > dist) minimum = dist;
			if (maximum < dist) maximum = dist;
			average += dist/d.length;
		}
	}
	
	public void computeFloydWarshallNodeLatencies() {
		Arrays.fill(d, Double.MAX_VALUE);
		for (int i=0; i < sp.size(); i++) sp.get(i).clear();
		// initialize with edges
		for (int i = 0; i < g.getn(); i++) {
			for (int j=g.ind[i]; j < g.ind[i+1]; j++) {
				d[getind(i,g.endv[j])] = g.we[j] + g.wn[i] + g.wn[g.endv[j]];
				sp.get(getind(i,g.endv[j])).add(i);
				sp.get(getind(i,g.endv[j])).add(g.endv[j]);
			}
		}
		
		// Triple loop
		for (int k=0; k<g.getn(); k++){
		    for (int i=0; i<g.getn(); i++){
		        for (int j=0; j<g.getn(); j++){
		        	if (i==j || i==k || k == j) continue;
		            if (d[getind(i, j)] > d[getind(i, k)] + d[getind(k, j)] - g.wn[k]) {
		            	d[getind(i, j)] = d[getind(i, k)] + d[getind(k, j)] - g.wn[k];
		            	sp.get(getind(i,j)).clear();
		            	sp.get(getind(i,j)).addAll(sp.get(getind(i,k)));
		            	sp.get(getind(i,j)).remove(sp.get(getind(i,j)).size()-1);
		            	sp.get(getind(i,j)).addAll(sp.get(getind(k,j)));
		            }
		        }
		    }
		}
		// get min and max average too
		for(double dist: d) {
			if (minimum > dist) minimum = dist;
			if (maximum < dist) maximum = dist;
			average += dist/d.length;
		}
	}
	
	public int getCenter(BitSet edges) {
		HashSet<Integer> nds = new HashSet<Integer>();
		for (int i=0;i< g.getn(); i++) {
			for (int j=g.ind[i]; j < g.ind[i+1]; j++) {
				if(edges.get(j)) {
					nds.add(i); nds.add(g.endv[j]);
				}
			}
		}
	
		Integer minnd = g.getn()+1;
		Double minval = Double.MAX_VALUE;
		
		for (Integer n1: nds) {
			double n1w = 0;
			for (Integer n2: nds) {
				if (n1!=n2) {
					double d = getD(n1, n2);
					n1w += d;
				}
			}
			if (n1w < minval) {
				minnd = n1;
				minval = n1w;
			} else if ((minnd != g.getn()+1) && (minval.equals(n1w)) && (n1 < minval)) {
				minnd = n1;
			}
		}
		return minnd;
	}
	
	public TreeSet<EdgeComparable> getOrderedEdges(boolean only_positive) {
		TreeSet<EdgeComparable> ec = new TreeSet<EdgeComparable>();
		for (int i=0; i < g.getn(); i++) {
			if (only_positive && g.wn[i] == 0) continue;
			for (int j= i+1; j < g.getn(); j++) {
				if (only_positive && g.wn[j] == 0) continue;
				ec.add(new EdgeComparable(i,j,getD(i,j)));
			}
		}
		return ec;
	} 
	
	public String toString() {
		String result = "";
		for (int i=0; i < g.getn(); i++) {
			for (int j=0; j < g.getn(); j++) {
				if (i==j) continue;
				result += i + "\t" + j + "\t" + d[getind(i, j)] + "\t" + 
						  sp.get(getind(i,j)).toString() + "\n"; 
			}
		}
		return result;
	}

	public static void main(String[] argv) {
		long start;
		for (int i = 1; i < 100; i++) {
			//Graph g = GraphGenerator.generateRandom(i*10, i*12);
			Graph g = GraphGenerator.generateScaleFree(i*10);
			start = System.currentTimeMillis();
			APSP apsp = new APSP(g);
			apsp.computeFloydWarshall();
			System.out.print(i*10 + "\t" + (System.currentTimeMillis()-start));
			
			start = System.currentTimeMillis();
			MetricGraph mg = new MetricGraph(g);
			mg.computeFloydWarshall();
			System.out.print("\t" + (System.currentTimeMillis()-start) + "\t|\t");
			
			
			double d;
			ArrayList<Integer> sp;
			int node;
			
			start = System.currentTimeMillis();
			for (int x=0; x < 1; x++) {
				for (int j=0; j < g.getn(); j++) {
					for (int k=0; k < g.getn(); k++) {
						if (j==k) continue;
						d = apsp.getD(j, k);
						sp = apsp.getSPath(j,k);
						for (int m=0; m < sp.size(); m++) { 
							node = sp.get(m);
						}
					}
				}
			}
			System.out.print("\t" + (System.currentTimeMillis()-start) + "\t");
			
			start = System.currentTimeMillis();
			for (int x=0; x < 1; x++) {
				for (int j=0; j < g.getn(); j++) {
					for (int k=0; k < g.getn(); k++) {
						if (j==k) continue;
						d = mg.d[j][k];
						for (int m=0; m < mg.sp[j][k].length; m++) {
							if (mg.sp[j][k][m] < 0) break;
							node = mg.sp[j][k][m];
						}
					}
				}
			}
			System.out.print("\t" + (System.currentTimeMillis()-start) + "\n");
		}
		//System.out.print(apsp.toString());
		//System.out.print(mg.toString());
	}
}
