/**
 * jigsawpuzzle-rhill 2.0 (3-Jun-2009) (c) by Raymond Hill
 *
 * jigsawpuzzle-rhill licensed under a Creative Commons
 * Attribution-Noncommercial-Share Alike 2.5 Canada License.
 * Source: http://www.raymondhill.net/puzzle-rhill.php
 *
 * Sorry for the blend name, I didn't want to spend any time figuring
 * some unique, snappy name.
 *
 * I made this puzzle project simply because I was curious if
 * this could be done using the HTML5 <canvas> tag, and yet
 * still have a smooth and fluid in interface. As far as I can tell,
 * It can :)
 * 
 * The key to have responsive graphics interface is to redraw
 * *only* what is necessary. Thus, when moving a piece of puzzle,
 * it is necessary to redraw only the area intersecting the
 * former position, and the area intersecting the new position.
 * Seems trivial enough, but I couldn't find any canvas-based puzzle
 * which actually did that. Using minimal refresh allows huge amount
 * of puzzle piece: I tried 400 pieces, and except for the
 * initialization phase which takes longer to complete, the interface
 * stays smooth.
 *
 * What I learned:
 * - When using drawImage(), canvas to canvas operations are much
 *   faster than image to canvas operations. Thus it is a good idea
 *   to convert an image object into a canvas object if an image
 *   needs to be draw often onto a canvas object (this holds true
 *   for pattern objects.)
 * - The canvas element can handle subpixel positioning. However, there
 *   is a significant performance cost, and it should be avoided if
 *   wherever possible.
 *
 * Still a work in progress, as I wish to experiment further with
 * this little project.
 * 
 * Revisions:
 * 29-May-2009:
 *     - Added button to toggle on/off the showing of edge pieces only
 *     - Added shuffle button
 *     - When moving a piece, all other pieces fade
 *     - num_rows/num_cols respects more original image w/h ratio
 * 31-May-2009:
 *     - JSlint'ed
 *     - Gotten rid of cloneObject() as seen at
 *       http://www.andrewsellick.com/93/javascript-clone-object-function:
 *       The performance cost is way too high. Intelligent copy constructors
 *       are preferred
 * 04-Jun-2009:
 *     - Added rotation, this required rewrite of a good portion  of
 *       the code
 *     - Because of rotation, added code to correctly generate border
 *       shade for floating pieces
 *     - Added preview
 */


/**
  Development notes

  Each PuzzlePiece object is decomposed in three type of tiles:

  Source tile descriptor:
    Information on where to find the tile in the source image:
    - Polygon describing the tile. Coords relative to source
      image = polySource

  Transient tile descriptor:
    Information about the extracted tile. Rotation is applied at
    this level:
    - Polygon describing the tile. Coords relative to the bounding box
      of the polygon = polyTransient
    - A copy of the pixels contained in the src polygon, after rotation.

  Display tile descriptor:
    Information about the location of the tile on screen:
    - Polygon describing the tile on screen = polyDisplay

  Each polygon object caches:
    - the bounding box containing the polygon
    - the centroid of the polygon

  If polySource is modified, the transient tile and onscreen tile
  descriptors must be recalculated.

  If polyTransient is modified (ex.: changing the rotation angle),
  the transient tile and onscreen tile descriptors must be recalculated

  If polyDisplay is changed, the display descriptor must be recalculated.
  However, this can be done efficiently when moving the object around, as
  this requires simply applying delta x and delta y to all cached coords.

  By convention, sTile = source tile descriptor,
  tTile = transient tile descriptor, dTile = display tile descriptor,
  or more generally s*, t*, d*
 */


/*global self*/
// Sound Manager initialization
if (self.soundManager){
	self.soundManager.debugMode=false; // disable debug output
	self.soundManager.onload=function(){
		self.soundManager.createSound({id:'snap1',url:'12842__schluppipuppie__klick_01.mp3',autoLoad:true});
		self.soundManager.createSound({id:'snap2',url:'12843__schluppipuppie__klick_02.mp3',autoLoad:true});
		self.soundManager.createSound({id:'applaud_low',url:'35102_m1rk0_applause_5sec.mp3',autoLoad:false});
		self.soundManager.createSound({id:'applaud_medium',url:'35104_m1rk0_applause_5sec.mp3',autoLoad:false});
		self.soundManager.createSound({id:'applaud_high',url:'60789_J.Zazvurek_Applause_9s.mp3',autoLoad:false});
		};
	}
else {
	self.soundManager={play:function(){}};
	}

var mthrnd = self.Math.round;
var mthceil = self.Math.ceil;
var mthrand = self.Math.random;
var mthsqrt = self.Math.sqrt;
var mthmx = self.Math.max;
var mthmn = self.Math.min;
var mthabs = self.Math.abs;
var mthatan = self.Math.atan2;
var debug_on = true;

// helper functions
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);
		}
	}
// Point object
function Point(a,b) {
	//stderr("Point ctor: a="+a+",b="+b);
	// a=x,b=y
	if (b!==undefined) {
		this.x=a;
		this.y=b;
		}
	// a=Point or {x:?,y:?}
	else if (a!==undefined) {
		this.x=a.x;
		this.y=a.y;
		}
	// empty
	else {
		this.x=0;
		this.y=0;
		}
	}
Point.prototype.toString = function() {
	return "{x:"+this.x+",y:"+this.y+"}";
	};
Point.prototype.offset = function(dx,dy) {
	this.x+=dx; this.y+=dy;
	};
Point.prototype.set = function(x,y) {
	this.x=x; this.y=y;
	};

