morpheus.Positions = function() {
	this.spaces = undefined;
	this.defaultPositionFunction = function(index) {
		return (this.size * index);
	};
	this.squishedPositionFunction = function(index) {
		return this.positions[index];
	};
	this.positionFunction = this.defaultPositionFunction;
	this.squishedIndices = {};
	this.isSquished = false;
};
morpheus.Positions.getBottom = function(rect, rowPositions) {
	var bottom = rowPositions.getLength();
	if (rect != null) {
		bottom = 1 + rowPositions.getIndex(rect.y + rect.height, false);
		bottom = Math.max(0, bottom);
		bottom = Math.min(rowPositions.getLength(), bottom);
	}
	return bottom;
};
morpheus.Positions.getTop = function(rect, rowPositions) {
	var top = 0;
	if (rect != null) {
		top = rowPositions.getIndex(rect.y, false) - 1;
		top = Math.max(0, top);
		top = Math.min(rowPositions.getLength(), top);
	}
	return top;
};
morpheus.Positions.getLeft = function(rect, columnPositions) {
	var left = 0;
	if (rect != null) {
		left = columnPositions.getIndex(rect.x, false) - 1;
		left = Math.max(0, left);
		left = Math.min(columnPositions.getLength(), left);
	}
	return left;
};
morpheus.Positions.getRight = function(rect, columnPositions) {
	var right = columnPositions.getLength();
	if (rect != null) {
		right = 1 + columnPositions.getIndex(rect.x + rect.width, false);
		right = Math.min(columnPositions.getLength(), right);
	}
	return right;
};
morpheus.Positions.prototype = {
	length : 0,
	size : 13,
	squishFactor : 0.1,
	compress : true,
	copy : function() {
		var copy = new morpheus.Positions();
		if (this.spaces) {
			copy.spaces = this.spaces.slice();
		}
		copy.compress = this.compress;
		copy.squishFactor = this.squishFactor;
		copy.size = this.size;
		copy.length = this.length;
		if (this.isSquished) {
			copy.positionFunction = copy.squishedPositionFunction;
			copy.squishedIndices = _.clone(this.squishedIndices);
			copy.isSquished = true;
		}
		return copy;
	},
	getIndex : function(position, exact) {
		if (exact) {
			return this.binaryExactSearch(position);
		} else {
			return this.binaryInExactSearch(position);
		}
	},
	getLength : function() {
		return this.length;
	},
	getPosition : function(index) {
		return this.positionFunction(index)
				+ (this.spaces !== undefined ? this.spaces[index] : 0);
	},
	getItemSize : function(index) {
		return this.squishedIndices[index] === true ? this.size
				* this.squishFactor : this.size;
	},
	getSize : function() {
		return this.size;
	},
	setSpaces : function(spaces) {
		this.spaces = spaces;
	},
	setLength : function(length) {
		this.length = length;
	},
	setSize : function(size) {
		this.size = size;
		if (this.isSquished) {
			this.setSquishedIndices(this.squishedIndices);
		}
	},
	setSquishedIndices : function(squishedIndices) {
		if (squishedIndices != null) {
			var compress = this.compress;
			this.squishedIndices = squishedIndices;
			var positions = [];
			var squishFactor = this.squishFactor;
			var size = this.size;
			var position = 0;
			for (var i = 0, length = this.getLength(); i < length; i++) {
				var itemSize;
				if (squishedIndices[i] === true) {
					positions.push(position);
					itemSize = size * squishFactor;
					position += itemSize;
				} else {
					if (!compress) {
						position = size * i;
					}
					positions.push(position);
					position += size;
				}
			}
			this.isSquished = true;
			this.positions = positions;
			this.positionFunction = this.squishedPositionFunction;
		} else {
			this.squishedIndices = {};
			this.isSquished = false;
			this.positionFunction = this.defaultPositionFunction;
		}
	},
	setSquishFactor : function(f) {
		if (this.squishFactor !== f) {
			this.squishFactor = f;
			if (this.isSquished) {
				this.setSquishedIndices(this.squishedIndices);
			}
		}
	},
	getSquishFactor : function() {
		return this.squishFactor;
	},
	binaryExactSearch : function(position) {
		var low = 0;
		var high = this.length - 1;
		while (low <= high) {
			var mid = (low + high) >> 1;
			var midVal = this.getPosition(mid);
			var size = this.getItemSize(mid);
			if (midVal <= position && position < (midVal + size)) {
				return mid;
			}
			if (midVal < position) {
				low = mid + 1;
			} else if (midVal > position) {
				high = mid - 1;
			} else {
				return mid;
				// key found
			}
		}
		return -1;
		// key not found
	},
	binaryInExactSearch : function(position) {
		var low = 0;
		var high = this.getLength() - 1;
		var maxIndex = this.getLength() - 1;
		if (position <= this.getPosition(0)) {
			return 0;
		}
		while (low <= high) {
			var mid = (low + high) >> 1;
			var midVal = this.getPosition(mid);
			var size = this.getItemSize(mid);
			var nextStart = maxIndex === mid ? midVal + size : this
					.getPosition(mid + 1);
			if (midVal <= position && position < nextStart) {
				return mid;
			}
			if (midVal < position) {
				low = mid + 1;
			} else if (midVal > position) {
				high = mid - 1;
			} else {
				return mid;
				// key found
			}
		}
		return low - 1;
		// key not found
	}
};