/*
 * newickParser.js
 * http://tasuke.dna.affrc.go.jp/
 *
 * Author: Jungsok Kim, Ryutaro Itoh, Norio Tabei
 *
 * Copyright (c) 2013 National Institute of Agrobiological Sciences
 *
 */
function parseNewick(newickStr, defLength) {
	if(defLength == null) defLength = 0;

	var FLG_DEBUG = false;
//var FLG_DEBUG = true;
	var endBranchPttern = /^[^,\(\)]+/;
	
	newickStr = newickStr.replace(/\s/g, "");
/*
	if(newickStr.match(/\);$/)) {
		newickStr = newickStr.replace(/^\(/, "");
		newickStr = newickStr.replace(/\);$/, "");
	}
*/
//console.log("Conv:" + newickStr);

	var newickStrLen = newickStr.length;
	var serial = 0;
	var strStart = 0;
	var serial2branch = {};
	var newickObj = scanTreeRecursive(null);
/*
	console.log("RootChilds:" + newickObj.childs.length);
	while(newickObj.childs.length === 1) {
		console.log("Cut root");
		newickObj.childs[0].remove();	// If newick is like "((...));", truncate root
	}
*/
	var stat = updateDepthParseNewickTree(newickObj);
	var maxDepth = stat['maxDepth'];
	var maxHeight = stat['maxHeight'];
	var leafOrder = stat['leafOrder'];

/*
	console.log("MaxDepth:" + maxDepth);
	console.log("MaxHeight:" + maxHeight);
	console.log("Leafs:" + leafOrder.length);
*/
	return {
		"tree": newickObj,
		"order": leafOrder,
		"maxDepth": maxDepth,
		"maxHeight": maxHeight,
		"serial2branch": serial2branch
	};
	
	function scanTreeRecursive(clstr) {
		if(clstr !== null) {
			clstr.serial = serial++;
if(FLG_DEBUG) console.log("NodeStart:" + clstr.serial);
			serial2branch[clstr.serial] = clstr;
		}
		var b2t  = 0;
		while(true) {
			if(newickStrLen <= strStart) {
				break;
			} else if(newickStr.substr(strStart, 1) === '(') {
if(FLG_DEBUG) console.log("(");
				strStart++;
				if(clstr === null) {
					// Top of newick string
					clstr = scanTreeRecursive(getEmptyBranch());
				} else {
					// In the middle of newick string
					clstr.addChild(scanTreeRecursive(getEmptyBranch()));
				}
			} else if(newickStr.substr(strStart, 1) === ')') {
				strStart++;
				var end_len = newickStr.substr(strStart).match(/^([^\:\)]*)\:([^,\)]+)/);
				if(end_len) {
					strStart += end_len[0].length;
					if(end_len[1] !== '') clstr.bootstrap =  parseFloat(end_len[1]);	// Bootstrap
					clstr.length = parseFloat(end_len[2]);	// Length
				} else {
					end_len = newickStr.substr(strStart).match(/^([^,\)]+)/);
					if(end_len) {
						// Bootstrap only
						strStart += end_len[0].length;
						if(end_len[1] !== ';') clstr.bootstrap =  parseFloat(end_len[1]);
					} else {
						end_len = ["no length"];	// For debug
					}
					clstr.length = defLength;
				}
if(FLG_DEBUG) console.log(")" + end_len[0] + " : " + clstr.serial + ", " + clstr.bootstrap + ", " + clstr.length);
				break;
			} else if(newickStr.substr(strStart, 1) === ',') {
if(FLG_DEBUG) console.log(",");
				strStart++;
			} else {
				var endBranch = newickStr.substr(strStart).match(endBranchPttern);
				var leaf = parseIdLen(endBranch[0]);
				leaf.serial = serial++;
				clstr.addChild(leaf);
				serial2branch[leaf.serial] = leaf;
				strStart += endBranch[0].length;
if(FLG_DEBUG) console.log(endBranch[0] + " : " + leaf.childs + ", " + leaf.serial + ", " + leaf.length + " => " + clstr.serial);
			}
		}
		return clstr;
	}
	function getEmptyBranch() {
		return new PhyloTreeCluster([], null, null);
	}
	function parseIdLen(str) {
		var params = str.match(/^([^\:]+)\:(.+)$/);
		var clstr;
		if(params) {
			var len = parseFloat(params[2]);
			clstr = new PhyloTreeCluster(params[1], len, null);
			
		} else {
			clstr = new PhyloTreeCluster(str, defLength, null);
		}
		return clstr;
	}
}
function updateDepthParseNewickTree(tree) {
	var leafIndex = 0;
	var leafOrder = [];
	var maxDepth = 0;
	var maxHeight = 0;
	setHeightRecursive(tree, 0, 0);
	return {"maxDepth":maxDepth, "maxHeight":maxHeight, "leafOrder":leafOrder};
	
	function setHeightRecursive(clstr, parentHeight, depth) {
		var bufLeafs = clstr.leafs;
		clstr.leafs = [];
		clstr.appearanceLeafs = [];
		clstr.depthFromBottom = null;
//		clstr.heightFromLeaf = null;

		clstr.height = parentHeight + clstr.length;	// ".height" changes only when clstr.remove().
		if(clstr.isBranch()) {
			clstr.depthFromTop = depth;
			if(maxDepth < depth) maxDepth = depth;
		
			var isEndBranch = true;
			var maxBottom2Top = -1;
			var maxHeightFromLeaf = -1;
			var maxLeafHeight = -1;
			var branchIndexs = [];
			for(var i=0, len=clstr.childs.length; i<len; i++) {
				isEndBranch = isEndBranch && clstr.childs[i].isLeaf();	// clstr is EndBranch if Child is all leaf.
				setHeightRecursive(clstr.childs[i], clstr.height, depth+1);

				clstr.leafs = clstr.leafs.concat(clstr.childs[i].leafs);
				clstr.appearanceLeafs = clstr.appearanceLeafs.concat(clstr.childs[i].appearanceLeafs);
				if(maxBottom2Top < clstr.childs[i].depthFromBottom+1) maxBottom2Top = clstr.childs[i].depthFromBottom+1
				if(maxLeafHeight < clstr.childs[i].maxLeafHeight) maxLeafHeight = clstr.childs[i].maxLeafHeight;
				branchIndexs.push(clstr.childs[i].leafIndex);
			}
//			clstr.heightFromLeaf = clstr.length + maxHeightFromLeaf;
			clstr.maxLeafHeight = maxLeafHeight;
			clstr.leafIndex = (branchIndexs[0] + branchIndexs[branchIndexs.length-1]) / 2;
			if(isEndBranch) {
				clstr.depthFromBottom = 0;
			} else if(clstr.depthFromBottom===null || clstr.depthFromBottom < maxBottom2Top){
				clstr.depthFromBottom = maxBottom2Top;
			}
		} else {
//			clstr.heightFromLeaf = clstr.length;
			clstr.maxLeafHeight = clstr.height;
			if(clstr.collapsedBranch == null) {
				clstr.leafs = [clstr];
			} else {
				clstr.leafs = bufLeafs;
			}
			clstr.appearanceLeafs = [clstr];
			clstr.leafIndex = leafIndex++;
			leafOrder.push(clstr);
			if(maxHeight < clstr.height) maxHeight = clstr.height;
		}
	}
}
function clearParseNewick(obj) {
	if(obj==null) return;

	var serials = Object.keys(obj.serial2branch);
	for(var i=0,len=serials.length; i<len; i++) {
		obj.serial2branch[serials[i]].clear();
	}
	obj.serial2branch = {};
	obj.order = [];
	obj.tree = null;
}