// Bounding box object
function Bbox(a,b,c,d) {
	//stderr("Bbox ctor: a="+a+",b="+b+",c="+c+",d="+d);
	// a=x1,b=y1,c=x2,d=y2
	if (d!==undefined) {
		this.tl=new Point(a,b);
		this.br=new Point(c,d);
		}
	// a=Point or {x:?,y:?},b=Point or {x:?,y:?}
	else if (b!==undefined) {
		var mn=Math.min;
		var mx=Math.max;
		this.tl=new Point(mn(a.x,b.x),mn(a.y,b.y));
		this.br=new Point(mx(a.x,b.x),mx(a.y,b.y));
		}
	// a=Bbox or {tl:{x:?,y:?},br:{x:?,y:?}}
	else if (a!==undefined) {
		this.tl=new Point(a.tl);
		this.br=new Point(a.br);
		}
	// empty
	else {
		this.tl=new Point();
		this.br=new Point();
		}
	}
Bbox.prototype.toString = function() {
	return "{tl:"+this.tl+",br:"+this.br+"}";
	};
Bbox.prototype.getTopleft = function() {
	return new Point(this.tl);
	};	
Bbox.prototype.getBottomright = function() {
	return new Point(this.br);
	};
Bbox.prototype.union_point = function(p) {
	//stderr("Bbox.union_point: p="+p);
	var mn=Math.min;
	var mx=Math.max;
	this.tl.x=mn(this.tl.x,p.x);
	this.tl.y=mn(this.tl.y,p.y);
	this.br.x=mx(this.br.x,p.x);
	this.br.y=mx(this.br.y,p.y);
	};
Bbox.prototype.width = function() {
	return (this.br.x-this.tl.x)+1;
	};
Bbox.prototype.height = function() {
	return (this.br.y-this.tl.y)+1;
	};
Bbox.prototype.offset = function(dx,dy) {
	this.tl.offset(dx,dy); this.br.offset(dx,dy);
	};
Bbox.prototype.set = function(a) {
	// array of Points
	var mx = self.Math.max;
	var mn = self.Math.min;
	this.tl.x = this.br.x = a[0].x;
	this.tl.y = this.br.y = a[0].y;
	for ( var i=1; i<a.length; i++ ) {
		var p = a[i];
		this.tl.x = mn(this.tl.x,p.x);
		this.tl.y = mn(this.tl.y,p.y);
		this.br.x = mx(this.br.x,p.x);
		this.br.y = mx(this.br.y,p.y);
		}
	};
Bbox.prototype.point_in = function(p) {
	return p.x > this.tl.x && p.x < this.br.x && p.y > this.tl.y && p.y < this.br.y;
	};
Bbox.prototype.does_intersect = function(bb) {
	var mn = self.Math.min;
	var mx = self.Math.max;
	return (mn(bb.br.x,this.br.x)-mx(bb.tl.x,this.tl.x)) > 0 && 
	       (mn(bb.br.y,this.br.y)-mx(bb.tl.y,this.tl.y)) > 0;
	};
Bbox.prototype.union = function(bb) {
	//stderr("Bbox.union: bb="+bb);
	var mn = self.Math.min;
	var mx = self.Math.max;
	this.tl.x = mn(this.tl.x,bb.tl.x);
	this.tl.y = mn(this.tl.y,bb.tl.y);
	this.br.x = mx(this.br.x,bb.br.x);
	this.br.y = mx(this.br.y,bb.br.y);
	};
Bbox.prototype.inflate = function(a) {
	this.tl.x -= a;
	this.tl.y -= a;
	this.br.x += a;
	this.br.y += a;
	};

// Region object (collection of [todo:non-overlapping] bounding boxes
function Region() {
	this.bboxes=[];
	}
Region.prototype.add = function(tl,br) {
	this.bboxes[this.bboxes.length]=new Bbox(tl,br);
	};
Region.prototype.fill = function(ctx,fillStyle,clip) {
	ctx.fillStyle = fillStyle;
	for ( var i=0; i<this.bboxes.length; i++ ) {
		var bbox = this.bboxes[i];
		if ( clip === undefined || !clip || bbox.does_intersect(clip) ) {
			ctx.fillRect(bbox.tl.x,bbox.tl.y,bbox.width(),bbox.height());
			}
		}
	};

// Quadrilateral object
function Quadrilateral(a,b,c,d) {
	//stderr("Quadrilateral ctor: a="+a+",b="+b+",c="+c+",d="+d);
	this.setPoly(a,b,c,d);
	}
Quadrilateral.prototype.toString = function() {
	return "["+this.pts[0]+","+this.pts[1]+","+this.pts[2]+","+this.pts[3]+"],bbox:"+this.getBbox();
	};
Quadrilateral.prototype.setPoly = function(a,b,c,d) {
	// a=Point, b=Point, c=Point, d=Point
	if ( b !== undefined ) {
		this.pts = [new Point(a),new Point(b),new Point(c),new Point(d)];
		}
	// a=Quadrilateral
	else if ( a instanceof Quadrilateral ) {
		this.pts = [new Point(a.pts[0]),new Point(a.pts[1]),new Point(a.pts[2]),new Point(a.pts[3])];
		}
	// a=array of points
	else if ( a instanceof Array ) {
		this.pts = [new Point(a[0]),new Point(a[1]),new Point(a[2]),new Point(a[3])];
		}
	// empty
	else {
		this.pts = [new Point(),new Point(),new Point(),new Point()];
		}
	};
Quadrilateral.prototype.getBbox = function() {
	//stderr("Quadrilateral.getBbox");
	if ( !this.bbox ) {
		this.bbox = new Bbox(this.pts[0],this.pts[2]);
		this.bbox.union_point(this.pts[1]);
		this.bbox.union_point(this.pts[3]);		
		}
	return new Bbox(this.bbox);
	};
Quadrilateral.prototype.area = function() {
	// http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/
	var area=0;
	var n=this.pts.length;
	var j=n-1;
	var p1; var p2;
	for (var i=0;i<n;j=i++) {
		p1=this.pts[i];
		p2=this.pts[j];
		area+=p1.x*p2.y;
		area-=p1.y*p2.x;
		}
	return area/2;
	};
