function Rectangle(x, y, w, h)
{
	this.x = x;
	this.y = y;
	this.w = w;
	this.h = h;
};
Rectangle.prototype =
{
	bottom : function()
	{
		return this.y + this.h;
	},
	centerX : function()
	{
		return this.x + this.w / 2;
	},
	centerY : function()
	{
		return this.y + this.h / 2;
	},
	top : function()
	{
		return this.y;
	},
	left : function()
	{
		return this.x;
	},
	right : function()
	{
		return this.x + this.w;
	},
	intersects : function(that)
	{
		return this.x < that.right() && this.right() > that.x && this.y < that.bottom() && this.bottom() > that.y;
	},
	toString : function()
	{
		return "[Rectangle (" + this.x + ", " + this.y + ") " + this.w + " x " + this.h + "]";
	}
};

function PhyloCanvasHTML5(canvas)
{
	this.context = canvas.getContext("2d");
}
PhyloCanvasHTML5.prototype =
{
	context: null,
	// :TODO: more style properties
	fontFamily: "sans-serif",
	fontSize: 12,
	fontStyle: "italic",
	clear: function()
	{
		this.context.clearRect(0, 0, this.context.canvas.width, this.context.canvas.height);
	},
	drawArc: function(x1, y1, x2, y2, arrowSize)
	{
		this.context.strokeStyle = "rgb(0, 0, 0)";
		this.context.lineWidth = 1.5;
		this.context.beginPath();
		this.context.moveTo(x1, y1);
		this.context.quadraticCurveTo(x1, y2, x2 - arrowSize, y2);
		this.context.stroke();
		this.context.fillStyle = "rgb(0, 0, 0)";
		this.context.beginPath();
		this.context.lineTo(x2 - arrowSize, y2 - (arrowSize >> 1));
		this.context.lineTo(x2 - arrowSize, y2 + (arrowSize >> 1));
		this.context.lineTo(x2, y2);
		this.context.fill();
		this.context.closePath();
	},
	drawCladeLabel: function(leftX, centerY, label)
	{
		this.context.fillStyle = "rgba(255, 255, 255, 0.75)";
		this.context.fillRect(leftX, centerY - (this.fontSize >> 1), this.measureTextWidth(label), this.fontSize);
		this.context.textAlign = "left";
		this.context.textBaseline = "middle";
		this.context.font = "italic 12px sans-serif";
		this.context.fillStyle = "rgb(0, 0, 0)";
		this.context.fillText(label, leftX, centerY);
	},
	drawNodeCircle: function(x, y, radius)
	{
		this.context.fillStyle = "rgb(0,0,0)";
		this.context.lineWidth = 1;
		this.context.strokeStyle = "rgb(0,0,0)";
		this.context.beginPath();
		this.context.arc(x, y, radius, 0, Math.PI * 2, false);
		this.context.fill();
		this.context.stroke();
		this.context.closePath();
	},
	drawNodeLabel: function(centerX, centerY, label)
	{
		this.context.textAlign = "center";
		this.context.textBaseline = "middle";
		this.context.font = "bold italic 12px sans-serif";
		this.context.fillStyle = "rgb(255, 255, 255)";
		this.context.fillText(label, centerX, centerY);
	},
	drawNodeRect: function(rectangle, radius)
	{
		this.context.fillStyle = "rgb(0, 0, 0)";
		this.context.lineWidth = 1;
		this.context.strokeStyle = "rgb(0, 0, 0)";
		this.context.beginPath();
		this.context.moveTo(rectangle.x, rectangle.y + radius);
		this.context.quadraticCurveTo(rectangle.x, rectangle.y, rectangle.x + radius, rectangle.y);
		this.context.lineTo(rectangle.right() - radius, rectangle.y);
		this.context.quadraticCurveTo(rectangle.right(), rectangle.y, rectangle.right(), rectangle.y + radius);
		this.context.lineTo(rectangle.right(), rectangle.bottom() - radius);
		this.context.quadraticCurveTo(rectangle.right(), rectangle.bottom(), rectangle.right() - radius, rectangle.bottom());
		this.context.lineTo(rectangle.x + radius, rectangle.bottom());
		this.context.quadraticCurveTo(rectangle.x, rectangle.bottom(), rectangle.x, rectangle.bottom() - radius);
		this.context.lineTo(rectangle.x, rectangle.y + radius);
		this.context.fill();
		this.context.stroke();
		this.context.closePath();
	},
	measureTextWidth : function(t)
	{
		this.context.font = "bold italic 12px sans-serif";
		return this.context.measureText(t).width;
	},
	setSize: function(w, h)
	{
		this.context.canvas.width = w;
		this.context.canvas.height = h;
		this.context.strokeStyle = "rgb(0, 0, 0)";
		this.context.lineWidth = 2;
		this.context.fillStyle = "rgb(255, 255, 255)";
		this.context.fillRect(0, 0, w, h);
		this.context.strokeRect(0, 0, w, h);
	}
};

