// JavaScript Document
/*
	numColumns - width
	numRows - height
*/
function MaximalRectangle(imageData, numColumns, numRows){
	this.imageData = imageData;
	this.numColumns = numColumns;
	this.numRows = numRows;
}
MaximalRectangle.Cache = function(size){
	this.aggregateHeights = [];
	for(var i = 0; i <= size; i++) {
		this.aggregateHeights.push(0);
	}
};
MaximalRectangle.Cache.prototype ={
	get: function(col){
		return this.aggregateHeights[col];
	},
	aggregate: function(elements){
		var output = "";
		for(var col = 0; col < elements.length; col++) {
			var element = elements[col];
			output += element + " ";

			if(0 == element) {
				this.aggregateHeights[col] = 0;
			} else {
				this.aggregateHeights[col] = this.aggregateHeights[col] + 1;
			}
		}
	}
};
MaximalRectangle.Cell = function(colArg, rowArg) {
	this.col = colArg;
	this.row = rowArg;
};
MaximalRectangle.Cell.prototype = {
	col:null,
	row:null
};
MaximalRectangle.prototype = {
	calculate: function(){
		var bestArea = 0;
		var bestLowerLeftCorner = new MaximalRectangle.Cell(0, 0);
		var bestUpperRightCorner = new MaximalRectangle.Cell(-1, -1);

		var stack = [];
		var rectangleHeightCache = new MaximalRectangle.Cache(this.numColumns);
		for(var row = 0; row < this.numRows; row++) {
			
			rectangleHeightCache.aggregate(this.generateRow(this.imageData, this.numColumns, row));
			for(var col = 0, currentRectHeight = 0; col <= this.numColumns; col++) {
				var aggregateRectHeight = rectangleHeightCache.get(col);

				if(aggregateRectHeight > currentRectHeight) {
					stack.push(new MaximalRectangle.Cell(col, currentRectHeight));
					currentRectHeight = aggregateRectHeight;
				} else if(aggregateRectHeight < currentRectHeight) {

					var rectStartCell;
					do {
						rectStartCell = stack.pop();
						var rectWidth = col - rectStartCell.col;
						var area = currentRectHeight * rectWidth;
						if(area > bestArea) {
							bestArea = area;
							bestLowerLeftCorner = new MaximalRectangle.Cell(rectStartCell.col, row);
							bestUpperRightCorner = new MaximalRectangle.Cell(col - 1, row - currentRectHeight + 1);
						}
						currentRectHeight = rectStartCell.row;
					} while(aggregateRectHeight < currentRectHeight);

					currentRectHeight = aggregateRectHeight;
					if(currentRectHeight != 0) {
						stack.push(rectStartCell);
					}
				}
			}
		}
		var recDef = {
			width: bestUpperRightCorner.col - bestLowerLeftCorner.col + 1,
			height: bestLowerLeftCorner.row - bestUpperRightCorner.row + 1,
			left: bestLowerLeftCorner.col,
			top: bestUpperRightCorner.row,
		};
		return recDef;
	},
	rgbaToInt: function(r, g, b, a) {
		if(r == 255 && g == 255 && b == 255){
			return 1;
		}else{
			return 0;
		}
	//    return ((r << 24) | (g << 16) | (b << 8) | a);
	},
	generateRow: function(imageData, width, rowNumber){
		var elements = [];
		for(var i=(rowNumber*width*4); i<(rowNumber*width*4)+(4*width); i+=4){
			elements.push(this.rgbaToInt(imageData.data[i], imageData.data[i+1], imageData.data[i+2], imageData.data[i+3]));
		}
		return elements;
	}
};


function FindSourceArea(canvas, x, y){
	this.canvas = canvas;
	this.context =  this.canvas.getContext('2d');
	this.x = Math.floor(x);
	this.y = Math.floor(y);
}
FindSourceArea.prototype = {
	findBound: function(sourceLine, startPoint, direction){
		var r,g,b,a;
		var it;
		do{
			it = startPoint*4;
			r = sourceLine[it];
			g = sourceLine[it+1];
			b = sourceLine[it+2];
			a = sourceLine[it+3];
			if(direction){
				startPoint++;
			}else{
				startPoint--;
			}
		}while(
			this.center[0] == r &&
			this.center[1] == g &&
			this.center[2] == b
		);
		return startPoint;
	},
	calculate: function(){
		this.center =  this.context.getImageData(this.x, this.y, 1, 1).data;
		
		var verticalLine = this.context.getImageData(this.x, 1, 1, this.canvas.height).data;
		var horizontalLine = this.context.getImageData(1, this.y, this.canvas.width, 1).data;

		var topBound = this.findBound(verticalLine, this.y, false),
		bottomBound = this.findBound(verticalLine, this.y, true),
		leftBound = this.findBound(horizontalLine, this.x, false),
		rightBound = this.findBound(horizontalLine, this.x, true);
		var rect = {
			x: leftBound,
			y: topBound,
			width: rightBound - leftBound,
			height: bottomBound - topBound
		};
		return rect;
	}
};