Quadrilateral.prototype.getCentroid = function() {
	//stderr("Quadrilateral.getCentroid");
	if ( !this.centroid ) {
		//stderr("Quadrilateral.getCentroid: Calculating centroid...");
		// http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/
		var x=0; var y=0;
		var f;
		var n=this.pts.length;
		var j=n-1;
		var pts=this.pts;
		var p1; var p2;
		for (var i=0;i<n;j=i++) {
			p1=pts[i];
			p2=pts[j];
			f=p1.x*p2.y-p2.x*p1.y;
			x+=(p1.x+p2.x)*f;
			y+=(p1.y+p2.y)*f;
			}
		f=this.area()*6;
		var tl=this.getBbox().getTopleft();
		this.centroid=new Point(mthrnd(x/f-tl.x),mthrnd(y/f-tl.y));
		}
	return new Point(this.centroid);
	};
Quadrilateral.prototype.point_in = function(p) {
	//stderr("Quadrilateral.point_in: p="+p);
	/**
	 * The following function which test whether a point is inside a
	 * polygone is based on Wm. Randolph Franklin's algorithm, who
	 * allows his work to be reused in others' work as long as the
	 * following notice is included in the work. so here it is:
	 *
	 * =====
	 * Copyright (c) 1970-2003, Wm. Randolph Franklin
	 * Permission is hereby granted, free of charge, to any person
	 * obtaining a copy of this software and associated documentation
	 * files (the "Software"), to deal in the Software without restriction,
	 * including without limitation the rights to use, copy, modify, merge,
	 * publish, distribute, sublicense, and/or sell copies of the Software,
	 * and to permit persons to whom the Software is furnished to do so,
	 * subject to the following conditions:
	 *
	 * 1. Redistributions of source code must retain the above copyright
	 *    notice, this list of conditions and the following disclaimers.
	 * 2. Redistributions in binary form must reproduce the above copyright
	 *    notice in the documentation and/or other materials provided with
	 *    the distribution.
	 * 3. The name of W. Randolph Franklin may not be used to endorse or
	 *    promote products derived from this Software without specific
	 *    prior written permission. 
	 *
	 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
	 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
	 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
	 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
	 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
	 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
	 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
	 * SOFTWARE.
	 * =====
	 * http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
	**/
	var r = false;
	var ar = this.pts;

	for ( var i=0, j=3; i<4; j=i++ ) {
		var pti = ar[i];
		var ptj = ar[j];
		if ( (pti.y>p.y)!=(ptj.y>p.y) && p.x<((ptj.x-pti.x)*(p.y-pti.y)/(ptj.y-pti.y)+pti.x) ) {
			r=!r;
			}
		}
	return r;
	};
Quadrilateral.prototype.offset = function(dx,dy) {
	//stderr("Quadrilateral.offset: dx="+dx+",dy="+dy);
	this.pts[0].offset(dx,dy);
	this.pts[1].offset(dx,dy);
	this.pts[2].offset(dx,dy);
	this.pts[3].offset(dx,dy);
	if ( this.bbox ) {
		this.bbox.offset(dx,dy);		
		}
	};
Quadrilateral.prototype.moveto = function(x,y) {
	//stderr("Quadrilateral.moveto: x="+x+",y="+y);
	var tl=this.getBbox().getTopLeft();
	this.offset(x-tl.x,y-tl.y);
	};
Quadrilateral.prototype.rotate = function(angle,x0,y0) {
	//stderr("Quadrilateral.rotate: deg="+angle+",x0="+x0+",y0="+y0);
	if ( !angle ) { return;}
	var ar = this.pts;
	// http://www.webreference.com/js/tips/000712.html
	var cosang = self.Math.cos(angle);
	var sinang = self.Math.sin(angle);
	var rnd = self.Math.round;
	for ( var i=0; i<4; i++ ) {
		//stderr("Quadrilateral.rotate: in"+i+"="+ar[i]);
		var pt = ar[i];
		var x = pt.x-x0;
		var y = pt.y-y0;
		// http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2
		pt.x = rnd(x*cosang-y*sinang)+x0;
		pt.y = rnd(x*sinang+y*cosang)+y0;
		//stderr("Quadrilateral.rotate: out"+i+"="+ar[i]);
		}
	this.bbox = null; // no longer valid
	this.centroid = null; // no longer valid
	};
Quadrilateral.prototype.does_intersect = function(bbox) {
	return this.getBbox().does_intersect(bbox);
	};

/**
  Puzzle tile base class
 */
function PuzzleTile() {
	this.poly = null;
	}
PuzzleTile.prototype.setPoly = function(pts) {
	this.poly = new Quadrilateral(pts);
	};
PuzzleTile.prototype.getPoly = function() {
	return new Quadrilateral(this.poly);
	};
PuzzleTile.prototype.getBbox = function() {
	return this.poly.getBbox();
	};
PuzzleTile.prototype.getCentroid = function() {
	return this.poly.getCentroid();
	};

/**
  Source tile descriptor
 */
function PuzzleSourceTile(img) {
	PuzzleTile.call(this);
	this.sImage = img;
	}
PuzzleSourceTile.prototype = new PuzzleTile();
PuzzleSourceTile.prototype.getSourceImage = function() {
	return this.sImage;
	};

/**
  Transient tile descriptor
 */
function PuzzleTransientTile(sTile) {
	PuzzleTile.call(this);
	this.sTile = sTile;
	this.angleStep = 0;
	this.angleMaxSteps = 1; // default = no rotation
	this.angleRadians = 6.28318530718; // precalculated angle in radians for performance purpose
	}
PuzzleTransientTile.prototype = new PuzzleTile();
PuzzleTransientTile.prototype.getAngleStep = function() {
	return this.angleStep;
	};
PuzzleTransientTile.prototype.setAngleStep = function(step,maxSteps) {
	// quantize max steps into a factor of 360
	if ( maxSteps !== undefined ) {
		this.angleMaxSteps = 360/self.Math.round(360/self.Math.min(self.Math.max(maxSteps,1),90));
		}
	// ensure step is within range
	this.angleStep = step % this.angleMaxSteps;
	// precalculate angle in radian: 2PI*step/maxsteps
	this.angleRadians = 6.28318530718 * this.angleStep / this.angleMaxSteps;
	// invalidate internal state
	this.tImage = null;
	};
