package alg;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.logging.Level;

import graph.Graph;
import graph.Tree;
import generator.GraphGenerator;

public class PCST {
	
	// TODO(petko): add the Steiner nodes along an expanded path 
	// to consider in the next steps of the MST on the G_c
	// It basically selects edges and then does a subgraph of t
	public static Tree computeOptTreeNW(Tree t) {
		HashMap<Integer,Double> vals = new HashMap<Integer, Double>();
		HashMap<Integer,ArrayList<Integer>> e_children = new HashMap<Integer, ArrayList<Integer>>();
		
		// Aggregate values up
		for (int l=0; l<=t.height; l++) {
			for (int i = 0; i < t.ind.length-1; i++){
				if (t.levels[i]==l) {
					vals.put(i, t.wn[i]);
					e_children.put(i, new ArrayList<Integer>());
					for (int j=t.ind[i]; j < t.ind[i+1]; j++) {
						if(t.levels[t.endv[j]] == l-1 && 
						   vals.get(t.endv[j]) - t.we[j] >= 0) {
						   vals.put(i, vals.get(i) + vals.get(t.endv[j]) - t.we[j]);
						   e_children.get(i).add(j);
						}
					}	
				}
			}
		}
		
		// Find Max
		int  ind = -1;
		double max = -1;
		for (int i:vals.keySet()) {
			if (vals.get(i) > max) {
				max = vals.get(i);
				ind = i;
			}
		}
		
		
		PriorityQueue<Integer> q = new PriorityQueue<Integer>();
		ArrayList<Integer> edges = new ArrayList<Integer>();
		q.add(ind);
		// collect the best subtree of ind
		Integer v = null;
		while (q.size() > 0) {
			v = q.poll();
			for(int edge:e_children.get(v)){
				edges.add(edge);
				edges.add(t.getEdgeIndex(t.endv[edge], v));
				assert(!q.contains(t.endv[edge]));
				q.add(t.endv[edge]);
			}
		}
		if(edges.size()==0) {
			return new Tree(new Graph(t.names[ind],t.wn[ind]));
		}
		
		return new Tree(t.subgraph(edges));
	}
	
	public static void main(String[] argv) {
		Graph g = GraphGenerator.getTestGraph();
		System.out.print(g.toString());
		//ST.computeMST();
		ArrayList<String> terminals = new ArrayList<String>();
		//terminals.add("6");terminals.add("5"); terminals.add("3"); terminals.add("1");terminals.add("4");
		terminals.add("6");terminals.add("1"); //terminals.add(2); terminals.add(6);
		Tree t = ST.computeSteiner(g,terminals);
		System.out.print(computeOptTreeNW(t).toStringHuman());
	} 
	
}