/*
 * phyloTreeCreater.js
 * http://tasuke.dna.affrc.go.jp/
 *
 * Author: Jungsok Kim, Ryutaro Itoh, Norio Tabei
 *
 * Copyright (c) 2013 National Institute of Agrobiological Sciences
 *
 */
var PhyloTreeCreater = function(cvs) {
/*
	cvs:	Canvas object
	rowHeight:
	lengthUnit:
	tree:	result from parseNewick().tree
	order:	result from parseNewick().order
	maxDepth:	result from parseNewick().maxDepth
	maxHeight:	result from parseNewick().maxHeight
	type:	cladogram/phyrogram
	correctMethod:	none/sqrt/asec/log
	
*/
	/* The following are system-managed variables and should not be changed by user. */
	this.cvs = cvs;
	this.ctx = null;
	if(this.cvs != null) this.ctx = this.cvs.getContext('2d');
	this.tree = null;
	this.order = null;
	this.maxDepth = null;
	this.maxHeight = null;
	this.pow2MaxHeight = null;	// Square(pow2) of max height
	this.avgHeight = null;	// Average of branch height
	this.varHeight = null;	// Variance of branch height
	this.serial2branch = {};	// Dynamic hash that change with branch expand/collapse.
	this.name2leaf = {};	// Static hash that does not change with branch expand/collapse.
	this.collapsedBranchSerial = {};	// Collapsed original branch
	this.lastChangedBranch = null;

//	this.oriMaxDepth = null;
	this.oriMaxHeight = null;

	this.row2Branch = {};		// rowIndex -> PhyloTreeCluster
	this.row2CollapsedBranch = {};	// rowIndex -> PhyloTreeCluster
	this.col2Branch = {};		// xIndex(by this.lineMargin) -> PhyloTreeCluster
	this.lineMargin = 2;	// Resolution when creating Clickable Map

	this.undoTrimImage = null;	// Temporarily cache(ImageData) the original image to restore branch highlight.
	this.undoTrimImageTop = null;	// top pos of undoTrimImage

	this.maxSerial = null;
	this.lengthUnit = 10;	// treeWidth / maxHeight
	this.branchHighlightOffset = 1;	// Offset that adjusts branchHighlight height for rowHeight < hLineOffset.

	/* The following are variables that user changes */
	this.rowHeight = 10;
	this.hLineOffset = 7;	// Horizontal line offset for each row.

	this.type = "phylogram";	// phylogram/cladogram
	this.correctMethod = "none";

	if(this.ctx != null) this.ctx.font = String(this.rowHeight) + "px 'Helvetica'";
	this.treeWidth = 400;	// Canvas area where tree is drawn
	this.tMargin = 10;
	this.bMargin = 10;
	this.lMargin = 10;
	this.rMargin = 10;
	this.lineWidth = 2;
	this.lineWidthMouseOver = 2;
	this.lineWidthCollapsedLeaf = 2;
	this.bgColor = "white";
	this.lineColor = "black";
	this.mouseOverColor = "red";
	this.collapsedColor = "blue";
	this.auxLineColor = "#eaeaea";
	this.branchHighlightColor = "rgba(255,0,0,0.1)";	// rgba(255,0,0,0.1)
	this.branchMouseOverColor = "rgba(0,255,0,0.2)";	// rgba(0,220,255,0.25) > rgba(0,255,110,0.25)

	this.headerString = "";
	
	// Switch
	this.flgDrawLeafName = true;
	this.flgDrawAuxLine = true;
}
PhyloTreeCreater.prototype = {
  isTreeUsing: function() {
	if(this.tree !== null) {
		return true;
	} else {
		return false;
	}
  },
  initTree: function() {
	if(this.tree != null) {
		this.expandAllBranch();	//TODO Unnecessary updateTree() is executed.
		this.clearTreeRecursively();
//		this.tree.clearRecursively();
	}
	this.tree = null;
	this.order = null;
	this.maxDepth = null;
	this.maxHeight = null;
	this.pow2MaxHeight = null;
	this.avgHeight = null;
	this.varHeight = null;
	this.serial2branch = {};
	this.name2leaf = {};
	this.collapsedBranchSerial = {};
	this.lastChangedBranch = null;

//	this.oriMaxDepth = null;
	this.oriMaxHeight = null;

	this.row2Branch = {};
	this.row2CollapsedBranch = {};
	this.col2Branch = {};
  },
  clearTreeRecursively: function() {
	var serials = Object.keys(this.serial2branch);
	for(var i=0,len=serials.length; i<len; i++) {
		this.serial2branch[serials[i]].clear();
	}
  },
  parseNewick: function(newickStr) {
	// require newickPaser.js
	var treeResult = parseNewick(newickStr);
	this.setParsedNewick(treeResult);	// initTree() is executed in this.
  },
  setParsedNewick: function(treeResult) {
	// set newickPaser.js result
	this.initTree();

	this.tree = treeResult['tree'];
	this.order = treeResult['order'];
	this.maxDepth = treeResult['maxDepth'];
		if(this.tree.length!=null && this.tree.length>0) this.maxDepth++;	// For root node height
	this.maxHeight = treeResult['maxHeight'];
	this.pow2MaxHeight = this.maxHeight * this.maxHeight;
	this.serial2branch = treeResult['serial2branch'];

//	this.oriMaxDepth = this.maxDepth;
	this.oriMaxHeight = this.maxHeight;
//console.log("oriMaxHeight:" + this.oriMaxHeight);

	this.avgHeight = 0;
	var total = 0;
	for(var serial in this.serial2branch) {
		var branch = this.serial2branch[serial];
		if(branch.isLeaf()) {
			this.name2leaf[branch.childs] = branch;
		}
		else {
			this.avgHeight += branch.height;
			total++;
		}
		serial = Number(serial);
		if(this.maxSerial===null || this.maxSerial < serial) this.maxSerial = serial;
	}
	this.avgHeight = this.avgHeight / total;

	this.varHeight = 0;
	var serials = Object.keys(this.serial2branch);
	for(var i=0,len=serials.length; i<len; i++) {
		var serial = serials[i];
		var branch = this.serial2branch[serial];
//		this.varHeight += Math.pow(branch.height - this.avgHeight, 2);
		if(branch.isBranch()) this.varHeight += Math.pow(branch.height - this.avgHeight, 2);
	}
	this.varHeight = this.varHeight / total;

  },
  // After parsing Newick, you can use Newick control characters in the name.
  changeLeafName: function(names) {
	if(!(names instanceof Array) || names.length !== this.order.length) {
		console.log("Array lengths are different. leaves:" + this.order.length + " names:" + names.length);
		return false;
	}

	var name2leaf = {};
	for(var i=0,len=this.order.length; i<len; i++) {
		var clstr = this.order[i];
//		var oriName = clstr.childs;
		clstr.childs = names[i];
		name2leaf[names[i]] = clstr;
	}
	this.name2leaf = name2leaf;
	return true;
  },
  correct: function(val) {
	if(this.correctMethod === "asec") {
		return  this.asec(val);
	} else if(this.correctMethod === "asec2") {
		return  this.asec(this.asec(val));
	} else if(this.correctMethod === "sqrt") {
		return Math.sqrt(val);
	} else if(this.correctMethod === "pow") {
		return Math.pow(val, 3) / this.pow2MaxHeight;
//		return val * val / this.maxHeight;
/*
		var treeHeight = this.maxHeight + 0.001 * this.maxHeight;
		var lso = 0.001 * treeHeight;
		var rate = (Math.log(val + lso) - Math.log(lso)) / (Math.log(treeHeight + lso) - Math.log(lso));
		var h = rate * this.maxHeight;
console.log("height=" + val + "/" + treeHeight + "; Offset=" + "0.001" + "; res=" + rate + " => " + h + "*" + this.lengthUnit + " => " + (h * this.lengthUnit) + "/" + this.treeWidth);
		return h;
*/
	} else if(this.correctMethod === "cdf") {
//		return this.lognormalcdf(val);
		return this.normalcdf(val);
	} else {
		return val;
	}
  },
  normalcdf: function(x) {
    var z = (x - this.avgHeight)/Math.sqrt(2 * this.varHeight);
    var t = 1/(1+0.3275911 * Math.abs(z));
    var a1 =  0.254829592;
    var a2 = -0.284496736;
    var a3 =  1.421413741;
    var a4 = -1.453152027;
    var a5 =  1.061405429;
    var erf = 1-(((((a5*t + a4)*t) + a3)*t + a2)*t + a1)*t*Math.exp(-z*z);
    var sign = 1;
    if(z < 0) {
        sign = -1;
    }
    return 0.5*(1+sign*erf);
  },
/*
  lognormalcdf: function(x) {
    var mu = this.avgHeight;
    var sigma2 = this.varHeight;
    if (x < 0)
      return 0;
    return 0.5 +
        (0.5 * this.erf((Math.log(x + 1) - mu) / Math.sqrt(2 * sigma2)));
  },
  erf: function(x) {

    // constants
    var p  =  0.3275911;
    var a1 =  0.254829592;
    var a2 = -0.284496736;
    var a3 =  1.421413741;
    var a4 = -1.453152027;
    var a5 =  1.061405429;

    var t = 1 /(1 + p * Math.abs(x));
    var y = 1 - (((((a5 * t + a4) * t) + a3) * t + a2) * t + a1) * t * Math.exp(-x * x);

    return (x > 0) ? y : -y;
  },
*/
  asec: function(val) {
	return  Math.acos(1/(val + 1));
  },
  getHeightByX: function(x) {
	var height = null;
	if(this.correctMethod == null || this.correctMethod === "" || this.correctMethod === "none") {
		height = (x-this.lMargin+1) / this.treeWidth * this.maxHeight;
	}
	return height;
  },
  adjustCanvasSizeAuto: function() {
//	this.cvs.width = this.treeWidth + this.lMargin + this.rMargin;
	this.cvs.width = this.treeWidth;
	if(this.lMargin >= 0) this.cvs.width += this.lMargin;
	if(this.rMargin >= 0) this.cvs.width += this.rMargin;

	var treeHeight = this.order.length * this.rowHeight;
//	this.cvs.heigh = treeHeight + this.tMargin + this.bMargin;
	this.cvs.heigh = treeHeight;
	if(this.tMargin >= 0) this.cvs.heigh += this.tMargin;
	if(this.bMargin >= 0) this.cvs.heigh += this.bMargin;

	this.updateLengthUnit();
/*
	if(this.type === "cladogram") {
		this.lengthUnit = (this.treeWidth - this.lineWidth/2) / (this.maxDepth + 1);
	} else {
		this.lengthUnit = (this.treeWidth - this.lineWidth/2) / this.correct(this.maxHeight);
	}
*/
	this.branchHighlightOffset = this.hLineOffset - this.rowHeight/2;

	this.cvs.setAttribute("width", this.cvs.width);
	this.cvs.setAttribute("height", this.cvs.heigh);
//console.log("Check:" + this.cvs.width + "," + this.cvs.heigh + " <= " + this.treeWidth + "+" + this.lMargin + "+" + this.rMargin);
  },
  updateLengthUnit: function() {
	if(this.type === "cladogram") {
		this.lengthUnit = (this.treeWidth - this.lineWidth/2) / (this.maxDepth + 1);
	} else {
		this.lengthUnit = (this.treeWidth - this.lineWidth/2) / this.correct(this.maxHeight);
	}
  },
  clear: function() {
	var ctx = this.ctx;
	ctx.clearRect(0, 0, ctx.canvas.clientWidth, ctx.canvas.clientHeight);
  },
  draw: function() {
	this.row2Branch = {};
	this.col2Branch = {};
	this.row2CollapsedBranch = {};

	if(this.lastChangedBranch != null) this.drawBranchHighlight(this.lastChangedBranch);

	var thisObj = this;	
	this.ctx.save();
	this.ctx.translate(this.lMargin, this.tMargin);	// Set origin at the margin position
	scanTree(this.tree);
	this.ctx.restore();	// reset margin
/*
	if(this.headerString) {
		this.ctx.save();
		this.ctx.textAlign = "start";
		this.ctx.fillText(this.headerString, 2, 10, this.treeWidth + this.lMargin + this.rMargin - 4);
		this.ctx.restore();
	}
	this.drawScaleBar();
*/

	function scanTree(clstr) {
		var h = 0;
		if(clstr.isBranch()) {
			for(var i=0,len = clstr.childs.length; i<len; i++) {
				scanTree(clstr.childs[i]);
			}
		}
		clstr.y = thisObj.drawBranch(clstr);

		return clstr.y
	}
  },
  updateTree: function() {
	var stat = updateDepthParseNewickTree(this.tree);
	this.maxDepth = stat['maxDepth'];
	this.maxHeight = stat['maxHeight'];
	this.order = stat['leafOrder'];
	this.row2Branch = {};	// rowIndex -> PhyloTreeCluster. Updated in draw().
	this.row2CollapsedBranch = {};	// rowIndex -> PhyloTreeCluster. Updated in draw().
	this.col2Branch = {};	// Updated in draw().
  },
  updateTreeUpstreamFromBranch: function(myself) {
	var clstr = myself.parent;
	while(clstr != null) {
		clstr.appearanceLeafs = [];
		for(var i=0, len=clstr.childs.length; i<len; i++) {
			clstr.appearanceLeafs = clstr.appearanceLeafs.concat(clstr.childs[i].appearanceLeafs);
		}
		clstr = clstr.parent;
	}
  },
/*
  getLeafHeight: function(clstr) {
	return clstr.leafIndex * this.rowHeight + this.hLineOffset;
//	return clstr.leafIndex * this.rowHeight + this.rowHeight/2;
  },
*/
  getNameOrder: function() {
	var array = [];
	for(var i=0,len=this.order.length; i<len; i++) {
		array.push(this.order[i].childs);
	}
	return array;
  },
  getAllPotentialNameOrder: function() {
	var array = [];
	for(var i=0,len=this.order.length; i<len; i++) {
		if(this.order[i].collapsedBranch != null ) {
			var potentialLeafs = this.order[i].collapsedBranch.leafs;
			for(var j=0,jLen=potentialLeafs.length; j<jLen; j++) {
				array.push(potentialLeafs[j].childs);
			}
		} else {
			array.push(this.order[i].childs);
		}
	}
	return array;
  },
  getCollapsedNameOrder: function() {
	var array = [];
	for(var i=0,len=this.order.length; i<len; i++) {
		if(this.order[i].collapsedBranch != null ) {

			var potentialLeafs = this.order[i].collapsedBranch.leafs;
			var subArr = [];
			for(var j=0,jLen=potentialLeafs.length; j<jLen; j++) {
				subArr.push(potentialLeafs[j].childs);
			}
			array.push(subArr);
		} else {
			array.push(this.order[i].childs);
		}
	}
	return array;
  },
  getCollapsedLeafsByName: function(name) {
	var res = [];
	var serials = Object.keys(this.collapsedBranchSerial);
	for(var i=0,len=serials.length; i<len; i++) {
		var branch = this.serial2branch[serials[i]];
		if(branch.alternativeLeaf.childs === name) {
			res = branch.leafs;
			break;
		}
	}
	return res;
  },
  drawScaleBar: function() {
	if(this.type === 'cladogram') return;

	var unit = this.getScaleUnit();
	var top = this.tMargin + this.getNameOrder().length * this.rowHeight + this.bMargin/2;
	var right = this.lMargin + (this.correct(unit) * this.lengthUnit);
	this.drawLine(this.lMargin, top, right, top, 'black', 1);
	this.ctx.fillText(String(unit), right + 2, top);
  },
  getScaleUnit: function() {
//	var units = [10000, 5000, 1000, 500, 100, 50, 10, 5, 1, 0.5, 0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001, 0.00005, 0.00001];
	var units = [10000, 1000, 100, 10, 1, 0.1, 0.01, 0.001, 0.0001, 0.00001];
	var unit;
	for(var i=0,len=units.length; i<len; i++) {
		if(this.maxHeight/units[i] >= 1) {
			unit = units[i];
			break;
		}
	}
	return unit;
  },
  drawBranch: function(clstr, color, lineWidth) {
	if(color == null) color = this.lineColor;	// if color=="undefined" then true
	if(lineWidth == null) lineWidth = this.lineWidth;	// if lineWidth=="undefined" then true

	// The only difference between cladgram and phylogram is height(x) calculation.
	var parentX = 0;
	if(this.type === "cladogram") {
		var depth = clstr.depthFromBottom;
		if(depth === null) depth = -1;
		x = (this.maxDepth - depth) * this.lengthUnit;
		if(!clstr.isRoot()) parentX = (this.maxDepth - clstr.parent.depthFromBottom) * this.lengthUnit;
	} else {
		x = this.correct(clstr.height) * this.lengthUnit;
		if(!clstr.isRoot()) parentX = this.correct(clstr.parent.height) * this.lengthUnit;
	}

	var horizY;
	if(clstr.isBranch()) {
		var len = clstr.childs.length;
		var top = clstr.childs[0].y;
		var bottom = clstr.childs[len-1].y;
		horizY = (top + bottom)/2;
		if(parentX < x) {
			this.drawLine(parentX + lineWidth/2, horizY, x, horizY, color, lineWidth);
			if(!clstr.isRoot()) this.addBranchMap(new BranchPartRect(clstr, this.lineMargin, parentX + lineWidth/2, horizY, x, horizY));
		}
		this.drawVerticalLine(clstr, color, lineWidth);
		if(!clstr.isRoot()) this.addBranchMap(new BranchPartRect(clstr, this.lineMargin, x, top, x, bottom));
	} else {
		horizY = clstr.leafIndex * this.rowHeight + this.hLineOffset;
		var horizColor = color;
		var horizLineWidth = lineWidth;
		if(clstr.collapsedBranch != null) {
			horizColor = this.collapsedColor;
			horizLineWidth = this.lineWidthCollapsedLeaf;
			this.addCollapsedBranchMap(new BranchPartRect(clstr, this.lineMargin, parentX + lineWidth/2, horizY, x, horizY));
		}
		this.drawLine(parentX + lineWidth/2, horizY, x, horizY, horizColor, horizLineWidth);

		// draw Name & AuxLine
		var textX = x;
		if(this.type !== "cladogram" && this.flgDrawAuxLine) {
			this.drawLine(x+lineWidth, horizY, this.treeWidth, horizY, this.auxLineColor, lineWidth);
			textX = this.treeWidth;
		}
		if(this.flgDrawLeafName) this.drawLeafName(clstr, textX, horizY);

	}
	return horizY;
/*		
	var h = 0;
	if(this.type === "cladogram") {
		h = this.drawBranchClado(clstr, color, lineWidth);
	} else {
		h = this.drawBranchPylo(clstr, color, lineWidth);
	}
	return h;
*/
  },
  drawMouseOverBranch: function(clstr) {
	var topLeafIndex = clstr.appearanceLeafs[0].leafIndex;
	this.undoTrimImageTop = this.tMargin+topLeafIndex*this.rowHeight + this.branchHighlightOffset;
	this.undoTrimImage = this.ctx.getImageData(
		0,
		this.undoTrimImageTop,
		this.cvs.width,
		clstr.appearanceLeafs.length * this.rowHeight + 1	// Trim 1px large just in case
	);
	this.drawBranchHighlight(clstr, this.branchMouseOverColor);

	this.ctx.save();
	this.ctx.translate(this.lMargin, this.tMargin);	// Set origin at the margin position

	if(clstr.collapsedBranch == null) {
		this.drawVerticalLine(clstr, this.mouseOverColor, this.lineWidthMouseOver);	
		this.drawParentLine(clstr, this.mouseOverColor, this.lineWidthMouseOver);
	}	
	this.ctx.restore();
  },
  undoMouseOverBranch: function() {
	if(this.undoTrimImage != null) {
		this.ctx.putImageData(this.undoTrimImage, 0, this.undoTrimImageTop);
	}
/*
	this.ctx.save();
	this.ctx.translate(this.lMargin, this.tMargin);	// Set origin at the margin position
	
	this.drawVerticalLine(clstr, this.bgColor, this.lineWidthMouseOver);
	this.drawParentLine(clstr, this.bgColor, this.lineWidthMouseOver);

	this.drawVerticalLine(clstr, this.lineColor, this.lineWidthMouseOver);	
	this.drawParentLine(clstr);
	
	this.ctx.restore();
*/
  },
/*
  drawBranchClado: function(clstr, color, lineWidth) {
	var len = clstr.childs.length;
	var top = clstr.childs[0].y;
	var bottom = clstr.childs[len-1].y;
	var x = (this.maxDepth - clstr.depthFromBottom) * this.lengthUnit;

	this.drawVerticalLine(clstr, color, lineWidth);
		if(!clstr.isRoot()) this.addBranchMap(new BranchPartRect(clstr, this.lineMargin, x, top, x, bottom));
	for(var i=0; i<len; i++) {
		var child = clstr.childs[i];
		if(clstr.childs[i].isBranch()) {
			var right = x + (clstr.depthFromBottom - child.depthFromBottom) * this.lengthUnit;
			this.drawLine(x, child.y, right, child.y, color, lineWidth);
			this.addBranchMap(new BranchPartRect(child, this.lineMargin, x, child.y, right, child.y));
		} else {
			var horizColor = color;
			var horizLineWidth = lineWidth;
			if(child.collapsedBranch != null) {
				horizColor = this.collapsedColor;
				horizLineWidth = this.lineWidthCollapsedLeaf;
				this.addCollapsedBranchMap(new BranchPartRect(child, this.lineMargin, x, child.y, this.cvs.width, child.y));
			} else {
				if(child.isBranch()) this.addBranchMap(new BranchPartRect(child, this.lineMargin, x, child.y, this.cvs.width, child.y));
			}
			this.drawLine(x, child.y, this.treeWidth, child.y, horizColor, horizLineWidth);
			
			if(clstr.childs[i].isLeaf()) {
				if(this.flgDrawLeafName) this.drawLeafName(child, this.treeWidth, child.y);
			}
		}
	}
	return (top + bottom) / 2;
  },
  drawBranchPylo: function(clstr, color, lineWidth) {
	var len = clstr.childs.length;
	var top = clstr.childs[0].y;
	var bottom = clstr.childs[len-1].y;
	var x = this.correct(clstr.height) * this.lengthUnit;

	this.drawVerticalLine(clstr, color, lineWidth);
		if(!clstr.isRoot()) this.addBranchMap(new BranchPartRect(clstr, this.lineMargin, x, top, x, bottom));
	for(var i=0; i<len; i++) {
			var child = clstr.childs[i];
			var right = this.correct(child.height) * this.lengthUnit;
			var horizColor = color;
			var horizLineWidth = lineWidth;
			if(clstr.childs[i].collapsedBranch != null) {
				horizColor = this.collapsedColor;
				horizLineWidth = this.lineWidthCollapsedLeaf;
				this.addCollapsedBranchMap(new BranchPartRect(child, this.lineMargin, x, child.y, right, child.y));
			} else {
				if(child.isBranch()) this.addBranchMap(new BranchPartRect(child, this.lineMargin, x, child.y, right, child.y));
			}
			this.drawLine(x + lineWidth/2, child.y, right, child.y, horizColor, horizLineWidth);
			
			if(child.isLeaf()) {
				var textX = right;
				if(this.flgDrawAuxLine) {
					this.drawLine(right+lineWidth, child.y, this.treeWidth, child.y, this.auxLineColor, lineWidth);
					textX = this.treeWidth;
				}
				if(this.flgDrawLeafName) this.drawLeafName(child, textX, child.y);
			}
	}
	return (top + bottom)/2;
  },
*/
  drawVerticalLine: function(clstr, color, lineWidth) {
	var len = clstr.childs.length;
	var top = clstr.childs[0].y;
	var bottom = clstr.childs[len-1].y;
	var x;
	if(this.type === "phylogram") {
		x = this.correct(clstr.height) * this.lengthUnit;
	} else {
		x = (this.maxDepth - clstr.depthFromBottom) * this.lengthUnit;
	}

	this.drawLine(x, top, x, bottom, color, lineWidth);
  },
  drawParentLine: function(clstr, color, lineWidth) {
	if(clstr.parent === null) return;

	if(color == null) color = this.lineColor;	// if color=="undefined" then true
	if(lineWidth == null) lineWidth = this.lineWidth;	// if lineWidth=="undefined" then true

	var parent = clstr.parent;
	for(var i=0,len=parent.childs.length; i<len; i++) {
		if(clstr === parent.childs[i]) {
			// Same instance
			var y = parent.childs[i].y
			var x1, x2;
			if(this.type === "cladogram") {
				var x1 = (this.maxDepth - parent.depthFromBottom) * this.lengthUnit;
				var x2 = x1 + (parent.depthFromBottom - parent.childs[i].depthFromBottom) * this.lengthUnit;
			} else {
				var x1 = this.correct(parent.height) * this.lengthUnit;
				var x2 = this.correct(parent.childs[i].height) * this.lengthUnit;
			}
			this.drawLine(x1 + lineWidth/2, y, x2, y, color, lineWidth);
		}
	}

  },
  drawLine: function(x1, y1, x2, y2, color, lineWidth) {
	var ctx = this.ctx;
	
	var halfWidth = lineWidth/2;
	
	ctx.fillStyle = color;
	ctx.fillRect(x1-halfWidth, y1-halfWidth, x2-x1+lineWidth, y2-y1+lineWidth);	
/*
	ctx.beginPath();
	ctx.moveTo(x1, y1);
	ctx.lineTo(x2, y2);
	ctx.strokeStyle = color;
	ctx.lineWidth = lineWidth;
	ctx.closePath();
	ctx.stroke();
*/
  },
  drawLeafName: function(clstr, x, y, color) {
	if(clstr.parent === null) return;
	
	if(color == null) {
		color = this.lineColor;	// if color=="undefined" then true
		if(clstr.collapsedBranch != null) color = this.collapsedColor;
	}
	this.ctx.fillStyle = color;
	this.ctx.textAlign = 'start';
	this.ctx.fillText(this.getLeafName(clstr), x, y+(this.rowHeight/2));
  },
  drawBranchHighlight: function(clstr, color) {
	if(color == null) color = this.branchHighlightColor;

	var l;
	var arrowL = null;
	if(this.type === 'phylogram') {
		if(clstr.isBranch()) {
			l = this.correct(clstr.height) * this.lengthUnit - this.lineWidth/2 - 1;
			arrowL = this.correct(clstr.parent.height) * this.lengthUnit - this.lineWidth/2 + 3;
		} else {
			l = this.correct(clstr.parent.height) * this.lengthUnit - this.lineWidth/2;
		}
	} else {
		if(clstr.isBranch()) {
			l = (this.maxDepth - clstr.depthFromBottom) * this.lengthUnit - 2;
			arrowL = (this.maxDepth - clstr.parent.depthFromBottom) * this.lengthUnit + 3;
		} else {
			l = (this.maxDepth - clstr.parent.depthFromBottom) * this.lengthUnit - 2;
		}
	}
	var t = clstr.appearanceLeafs[0].leafIndex * this.rowHeight + this.branchHighlightOffset;

	this.ctx.save();
	this.ctx.translate(this.lMargin, this.tMargin);
	this.ctx.fillStyle = color;
/*
	var w = this.treeWidth - l + 1;
	var h = (clstr.appearanceLeafs[clstr.appearanceLeafs.length-1].leafIndex - clstr.appearanceLeafs[0].leafIndex + 1) * this.rowHeight;
	this.ctx.fillRect(l, t, w, h);
*/
	var r = this.treeWidth;
	var b = (clstr.appearanceLeafs[clstr.appearanceLeafs.length-1].leafIndex + 1) * this.rowHeight + this.branchHighlightOffset;
	this.ctx.beginPath();
	this.ctx.lineTo(l, t);
	this.ctx.lineTo(r, t);
	this.ctx.lineTo(r, b);
	this.ctx.lineTo(l, b);
	if(arrowL !== null) this.ctx.lineTo(arrowL, clstr.leafIndex * this.rowHeight + this.hLineOffset);
	this.ctx.closePath();
	this.ctx.fill();

	this.ctx.restore();
  },
  getLeafName: function(clstr) {
	if(clstr.collapsedBranch != null) {
		return clstr.childs + " +" + String(clstr.leafs.length - 1);
//		return clstr.childs + " +" + String(clstr.memberNum - 1);
	} else {
		return clstr.childs;
	}
  },
  addBranchMap: function(branchPart) {
	if(branchPart.y1 === branchPart.y2) {
		// Horizontal line
		var rowStr = this.convY2row(branchPart.y1);
		if(!(rowStr in this.row2Branch)) this.row2Branch[rowStr] = [];
		this.row2Branch[rowStr].push(branchPart);
	} else {
		// Vertical line
		var colStr = this.convX2col(branchPart.x1);
		if(!(colStr in this.col2Branch)) this.col2Branch[colStr] = [];
		this.col2Branch[colStr].push(branchPart);
	}
  },
  addCollapsedBranchMap: function(branchPart) {
	var rowStr = this.convY2row(branchPart.y1);
	if(!(rowStr in this.row2CollapsedBranch)) this.row2CollapsedBranch[rowStr] = [];
	this.row2CollapsedBranch[rowStr].push(branchPart);
  },
  convX2col: function(x) {
	return String(Math.floor(x / (this.lineMargin * 2)));
  },
  convY2row: function(y) {
	return String(Math.floor(y / this.rowHeight));
  },
  collisionRect: function(a, b)	{
   	const horizontal = (b.l <= a.r) && (a.l <= b.r);
   	const vertical = (b.t <= a.b) && (a.t <= b.b);
   	return (horizontal && vertical);

//	return (Math.abs(a.x - b.x) < a.w/2 + b.w/2) && (Math.abs(a.y - b.y) < a.h/2 + b.h/2);
  },
  getMouseOverBranch: function(oriX, oriY) {
	var x = oriX - this.lMargin;
	var y = oriY - this.tMargin;
//	var mouseRect = {"x":x, "y":y, "w":2, "h":2};
	var mouseRect = {"l":x, "t":y, "r":x+1, "b":y+1};

	var rowStr = this.convY2row(y);
	var colStr = this.convX2col(x);

	// Highest priority: Collepsed Branch check
	if(rowStr in this.row2CollapsedBranch) {
		var branchPart = this.row2CollapsedBranch[rowStr][0];
		if(this.collisionRect(mouseRect, branchPart.getCollisionRect())) {
			return branchPart.branch;
		}
	}
	
	// Vertical line
	if(colStr in this.col2Branch) {
		for(var i=0,len=this.col2Branch[colStr].length; i<len; i++) {
			var branchPart = this.col2Branch[colStr][i];
			if(this.collisionRect(mouseRect, branchPart.getCollisionRect())) {
//console.log("Vert: " + JSON.stringify(branchPart.getCollisionRect()));
				return branchPart.branch;
			}
		}
	}

	// Horizontal line
	if(rowStr in this.row2Branch) {
		for(var i=0,len=this.row2Branch[rowStr].length; i<len; i++) {
			var branchPart = this.row2Branch[rowStr][i];
			if(this.collisionRect(mouseRect, branchPart.getCollisionRect())) {
//console.log("Horiz: " + JSON.stringify(branchPart.getCollisionRect()));
				return branchPart.branch;
			}
		}
	}
	return null;
  },
  /**
  * Be sure to execute updateTree() after execution this.
  */
  collapseBranch: function(clstr) {
	if(clstr.parent === null || clstr.isLeaf()) return;	// root branch does not collapse

	this.collapsedBranchSerial[String(clstr.serial)] = true;

	var topLeaf = clstr.leafs[0];	
//	var topLeaf = scanTopTree(clstr);	// Obtain representative leaf of cluster.
	var name = topLeaf.childs;
	var length = topLeaf.height - clstr.height + clstr.length;
	var newLeaf = new PhyloTreeCluster(name, length, null);
	var parent = clstr.parent;
	newLeaf.serial = ++this.maxSerial;
	newLeaf.parent = parent;
	newLeaf.leafs = clstr.leafs;
	newLeaf.appearanceLeafs = [newLeaf];	// Since collapsed branche is leaf, register myself.
//	newLeaf.memberNum = clstr.memberNum;	// memberNum is reaggregated with updateDepthParseNewickTree(), but it should be left in the Collapsed Branch so that it is not set to 0.
	newLeaf.collapsedBranch = clstr;	// add new property
	newLeaf.height = topLeaf.height;
	newLeaf.maxLeafHeight = topLeaf.height;	//TODO topLeaf.maxLeafHeight?
	newLeaf.y = clstr.appearanceLeafs[0].y;
	this.serial2branch[newLeaf.serial] = newLeaf;
	parent.appearanceLeafs = [];
	for(var i=0,len=parent.childs.length; i<len; i++) {
		if(clstr === parent.childs[i]) {
//			this.clear();
			parent.childs[i] = newLeaf;
			clstr.alternativeLeaf = newLeaf;	// add new property. Replaced collapse leaf
			break;
		}
	}
	this.lastChangedBranch = newLeaf;
	this.updateTreeUpstreamFromBranch(newLeaf);
//this.updateTree();
	return  this.collapsedBranchSerial;
  },
  /**
  * Be sure to execute updateTree() after execution this.
  */
  expandBranch: function(leaf) {
	if(leaf.collapsedBranch == null) return;

	delete this.collapsedBranchSerial[String(leaf.collapsedBranch.serial)];
	
	var parent = leaf.parent;
	parent.appearanceLeafs = [];
	for(var i=0,len=parent.childs.length; i<len; i++) {
		if(leaf === parent.childs[i]) {
			delete leaf.collapsedBranch.alternativeLeaf;	// delete prototype property
			parent.childs[i] = leaf.collapsedBranch;
			this.lastChangedBranch = leaf.collapsedBranch;

			// destruct prototype object
			// Remove reference just in case.
//console.log("RemoveCollapseLeaf:" + leaf.serial);
			delete this.serial2branch[leaf.serial];
			leaf.collapsedBranch = null;
			leaf.clear();
//			break;
		}
	}
	this.updateTreeUpstreamFromBranch(leaf);
//this.updateTree();
	return  this.collapsedBranchSerial;
  },
  expandAllBranch: function() {
	var serials = Object.keys(this.collapsedBranchSerial);
	for(var i=0,len=serials.length; i<len; i++) {
		var collapsedBranch = this.serial2branch[serials[i]].alternativeLeaf;
		var dummy = this.expandBranch(collapsedBranch);
	}
	this.lastChangedBranch = null;
	this.updateTree();

	return this.collapsedBranchSerial;	// Always empty hash
  },
  autoCollapseBySerials: function(serials) {
	if(serials == null || !(serials instanceof Array)) return;

	for(var i=0,len=serials.length; i<len; i++) {
		var branch = this.serial2branch[serials[i]];
		if(branch != null) {
			if(branch.isBranch()) this.collapseBranch(branch);
		}
	}
	this.lastChangedBranch = null;
	this.updateTree();

	return this.collapsedBranchSerial; 
  },
  autoCollapseByHeight: function(threshold) {
	if(threshold==null || threshold==0) return this.collapsedBranchSerial;

/*
	var changed = false;
	for(var i=0, len=this.tree.leafs.length; i<len; i++) {
		var clstr = this.tree.leafs[i];	// Leaf
//var startLeaf = clstr.childs;
		var heightFromLeaf = 0;
		while(!clstr.isRoot()) {
			heightFromLeaf += clstr['length'];
			if(clstr.isBranch()) {
//				if((clstr.isBranchWithLeaf() || clstr.parent.isRoot()) && heightFromLeaf >= threshold) {
				if(heightFromLeaf >= threshold) {
					if(!this.collapsedBranchSerial[String(clstr.serial)]) {
						this.collapseBranch(clstr);
//console.log("Collapsed:" + startLeaf + ", " + heightFromLeaf + "/" + threshold + " => " + clstr.serial);
						changed = true;
					}
					break;
				}
			}
			clstr = clstr.parent;
		}
	}
	if(changed) this.updateTree();
	this.lastChangedBranch = null;
	return this.collapsedBranchSerial;
*/

/*
	var thisObj = this;
	var autoCollapseOk = false;
	scanTree(this.tree, threshold);
	this.updateTree();
	this.lastChangedBranch = null;
	return this.collapsedBranchSerial;
	
	function scanTree(clstr, threshold) {
		if(clstr.isBranch()) {
			autoCollapseOk = true;
			for(var i=0,len=clstr.childs.length; i<len; i++) {
				scanTree(clstr.childs[i], threshold);
			}
console.log("Branch:" + clstr.serial + ", " + autoCollapseOk + ", " + clstr.isRoot() + ", " + (thisObj.oriMaxHeight - clstr.height) + " >= " + threshold);
			if(autoCollapseOk && !clstr.isRoot()) {
				var diffHeight = clstr.maxLeafHeight - clstr.height;
				if(diffHeight >= threshold) {
console.log("Collapse!");
					thisObj.collapseBranch(clstr);
					autoCollapseOk = false;
				}
			}
		} else {
console.log("Leaf:" + clstr.serial);
		}
	}
*/

	var thisObj = this;
	scanTree(this.tree, threshold);
	this.updateTree();
	this.lastChangedBranch = null;
	return this.collapsedBranchSerial;

  	function scanTree(clstr, height) {
                if(clstr.height >= height) {
                        if(clstr.isBranch()) thisObj.collapseBranch(clstr);
                        return;
                } else {
                        if(clstr.isBranch()) {
                                for(var i=0,len=clstr.childs.length; i<len; i++) {
                                        scanTree(clstr.childs[i], height);
                                }
                        }
                        return;
                }
	}
  },
  autoCollapseByLength: function(minLength) {
	var thisObj = this;
	scanTree(this.tree, minLength);
	this.updateTree();
	this.lastChangedBranch = null;
	return this.collapsedBranchSerial;

	function scanTree(clstr, minLength) {
		if(clstr.isBranch()) {
			for(var i=0,len=clstr.childs.length; i<len; i++) {
				scanTree(clstr.childs[i], minLength);
				if(clstr.childs[i].isBranch() && clstr.childs[i].collapsed == null && clstr.childs[i].length < minLength) {
					 thisObj.collapseBranch(clstr.childs[i]);
				}
			}
		} 
	}
  },
  autoCollapseByRatioToMaxHeight: function(ratio) {
	if(ratio==null || ratio==0) return this.collapsedBranchSerial;

	var borderHeight = this.oriMaxHeight * ratio;
//console.log("borderHeight:" + this.oriMaxHeight + " * " + ratio + " = " + borderHeight);
	this.lastChangedBranch = null;
	return this.autoCollapseByHeight(borderHeight);
  },
  sortByLength: function(xscend, type) {
	if(this.tree == null || xscend === "") return;

	this.lastChangedBranch = null;
	var thisObj = this;

	var sorterByHeightFromLeft = function(a,b) {
		var val;
		if(a.maxLeafHeight === b.maxLeafHeight) {
			if (a.serial > b.serial) {
				val = -1;
			} else {
				val = 1;
			}
		} else if (a.maxLeafHeight > b.maxLeafHeight) {
			val = 1;
		} else {
			val = -1;
		}
		if(xscend === 'desc') val = val * -1;
		return val;
	};
	var sorterByLeafs = function(a,b) {
		var aNum = a.leafs.length;
		var bNum = b.leafs.length;
		if(aNum === bNum) {
			if(a.maxLeafHeight === b.maxLeafHeight) {
				if (a.serial > b.serial) {
					val = -1;
				} else {
					val = 1;
				}
			} else if (a.maxLeafHeight > b.maxLeafHeight) {
				val = 1;
			} else {
				val = -1;
			}
/*
			if (a.serial > b.serial) {
				val = -1;
			} else {
				val = 1;
			}
*/
		} else if (aNum > bNum) {
			val = 1;
		} else {
			val = -1;
		}
		if(xscend === 'desc') val = val * -1;
		return val;
	};

	var serials = Object.keys(this.serial2branch);
//console.log("Serials:" + serials.length);
	for(var i=0,len=serials.length; i<len; i++) {
		var clstr = this.serial2branch[serials[i]];
		var target;
		if(clstr.isBranch()) {
			target = clstr;
		} else if(clstr.collapsedBranch != null){
//console.log("CollapseLeaf:" + clstr.serial);
			target = clstr.collapsedBranch;
		} else {
//console.log("LeafSkip:" + clstr.serial);
			continue;
		}
//console.log("Clstr:" + target.serial + "/" + xscend);
		if(type === 'height') {
			target.childs.sort(sorterByHeightFromLeft);
		} else {
			target.childs.sort(sorterByLeafs);
		}
	}
	this.updateTree();	//TODO It is only "this.order" that needs to be updated. Is it possible to save weight?
  },
  removeLeafsAndUpdate: function(names) {
//	if(names == null) return;
	if(names == null || !(names instanceof Array) || names.length == 0) return;

	for(var i=0,len=names.length; i<len; i++) {
		var leaf = this.name2leaf[names[i]];
		if(leaf == null || leaf.isBranch()) continue;
		this.removeNode(leaf);
//		leaf.remove();
	} 
	this.updateTree();
  },
  /**
  * Be sure to execute updateTree() after execution this.
  */
  removeNode: function(clstr) {
	delete this.serial2branch[clstr.serial];
	if(clstr.isLeaf()) delete this.name2leaf[clstr.childs];
	var gparent = clstr.parent.parent;
	if(gparent) {
		clstr.remove();
	} else {
		// Parent is root node.
		var brothers = clstr.parent.childs;
		var newArray = [];
		for(var i=0,len=brothers.length; i<len; i++) {
			if(brothers[i] !== clstr) newArray.push(brothers[i]);
		}
		if(newArray.length === 1) {
			// Remove root node and make the child node the root.
			newArray[0].parent = null;
			newArray[0].length = 0;
			this.tree = newArray[0];
		} else {
			// 
			clstr.parent.childs = newArray;
		}
		clstr.clear();
	} 
  }
/*
  removeNode: function(clstr) {
	delete this.serial2branch[clstr.serial];
	if(clstr.isLeaf()) delete this.name2leaf[clstr.childs];
	clstr.remove();
  }
*/
}

/**
	Data Holder of Branch info
*/
var BranchPartRect = function(branch, margin, x1, y1, x2, y2) {
	this.margin = margin;
	this.branch = branch;
	this.x1 = x1;
	this.y1 = y1;
	this.x2 = x2;
	this.y2 = y2;
}
BranchPartRect.prototype.getCollisionRect = function() {
	return {
		"l":this.x1 - this.margin,
		"t":this.y1 - this.margin,
		"r":this.x2 + this.margin,
		"b":this.y2 + this.margin
	};
}