function PhyloCanvasRaphael(paper)
{
	this.paper = paper;
}
PhyloCanvasRaphael.prototype =
{
	// :TODO: more style properties
	fontFamily: "sans-serif",
	fontSize: 12,
	fontStyle: "italic",
	paper: null,
	clear: function()
	{
		this.paper.clear();
	},
	drawArc: function(x1, y1, x2, y2, arrowSize)
	{
		var d = ["M", x1, y1,
                 "Q", x1, y2, x2 - arrowSize, y2
                 ].join(" ");
		var line = this.paper.path(d);
		line.attr({"stroke": "#000",
		           "stroke-width": 1.5});
		d = ["M", x2 - arrowSize, y2 - (arrowSize >> 1),
             "v", arrowSize,
             "L", x2, y2,
             "Z"
             ].join(" ");
		var arrow = this.paper.path(d);
		arrow.attr("fill", "#000");
	},
	drawCladeLabel: function(leftX, centerY, label)
	{
		var box = this.measureText(label, leftX, centerY);
		var back = this.paper.rect(box.x, box.y, box.width, box.height);
		back.attr({"fill": "#FFF",
		           "fill-opacity": 0.75,
		           "stroke": "none"});
		var cText = this.paper.text(leftX, centerY, label);
		cText.attr({"alignment-baseline": "central",
	                "fill": "#000",
			        "font-family": this.fontFamily,
			        "font-size": this.fontSize + "px",
			        "font-style": this.fontStyle,
	                "text-anchor": "start"});
	},
	drawNodeCircle: function(x, y, radius)
	{
		var c = this.paper.circle(x, y, radius);
		c.attr({"stroke": "#000", "fill": "#000"});
	},
	drawNodeLabel: function(centerX, centerY, label)
	{
		var text = this.paper.text(centerX, centerY, label);
		text.attr({"alignment-baseline": "central",
		           "fill": "#FFF",
		           "font-family": this.fontFamily,
		           "font-size": this.fontSize + "px",
		           "font-style": this.fontStyle,
		           "text-anchor": "middle"});
	},
	drawNodeRect: function(rectangle, radius)
	{
		var rect = this.paper.rect(rectangle.x, rectangle.y, rectangle.w, rectangle.h, radius);
		rect.attr({"stroke": "#000", "fill": "#000"});
	},
	measureText : function(t, x, y)
	{
		var text = this.paper.text(x, y, t);
		text.attr({"font-family": "sans-serif",
		           "font-size": this.fontSize + "px",
		           "font-style": "italic",
		           "alignment-baseline": "central",
		           "text-anchor": "start"});
		var box = text.getBBox();
		text.remove();
		return box;
	},
	measureTextWidth : function(t)
	{
		var text = this.paper.text(0, 0, t);
		text.attr({"font-family": "sans-serif",
	               "font-size": this.fontSize + "px",
	               "font-style": "italic"});
		var w = text.getBBox().width;
		text.remove();
		return w;
	},
	setSize: function(w, h)
	{
		this.paper.setSize(w, h);
		var rect = this.paper.rect(0, 0, w, h);
		rect.attr({"stroke": "#000", "stroke-width": 2, "fill": "#FFF"});
	}
};