PuzzleTransientTile.prototype.sync = function() {
	if ( !this.tImage ) {
		this.tImage = self.document.createElement('canvas');
		// we need to find out the bbox of the rotated source
		// in order to know the required image size
		this.poly = this.sTile.getPoly();
		var sBbox = this.sTile.getBbox();
		var sTopleft = sBbox.getTopleft();
		var sCentroid = this.sTile.getCentroid();
		// rotate
		this.poly.rotate(this.angleRadians,sTopleft.x+sCentroid.x,sTopleft.y+sCentroid.y);
		// post-rotation bbox different from pre-
		var tBbox = this.poly.getBbox();
		var tTopleft = tBbox.getTopleft();
		// set origin to self
		this.poly.offset(-tTopleft.x,-tTopleft.y);
		var tCentroid = this.poly.getCentroid();
		this.tImage.width = tBbox.width();
		this.tImage.height = tBbox.height();
		// transfer/rotate source tile image
		var ctx = this.tImage.getContext('2d');
		ctx.save();
		ctx.beginPath();
		ctx.moveTo(this.poly.pts[0].x,this.poly.pts[0].y);
		ctx.lineTo(this.poly.pts[1].x,this.poly.pts[1].y);
		ctx.lineTo(this.poly.pts[2].x,this.poly.pts[2].y);
		ctx.lineTo(this.poly.pts[3].x,this.poly.pts[3].y);
		ctx.closePath();
		ctx.clip();
		ctx.save();
		if ( this.angleStep ) {
			ctx.translate(tCentroid.x,tCentroid.y);
			ctx.rotate(this.angleRadians);
			ctx.translate(-tCentroid.x,-tCentroid.y);
			}
		ctx.drawImage(this.sTile.getSourceImage(),sTopleft.x,sTopleft.y,sBbox.width(),sBbox.height(),tCentroid.x-sCentroid.x,tCentroid.y-sCentroid.y,sBbox.width(),sBbox.height());
		ctx.restore();
		// draw each segment
		// color of segment depends of the slope, for a 3d effect
		ctx.lineWidth = 2;
		var n=this.poly.pts.length;
		var j=n-1;
		var p1; var p2;
		var dx; var dy;
		var g;
		for ( var i=0; i<n; j=i++ ) {
			p1=this.poly.pts[j];
			p2=this.poly.pts[i];
			// we rotate the segment backward 45 deg, this allow the light
			// source to be located top-left otherwise it would be located
			// left
			// we precalculate as much as we can for performance
			// cos(-PI/4)=0.70710678 and sin(-PI/4)=-0.70710678
			// dx,dy represent the rotated slope parameters as per
			// m = (y2-y1)/(x2-x1)
			// sin(PI/4) = cos(PI/4) = 0.70710678118654752440084436210485
			// 255/PI = 81.169020976866621242130719319982
			dx=(p2.x-p1.x)*0.70710678;
			dy=(p2.y-p1.y)*0.70710678;
			g=mthabs(mthrnd(mthatan(dx+dy,dy-dx)*81.16902098));
			g=(g<16)?"0"+g.toString(16):g.toString(16);
			ctx.strokeStyle = "#"+g+g+g;
			ctx.beginPath();
			ctx.moveTo(p1.x,p1.y);
			ctx.lineTo(p2.x,p2.y);
			ctx.stroke();
			}
		ctx.restore();
		}
	};
PuzzleTransientTile.prototype.getPoly = function() {
	// we need to overload since our image is valid only when we are in sync with source tile
	if ( !this.tImage ) { this.sync(); }
	return PuzzleTile.prototype.getPoly.call(this);
	};
PuzzleTransientTile.prototype.getTransientImage = function() {
	// we need to overload since our image is valid only when we are in sync with source tile
	if ( !this.tImage ) { this.sync(); }
	return this.tImage;
	};
PuzzleTransientTile.prototype.getBbox = function() {
	// we need to overload since our bbox is valid only when we are in sync with source tile
	if ( !this.tImage ) { this.sync(); }
	return PuzzleTile.prototype.getBbox.call(this);
	};
PuzzleTransientTile.prototype.getCentroid = function() {
	// we need to overload since our poly is valid only when we are in sync with source tile
	if ( !this.tImage ) { this.sync(); }
	return PuzzleTile.prototype.getCentroid.call(this);
	};

/**
  Display tile descriptor
 */
function PuzzleDisplayTile(tTile) {
	PuzzleTile.call(this);
	this.tTile = tTile;
	this.dPos = new Point();
	}
PuzzleDisplayTile.prototype = new PuzzleTile();
PuzzleDisplayTile.prototype.getDisplayPos = function() {
	return new Point(this.dPos);
	};
PuzzleDisplayTile.prototype.setDisplayPos = function(a,b) {
	var dx = this.dPos.x;
	var dy = this.dPos.y;
	this.dPos.set(a,b);
	dx = this.dPos.x - dx;
	dy = this.dPos.y - dy;
	if ( this.poly ) {
		this.poly.offset(dx,dy);
		}
	};
PuzzleDisplayTile.prototype.getDisplayImage = function() {
	// the display image is the same as the transient image
	return this.tTile.getTransientImage();
	};
PuzzleDisplayTile.prototype.getAngleStep = function() {
	return this.tTile.getAngleStep();
	};
PuzzleDisplayTile.prototype.setAngleStep = function(step,maxSteps) {
	// pass call down to the transient tile and invalid self
	this.tTile.setAngleStep(step,maxSteps);
	this.poly = null;
	};
