package myFlowmap;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.StringTokenizer;

public class buildWeightedTree {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		double MAXDIST = Math.pow(10, 12);

		// Start file i/o
		System.out.println("Starting read from graph.in");
		FileReader file = new FileReader("graph.in");
		BufferedReader in = new BufferedReader(file);

		// First line of data file tells us number of targets.
		StringTokenizer data = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(data.nextToken());
		System.out.println("\tHave " + n + " targets");
		// Now we know n, can set up array dimensions and do some other setup
		int numInC = n + 1;
		boolean[] inC = new boolean[2 * n + 1];
		double[] x = new double[2 * n + 1];
		double[] maxx = new double[2 * n + 1];
		double[] minx = new double[2 * n + 1];
		double[] y = new double[2 * n + 1];
		double[] maxy = new double[2 * n + 1];
		double[] miny = new double[2 * n + 1];
		double[] w = new double[2 * n + 1];
		String[] clusterName = new String[2 * n + 1];
		double[][] d = new double[2 * n + 1][2 * n + 1];

		for (int i = 0; i <= 2 * n; i++) {
			for (int j = 0; j <= 2 * n; j++) {
				d[i][j] = 0;
			}
		}

		// Continue IO by parsing source (no weight)
		data = new StringTokenizer(in.readLine(), ",");
		clusterName[0] = data.nextToken();
		x[0] = Double.parseDouble(data.nextToken());
		y[0] = Double.parseDouble(data.nextToken());
		w[0] = 0;

		// Remaining datalines have name,x,y,weight
		for (int i = 1; i <= n; i++) {
			data = new StringTokenizer(in.readLine(), ",");
			clusterName[i] = data.nextToken();
			x[i] = Double.parseDouble(data.nextToken());
			y[i] = Double.parseDouble(data.nextToken());
			w[i] = Double.parseDouble(data.nextToken());
			w[0] -= w[i];
			System.out
					.println("\tAdded target " + clusterName[i] + " with flow "
							+ w[i] + " at (" + x[i] + "," + y[i] + ").");
		}
		// Done with IO
		in.close();
		System.out.println("\tSource is " + clusterName[0] + " at (" + x[0]
				+ "," + y[0] + ") with total flow " + Math.abs(w[0]) + ".");

		// Initial bounding boxes are simply coordinates
		for (int i = 0; i <= n; i++) {
			inC[i] = true;
			maxx[i] = x[i];
			minx[i] = x[i];
			maxy[i] = y[i];
			miny[i] = y[i];
		}

		// We know how many clusters we'll create, so let's give them convenient
		// names
		for (int i = n + 1; i <= 2 * n; i++) {
			clusterName[i] = "Cluster " + i;
			inC[i] = false;
		}

		// Clustering dendrogram will be stored as H; we know its vertices
		Graph H = new Graph(2 * n, 2 * n + 1);
		for (int i = 0; i <= n; i++) {
			H.addFixedVertex(clusterName[i], x[i], y[i]);
		}
		for (int i = n + 1; i <= 2 * n; i++) {
			H.addVertex(clusterName[i]);
		}

		// Placeholders for closest clusters on a given iteration
		double minDist = MAXDIST;
		int besti = 0;
		int bestj = 0;
		int k = n + 1;

		// Initial population of distance matrix only needs source and target
		// vertices;
		// Also only compare j>i; and work with squares of distance
		for (int i = 0; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				d[i][j] = Math.pow(x[i] - x[j], 2) + Math.pow(y[i] - y[j], 2);
			}
		}

		System.out.println();
		System.out.println("Clustering");
		while (numInC > 1) {
			minDist = MAXDIST;
			for (int i = 0; i <= 2 * n; i++) {
				if (inC[i]) {
					for (int j = i + 1; j <= 2 * n; j++) {
						if (inC[j]) {
							// Have a candidate i,j pair from C
							if (d[i][j] < minDist) {
								minDist = d[i][j];
								besti = i;
								bestj = j;
							}
						}
					}
				}
			}
			// Now we have identified the closest two clusters
			H.addEdge(clusterName[besti], clusterName[k], Math.abs(w[besti]));
			H.addEdge(clusterName[bestj], clusterName[k], Math.abs(w[bestj]));
			w[k] = w[besti] + w[bestj];
			// Bounding box update
			maxx[k] = Math.max(maxx[besti], maxx[bestj]);
			minx[k] = Math.min(minx[besti], minx[bestj]);
			maxy[k] = Math.max(maxy[besti], maxy[bestj]);
			miny[k] = Math.min(miny[besti], miny[bestj]);
			// Bounding box centering
			x[k] = (maxx[k] + minx[k]) / 2;
			y[k] = (maxy[k] + miny[k]) / 2;
			// Alternative centering:
			// Simple average
			// x[k]=(x[besti]+x[bestj])/2;
			// y[k]=(y[besti]+y[bestj])/2;
			// Weighted average
			// x[k]=x[besti]+(x[bestj]-x[besti])*Math.abs(w[bestj])/(Math.abs(w[besti])+Math.abs(w[bestj]));
			// y[k]=y[besti]+(y[bestj]-y[besti])*Math.abs(w[bestj])/(Math.abs(w[besti])+Math.abs(w[bestj]));
			inC[k] = true;
			System.out.println("\tMerging " + clusterName[besti] + " with "
					+ clusterName[bestj] + " to create " + clusterName[k]);
			System.out.println("\t\tIt has net flow " + w[k]
					+ " and is centred at " + x[k] + "," + y[k] + ".");
			inC[besti] = false;
			inC[bestj] = false;
			// Distance matrix update; any cluster i still in C could be
			// requested
			for (int i = 0; i <= 2 * n; i++) {
				if (inC[i])
					d[i][k] = Math.pow(x[i] - x[k], 2)
							+ Math.pow(y[i] - y[k], 2);
			}
			k++;
			numInC--;
		}
		System.out.println();
		// Uncomment next lines to review or write the weighted dendrogram
		// H.printJSON();
		// H.writeJSON();
		Graph F = H.reHang();
		// F.printJSON();
		F.writeJSON();
	}

}