/**
June 25, 2009
Javascript demo of Steve Fortune algorithm by Raymond Hill
(www.raymondhill.net).

I ported to Javascript the C# implementation of Benjamin Dittes
(http://bdittes.googlepages.com/), who submitted his code to Code
Project (http://www.codeproject.com/KB/recipes/fortunevoronoi.aspx)
under the Code Project Open License.

Steve Fortune (http://ect.bell-labs.com/who/sjf/) published this clever
algorithm in 1987 (http://en.wikipedia.org/wiki/Fortune%27s_algorithm)
in "A Sweepline Algorithm for Voronoi Diagrams," Algorithmica 2, 153-174.

This is a work in progress, with plenty of unnecessary debug code and
non-optimzed portions. I want to consider alternative implementations of
Fortune's algorithm without using a tree graph for the Javascript version.
I would also like to add feature to the visual interface like animation,
grid, etc. to experiment further with Steve Fortune's algorithm/Voronoi
diagram.

Steve Fortune created an excellent Powerpoint presentation of how his
algorithm works. (http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt)

**/

/*jslint browser: true */
/*global self*/
// helper functions
var debug_on=true;
function stdout(s,clear) {
	var consoleObj=self.document.getElementById('console');
	if ( consoleObj ) {
		if ( clear ) {
			consoleObj.innerHTML = "";
			}
		consoleObj.innerHTML += s + "<br>";
		}
	}
function stderr(s) {
	if ( debug_on ) {
		//stdout(s);
		}
	}
function equalWithEpsilon(a,b){
	return self.Math.abs(a-b)<1e-6;
	}
function greaterThanWithEpsilon(a,b){
	return (a-b)>1e-6;
	}
function greaterThanOrEqualWithEpsilon(a,b){
	return (b-a)<1e-6;
	}
function lessThanWithEpsilon(a,b){
	return (b-a)>1e-6;
	}
function lessThanOrEqualWithEpsilon(a,b){
	return (a-b)<1e-6;
	}

/**
  Point object
 */
function Point(a,b) {
	// a=x,b=y
	if (b!==undefined) {
		this.x=a;
		this.y=b;
		}
	// a=Point or {x:?,y:?,id:?}
	else if (a && a.x!==undefined) {
		this.x=a.x;
		this.y=a.y;
		}
	// empty
	else {
		this.x=this.y=this.id=0;
		}
	}
Point.prototype.toString = function() {
	return "{x:"+this.x+",y:"+this.y+"}";
	};
Point.prototype.toHashkey = function() {
	// We could use toString(), but I am concerned with
	// the performance of Polygon.merge(). As for now
	// I have no idea if its really that much of an
	// improvement, but I figure the shorter the string
	// used as a hash key, the better. This also reduce
	// the number of concatenations from 6 to 2. Ultimately,
	// I could cache the hash key..
	return this.x.toFixed(6)+","+this.y.toFixed(6);
	};
Point.prototype.compare = function(other) {
	var r=this.y-other.y;
	if (r) {return r;}
	return this.x-other.x;
	};
Point.prototype.doesEqual=function(other) {
	//stdout("Point.doesEqual: this="+this+"; "+other);
	return equalWithEpsilon(this.x,other.x) && equalWithEpsilon(this.y,other.y);
	};
Point.prototype.distance=function(other) {
	var dx=other.x-this.x;
	var dy=other.y-this.y;
	return self.Math.sqrt(dx*dx+dy*dy);
	};

/**
  Fortune's Voronoi generator
  http://www.codeproject.com/KB/recipes/fortunevoronoi.aspx
 */
function VoronoiEvent() {
	}
VoronoiEvent.prototype.getX=function() {
	return this.pt.x;
	};
VoronoiEvent.prototype.getY=function() {
	return this.pt.y;
	};
VoronoiEvent.prototype.compare=function(other) {
	var r=this.getY()-other.getY();
	if (!r) {
		r=this.getX()-other.getX();
		}
	return r;
	};

function VoronoiDataEvent(dp) {
	VoronoiEvent.call(this);
	this.pt=new Point(dp);
	this.isDataEvent=true;
	}
VoronoiDataEvent.prototype=new VoronoiEvent();
VoronoiDataEvent.prototype.toString=function() {
	return "pt:"+this.pt;
	};

function VoronoiCircleEvent(l,n,r,center) {
	VoronoiEvent.call(this);
	this.nodeN=n;
	this.nodeL=l;
	this.nodeR=r;
	this.center=new Point(center);
	this.falseAlarm=false;
	this.isCircleEvent=true;
	}
VoronoiCircleEvent.prototype=new VoronoiEvent();
VoronoiCircleEvent.prototype.getX=function() {
	return this.center.x;
	};
VoronoiCircleEvent.prototype.getY=function() {
	if (this.y===undefined) { // cache bottom y value
		this.y=this.center.y+self.Math.sqrt((this.center.x-this.nodeN.pt.x)*(this.center.x-this.nodeN.pt.x)+(this.center.y-this.nodeN.pt.y)*(this.center.y-this.nodeN.pt.y));
		}
	return this.y;
	};
VoronoiCircleEvent.prototype.toString=function() {
	return "{center:"+this.center+",falseAlarm:"+this.falseAlarm+",getY():"+this.getY()+"}";
	};

function VoronoiEdge(lPt,rPt) {
	if (lPt) {
		this.lPt=new Point(lPt);
		}
	if (rPt) {
		this.rPt=new Point(rPt);
		}
	}
VoronoiEdge.prototype.addVertex = function(p) {
	if (!this.va) {
		this.va=new Point(p);
		}
	else if (!this.vb) {
		this.vb=new Point(p);
		}
	else {
		throw "VoronoiEdge.addVertex(): Tried to add third vertex!";
		}
	};
VoronoiEdge.prototype.toHash=function(){
	var key=this.lPt.toHashkey()+";"+this.rPt.toHashkey();
	if (this.va) {
		key+=this.va.toHashkey();
		}
	if (this.vb) {
		key+=this.vb.toHashkey();
		}
	return key;
	};
VoronoiEdge.prototype.toString=function(){
	return "{lPt:"+this.lPt+",rPt:"+this.rPt+",va:"+this.va+",vb:"+this.vb+"}";
	};

