/*
  Rectangular Packing
  Version: v0.1

  Copyright (C) 2008 by Systemantics, Bureau for Informatics

  Lutz Issler
  Mauerstr. 10-12
  52064 Aachen
  GERMANY

  Web:    www.systemantics.net
  Email:  mail@systemantics.net

  This script is NOT open source. If you want to use this script,
  please contact Systemantics in order to obtain a licence.
*/

var RECTANGULAR_PACKING = {
	rectangles : null,
	width : null,
	height : null,
	field : null,

	checkPosition : function(rect, x, y) {
		// Check the borders of the rectangle whether they are free
		for (var dx=x; dx<x+this.rectangles[rect].width; dx++) {
			// Check top border
			if (this.field[y][dx]>0) {
				return false;
			}
			// Check bottom border
			if (this.field[y+this.rectangles[rect].height-1][dx]>0) {
				return false;
			}
		}
		for (var dy=y+1; dy<y+this.rectangles[rect].height-1; dy++) {
			// Check left border
			if (this.field[dy][x]>0) {
				return false;
			}
			// Check right border
			if (this.field[dy][x+this.rectangles[rect].width-1]>0) {
				return false;
			}
		}
		return true;
	},

	placement : function(rectangles, width) {
		this.rectangles = rectangles;
		// Set the width
		this.width = width;
		// Determine the initial height using a greedy placement
		// Necessary precondition: The rectangles must be sorted by width
		// Simple bubblesort along the width
//		var changeCount;
//		do {
//			changeCount = 0;
//			for (var i=0; i<this.rectangles.length-1; i++) {
//				if (this.rectangles[i].width<this.rectangles[i+1].width) {
//					changeCount++;
//					var third = this.rectangles[i];
//					this.rectangles[i] = this.rectangles[i+1];
//					this.rectangles[i+1] = third;
//				}
//			}
//		} while (changeCount>0);
		// Init the field
		this.field = new Array(1);
		this.field[0] = new Array(this.width);
		// Place the rectangles
		var placement = new Array(this.rectangles.length);
		for (var rect=0; rect<this.rectangles.length; rect++) {
			// Find the leftmost and uppermost position
			var y = 0;
			search: do {
				for (var x=0; x<=this.width-this.rectangles[rect].width; x++) {
					// Check whether this place is free
					var dx = this.field[y][x];
					if (!dx || dx==0) {
						// This place is free
						// Extend the field
						while (y+this.rectangles[rect].height>this.field.length) {
							this.field.push(new Array(this.width));
						}
						// Check whether this place is valid
						if (this.checkPosition(rect, x, y)) {
							// Place the rectangle here
							for (var ry=y; ry<y+this.rectangles[rect].height; ry++) {
								for (var rx=x; rx<x+this.rectangles[rect].width; rx++) {
									this.field[ry][rx] = this.rectangles[rect].width;
								}
							}
							placement[rect] = new Object();
							placement[rect].id = this.rectangles[rect].id;
							placement[rect].x = x;
							placement[rect].y = y;
							// Store the height
							this.height = Math.max(this.height, y+this.rectangles[rect].height);
							// Continue with next rectangle
							break search;
						}
					} else {
						// This place is occupied
						// Fasten search by adding the skip value
						x += dx-1;
					}
				}
				y++;
				if (y==this.field.length) {
					// Extend the field
					this.field.push(new Array(this.width));
				}
			} while (y<100);
		}
		return placement;
	}
}