/**
	Data Holder of Cluster info.
	This instance can't JSON.stringify() because "parent" property is cyclic.
*/
var PhyloTreeCluster = function(childs, length, bootstrap) {
	this.serial = null;
	this.parent = null;
	this.childs = childs;	// "childs" is Array in Branch, but String(ID) in Leaf.
	this.length = length;
	this.bootstrap = bootstrap;
	this.leafs = [];	// Leaves under the cluster. In the case of Leaf, have itself. collapsed branches are unfolded. Order is the same as newick. 
	this.appearanceLeafs = [];	// "leafs" when a collapseed branch is treated as a leaf. It is used only for Canvas sliding animation.
	this.height = null;
//	this.heightFromLeaf = null;
	this.maxLeafHeight = null;
	this.depthFromTop = null;
	this.depthFromBottom = null;
	this.leafIndex = null;	// leaf:int(0 origin), branch:float based on Leaf's index
	this.otherInfo = {};
}
PhyloTreeCluster.prototype = {
  addChild: function(clstr) {
	if(this.childs === null) this.childs = [];
	clstr.parent = this;
	var count = this.childs.push(clstr);
	return this.childs[count-1];
  },
  isRoot: function() {
	return this.parent === null;
  },
  isBranch: function() {
	return (this.childs instanceof Array);
  },
  isLeaf: function() {
	return !(this.isBranch());
  },
  isBranchWithLeaf: function() {
	if(this.isLeaf()) return false;
	var withLeaf = false;
	for(var i=0,len=this.childs.length; i<len; i++) {
		if(this.isLeaf()) {
			withLeaf = true;
			break;
		}
	}
	return withLeaf;
  },
  remove: function() {
	if(this.isRoot()) return;

	/* After concatenating parent and childs, initialize myself. */ 
	var brothers = this.parent.childs;
	var newArray = [];
	for(var i=0,len=brothers.length; i<len; i++) {
		if(brothers[i] !== this) newArray.push(brothers[i]);
	}
	if(this.isLeaf()) {
		if(newArray.length === 1) {
//console.log("newArray.length === 1 Branch:" + newArray[0].isBranch());
			var gparent = this.parent.parent;
			for(var i=0,len=gparent.childs.length; i<len; i++) {
				if(gparent.childs[i].serial === this.parent.serial) {
//console.log("gparent.childs Index:" + i + "  serial:" + gparent.childs[i].serial + "->" + newArray[0].serial);
					newArray[0].parent = gparent;
					newArray[0].length += this.parent.length;
					gparent.childs[i] = newArray[0];
					this.parent.clear();
					break;
				}
			} 
		} else {
			this.parent.childs = newArray;
		}
	} else {
		if(newArray.length === 0) {
			// For example, newick as "((...));".
			this.parent.childs = this.childs;
			this.childs[0].parent = this.parent;
		} else {
			//TODO Merge child nodes of the removed node into parent node. 
		}
	}
	this.clear();
  },
  clearRecursively: function() {
	/* Clear tree recursively.
	   Since each Node is cross-referenced, it will not be erased unless clearRecursively() is executed, and a memory leak will occur.
	*/
	if(this.isBranch()) {
		for(var i=0,len=this.childs.length; i<len; i++) {
			this.childs[i].clearRecursively();
		}
		this.clear();
	} else {
		this.clear();
	}
  },
  clear: function() {
//var msg = "Clear:" + this.serial; if(this.isLeaf()) msg += "," + this.childs; console.log(msg);
	this.parent = null;
	this.childs = null;
	this.leafs = [];
	this.appearanceLeafs = [];
	this.otherInfo = {};

	if('collapsedBranch' in this) this.collapsedBranch = null;
	if('alternativeLeaf' in this) this.alternativeLeaf = null;	// Normally, this is not done.
  },
  getNewick: function(leafNames) {
	thisObj = this;
	return scanTree(this) + ";";

	function scanTree(clstr) {
		var newick;
		if(clstr.isBranch()) {
			var nwks = [];
			for(var i=0,len=clstr.childs.length; i<len; i++) {
				nwks.push(scanTree(clstr.childs[i]));
			}
			newick = "(" + nwks.join(",") + ")";
			if(clstr !== thisObj) newick += ":" + thisObj.getFloatPrecisionStr(clstr.length, 6);
		} else {
			var name = clstr.childs;
			if(leafNames != null) name = leafNames[clstr.leafIndex];
			newick = name + ":" + thisObj.getFloatPrecisionStr(clstr.length, 6);
		}
		return newick;
	}
  },
  getFloatPrecisionStr: function(num, digits) {
	if(num == 0) return '0';

	var str = '';
	if(num >= 1) {
		str = parseFloat(num).toFixed(5);
	} else {
		var longNumStr = parseFloat(num).toFixed(20);
		var currentDigit = 0;
		var startDigits = false
		for(var i=0,len=longNumStr.length; i<len; i++) {
			var ch = longNumStr.substr(i, 1);
			str += ch;
			if(startDigits) {
				currentDigit++;
				if(currentDigit >= digits) break;
			} else if(/[1-9]/.test(ch)) {
				startDigits = true;
			}
		}
	}
	return str.replace(/0+$/, '');
  }
}