function VoronoiGraph() {
	this.vertices=[];
	this.edges=[];
	}

function VoronoiBeachsection(site){
	this.site=site;
	this.xLeft=this.xRight=site.x;
	this.p=0;
	}
VoronoiBeachsection.prototype.compare=function(other){
	return this.xRight<other.xLeft?-1:(xLeft>other.xRight?1:0);
	};
// split a section, return the right part (this will be set to be the left part)
VoronoiBeachsection.prototype.split=function(x){
	if (x<=this.xLeft || x>=this.xRight) {
		return null;
		}
	var leftPart=this;
	var rightPart=new VoronoiBeachsection(this.site);
	leftPart.xRight=rightPart.xLeft=x;
	return rightPart;
	};

function VoronoiBeachline() {
	this.sections=[];
	}
VoronoiBeachline.prototype.addSection=function(site){
	// create a beach section from the site
	var newSection=new VoronoiBeachsection(site);
	// ordered according to x (the site is assumed to be the vertex of a parabola with p=0)
	// using binary search: il=index left, ir=index right
	var ir=this.sections.length;
	var c;
	if (ir) {
		var il=0;
		var i;
		while (il<ir) {
			i=(il+ir)>>1;
			c=newSection.compare(this.sections[i]);
			if (c<0) {
				ir=i;
				}
			else if (c>0) {
				il=i+1;
				}
			else {
				break;
				}
			}
		var rightPart=this.beachline[i].split(site.x);
		if (rightPart) {
			this.sections.splice(i,0,newSection,rightPart);
			}
		else { // rare case where the new section falls exactly in between two existing sections
			this.sections.splice(i,0,newSection);
			}
		}
	else { // first section to be added to the beach line
		this.sections.push(beachSection);
		}
	};

var VoronoiNodeIdGenerator=1;
function VoronoiNode() {
	this.id=VoronoiNodeIdGenerator++;
	}
VoronoiNode.prototype.setLeft=function(n) {
	if (n!==undefined) {
		this.left=n;
		n.parent=this;
		}
	else {
		delete this.left;
		}
	};
VoronoiNode.prototype.setRight=function(n) {
	if (n!==undefined) {
		this.right=n;
		n.parent=this;
		}
	else {
		delete this.right;
		}
	};
VoronoiNode.prototype.setParent=function(n) {
	this.parent=n;
	};
VoronoiNode.prototype.getPointConst=function() {
	return null;
	};
VoronoiNode.prototype.toHash=function() {
	return undefined;
	};
VoronoiNode.prototype.toString=function() {
	return "id:"+this.id+",left:"+(this.left?this.left.id:"nil")+",right:"+(this.right?this.right.id:"nil");
	};

function VoronoiDataNode(pt) {
	VoronoiNode.call(this);
	this.pt=new Point(pt);
	this.isDataNode=true;
	}
VoronoiDataNode.prototype=new VoronoiNode();
VoronoiDataNode.prototype.toHash=function() {
	return this.pt.toHashkey();
	};
VoronoiDataNode.prototype.getPointConst=function() {
	return this.pt?this.pt:null;
	};
VoronoiDataNode.prototype.toString=function() {
	return "{"+VoronoiNode.prototype.toString.call(this)+",pt:"+this.pt+",isDataNode:true}";
	};

function VoronoiEdgeNode(e,flipped,l,r) {
	VoronoiNode.call(this);
	this.setLeft(l);
	this.setRight(r);
	this.edge=e;
	this.flipped=flipped;
	this.isEdgeNode=true;
	}
VoronoiEdgeNode.prototype=new VoronoiNode();
VoronoiEdgeNode.prototype.toHash=function() {
	return this.edge.toHashkey();
	};
VoronoiEdgeNode.prototype.getPointConst=function() {
	return this.edge&&this.edge.va?this.edge.va:null;
	};
VoronoiEdgeNode.prototype.toString=function() {
	return "{"+VoronoiNode.prototype.toString.call(this)+",e:"+this.edge+",flipped:"+this.flipped+",isEdgeNode:true}";
	};