PuzzleDisplayTile.prototype.sync = function() {
	if ( !this.poly ) {
		this.poly = this.tTile.getPoly();
		// shift to screen position
		var tCentroid = this.tTile.getCentroid();
		this.poly.offset(this.dPos.x-tCentroid.x,this.dPos.y-tCentroid.y);
		}
	};
PuzzleDisplayTile.prototype.getPoly = function() {
	// we need to overload since our image is valid only when we are in sync with transient tile
	if ( !this.poly ) { this.sync(); }
	return PuzzleTile.prototype.getPoly.call(this);
	};
PuzzleDisplayTile.prototype.getBbox = function() {
	// we need to overload since our bbox is valid only when we are in sync with transient tile
	if ( !this.poly ) { this.sync(); }
	return PuzzleTile.prototype.getBbox.call(this);
	};
PuzzleDisplayTile.prototype.getCentroid = function() {
	// we need to overload since our poly is valid only when we are in sync with transient tile
	if ( !this.poly ) { this.sync(); }
	return PuzzleTile.prototype.getCentroid.call(this);
	};
PuzzleDisplayTile.prototype.point_in = function(p) {
	if ( !this.poly ) { this.sync(); }
	return this.poly.point_in(p);
	};

/**
 Puzzle part
 */
function PuzzlePart() {
	}

// Puzzle piece
function PuzzlePiece(edge,pts,img) {
	this.sTile = new PuzzleSourceTile(img);
	this.sTile.setPoly(pts);
	this.tTile = new PuzzleTransientTile(this.sTile);
	this.dTile = new PuzzleDisplayTile(this.tTile);
	this.piece = true; // this is a puzzle piece
	this.edge = edge; // whether the piece is on the edge
	this.correct = false; // whether the piece is correctly placed
	PuzzlePart.call(this);
	}
PuzzlePiece.prototype = new PuzzlePart();
PuzzlePiece.prototype.getAngleStep = function() {
	return this.dTile.getAngleStep();
	};
PuzzlePiece.prototype.setAngleStep = function(step,numsteps) {
	this.dTile.setAngleStep(step,numsteps);
	};
PuzzlePiece.prototype.setDisplayPos = function(x,y) {
	this.dTile.setDisplayPos(x,y);
	};
PuzzlePiece.prototype.getDisplayPos = function() {
	return this.dTile.getDisplayPos();
	};
PuzzlePiece.prototype.getDisplayBbox = function() {
	return this.dTile.getBbox();
	};
PuzzlePiece.prototype.draw = function(ctx) {
	var dImage = this.dTile.getDisplayImage();
	var dTopleft = this.dTile.getBbox().getTopleft();
	ctx.drawImage(dImage,dTopleft.x,dTopleft.y);
	};
PuzzlePiece.prototype.point_in = function(p) {
	return this.dTile.point_in(p);
	};
PuzzlePiece.prototype.does_intersect = function(bbox) {
	return bbox.does_intersect(this.getDisplayBbox());
	};

// Puzzle preview box
function PuzzlePreview(img) {
	// preview is ?px max on either side
	this.shadow = 8;
	var imgw = 160;
	var imgh = 160;
	var ratio = img.width / img.height;
	if ( ratio >= 1 ) { imgh /= ratio; }
	else { imgw *= ratio; }
	// ensure no fraction, thus no subpixel operations on the canvas
	imgw = self.Math.round(imgw);
	imgh = self.Math.round(imgh);
	this.image = self.document.createElement('canvas');
	this.image.width = imgw+this.shadow;
	this.image.height = imgh+this.shadow;
	this.bbox = new Bbox(0,0,imgw+this.shadow,imgh+this.shadow);
	// transfer source tile image
	var ctx = this.image.getContext('2d');
	ctx.drawImage(img,0,0,imgw,imgh);
	// frame to highlight preview
	ctx.save();
	ctx.beginPath();
	ctx.moveTo(0,0);
	ctx.lineTo(imgw,0);
	ctx.lineTo(imgw,imgh);
	ctx.lineTo(0,imgh);
	ctx.closePath();
	ctx.clip();
	ctx.strokeStyle = '#f00';
	ctx.lineWidth = 2;
	ctx.globalAlpha = 0.8;
	ctx.strokeRect(0,0,imgw,imgh);
	ctx.restore();
	// shadow simulation, I can't make the built-in work
	ctx.fillStyle = '#000';
	ctx.globalAlpha = 0.5;
	ctx.fillRect(imgw,this.shadow,this.shadow,imgh); // left shadow
	ctx.fillRect(this.shadow,imgh,imgw-this.shadow,this.shadow); // bottom shadow
	}
PuzzlePreview.prototype = new PuzzlePart();
PuzzlePreview.prototype.draw = function(ctx) {
	ctx.save();
	//ctx.shadowOffsetX = ctx.shadowOffsetY = this.shadow;
	//ctx.shadowColor = 'rgba(127, 127, 127, 0.33)';
	//ctx.shadowBlur = 2;
	ctx.drawImage(this.image,this.bbox.tl.x,this.bbox.tl.y);
	ctx.restore();
	};
PuzzlePreview.prototype.setDisplayPos = function(x,y) {
	var topleft = this.bbox.getTopleft();
	this.bbox.offset(x-topleft.x,y-topleft.y);
	};
PuzzlePreview.prototype.getDisplayPos = function() {
	return this.bbox.getTopleft();
	};
PuzzlePreview.prototype.getDisplayBbox = function() {
	return new Bbox(this.bbox);
	};
PuzzlePreview.prototype.point_in = function(p) {
	var noShadowBbox = new Bbox(this.bbox);
	noShadowBbox.br.x -= this.shadow;
	noShadowBbox.br.y -= this.shadow;
	return noShadowBbox.point_in(p);
	};
PuzzlePreview.prototype.does_intersect = function(bbox) {
	return this.bbox.does_intersect(bbox);
	};

