/**
 * Title:        ProAlign<p>
 * Description:  <p>
 * Copyright:    Copyright (c) Ari Loytynoja<p>
 * License:      GNU GENERAL PUBLIC LICENSE<p>
 * @see          http://www.gnu.org/copyleft/gpl.html
 * Company:      ULB<p>
 * @author       Ari Loytynoja
 * @version      1.0
 */
package proalign;

// As Implemented by Studier and Keppler (1988) in Li (1997), p. 111.
//
class NeighborJoining {

    String[] newOtus;
    String tree = new String();
    String tree3 = new String();

    NeighborJoining(double[][] distance, String[] otus) {

	ProAlign.log("NeighborJoining");

	while(distance.length>2) {
	    distance = joinNeighbors(distance, otus);
	    otus = newOtus;
	}

	double dist = Math.abs((distance[0][0]+distance[0][1])/2d);


	tree = "("+otus[0]+":"+dist+","+otus[1]+":"+dist+");";

	if(otus[0].startsWith("(")&&otus[0].endsWith(")")) {
	    tree3 = otus[0].substring(0,otus[0].length()-2)+","+
		otus[1]+":"+dist*2d+");";
	} else {
	    tree3 = "("+otus[0]+":"+dist*2d+","+otus[1].substring(1)+";";;
	}
    }

    String getTree() {
	return tree;
    }
    String getTree3() {
	return tree3;
    }

    double[][] joinNeighbors(double[][] distance, String[] otus) {

	
	int no = distance.length;
	int otu1=0, otu2=0;
	double minM = Double.POSITIVE_INFINITY;

	double[] rDist = new double[no]; // sum of distances d_i,j

	for(int i=0; i<no; i++) {
	    for(int j=0; j<no; j++) {
		rDist[i] += distance[i][j];
	    }
	}
	for(int i=0; i<no; i++) {
	    for(int j=0; j<no; j++) {
		if(j==i) {
		    continue;
		}
		double mDist = distance[i][j]-(rDist[i]+rDist[j])/(no-2);
		if(mDist<minM) {
		    minM = mDist;
		    otu1 = Math.min(i,j);
		    otu2 = Math.max(i,j);
		}
	    }
	}

	double brl1 = distance[otu1][otu2]/2+
	    (rDist[otu1]-rDist[otu2])/(2*(no-2));
	double brl2 = distance[otu1][otu2]-brl1;

	    
	double[][] newDistance = new double[no-1][no-1];
	newOtus = new String[no-1];
	int ci=0;
	int cj=0;

	for(int i=0; i<no; i++) {
	    for(int j=0; j<no; j++) {
		if(i==j) {
		    continue;
		}

		if(j<otu2) {
		    cj=j;
		} else if(j==otu2) {
		    continue;
		} else {
		   cj=j-1;
		} 

		if(i<otu2) {
		    ci=i;
		} else if(i==otu2) {
		    continue;
		} else { 
		    ci=i-1;
		}

		if(i==otu1) {
		    newDistance[ci][cj] = (distance[otu1][j]+distance[otu2][j]-
						 distance[otu1][otu2])/2;
		} else if(j==otu1) {  
		    newDistance[ci][cj] = (distance[otu1][i]+distance[otu2][i]-
					   distance[otu1][otu2])/2;
		} else {
		    newDistance[ci][cj] = distance[i][j];
		}
	    }
	}
	
	for(int i=0; i<no; i++) {
	    if(i==otu1) {
		newOtus[i] = "("+otus[otu1]+":"+Math.abs(brl1)+","+
		    otus[otu2]+":"+Math.abs(brl2)+")";
		continue;
	    } else if(i<otu2) {
		ci = i;
	    } else if(i==otu2) {
		continue;
	    } else {
		ci=i-1;
	    } 
	    newOtus[ci] = otus[i];
	}

	return newDistance;
    }

    public static void main(String[] args) {

	// Reads PHYLIP distance tables

	double[][] distance = new double [0][0];
	String[] otus = new String[0];

	try {

            InFile in = new InFile(args[0]);
	    String row = in.readLine();
	    int no = new Integer(row.trim()).intValue();

	    otus = new String[no];
	    distance = new double[no][no];
	    
	    int i=0;
            while((row = in.readLine()) != null) {
		otus[i] = row.substring(0,10).trim();
		row = row.substring(11).trim();
		for(int j=0; j<no-1; j++) {
		    String value = row.substring(0,row.indexOf(" ")).trim();
		    distance[i][j] = new Double(value).doubleValue();
		    row = row.substring(row.indexOf(" ")).trim();
		}		
		distance[i][no-1] = new Double(row.trim()).doubleValue();
		i++;
	    }
	 }  catch(Exception e) { 
	     System.out.println("Problems with "+args[0]);
	     e.printStackTrace();
	     System.exit(0);
	 }

	NeighborJoining nj = new NeighborJoining(distance,otus);
	System.out.println(nj.getTree());
	System.out.println(nj.getTree3());
    }
}