function Fortune() {
	// remove the no-javascript alert
	self.document.getElementById('canvasParent').removeChild(self.document.getElementById('voronoiNoJSAlert'));
	// this is me
	var me=this;
	var o; // all purpose object variable
	// create drawing surface
	if (!this.canvas){
		this.canvas=self.document.getElementById('voronoiCanvas');
		if (this.canvas.getContext && this.canvas.getContext('2d')) {
			var ctx=this.canvas.getContext('2d');
			ctx.fillStyle='#fff';
			ctx.rect(0,0,this.canvas.width,this.canvas.height);
			ctx.fill();
			ctx.strokeStyle='#888';
			ctx.stroke();
			}
		else {
			// turn on the no-canvas alert
			self.document.getElementById('voronoiNoCanvasAlert').style.display="block";
			return;
			}
		}
	if (!this.breakImage) {
		this.breakImage=self.document.getElementById('break');
		}
	// update stats
	this.updateStats=function(){
		var o;
		if (!!(o=self.document.getElementById('voronoiTotalSites'))) {o.innerHTML=this.sites?this.sites.length:"0";}
		if (!!(o=self.document.getElementById('voronoiQueueEvents'))) {o.innerHTML=this.pq?me.pq.length():"0";}
		if (!!(o=self.document.getElementById('voronoiTotalEvents'))) {o.innerHTML=this.nProcessedEvents;}
		if (!!(o=self.document.getElementById('voronoiFalseAlarms'))) {o.innerHTML=this.nFalseAlarms;}
		if (!!(o=self.document.getElementById('voronoiTotalVertices'))) {o.innerHTML=this.vg?this.vg.vertices.length:"0";}
		if (!!(o=self.document.getElementById('voronoiTotalEdges'))) {o.innerHTML=this.vg?this.vg.edges.length:"0";}
		};
	// assign interface components to js code
	if (!!(o=self.document.getElementById('voronoiCanvasSize'))){
		o.onclick=function(){
			var ow=self.document.getElementById('voronoiWidth');
			var oh=self.document.getElementById('voronoiHeight');
			if (ow && oh && self.parseInt(ow.value)!="NaN" && self.parseInt(oh.value)!="NaN") {
				me.canvas.width=self.parseInt(ow.value);
				me.canvas.height=self.parseInt(oh.value);
				me.randomSites(o.value);
				me.draw();
				}
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiRandomSites'))){
		o.onclick=function(){
			var o=self.document.getElementById('voronoiNumberSites');
			if (o && self.parseInt(o.value)!="NaN") {
				me.randomSites(o.value);
				me.draw();
				}
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiParseSites'))){
		o.onclick=function(){
			var o=self.document.getElementById('voronoiUserInput');
			if (o) {
				me.parseUserSites(o.value);
				me.draw();
				}
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiParseLattices'))){
		o.onclick=function(){
			var o=self.document.getElementById('voronoiUserInput');
			if (o) {
				me.parseUserLattices(o.value);
				me.draw();
				}
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiClearSites'))){
		o.onclick=function(){
			me.clearSites();
			me.resetEventQueue();
			me.draw();
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiReset'))){
		o.onclick=function(){
			me.resetEventQueue();
			me.draw();
			me.updateStats();
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiProcessAll'))){
		o.onclick=function(){
			me.computeVoronoiGraph(100000000); // 100-million should do it...
			me.draw();
			me.updateStats();
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiProcessOne'))){
		o.onclick=function(){
			me.computeVoronoiGraph(1);
			me.draw();
			me.updateStats();
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiProcessNDo'))){
		o.onclick=function(){
			var o=self.document.getElementById('voronoiProcessN');
			if (self.parseInt(o.value)!="NaN") {
				me.computeVoronoiGraph(self.parseInt(o.value));
				me.draw();
				me.updateStats();
				}
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiDumpBeachline'))){
		o.onclick=function(){
			me.dumpBeachline();
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiDumpVertices'))){
		o.onclick=function(){
			me.dumpVertices();
			return false;
			};
		}
	if (!!(o=self.document.getElementById('voronoiDumpEdges'))){
		o.onclick=function(){
			me.dumpEdges();
			return false;
			};
		}
	// normalize event position
	// based on Quirksmode.org's Peter-Paul Koch
	// http://www.quirksmode.org/js/events_properties.html#position
	this.normalizeEventPos=function(e){
		if (!e) {e=self.event;}
		var pos=new Point();
		if (e.pageX || e.pageY){
			pos.x=e.pageX;
			pos.y=e.pageY;
			}
		else if (e.clientX || e.clientY) {
			pos.x=e.clientX+self.document.body.scrollLeft+self.document.documentElement.scrollLeft;
			pos.y=e.clientY+self.document.body.scrollTop+self.document.documentElement.scrollTop;
			}
		pos.x-=me.canvas.offsetLeft;
		pos.y-=me.canvas.offsetTop;
		return pos;
		};
	// event handlers
	this.canvas.onclick=function(e){
		if (!e) {e=self.event;}
		me.addSite(me.normalizeEventPos(e));
		me.resetEventQueue();
		me.draw();
		};
	self.onkeydown = function(e) {
		if (!e) {e=self.window.event;}
		var code=e.keyCode?e.keyCode:(e.which?e.which:0);
		switch (code) {
			// down arrow=execute 1 step
			case 40:
				me.computeVoronoiGraph(1);
				me.draw();
				me.updateStats();
				break;
			default:
				return true;
			}
		return false;
		};

	// all done initializing, engage
	this.randomSites(40);
	this.draw();
	}
VoronoiNode.prototype.replace=function(o,n) {
	if (this.left.id==o.id) {
		this.setLeft(n);
		}
	else if (this.right.id==o.id) {
		this.setRight(n);
		}
	else {
		throw "VoronoiNode.replace(): Child not found!";
		}
	delete o.parent;
	};
Fortune.prototype.firstDataNode=function(root) {
	var c=root;
	while (c.left) {
		c=c.left;
		}
	return c;
	};
Fortune.prototype.leftDataNode=function(current){
	var c=current;
	//1. Up
	while (true) {
		if (!c.parent) {
			return null;
			}
		if (c.parent.left.id==c.id) {
			c=c.parent;
			continue;
			}
		else {
			c=c.parent;
			break;
			}
		}
	//2. One Left
	c=c.left;
	//3. Down
	while (c.right) {
		c=c.right;
		}
	return c;
	};
Fortune.prototype.rightDataNode=function(current) {
	var c=current;
	//1. Up
	while (true) {
		if (!c.parent) {
			return null;
			}
		if (c.parent.right.id==c.id) {
			c=c.parent;
			continue;
			}
		else {
			c=c.parent;
			break;
			}
		}
	//2. One Right
	c=c.right;
	//3. Down
	while (c.left) {
		c=c.left;
		}
	return c;
	};
Fortune.prototype.edgeToRightDataNode=function(current) {
	var c=current;
	//1. Up
	while (true) {
		if (!c.parent) {
			throw "VoronoiNode.edgeToRightDataNode(): No Left Leaf found!";
			}
		if (c.parent.right.id==c.id) {
			c=c.parent;
			continue;
			}
		else {
			c=c.parent;
			break;
			}
		}
	return c;
	};
// changed from original code
// Find where two beach sections intersect
// Knowing that the two beach sections are parabolas with:
//   Focuses at pt1 and pt2,
//   Directrix at ys
// Equation of a parabola in cartesian coords:
// http://en.wikipedia.org/wiki/Parabola#Cartesian
//   y = (x-h)*(x-h)/(4*p)+k
//   h,k is the vertex of the parabola
Fortune.prototype.parabolicCut=function(pt1,pt2,directrix) {
	var x1=pt1.x;
	var y1=pt1.y;
	var x2=pt2.x;
	var y2=pt2.y;
	// both parabolas have same opening, same distance to directrix
	if (equalWithEpsilon(y1,y2)) {
		return (x1+x2)/2;
		}
	// parabola 1 in degenerate case where p=0
	if (equalWithEpsilon(y1,directrix)) {
		return x1;
		}
	// parabola 2 in degenerate case where p=0
	if (equalWithEpsilon(y2,directrix)) {
		return x2;
		}
	// http://en.wikipedia.org/wiki/Parabola
	// parabola 1: y = (x - h1)^2 / 4p1 + k1
	// parabola 2: y = (x - h2)^2 / 4p2 + k2
	// (x - h1)^2 / 4p1 + k1 = (x - h2)^2 / 4p2 + k2
	// let's say a1=1/4p1, a2=1/4p2
	// a1(x - h1)^2 + k1 = a2(x - h2)^2 + k2
	// points of intersection found where parabola 1 = parabola 2
	// (a1 - a2)x^2 + (2a2h2 - 2a1h1)x + (a1h1^2 + k1 - a2h2^2 - k2)
	// transient calculations can be simplified if we shift the origin to h1,k1 => 0,0
	// (a1 - a2)x^2 + 2a2h2.x + (-a2h2^2 - k2)
	//     a    x^2 +   b   x +       c
	var p1=(y1-directrix)/2;
	var p2=(y2-directrix)/2;
	var h1=x1;
	var k1=y1-p1;
	// we set the origin at h1,k1, to simplify our quadratic formula
	var h2=x2-h1;
	//var k2=(y2-p2)-k1;
	// parabolas' constant a
	//var a1=1/(4*p1);
	var a2=1/(4*p2);
	// here are the a, b and c of the combined parabolas
	var a=1/(4*p1)-a2; // really a1 - a2, but since a1 is used once, no need to keep it around
	var b=2*a2*h2;
	//var c=-a2*h2*h2-y2+p2+k1; // really -a2*h2*h2-k2, but since k2 is used once, no need to keep it around
	// we have enough to solve using quadratic formula
	// http://en.wikipedia.org/wiki/Quadratic_equation#Quadratic_formula
	// square root of discriminant, keep copy around since used more than once
	var sqrtd=self.Math.sqrt(b*b-4*a*(-a2*h2*h2-y2+p2+k1)); // really self.Math.sqrt(b*b-4*a*c), but since c is used once, no need to keep it around
	var da=2*a; // "double a"
	var xs1=(-b+sqrtd)/da+h1; // must not forget to shift back origin
	var xs2=(-b-sqrtd)/da+h1;
	return y1>=y2?self.Math.max(xs1,xs2):self.Math.min(xs1,xs2);
	/*this was original code
	var xs1=0.5/(2*a1-2*a2)*(4*a1*x1-4*a2*x2+2*self.Math.sqrt(-8*a1*x1*a2*x2-2*a1*y1+2*a1*y2+4*a1*a2*x2*x2+2*a2*y1+4*a2*a1*x1*x1-2*a2*y2));
	var xs2=0.5/(2*a1-2*a2)*(4*a1*x1-4*a2*x2-2*self.Math.sqrt(-8*a1*x1*a2*x2-2*a1*y1+2*a1*y2+4*a1*a2*x2*x2+2*a2*y1+4*a2*a1*x1*x1-2*a2*y2));

	if (xs1>xs2) {
		var h=xs1;
		xs1=xs2;
		xs2=h;
		}
	if (y1>=y2) {
		return xs2;
		}
	return xs1;*/
	};
// VoronoiNode.findDataNode:
//   root=VoronoiNode
//   ys=double
//   x=double
Fortune.prototype.findDataNode=function(root,ys,x) {
	var c=root;
	var dx;
	while (true) {
		if (c.isDataNode) {
			return c;
			}
		dx=x-this.parabolicCut(c.flipped?c.edge.rPt:c.edge.lPt,c.flipped?c.edge.lPt:c.edge.rPt,ys);
		if (dx<0) {
			if (!c.left) {
				throw "Fortune.findDataNode(): c.left is null!";
				}
			c=c.left;
			}
		else {
			if (!c.right) {
				throw "Fortune.findDataNode(): c.right is null!";
				}
			c=c.right;
			}
		}
	};
function FortuneProcessAnswer(root,checklist) {
	this.root=root;
	this.checklist=[];
	for (var i=0; i<checklist.length; i++) {
		this.checklist.push(checklist[i]);
		}
	}
// VoronoiNode.processDataEvent:
//   e=VoronoiDataEvent
//   root=VoronoiNode
//   vg=VoronoiGraph
//   ys=double
Fortune.prototype.processDataEvent=function(e,root,vg,ys) {
	// add a beach section (sweep line implicitly at site's y)
	//var iSection=this.beachline.addSection(e.pt);
	// look for potential circle events by analyzing the modified beach portion
	

	if (!root) {
		root=new VoronoiDataNode(e.pt);
		return new FortuneProcessAnswer(root,[root]);
		}
	//1. Find the node to be replaced
	var c=this.findDataNode(root,ys,e.pt.x);
	//2. Create the subtree (ONE Edge, but two VEdgeNodes)
	var ve=new VoronoiEdge(c.pt,e.pt);
	vg.edges.push(ve);
	var subRoot;
	var circleCheckList;
	if (equalWithEpsilon(ve.lPt.y,ve.rPt.y)) {
		if (ve.lPt.x<ve.rPt.x) {
			subRoot=new VoronoiEdgeNode(ve,false,new VoronoiDataNode(ve.lPt),new VoronoiDataNode(ve.rPt));
			}
		else {
			subRoot=new VoronoiEdgeNode(ve,true,new VoronoiDataNode(ve.rPt),new VoronoiDataNode(ve.lPt));
			}
		circleCheckList=[subRoot.left,subRoot.right];
		}
	else {
		subRoot=new VoronoiEdgeNode(ve,false,new VoronoiDataNode(ve.lPt),new VoronoiEdgeNode(ve,true,new VoronoiDataNode(ve.rPt),new VoronoiDataNode(ve.lPt)));
		circleCheckList=[subRoot.left,subRoot.right.left,subRoot.right.right];
		}
	//3. Apply subtree
	if (!c.parent) {
		return new FortuneProcessAnswer(subRoot,circleCheckList);
		}
	c.parent.replace(c,subRoot);
	return new FortuneProcessAnswer(root,circleCheckList);
	};
// VoronoiNode.processCircleEvent:
//   e=VoronoiCircleEvent
//   root=VoronoiNode
//   vg=VoronoiGraph
//   ys=double
Fortune.prototype.processCircleEvent=function(e,root,vg,ys) {
	//stdout("Fortune.processCircleEvent: "+e.toString());
	var b=e.nodeN;
	var a=this.leftDataNode(b);
	var c=this.rightDataNode(b);
	//stdout("Fortune.processCircleEvent: a="+a+", b.parent="+b.parent+", c="+c+(a?", a.pt="+a+"!=e.nodeL.pt="+e.nodeL.pt+a.pt:"")+(c?", c.pt="+c.pt+"!=e.nodeR.pt="+e.nodeR.pt:""));
	if (!a || !b.parent || !c || !a.pt.doesEqual(e.nodeL.pt) || !c.pt.doesEqual(e.nodeR.pt)) {
		return new FortuneProcessAnswer(root,[]);
		}
	var eu=b.parent;
	var circleCheckList=[a,c];
	//1. Create the new Vertex
	var ptNew=new Point(e.center.x,e.center.y);
	//stdout("<span style='color:red'>Fortune.processCircleEvent: adding vertex="+ptNew+"</span>");
	vg.vertices.push(ptNew);
	//2. Find out if a or c are in a distant part of the tree (the other is then b's sibling) and assign the new vertex
	var eo;
	if (eu.left.id==b.id) { // c is sibling
		eo=this.edgeToRightDataNode(a);
		// replace eu by eu's Right
		eu.parent.replace(eu,eu.right);
		}
	else { // a is sibling
		eo=this.edgeToRightDataNode(b);
		// replace eu by eu's Left
		eu.parent.replace(eu,eu.left);
		}
	eu.edge.addVertex(ptNew);
	eo.edge.addVertex(ptNew);
	//2. Replace eo by new Edge
	var ve=new VoronoiEdge(a.pt,c.pt);
	ve.addVertex(ptNew);
	//stdout("<span style='color:red'>Fortune.processCircleEvent: adding edge="+ve+"</span>");
	vg.edges.push(ve);
	var ven=new VoronoiEdgeNode(ve,false,eo.left,eo.right);
	if (!eo.parent) {
		return new FortuneProcessAnswer(ven,circleCheckList);
		}
	eo.parent.replace(eo,ven);
	return new FortuneProcessAnswer(root,circleCheckList);
	};
// Changed from original code
// Test for convergence: Powerpoint panel 47
// There is convergence if polygon
// traced by sites p->p(left)->p(right) is counterclockwise.
// About polygon orientation:
// http://en.wikipedia.org/wiki/Curve_orientation
// (x1y2+x0y1+y0x2)>(y0x1+y1x2+x0y2) = true if counterclockwise
// by shifting x1y1 to the origin:
// (y0-y1)(x2-x1)>(x0-x1)(y2-y1) = true if counterclockwise
Fortune.prototype.counterclockwise=function(pl,p,pr) {
	return (pl.y-p.y)*(pr.x-p.x)>(pl.x-p.x)*(pr.y-p.y);
	};
// Changed from original code
Fortune.prototype.circumCircleCenter=function(a,b,c) {
	if (a.doesEqual(b) || b.doesEqual(c) || a.doesEqual(c)) {
		throw "Fortune.circumCircleCenter(): Need three different points!";
		}
	// http://en.wikipedia.org/wiki/Circumscribe#Cartesian_coordinates
	var ax=a.x;
	var ay=a.y;
	var bx=b.x-ax;
	var by=b.y-ay;
	var cx=c.x-ax;
	var cy=c.y-ay;
	var d=2*(bx*cy-by*cx);
	var hb=bx*bx+by*by;
	var hc=cx*cx+cy*cy;
	return new Point((cy*hb-by*hc)/d+ax,(bx*hc-cx*hb)/d+ay);
	};
// Fortune.circleCheckDataNode:
//   n=VDataNode
//   ys=double
Fortune.prototype.circleCheckDataNode=function(n,ys) {
	var l=this.leftDataNode(n);
	var r=this.rightDataNode(n);
	// if any two sites are repeated in the same beach section
	// triplet, there can't be convergence
	if (!l || !r || l.pt.doesEqual(r.pt) || l.pt.doesEqual(n.pt) || n.pt.doesEqual(r.pt)) {
		return null;
		}
	// if points n->l->r are clockwise, then beach section n
	// does not converge, hence it can't end up as a vertex
	if (!this.counterclockwise(l.pt,n.pt,r.pt)) {
		return null;
		}
	var center=this.circumCircleCenter(l.pt,n.pt,r.pt);
	var vce=new VoronoiCircleEvent(l,n,r,center);
	// not valid if the bottom-most point of the circumcircle
	// is above the sweep line
	if (!greaterThanOrEqualWithEpsilon(vce.getY(),ys)) {
		return null;
		}
	return vce;
	};
// FortuneEventQueue:
//   Array as base class, for a reverse ordered array so
//   that pop() return the topmost, leftmost event object
function FortuneEventQueue() {
	this.queue=[];
	}
FortuneEventQueue.prototype.push=function(o) {
	var r=this.queue.length;
	var c;
	if (r) {
		var l=0;
		var i;
		while (l<r) {
			i=(l+r)>>1;
			c=o.compare(this.queue[i]);
			if (c>0) {
				r=i;
				}
			else if (c<0) {
				l=i+1;
				}
			else {
				return;//throw "FortuneEventQueue.push(): Duplicate sites not allowed!";
				}
			}
		this.queue.splice(l,0,o);
		}
	else {
		this.queue.push(o);
		}
	};
FortuneEventQueue.prototype.pop=function() {
	return this.queue.pop();
	};
FortuneEventQueue.prototype.length=function() {
	return this.queue.length;
	};

// Fortune.computeVoronoiGraph:
//   pts=array of Point objects
Fortune.prototype.computeVoronoiGraph=function(nExecuteSteps) {
	var ve; var vce; var vdn;
	for (; nExecuteSteps>0 && this.pq.length()>0; nExecuteSteps--) {
		ve=this.pq.pop();
		this.nProcessedEvents++; // keep track of stats
		this.sweepy=ve.getY();
		if (ve.isDataEvent) {
			this.result=this.processDataEvent(ve,this.result.root,this.vg,ve.getY());
			}
		else if (ve.isCircleEvent) {
			delete this.currentCircles[ve.nodeN.id];
			if (ve.falseAlarm) {
				nExecuteSteps++; // invalid event, nothing was processed really
				this.nFalseAlarms++; // keep track of number of false alarm
				continue;
				}
			this.result=this.processCircleEvent(ve,this.result.root,this.vg,ve.getY());
			}
		for (var iDataNode=0; iDataNode<this.result.checklist.length; iDataNode++) {
			vdn=this.result.checklist[iDataNode];
			// currently pointless, as my JS implementation uses a new unique id for
			// newly created data node, which means no matching circle will be found
			// in the current list of circle... need to fix this. Currently, I think
			// this means two exactly similar circles can be found in the queue...

/*			if (this.currentCircles[vdn.id]!==undefined) {
				this.currentCircles[vdn.id].falseAlarm=true;
				delete this.currentCircles[vdn.id];
				}
*/
			vce=this.circleCheckDataNode(vdn,ve.getY());
			if (vce) {
				this.pq.push(vce);
				this.currentCircles[vdn.id]=vce;
				}
			}
		// ensure that the newly found site doesn't fall within
		// a pending circle event, if so, the circle event is no
		// good.
		if (ve.isDataEvent) {
			for (var vceKey in this.currentCircles) {
				if (this.currentCircles.hasOwnProperty(vceKey)) {
					vce=this.currentCircles[vceKey];
					if (lessThanWithEpsilon(ve.pt.distance(vce.center),vce.getY()-vce.center.y)) {
						vce.falseAlarm=true;
						delete this.currentCircles[vceKey];
						}
					}
				}
			}
		}
	};
Fortune.prototype.resetEventQueue=function() {
	// initialize queue
	this.pq=new FortuneEventQueue();
	var nPts=this.sites.length;
	for (var iPt=0; iPt<nPts; iPt++) {
		this.pq.push(new VoronoiDataEvent(this.sites[iPt]));
		}
	// stats
	this.nProcessedEvents=0;
	this.nFalseAlarms=0;
	// initialize resulting graph
	this.vg=new VoronoiGraph();
	this.currentCircles={};
	this.result={root:null,circleCheckList:[]};
	this.sweepy=0;
	};
Fortune.prototype.clearSites=function() {
	this.sites=[];
	delete this.minxUser;
	delete this.minyUser;
	delete this.fxUser;
	delete this.fyUser;
	};
Fortune.prototype.setSites=function(a) {
	this.clearSites();
	for (var i=0; i<a.length; i++) {
		this.sites[i]=new Point(a[i]);
		}
	this.resetEventQueue();
	};
Fortune.prototype.randomSites=function(n) {
	this.clearSites();
	var w=this.canvas.width;
	var h=this.canvas.height;
	for (var i=0; i<n; i++) {
		this.sites[i]=new Point(self.Math.round(self.Math.random()*w),self.Math.round(self.Math.random()*h));
		}
	this.resetEventQueue();
	};
Fortune.prototype.addSite=function(pt) {
	this.sites.push(new Point(pt));
	this.resetEventQueue();
	};
Fortune.prototype.parseUserSites=function(s) {
	this.clearSites();
	// split string into values, eliminate all NaNs
	var values=s.split(/[^0-9-.+e]+/);
	var nValues=values.length;
	var iValue=0;
	while (iValue<nValues) {
		if (self.isNaN(self.parseFloat(values[iValue]))) {
			values.splice(iValue,1);
			nValues--;
			}
		else {
			iValue++;
			}
		}
	// number of x,y pairs
	var nPairs=values.length&0xfffe;
	// populate sites
	var sites=this.sites;
	var x; var y; var nOutside=0;
	var minx; var maxx; var miny; var maxy;
	var cw=this.canvas.width;
	var ch=this.canvas.height;
	for (var iPair=0; iPair<nPairs; iPair+=2) {
		x=self.parseFloat(values[iPair]);
		y=self.parseFloat(values[iPair+1]);
		if (!self.isNaN(x) && !self.isNaN(y)) {
			sites.push(new Point(x,y));
			minx=minx!==undefined?self.Math.min(minx,x):x;
			maxx=maxx!==undefined?self.Math.max(maxx,x):x;
			miny=miny!==undefined?self.Math.min(miny,y):y;
			maxy=maxy!==undefined?self.Math.max(maxy,y):y;
			nOutside+=x<0||x>cw?1:0;
			nOutside+=y<0||y>ch?1:0;
			}
		}
	// if most values outside canvas, scale values to fit into the canvas (with [10%?] margins all around)
	var nSites=sites.length;
	if (nOutside>nSites) { // somewhat arbitrary.. if more than half values outside, rescale
		this.minxUser=minx; // remember these values to be able to convert back when reporting vertices
		this.minyUser=miny;
		var dx=maxx-minx;
		var dy=maxy-miny;
		// respect original ratio
		var ratio=dx/dy;
		var fx=cw*0.8/dx;
		var fy=ch*0.8/dy;
		if (ratio>1) {
			fy=fx/ratio;
			}
		else {
			fx=fy*ratio;
			}
		this.fxUser=fx; // remember these values to be able to convert back when reporting vertices
		this.fyUser=fy;
		var site;
		for (var iSite=0; iSite<nSites; iSite++) {
			site=sites[iSite];
			site.x=(site.x-minx)*fx+cw*0.1;
			site.y=(site.y-miny)*fy+ch*0.1;
			}
		}
	this.resetEventQueue();
	};
// 0,0,60,100,30,50,60,100 = hexagons
Fortune.prototype.parseUserLattices=function(s) {
	// split string into values, eliminate all NaNs
	var values=s.split(/[^0-9-.+e]+/);
	var nValues=values.length;
	var iValue=0;
	while (iValue<nValues) {
		if (self.isNaN(self.parseFloat(values[iValue]))) {
			values.splice(iValue,1);
			nValues--;
			}
		else {
			iValue++;
			}
		}
	// number of quadruplets
	var nQuads=values.length&0xfffc;
	// populate sites
	var sites=this.sites;
	var cw=this.canvas.width;
	var ch=this.canvas.height;
	var xoffset; var yoffset;
	var xdelta; var ydelta;
	for (var iQuad=0; iQuad<nQuads; iQuad+=4) {
		xoffset=self.parseFloat(values[iQuad]);
		yoffset=self.parseFloat(values[iQuad+1]);
		xdelta=self.parseFloat(values[iQuad+2]);
		ydelta=self.parseFloat(values[iQuad+3]);
		if (!self.isNaN(xoffset) && !self.isNaN(yoffset) && !self.isNaN(xdelta) && !self.isNaN(ydelta)) {
			for (var y=yoffset; y<=ch; y+=ydelta) {
				for (var x=xoffset; x<=cw; x+=xdelta) {
					sites.push(new Point(x,y));
					}
				}
			}
		}
	this.resetEventQueue();
	};
Fortune.prototype.drawBeachline=function(ctx,node) {
	if (node.isDataNode) {
		var p=(node.pt.y-this.sweepy)/2;
		if (p) {
			var width=this.canvas.width;
			var h=node.pt.x;
			var k=node.pt.y-p;
			var left=this.leftDataNode(node);
			var right=this.rightDataNode(node);
			var xleft=left?self.Math.max(this.parabolicCut(left.pt,node.pt,this.sweepy),0):0;
			var xright=right?self.Math.min(this.parabolicCut(node.pt,right.pt,this.sweepy),width):width;
			var xstep=(xright-xleft)/20;
			ctx.strokeStyle=this.alternate?'#00f':'#0cc';
			this.alternate^=1;
			var breakImageWidth=this.breakImage.width;
			var breakImageHeight=this.breakImage.height;
			if (p) {
				var y;
				ctx.beginPath();
				var x=xleft;
				y=self.Math.pow(xleft-h,2)/(4*p)+k;
				if (breakImageWidth && left) {
					ctx.drawImage(this.breakImage,x-breakImageWidth/2,y-breakImageHeight/2);
					}
				ctx.beginPath();
				ctx.moveTo(x,y);
				for (x=xleft; lessThanOrEqualWithEpsilon(x,xright); x+=xstep){
					y=self.Math.pow(x-h,2)/(4*p)+k;
					ctx.lineTo(x,y);
					if (xstep<1e-6) {break;} // quick fix, will revise later
					}
				ctx.stroke();
				if (breakImageWidth && right) {
					x=xright;
					y=self.Math.pow(xright-h,2)/(4*p)+k;
					ctx.drawImage(this.breakImage,x-breakImageWidth/2,y-breakImageHeight/2);
					}
				}
			}
		}
	if (node.left) {
		this.drawBeachline(ctx,node.left);
		}
	if (node.right) {
		this.drawBeachline(ctx,node.right);
		}
	};
Fortune.prototype.draw=function() {
	// clear canvas
	var ctx=this.canvas.getContext('2d');
	var cw=this.canvas.width;
	var ch=this.canvas.height;
	var x; var y;
	ctx.beginPath();
	ctx.rect(0,0,cw,ch);
	ctx.fillStyle='#fff';
	ctx.fill();
	ctx.strokeStyle='#888';
	ctx.stroke();
	// draw sites
	ctx.fillStyle='#000';
	var nSites=this.sites.length;
	for (var iSite=0; iSite<nSites; iSite++){
		var site=this.sites[iSite];
		ctx.beginPath();
		ctx.arc(site.x,site.y,2,0,self.Math.PI*2,true);
		ctx.fill();
		}
	// sweep line (only if queue is not empty))
	if (this.pq && this.pq.length()>0) {
		ctx.save();
		ctx.globalAlpha=0.5;
		ctx.strokeStyle='#f00';
		ctx.lineWidth=1;
		ctx.beginPath();
		ctx.moveTo(0,this.sweepy);
		ctx.lineTo(1000,this.sweepy);
		ctx.stroke();
		ctx.restore();
		}
	// circle events
	if (this.pq) {
		ctx.save();
		var nEvents=this.pq.queue.length;
		var ve;
		ctx.strokeStyle='#888';
		ctx.fillStyle='#aaa';
		for (var iEvent=0; iEvent<nEvents; iEvent++) {
			ve=this.pq.queue[iEvent];
			if (ve.isCircleEvent && !ve.falseAlarm) {
				ctx.globalAlpha=0.25;
				ctx.beginPath();
				ctx.arc(ve.center.x,ve.center.y,2,0,self.Math.PI*2,true);
				ctx.fill();
				ctx.beginPath();
				ctx.arc(ve.center.x,ve.center.y,ve.center.distance(new Point(ve.center.x,ve.getY())),0,self.Math.PI*2,true);
				ctx.stroke();
				ctx.globalAlpha=1;
				ctx.beginPath();
				ctx.arc(ve.center.x,ve.getY(),2,0,self.Math.PI*2,true);
				ctx.fill();
				}
			}
		ctx.restore();
		}
	// draw beach lines and break points (if event queue is empty, skip)
	if (this.result.root && this.pq && this.pq.length()) {
		this.alternate=0; // used to alternate the color of segments on the beach line
		ctx.save();
		ctx.strokeStyle='#f00';
		ctx.globalAlpha=1;
		this.drawBeachline(ctx,this.result.root);
		ctx.restore();
		}
	// draw edges
	if (!this.vg) {
		return;
		}
	var nEdges=this.vg.edges.length;
	var edge;
	for (var iEdge=0; iEdge<nEdges; iEdge++) {
		ctx.save();
		ctx.strokeStyle='#080';
		edge=this.vg.edges[iEdge];
		if (edge.vb) { // both vertices a and b are not infinite
			ctx.beginPath();
			ctx.arc(edge.va.x,edge.va.y,2,0,self.Math.PI*2,true);
			ctx.stroke();
			ctx.beginPath();
			ctx.arc(edge.vb.x,edge.vb.y,2,0,self.Math.PI*2,true);
			ctx.stroke();
			ctx.beginPath();
			ctx.moveTo(edge.va.x,edge.va.y);
			ctx.lineTo(edge.vb.x,edge.vb.y);
			ctx.stroke();
			}
/* the following code, not part of the original C# implementation, is to clip the edges
   extending to infinite with a bounding box. It doesn't work though because the "site
   on the left" is not consistently reported by the original C# algorithm. As I intend
   to replace the binary tree code with a flat data structure reflecting the beachline,
   this will solve the problem. 
		else if (edge.va) { // vertex b is infinite
			// reference: line-line intersection @ http://en.wikipedia.org/wiki/Line-line_intersection
			// x=((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))
			// y=((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4))

			// first: calculate mid-point
			var midx=edge.lPt.x+(edge.rPt.x-edge.lPt.x)/2;
			var midy=edge.lPt.y+(edge.rPt.y-edge.lPt.y)/2;
			// second: find the slope so that we know toward which quadrant the line is pointing
			var dx=edge.lPt.x-midx;
			var dy=edge.lPt.y-midy;
			if (dx===0) { //honrizontal
				x=edge.va.x;
				y=dy<0?0:cw;
				}
			else if (dy===0) { // vertical
				x=dx<0?0:cw;
				y=edge.va.y;
				}
			else { // bottom half
				var x1=edge.va.x; var y1=edge.va.y;
				var x2=midx; var y2=midy;
				var x3; var y3; var x4; var y4;
				var m=self.Math.abs(dx/dy);
				if (dx>0) { // bottom half
					if (dy>0) { // bottom-right quadrant
						if (m>1) { // rather bottom
							x3=0; y3=ch; x4=cw; y4=ch;
							}
						else { // rather right
							x3=cw; y3=0; x4=cw; y4=ch;
							}
						}
					else { // bottom-left quadrant
						if (m>1) { // rather bottom
							x3=0; y3=ch; x4=cw; y4=ch;
							}
						else { // rather left
							x3=0; y3=0; x4=0; y4=ch;
							}
						}
					}
				else{ // top half
					if (dy>0) { // top-right quadrant
						if (m>1) { // rather top
							x3=0; y3=0; x4=cw; y4=0;
							}
						else { // rather right
							x3=cw; y3=0; x4=cw; y4=ch;
							}
						}
					else { // top-left quadrant
						if (m>1) { // rather top
							x3=0; y3=0; x4=cw; y4=0;
							}
						else { // rather left
							x3=0; y3=0; x4=0; y4=ch;
							}
						}
					}
				x=((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));
				y=((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));
				}
			ctx.beginPath();
			ctx.moveTo(edge.va.x,edge.va.y);
			ctx.lineTo(x,y);
			ctx.stroke();
			}
		else { // both vertices a and b are infinite
			}*/
		ctx.restore();
		}
	// draw vertices
	var nVertices=this.vg.vertices.length;
	var vertex;
	for (var iVertex=0; iVertex<nVertices; iVertex++){
		vertex=this.vg.vertices[iVertex];
		ctx.fillStyle='#0f0';
		ctx.beginPath();
		ctx.arc(vertex.x,vertex.y,2,0,self.Math.PI*2,true);
		ctx.fill();
		}
	};
Fortune.prototype.dumpBeachline=function() {
	stdout("Beachline sections, from left to right. Beachline sections wholly outside bounding box displayed in red.",true);
	if (!this.result.root) {return;}
	var node=this.firstDataNode(this.result.root);
	var lnode; var rnode; var xleft; var xright;
	var width=this.canvas.width;
	var outside; var prefix; var postfix;
	var output=''; // for performance purpose, better not call innerHTML repeadtly
	while (node) {
		lnode=this.leftDataNode(node);
		xleft=lnode?this.parabolicCut(lnode.pt,node.pt,this.sweepy):"-Infinite";
		rnode=this.rightDataNode(node);
		xright=rnode?this.parabolicCut(node.pt,rnode.pt,this.sweepy):"+Infinite";
		outside=xright<0||xleft>width;
		prefix=outside?"<span style='color:red'>":"";
		postfix=outside?"</span>":"";
		output+=prefix+"<b>left-break</b>:"+xleft+","+" <b>right-break</b>:"+xright+","+" <b>site</b>:{"+"<b>x</b>:"+node.pt.x+", <b>y</b>:"+node.pt.y+"}"+postfix+"<br/>";
		node=rnode;
		}
	stdout(output);
	};
Fortune.prototype.dumpVertices=function() {
	stdout("Vertices &ndash; ordered on y, than x. Vertices outside bounding box displayed in red.",true);
	if (!this.vg) {return;}
	var vertices=this.vg.vertices;
	vertices.sort(function(a,b){return a.compare(b);}); // ensure vertices are sorted
	var nVertices=vertices.length;
	var vertex;
	var cw=this.canvas.width;
	var ch=this.canvas.height;
	var outside; var prefix; var postfix;
	var output=''; // for performance purpose, better not call innerHTML repeadtly
	for (var iVertex=0; iVertex<nVertices; iVertex++) {
		vertex=vertices[iVertex];
		outside=vertex.x<0||vertex.y<0||vertex.x>cw||vertex.y>ch;
		prefix=outside?"<span style='color:red'>":"";
		postfix=outside?"</span>":"";
		output+=prefix+"<b>y</b>:"+(this.fyUser?(vertex.y-cw*0.1)/this.fyUser+this.minyUser:vertex.y)+", <b>x</b>:"+(this.fxUser?(vertex.x-0.1*ch)/this.fxUser+this.minxUser:vertex.x)+postfix+"<br/>";
		}
	stdout(output);
	};
Fortune.prototype.dumpEdges=function() {
	stdout("Edges &ndash; ordered on vertex A y, than x. Vertices outside bounding box displayed in red.",true);
	if (!this.vg) {return;}
	var edges=this.vg.edges;
	var nEdges=edges.length;
	var cw=this.canvas.width;
	var ch=this.canvas.height;
	var output=''; // for performance purpose, better not call innerHTML repeadtly
	var edge;
	for (var iEdge=0; iEdge<nEdges; iEdge++) {
		edge=edges[iEdge];
		output+="<b>vertex-a</b>:{"+(edge.va?"x:"+edge.va.x+", y:"+edge.va.y:"Infinite")+"}, <b>vertex-b</b>:{"+(edge.vb?"x:"+edge.vb.x+", y:"+edge.vb.y:"Infinite")+"}, <b>left-site</b>:{x:"+edge.lPt.x+", y:"+edge.lPt.y+"}, <b>right-site</b>:{x:"+edge.rPt.x+", y:"+edge.rPt.y+"}, <b>flipped</b>:"+!!edge.flipped+"<br/>";
		}
	stdout(output);
	};