/*  
 *  src/org/metaqtl/factory/TreeFactory.java
 * 
 *  $Author: veyrieras $, $Date: 2006-10-17 15:41:55 $, $Version$
 *
 *  MetaQTL : a Java package for QTL Meta-Analysis
 * 
 *  Copyright (C) 2003-2006  Jean-Baptiste Veyrieras, INRA, France.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA * 
 */
package org.metaqtl.factory;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;

import org.metaqtl.Tree;
import org.metaqtl.TreeNode;
import org.metaqtl.bio.util.NumberFormat;

/**
 * A factory to deal with distance trees.
 */
public final class TreeFactory {
	
	/**
	 * This method writes out the given tree <code>nodes</code> as an array of 
	 * {@link TreeNode} on the given output stream </code>stream</code>. The
	 * user is responsible for closing the </code>stream</code>.
	 *  
	 * @param nodes the tree
	 * @param stream the output stream.
	 * @throws IOException
	 */
	public static void write(Tree tree, OutputStream stream) throws IOException {
		PrintWriter writer;
		
		if (tree == null) return;
		if (stream == null) return;
		
		writer = new PrintWriter(new OutputStreamWriter(stream));
		
		write(tree, writer);
		
	}
	/**
	 * This method writes out the given tree <code>nodes</code> as an array of 
	 * {@link TreeNode} using the given writer </code>writer</code>.
	 * 
	 * @param nodes the tree
	 * @param writer the writer.
	 */
	public static void write(Tree tree, PrintWriter writer) {
		if (tree  == null) return;
		if (writer == null) return;
		
		write_newick(tree.root,tree.root,writer);
		
		writer.flush();
	}
	/**
	 * This methods recursively writes out a binary tree with aribitrary
	 * root <code>root</code> from the current node <code>cur</code> in
	 * a Newick format using the given <code>writer</code>.
	 *   
	 * @param cur the current node of the tree.
	 * @param root the root of the tree (arbitrary).
	 * @param writer the writer
	 */
	private static void write_newick(TreeNode cur, TreeNode root, PrintWriter writer) {
		
		if (cur.leaf) {
	  		writer.print(cur.idx);
	  	} else {
	  		TreeNode[] children = cur.children;
	  		writer.print("(");
	  		for(int i=0;i<children.length;i++) {
	  			write_newick(children[i], root, writer);
	  			writer.print(":"+NumberFormat.formatDouble(children[i].dist));
	  			if (i<children.length-1)
	  				writer.print(",");
	  		}
	  		writer.print(")");
	  	}
	  	if (cur.equals(root)) {
	  		writer.print(";");
	  	}
	  	
	  	writer.flush();
	}
	/**
	 * 
	 * @param cur
	 * @param root
	 * @param reader
	 */
	public static Tree read_newick(Reader reader) throws IOException {
		BufferedReader buffer;	
		String line,treeStr;
		StringBuffer sbuffer;
		
		buffer  = new BufferedReader(reader);
		sbuffer = new StringBuffer();
		
		while((line = buffer.readLine())!=null) {
			line.replace("\n","");
			sbuffer.append(line);
			if (line.charAt(0) == ';') break;
		}
		treeStr = sbuffer.toString();
		
		System.out.println("tree = " + treeStr);
		
		return read_newick(treeStr);
	}
	/**
	 * 
	 * @param treeStr
	 * @return
	 * @throws IOException
	 */
	public static Tree read_newick(String treeStr) throws IOException {
		TreeNode  root;
		Tree tree = null;
		// remove all before first and last bracket and parse tree
		int p0 = treeStr.indexOf("(");
		int p1 = treeStr.lastIndexOf(");");
		
		if(!(0<=p0 && p0<p1)) {
		   throw new IOException("Invalid tree format");
		}
		
		root = new TreeNode();
		
		parse_newick(root, treeStr.substring(p0+1,p1));
		
		tree = new Tree(root);
		
		return tree;
	}
	/**
	 * 
	 * @param parent
	 * @param children
	 * @throws IOException
	 */
	private static void parse_newick(TreeNode parent, String children) throws IOException {
		
		//System.out.println("*** children='"+children+"'");
		
		// checking if it is a leaf
		if(children.indexOf("(")!=0) {
			// its a leaf
			int ends = children.indexOf(",");
			String leafData = null;
			if(ends<0) {
				leafData = children.trim();
			} else {
				leafData = children.substring(0, ends).trim();
			}
			// create and add leaf
			
			//System.out.println("* leafData='"+leafData+"'");
			
			int ends1 = leafData.indexOf(":");
			
			String leafLabel,leafDist;
			
			if (ends1 < 0) {
				leafLabel = leafData.trim();
				leafDist  = new String("1.0");
			} else {
				leafLabel = leafData.substring(0, ends1).trim();
				leafDist  = leafData.substring(ends1+1, leafData.length()).trim();
			}
			
			//System.out.println("* leafLabel='"+leafLabel+"'");
			//System.out.println("* leafDist='"+leafDist+"'");
			
			int    label = Integer.parseInt(leafLabel);
			double dist  = Double.parseDouble(leafDist);
			
			TreeNode leaf = new TreeNode(label);
			leaf.dist     = dist;
			
			parent.addChild(leaf);
		    
			// send it on
		    //System.out.println("** take next child");
		    if(ends>0) {
		    	parse_newick(parent, children.substring(ends+1).trim());
			}
			return;
		}
		// its a internal node
		int p0 = 0;
		int p1 = 0;
		int leftRight = 0;
		do {
		    int pl = children.indexOf("(", p1);
		    if(pl<0) {
		    	pl = Integer.MAX_VALUE;
		    }
		    int pr = children.indexOf(")", p1);
		    if(pr<0) {
		    	pr = Integer.MAX_VALUE;
		    }
		    //System.out.println("* (pl,pr)=("+pl+","+pr+")");
		    if(pl<pr) {
				leftRight++;
				p1 = pl+1;
		    } else {
				leftRight--;
				p1 = pr+1;
		    }
		    if(leftRight<0) {
		    	throw new IOException("Could not parse tree.");
		    }
		} while(leftRight!=0);
		// get edge value
		int ends = children.indexOf(",", p1);
		
		String nodeData = null;
		
		if(ends<0) {
		    nodeData = children.substring(p1).trim();
		} else {
		    nodeData = children.substring(p1, ends).trim();
		}
		//System.out.println("* nodeData='"+nodeData+"'");
		
		int ends1 = nodeData.indexOf(":");
		nodeData  = nodeData.substring(ends1+1, nodeData.length()).trim();
		
		TreeNode node = new TreeNode();
		node.dist     = Double.parseDouble(nodeData);
		
		parent.addChild(node);
		
		// if any more children then sending it on
		if(ends>=0) {
			parse_newick(parent, children.substring(ends+1).trim());
		}
		// sending it on down
		String newChildren = children.substring(p0+1,p1-1).trim();
		parse_newick(node, newChildren);
		//
		return;
	}
	/**
	 * @param buffer
	 * @return
	 */
	public static Tree read(Reader reader) throws IOException {
		return read_newick(reader);
	}
	
	public static Tree read(String str) throws IOException {
		String t = new String(str);
		t.replaceAll("\n", "");
		return read_newick(t);
	}
}