function PhyloPainter(graph, phyloCanvas)
{
	this.graph = graph;
	this.phyloCanvas = phyloCanvas;
	this._untraversedSinks = new IDSet();
	this._initRectangles();
	this._xSort();
	this._ySort();
	this._removeOverlap();
	this._cleanUp();
};
PhyloPainter.compareRectangles = function(a, b)
{
	return a.bottom() - b.bottom();
};
PhyloPainter.prototype =
{
	graph: null,
	hGap: 12,
	padding: 6,
	phyloCanvas: null,
	vGap: 6,
	_nodeRectangles : null,
	_nextSinkY : 0,
	_traversed : null,
	_untraversedSinks : null,
	render : function()
	{
		this.phyloCanvas.clear();
		this.phyloCanvas.setSize(this.maxRight, this.maxBottom);
		this._renderArcs();
		this._renderNodes();
	},
	_cleanUp : function()
	{
		this._traversed = null;
		this._untraversedSinks = null;
	},
	_renderArcs : function(s)
	{
		this.graph[1].forEach(this._renderArc, this);
	},
	_renderNodes : function(s)
	{
		this.graph[0].forEach(this._renderNode, this);
	},
	_renderArc : function(arc)
	{
		var pr = this._nodeRectangles[arc.head.id];
		if (!pr)
			throw new Error("No rectangle for node: " + arc.head + ".");
		var cr = this._nodeRectangles[arc.tail.id];
		if (!cr)
			throw new Error("No rectangle for node: " + arc.tail + ".");
		var px = arc.head.label.length == 0 ? (pr.x + this.padding) : pr.centerX();
		this.phyloCanvas.drawArc(px, pr.centerY(), cr.x, cr.centerY(), this.padding);
	},
	_renderNode : function(node)
	{
		var r = this._nodeRectangles[node.id];
		if (!r)
			throw new Error("No rectangle for node: " + node + ".");
		if (node.label.length)
		{
			this.phyloCanvas.drawNodeRect(r, this.padding);
			this.phyloCanvas.drawNodeLabel(r.centerX(), r.centerY(), node.label);
		}
		else
			this.phyloCanvas.drawNodeCircle(r.x + this.padding, r.centerY(), this.padding);
		if (node.cladeLabel.length)
			this.phyloCanvas.drawCladeLabel(r.x + this.padding * 2.5, r.centerY(), node.cladeLabel);
	},
	_initRectangle : function(node)
	{
		var r = this._createNodeRectangle(node);
		this._nodeRectangles[node.id] = r;
	},
	_initRectangles : function()
	{
		this._nodeRectangles = {};
		this.graph[0].forEach(this._initRectangle, this);
	},
	_createNodeRectangle : function(node)
	{
		var p = this.padding << 1;
		var r = new Rectangle(0, 0, p, p);
		var hasLabel = node.label.length != 0;
		var hasCladeLabel = node.cladeLabel.length != 0;
		if (hasLabel)
			r.w += this.phyloCanvas.measureTextWidth(node.label);
		if (hasCladeLabel)
			r.w += this.phyloCanvas.measureTextWidth(node.cladeLabel) + this.padding;
		if (hasLabel || hasCladeLabel)
			r.h += this.phyloCanvas.fontSize;
		return r;
	},
	// :TODO: move to IDDigraphSolver class
	_arcsFrom : function(node)
	{
		var arcs = [];
		var n = this.graph[1].size;
		for (var i = 0; i < n; ++i)
		{
			var arc = this.graph[1].list[i];
			if (arc.head == node)
				arcs.push(arc);
		}
		return arcs;
	},
	// :TODO: move to IDDigraphSolver class
	_arcsTo : function(node)
	{
		var arcs = [];
		var n = this.graph[1].size;
		for (var i = 0; i < n; ++i)
		{
			var arc = this.graph[1].list[i];
			if (arc.tail == node)
				arcs.push(arc);
		}
		return arcs;
	},
	_collapseNonSinkX : function(node)
	{
		if (this._traversed.contains(node))
			return;
		this._traversed[node.id] = node.id;
		var nodeRectangle = this._nodeRectangles[node.id];
		if (!nodeRectangle)
			return;
		var arcsFrom = this._arcsFrom(node);
		var n = arcsFrom.length;
		if (n == 0)
			return;
		var x = Number.MAX_VALUE;
		for (var i = 0; i < n; ++i)
		{
			var arc = arcsFrom[i];
			this._collapseNonSinkX(arc.tail);
			var childRectangle =
				this._nodeRectangles[arc.tail.id];
			if (childRectangle == undefined)
				continue;
			var childX =
				childRectangle.x - this.hGap - nodeRectangle.w;
			x = Math.min(x, childX);
		}
		if (x != Number.MAX_VALUE)
			nodeRectangle.x = x;
	},
	_sinks : function()
	{
		if (this._sinks_result)
			return this._sinks_result;
		this._sinks_result = new IDSet();
		this._sinks_result.addAll(this.graph[0]);
		var n = this.graph[1].size;
		for (var i = 0; i < n; ++i)
		{
			var nonSink = this.graph[1].list[i].head;
			this._sinks_result.remove(nonSink);
		}
		return this._sinks_result;
	},
	_sources : function()
	{
		if (this._sources_result)
			return this._sources_result;
		this._sources_result = new IDSet();
		this._sources_result.addAll(this.graph[0]);
		var n = this.graph[1].size;
		for (var i = 0; i < n; ++i)
		{
			var nonSource = this.graph[1].list[i].tail;
			this._sources_result.remove(nonSource);
		}
		return this._sources_result;
	},
	_collapseNonSinksX : function()
	{
		this._sinks().forEach(this._collapseNonSinkX, this);
	},
	_compareNodes : function(a, b)
	{
		if (a == b || a.id == b.id)
			return 0;
		var aRectangle = this._nodeRectangles[a.id];
		var bRectangle = this._nodeRectangles[b.id];
		var rectangleCompare;
		if (aRectangle == null)
		{
			if (bRectangle == null)
				rectangleCompare = 0;
			else
				rectangleCompare = -1;
		}
		else if (bRectangle == null)
			rectangleCompare = 1;
		else
			rectangleCompare = PhyloPainter.compareRectangles(aRectangle, bRectangle);
		if (rectangleCompare != 0)
			return rectangleCompare;
		if (a.id < b.id)
			return -1;
		if (b.id < a.id)
			return 1;
		return 0;
	},
	_removeOverlap : function()
	{
		var n = this.graph[0].size;
		if (n == 0)
			return;
		var rectangles = [];
		var i;
		for (i = 0; i < n; ++i)
			rectangles.push(this._nodeRectangles[this.graph[0].list[i].id]);
		rectangles.sort(PhyloPainter.compareRectangles);
		for (i = 1; i < n; ++i)
			for (var h = 0; h < i; ++h)
				if (rectangles[h].intersects(rectangles[i]))
				{
					var offset = rectangles[h].bottom() + this.vGap - rectangles[i].y;
					for (var j = i; j < n; ++j)
						rectangles[j].y += offset;
				}
		var lastRectangle = rectangles[rectangles.length - 1];
		this.maxBottom = lastRectangle.bottom() + this.vGap;
	},
	_setNonSinkY : function(node)
	{
		if (this._traversed.contains(node))
			return;
		this._traversed.add(node);
		var arcsFrom = this._arcsFrom(node);
		var n = arcsFrom.length;
		if (n == 0)
			return;
		var ySum = 0;
		var numChildren = n;
		for (var i = 0; i < n ; ++i)
		{
			var arc = arcsFrom[i];
			var child = arc.tail;
			this._setNonSinkY(child);
			var childRectangle = this._nodeRectangles[child.id];
			if (!childRectangle)
				numChildren--;
			else
				ySum += childRectangle.centerY();
		}
		var rectangle = this._nodeRectangles[node.id];
		rectangle.y = (numChildren == 0) ? 0 : (ySum / numChildren - rectangle.h / 2);
	},
	_setNonSinksY : function()
	{
		var sinks = this._sinks();
		var n = this.graph[0].size;
		for (var i = 0; i < n; ++i)
		{
			var node = this.graph[0].list[i];
			if (!sinks.contains(node))
				this._setNonSinkY(node);
		}
	},
	_setNonSourceX : function(node)
	{
		if (this._traversed.contains(node))
			return;
		var arcsTo = this._arcsTo(node);
		var x = 0;
		var n = arcsTo.length;
		if (n != 0)
		{
			var numParents = n;
			for (var i = 0; i < n; ++i)
			{
				var arc = arcsTo[i];
				var parentRectangle = this._nodeRectangles[arc.head.id];
				if (!(parentRectangle instanceof Rectangle))
					numParents--;
				else
				{
					this._setNonSourceX(arc.head);
					x = Math.max(x, parentRectangle.x + parentRectangle.w + this.hGap);
				}
			}
		}
		var rectangle = this._nodeRectangles[node.id];
		if (rectangle)
		{
			rectangle.x = x;
			rectangle.y = 0;
			this.maxRight = Math.max(this.maxRight, x + rectangle.w + this.hGap);
		}
		this._traversed.add(node);
	},
	_setNonSourcesX : function()
	{
		this.graph[0].forEach(this._setNonSourceX, this);
	},
	_setSinkSuccessorsY : function(node)
	{
		if (this._traversed.contains(node))
			return;
		this._traversed.add(node);
		var arcsFrom = this._arcsFrom(node);
		var n = arcsFrom.length;
		if (n == 0)
		{
			this._untraversedSinks.remove(node);
			var rectangle = this._nodeRectangles[node.id];
			if (rectangle)
			{
				rectangle.y = this._nextSinkY;
				this._nextSinkY += rectangle.h + this.vGap;
			}
		}
		else if (n == 1)
			this._setSinkSuccessorsY(arcsFrom[0].tail);
		else
		{
			var children = [];
			var i;
			for (i = 0; i < n; ++i)
			{
				var arc = arcsFrom[i];
				children.push(arc.tail);
			}
			var o = this;
			children = children.sort(function(a, b) {return o._compareNodes(a, b);});
			for (i = 0; i < n; ++i)
				this._setSinkSuccessorsY(children[i]);
		}
	},
	_setSinksY : function(node)
	{
		this._setSinkSuccessorsY(node);
		var arcsTo = this._arcsTo(node);
		var n = arcsTo.length;
		for (var i = 0; i < n; ++i)
		{
			var arc = arcsTo[i];
			this._setSinksY(arc.head);
		}
	},
	_setSourcesX : function()
	{
		var sources = this._sources();
		var n = sources.size;
		for (var i = 0; i < n; ++i)
		{
			var source = sources.list[i];
			var rectangle = this._nodeRectangles[source.id];
			if (rectangle)
			{
				rectangle.x = this.hGap;
				rectangle.y = this.vGap;
			}
			this._traversed.add(source);
		}
	},
	_xSort: function()
	{
		this.maxRight = 0;
		this.maxBottom = 0;
		this._traversed = new IDSet();
		this._setSourcesX();
		this._setNonSourcesX();
		this._traversed = new IDSet();
		this._collapseNonSinksX();
		this._traversed = null;
	},
	_nextUntraversedSink : function()
	{
		var sink = this._untraversedSinks.list[0];
		this._untraversedSinks.remove(sink);
		return sink;
	},
	_ySort : function()
	{
		this._traversed = new IDSet();
		this._untraversedSinks = new IDSet();
		var sinks = this._sinks();
		this._untraversedSinks.addAll(sinks);
		this._nextSinkY = this.vGap;
		while (this._untraversedSinks.size != 0)
			this._setSinksY(this._nextUntraversedSink());
		this._untraversedSinks = null;
		this._traversed = new IDSet();
		this._setNonSinksY();
		this._traversed = null;
	}
};