// Puzzle object
function Puzzle(id,puzzleOptions) {
	var me = this;
	this.canvasObj = self.document.createElement('canvas');
	this.canvasObj.width = '1040';
	this.canvasObj.height = '840';
	if ( this.canvasObj.getContext === undefined ) { return; }
	var canvasParent=self.document.getElementById('canvasParent');
	canvasParent.style.backgroundColor='#777';
	canvasParent.style.width=this.canvasObj.width+'px';
	canvasParent.style.height=this.canvasObj.height+'px';
	canvasParent.innerHTML='';
	canvasParent.appendChild(this.canvasObj);
	this.imoved = -1; // the (drawing stack) index of the part being moved
	this.movedAnchor = new Point(); // the distance of the mouse position relative to the top-left corner of the piece being moved
	this.showEdges = false;
	this.numPieces = puzzleOptions.puzzlePieces?puzzleOptions.puzzlePieces:16;
	this.complexity = puzzleOptions.puzzleComplexity!==undefined?mthmx(mthmn(puzzleOptions.puzzleComplexity,9),0):4;
	this.angleMaxSteps = puzzleOptions.puzzleRotate!==undefined?self.Math.max(self.Math.min(puzzleOptions.puzzleRotate,90),1):24;
	// handle user options
	self.document.getElementById("puzzleShowEdges").onclick = function() {
		me.showEdges = !me.showEdges;
		this.value = (me.showEdges)?"Show all pieces":"Show edge pieces only";
		me.draw();
		};
	// default drawing stack
	this.drawing_stack=[];
	// default puzzle frame
	this.bedFrame = new Region();
	this.bedFrame.add({x:0,y:0},{x:this.canvasObj.width,y:this.canvasObj.height});
	// default puzzle bed
	this.bbox_img = new Bbox();
	// background image for puzzle frame
	var bgFrm = new self.Image();
	bgFrm.onload = function(){
		me.bgCanvas = self.document.createElement('canvas');
		me.bgCanvas.width = this.width;
		me.bgCanvas.height = this.height;
		me.bgCanvas.getContext('2d').drawImage(bgFrm,0,0,me.bgCanvas.width,me.bgCanvas.height);
		this.onload = null;
		me.draw(); // force redraw now that we have our background image ready
		};
	bgFrm.src = 'bg-b19marbles013.jpg'; // Source: http://www.imageafter.com/category.php?category=marbles
	// background image for puzzle bed
	var bgBed = new self.Image();
	bgBed.onload = function(){
		me.bgBed = self.document.createElement('canvas');
		me.bgBed.width = this.width;
		me.bgBed.height = this.height;
		me.bgBed.getContext('2d').drawImage(bgBed,0,0,me.bgBed.width,me.bgBed.height);
		this.onload = null;
		me.draw(); // force redraw now that we have our background image ready
		};
	bgBed.src = 'checkerboard.png'; // Source: http://media.photobucket.com/image/transparent%20pattern%20background/bitwierd/Chequerboard.png

	this.shuffle = function() {
		for ( var ipart = 0; ipart < this.drawing_stack.length; ipart++ ) {
			var partref = me.drawing_stack[ipart];
			if ( !partref.piece ) {
				continue;
				}
			partref.setDisplayPos(mthrnd(mthrand()*(me.canvasObj.width-40)),mthrnd(mthrand()*(me.canvasObj.height-40)));
			partref.setAngleStep(mthrnd(mthrand()*me.angleMaxSteps),me.angleMaxSteps);
			partref.correct = false;
			}
		};
	this.draw = function(bbox) {
		//stderr("Puzzle.draw(): bbox="+bbox);
		var ctx = me.canvasObj.getContext('2d');
		ctx.save();
		// draw only what intersect with bbox
		if ( bbox ) {
			ctx.beginPath();
			ctx.moveTo(bbox.tl.x,bbox.tl.y);
			ctx.lineTo(bbox.br.x,bbox.tl.y);
			ctx.lineTo(bbox.br.x,bbox.br.y);
			ctx.lineTo(bbox.tl.x,bbox.br.y);
			ctx.closePath();
			ctx.clip();
			}
		// canvas area
		if ( !me.bgPat && me.bgCanvas!==undefined ) { 
			me.bgPat = ctx.createPattern(me.bgCanvas,'repeat');
			}
		me.bedFrame.fill(ctx,me.bgPat!==undefined?me.bgPat:self.document.getElementById('canvasParent').style.backgroundColor,bbox);
		// puzzle bed area
		if ( !me.bgBedPattern && me.bgBed!==undefined ) { 
			me.bgBedPattern = ctx.createPattern(me.bgBed,'repeat');
			}
		ctx.fillStyle = me.bgBedPattern!==undefined?me.bgBedPattern:'#fff';
		ctx.fillRect(me.bbox_img.tl.x,me.bbox_img.tl.y,me.bbox_img.width(),me.bbox_img.height());
		// puzzle parts
		ctx.globalCompositeOperation = "source-over";
		// if solved, display original picture
		if ( me.is_solved() ) {
			ctx.drawImage(me.imageObj,me.bbox_img.tl.x,me.bbox_img.tl.y,me.bbox_img.width(),me.bbox_img.height());
			}
		// else display parts
		else {
			var movingPiece = (me.imoved >= 0 && me.drawing_stack[me.imoved].piece);
			// store locally often used properties for efficiency
			var imoved = me.imoved;
			var showedges = me.showEdges;
			var stack = me.drawing_stack;
			// stack drawn from bottom to top
			var nparts = stack.length;
			for ( var ipart = 0; ipart < nparts; ipart++ ) {
				var partref = stack[ipart];
				if ( !bbox || partref.does_intersect(bbox) ) {
					ctx.globalAlpha = (partref.piece&&((movingPiece&&imoved>=0&&ipart!=imoved&&!partref.correct)||(showedges&&!partref.edge)))?0.1:1.0;
					partref.draw(ctx);
					}
				}
			}
		ctx.restore();
		};
	this.init = function() {
		//stderr("Puzzle.init()");
		var img_width = me.img.width;
		var img_height = me.img.height;
		var img_ratio = img_width / img_height;
		// if image size < 80px, zoom in
		if ( img_width < 80 || img_height < 80 ) {
			if ( img_ratio >= 1.0 ) {
				img_width = 80;
				img_height = mthrnd(img_width/img_ratio)|0;
				}
			else {
				img_height = 80;
				img_width = mthrnd(img_height*img_ratio)|0;
				}
			}
		else if ( img_width > (me.canvasObj.width-40) || img_height > (me.canvasObj.height-40) ) {
			if ( img_ratio >= 1.0 ) {
				img_width = me.canvasObj.width-40;
				img_height = mthrnd(img_width/img_ratio)|0;
				}
			else {
				img_height = me.canvasObj.height-40;
				img_width = mthrnd(img_height*img_ratio)|0;
				}
			}
		if ( img_width < 80 || img_height < 80 || img_width > (me.canvasObj.width-40) || img_height > (me.canvasObj.height-40) ) {
			stdout("Because of its size, this image can't be used as a puzzle");
			return;
			}
		stdout("Original image size (w x h): "+me.img.width+"px &times; "+me.img.height+"px");
		if ( img_width != me.img.width || img_height != me.img.height ) {
			stdout("Resized to "+img_width+"px &times; "+img_height+"px");
			}
		// following will be used to generate puzzle pieces
		var num_cols = mthmn(mthmx(mthceil(mthsqrt(me.numPieces)*mthsqrt(img_ratio)),2),mthrnd(this.width/40)); // pieces can't be smaller than 40px
		var num_rows = mthmn(mthmx(mthceil(mthsqrt(me.numPieces)/mthsqrt(img_ratio)),2),mthrnd(this.height/40)); // pieces can't be smaller than 40px
		stdout("Actual number of pieces: "+num_cols*num_rows+" ("+num_cols+" &times; "+num_rows+" pieces)");
		// create the image that will be used as a basis for the puzzle
		me.imageObj = self.document.createElement('canvas');
		me.imageObj.width = img_width;
		me.imageObj.height = img_height;
		var ctx = me.imageObj.getContext('2d');
		ctx.drawImage(me.img,0,0,me.img.width,me.img.height,0,0,img_width,img_height);
		// center puzzle bed in canvas
		me.bbox_img = new Bbox({x:0,y:0},{x:me.imageObj.width-1,y:me.imageObj.height-1});
		me.bbox_img.offset((me.canvasObj.width-me.imageObj.width)>>1,(me.canvasObj.height-me.imageObj.height)>>1);
		// build region for area surrounding puzzle bed
		me.bedFrame = new Region();
		me.bedFrame.add({x:0,y:0},{x:me.canvasObj.width,y:me.bbox_img.tl.y}); // top
		me.bedFrame.add({x:0,y:me.bbox_img.tl.y},{x:me.bbox_img.tl.x,y:me.canvasObj.height}); // left
		me.bedFrame.add({x:me.bbox_img.br.x,y:me.bbox_img.tl.y},{x:me.canvasObj.width,y:me.canvasObj.height}); // right
		me.bedFrame.add({x:me.bbox_img.tl.x,y:me.bbox_img.br.y},{x:me.bbox_img.br.x,y:me.canvasObj.height}); // bottom
		var part_width = mthrnd(me.bbox_img.width()/num_cols); // rounded to avoid fractional pixels
		var part_height = mthrnd(me.bbox_img.height()/num_rows); // rounded to avoid fractional pixels
		var part_width_var = mthrnd(part_width * mthmx(mthmn(me.complexity,9),0) * 0.48 / 9);
		var part_height_var = mthrnd(part_height * mthmx(mthmn(me.complexity,9),0) * 0.48 / 9);
		var random_part_x = function(part_index) { return part_width*part_index+mthrnd(part_width_var*2*mthrand())-part_width_var; };
		var random_part_y = function(part_index) { return part_height*part_index+mthrnd(part_height_var*2*mthrand())-part_height_var; };
		// drawing stack
		me.drawing_stack=[];
		// generate parts
		var parts=[num_rows];
		var imgw = me.bbox_img.width();  // local variables faster than looking up properties
		var imgh = me.bbox_img.height(); // this matters within loops
		for ( var row = 0; row < num_rows; row++ ) {
			parts[row] = [num_cols];
			for ( var col = 0; col < num_cols; col++ ) {
				me.drawing_stack[me.drawing_stack.length] = parts[row][col] = new PuzzlePiece(
					(row===0)||(col===0)||(row==num_rows-1)||(col==num_cols-1),
					[(col===0)?((row===0)?{x:0,y:0}:parts[row-1][0].sTile.getPoly().pts[3]):parts[row][col-1].sTile.getPoly().pts[1],
					(row===0)?{x:(col==num_cols-1)?imgw:random_part_x(col+1),y:0}:parts[row-1][col].sTile.getPoly().pts[2],
					{x:(col==num_cols-1)?imgw:random_part_x(col+1),y:(row==num_rows-1)?imgh:random_part_y(row+1)},
					(col===0)?{x:0,y:(row==num_rows-1)?imgh:random_part_y(row+1)}:parts[row][col-1].sTile.getPoly().pts[2]],
					me.imageObj);
				}
			}
		// create preview
		me.drawing_stack[me.drawing_stack.length] = new PuzzlePreview(me.img);
		me.shuffle();
		me.draw();
		};
	this.part_under_point = function(p) {
		for ( var ipart = this.drawing_stack.length-1; ipart >= 0; ipart-- ) {
			var partref = me.drawing_stack[ipart];
			if ( partref.point_in(p) && (!partref.piece || (!partref.correct && (!me.showEdges || partref.edge))) ) {
			    return ipart;
				}
			}
		return -1;
		};
	this.send_back = function(ipart) {
		if ( ipart >= 0 ) {
			var movedPart = me.drawing_stack[ipart];
			me.drawing_stack.splice(ipart,1);
			me.drawing_stack.unshift(movedPart);
			}
		};
	this.send_top = function(ipart) {
		if ( ipart >= 0 && ipart < me.drawing_stack.length-2 ) {
			var movedPart = me.drawing_stack[ipart];
			me.drawing_stack.splice(ipart,1);
			// insert below the preview part: todo: need to revisit for more solid programming
			ipart = me.drawing_stack.length - 1;
			me.drawing_stack.splice(ipart,0,movedPart);
			}
		return ipart;
		};
	// complete initialization of object
	// setup new image
	this.img = self.document.getElementById('puzzleImage');
	this.img.onload = me.init;
	// normalize event position
	// based on Quirksmode.org's Peter-Paul Koch
	// http://www.quirksmode.org/js/events_properties.html#position
	function normalizeEventPos(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.canvasObj.offsetLeft;
		pos.y -= me.canvasObj.offsetTop;
		return pos;
		}
	// event handlers
	this.canvasObj.onclick = function(e) {
		var moved;
		if ( me.imoved >= 0 ) {
			moved = me.drawing_stack[me.imoved];
			// is this a piece of puzzle?
			if ( moved.piece ) {
				// snap into place?
				var sTopleft = moved.sTile.getBbox().getTopleft();
				var dTopleft = moved.dTile.getBbox().getTopleft();
				if ( mthabs(dTopleft.x-me.bbox_img.tl.x-sTopleft.x) < 5 &&
				     mthabs(dTopleft.y-me.bbox_img.tl.y-sTopleft.y) < 5 &&
					 moved.getAngleStep() === 0 ) {
					self.soundManager.play('snap1');
					// send at the bottom of the drawing stack
					me.send_back(me.imoved);
					moved.correct = true;
					me.imoved = -1;
					// new position
					var sCentroid = moved.sTile.getCentroid();
					moved.setDisplayPos(sTopleft.x+me.bbox_img.tl.x+sCentroid.x,sTopleft.y+me.bbox_img.tl.y+sCentroid.y);
					// TODO: no need to keep this puzzle piece around,
					// slap it to the puzzle bed and remove it from the stack

					// if top part is correct, puzzle is solved
					if ( me.is_solved() ) {
						//self.soundManager.play('applaud');
						}
					}
				}
			me.imoved = -1;
			me.draw();
			}
		else {
			var pos = normalizeEventPos(e);
			var ipart = me.part_under_point(pos);
			if ( ipart >= 0 ) {
				// bring on top
				me.imoved = me.send_top(ipart);
				moved = me.drawing_stack[me.imoved];
				var dPos = moved.getDisplayPos();
				me.movedAnchor.x = pos.x - dPos.x;
				me.movedAnchor.y = pos.y - dPos.y;
				me.draw();
				}
			}
		};
	this.canvasObj.onmousemove = function(e) {
		if ( me.imoved < 0 ) { return; }
		var pos = normalizeEventPos(e);
		var moved = me.drawing_stack[me.imoved];
		var draw_bbox = moved.getDisplayBbox();
		moved.setDisplayPos(pos.x-me.movedAnchor.x,pos.y-me.movedAnchor.y);
		draw_bbox.union(moved.getDisplayBbox());
		me.draw(draw_bbox);
		};
	self.onkeypress = function(e) {
		if ( me.imoved < 0 || me.angleMaxSteps <= 1 ) { return true; }
		var moved = me.drawing_stack[me.imoved];
		if ( !moved.piece ) { return true; }
		if (!e) {e=self.window.event;}
		var code = e.keyCode?e.keyCode:(e.which?e.which:0);
		//stderr("canvasObj.onkeydown: code="+code+", string.fromCharCode()="+String.fromCharCode(code));
		var draw_bbox;
		if ( code == 37 || code == 65 || code == 97 ) { // left arrow or 'a'/'D'
			draw_bbox = moved.getDisplayBbox();
			moved.setAngleStep(moved.getAngleStep()-1);
			draw_bbox.union(moved.getDisplayBbox());
			me.draw(draw_bbox);
			}
		else if ( code == 39 || code == 68 || code == 100 ) { // right arrow or 'd'/'D'
			draw_bbox = moved.getDisplayBbox();
			moved.setAngleStep(moved.getAngleStep()+1);
			draw_bbox.union(moved.getDisplayBbox());
			me.draw(draw_bbox);
			}
		else if ( code == 38 || code == 87 || code == 119 ) { // up arrow or 'w'/'W'
			draw_bbox = moved.getDisplayBbox();
			moved.setAngleStep(0);
			draw_bbox.union(moved.getDisplayBbox());
			me.draw(draw_bbox);
			}
		return false;
		};
	// mouse wheel handling: http://adomas.org/javascript-mouse-wheel/
	self.onmousewheel = function(e) {
		if ( me.imoved < 0 || me.angleMaxSteps <= 1 ) { return true; }
		var d = 0;
		if (!e) {e=self.e;}
		if (e.wheelDelta) {
			d=e.wheelDelta;
			if (self.opera) {d=-d;}
			}
		else if (e.detail) {
			d = e.detail;
			}
		if (d) {
			d = d>0?1:-1;
			var moved = me.drawing_stack[me.imoved];
			if ( moved.piece ) {
				var draw_bbox = moved.getDisplayBbox();
				moved.setAngleStep(moved.getAngleStep()+(d>0?1:-1));
				draw_bbox.union(moved.getDisplayBbox());
				me.draw(draw_bbox);
				}
			}
		if (e.preventDefault) {e.preventDefault();}
		e.returnValue = false;
		return false;
		};
	/** DOMMouseScroll is for mozilla. */
	if (self.addEventListener) {self.addEventListener('DOMMouseScroll',self.onmousewheel,false);}

	// whether the puzzle is all solved
	this.is_solved = function() {
		return me.drawing_stack.length > 1 && me.drawing_stack[me.drawing_stack.length-2].correct;
		};
	}