function isArray(a) {
	return a.constructor.prototype == Array.prototype;
}
if (typeof Array.prototype.add == "undefined") {
	Array.prototype.add = function(a) {
		var b = [];
		for (var i = 0, l = Math.min(this.length, a.length); i < l; i++) {
			b[i] = this[i] + a[i];
		}
		return b;
	}
}
if (typeof Array.prototype.sub == "undefined") {
	Array.prototype.sub = function(a) {
		var b = [];
		for (var i = 0, l = Math.min(this.length, a.length); i < l; i++) {
			b[i] = this[i] - a[i];
		}
		return b;
	}
}
if (typeof Array.prototype.mul == "undefined") {
	Array.prototype.mul = function(m) {
		var b = [];
		for (var i = 0, l = this.length; i < l; i++) {
			b[i] = this[i] * m;
		}
		return b;
	}
}
if (typeof Array.prototype.affine == "undefined") {
	Array.prototype.affine = function(k, b) {
		var a = [];
		var _k = k, _b = b;
		for (var i = 0, l = this.length; i < l; i++) {
			if (typeof k == "object") _k = k[i];
			if (typeof b == "object") _b = b[i];
			a[i] = this[i] * _k + _b;
		}
		return a;
	}
}
if (typeof Array.prototype.scalar == "undefined") {
	Array.prototype.scalar = function(a) {
		var sum = 0;
		for (var i = 0, l = Math.min(this.length, a.length); i < l; i++) {
			sum += this[i] * a[i];
		}
		return sum;
	}
}
if (typeof Array.prototype.sum == "undefined") {
	Array.prototype.sum = function() {
		var sum = 0;
		for (var i = this.length-1; i >= 0; i--) {
			sum += this[i];
		}
		return sum;
	}
}
if (typeof Array.prototype.avg == "undefined") {
	Array.prototype.avg = function() {
		return this.sum() / this.length;
	}
}

if (typeof Array.prototype.mapRecursive == "undefined") {
	Array.prototype.mapRecursive = function(f) {
		var a = [];
		for (var i = 0; i < this.length; i++) {
			if (isArray(this[i])) {
				a.push( this[i].mapRecursive(f) );
			} else {
				a.push( f(this[i]) );
			}
		}
		return a;
	}
}

if (typeof Array.prototype.binSearch == "undefined") {
	var recursionDepth = 0;
	Array.prototype.binSearch = function(value, limits, cmp) {
		recursionDepth++;
		if (typeof limits == "undefined") limits = {};
		var min = limits.min || 0;
		var max = (typeof limits.max == "undefined") ? this.length-1 : limits.max;
		
		//console.log([min,max]);
		if (recursionDepth >= 10) {
			recursionDepth = 0;
			throw "Too much recursion";
		}
		if (min >= max) {
			recursionDepth = 0;
			return this[min] == value ? min : -1;
		}
		var mid = (min + max) >> 1;
		
		var isLower;
		if (typeof cmp != "function") {
			isLower = value < this[mid+1];
		} else {
			isLower = cmp(value, this[mid]);
		}
		if (isLower) {
			return this.binSearch(value, {min:min, max:mid});
		} else {
			return this.binSearch(value, {min:mid+1, max:max});
		}
	}
}

function hysto(str) {
	var h = { size: 0 };
	for (var i = str.length-1; i >= 0; i--) {
		var c = str.charCodeAt(i);
		if (typeof h[c] == "undefined") {
			h[c] = 1;
			h.size++;
		} else {
			h[c]++;
		}
	}
	return h;
}

function spiral(x) {
	var n = Math.sqrt(x);
	var n2 = Math.floor(n/2);
	var a = [];
	for (var i = 0; i < n2; i++) {
		var max = n - 2*i - 1;
		for (var j = 0; j < max; j++) a.push(j + i*(n+1)); // top
		for (var j = 0; j < max; j++) a.push(n-1 + j*n + i*(n-1)); // left
		for (var j = 0; j < max; j++) a.push(x-1 - j - i*(n+1)); // bottom
		for (var j = 0; j < max; j++) a.push(x-n - j*n - i*(n-1)); // right
	}
	if (n2*2 < n) {
		a.push((n2+1)*(n+1));
	}
	return a;
}

var max_calls = 100;
// recursive ppm algorightm of 2nd order
function ppm2(str, r, C) {
	if (max_calls-- < 0) return "ER404!";
	// init default params
	r = r || "";
	var ret = r.length/2+r+str;
	C = C || 97; // 'a'
	if (C == 90) C = 121;
	if (C >= 122) { // 'z'
		return ret;
	}
	
	//console.log(ret);

	// collect hystogram
	var hysto = {};
	for (var i = 0; i < str.length-1; i++) {
		var c = str.charAt(i) + str.charAt(i+1);
		hysto[c] = (hysto[c] || 0) + 1;
	}
	
	// process hystogram
	var a = [], rc = String.fromCharCode(C); // replace char
	for (c in hysto) {
		if (hysto[c] > 3) {
			var re = new RegExp(RegExp.escape(c), "g");
			a.push(ppm2(
				str.replace(re, rc),
				r + c,
				C + 1
			));
		}
	}
	
	var l = a.length;
	// if there were some better results
	if (l) {
		var min = 0, idx = -1;
		// detect shortest string
		for (var i = 0; i < l; i++) {
			var len = a[i].length;
			if (min < len) {
				min = len;
				idx = i;
			}
		}
		// return it
		return a[idx];
	} else {
		return ret;
	}
}

/**	
 *	from mozilla's dev center
 *	@url https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference/Objects/Array/Reduce
 */
if (!Array.prototype.reduce) {
	Array.prototype.reduce = function(fun /*, initial*/) {
		var len = this.length >>> 0;
		if (typeof fun != "function")
			throw new TypeError();
		// no value to return if no initial value and an empty array
		if (len == 0 && arguments.length == 1)
			throw new TypeError();
		var i = 0;
		if (arguments.length >= 2) {
			var rv = arguments[1];
		} else {
			do {
				if (i in this) {
					var rv = this[i++];
					break;
				}
				// if array contains no values, no initial value to return
				if (++i >= len)
					throw new TypeError();
			} while (true);
		}
		for (; i < len; i++) {
			if (i in this)
				rv = fun.call(null, rv, this[i], i, this);
		}
		return rv;
	};
}

if (typeof RegExp.escape == "undefined") {
	RegExp.escape = function(str) {
		return str.replace(/([()\[\]\\\/+*?.-])/g, "\\$1");
	}
}

if (typeof Array.prototype.sortBy == "undefined") {
	Array.prototype.sortBy = function(fieldName, sign) {
		if (!sign) sign = 1;
		return this.sort(function(a, b){
			return sign * (a[fieldName] - b[fieldName]);
		});
	}
}
if (typeof Array.prototype.findBy == "undefined") {
	Array.prototype.findBy = function(obj) {
		for (var i = this.length-1; i >= 0; i--) {
			var elt = this[i];
			var eq = true;
			for (p in obj) {
				if (!(p in elt)) continue;
				var f = obj[p], e = elt[p];
				eq = eq && (f.constructor == Function.prototype.constructor ? f.call(null, e) : e == f);
			}
			if (eq) return this[i];
		}		
	}
}

var $clone = function(obj) {
/*	if (typeof obj != "object") return obj;
	if (typeof obj.length != "undefined") return obj.clone(); // array */
	var o = {};
	for (p in obj) {
		o[p] = obj[p];
	}
	return o;
}

var $$clone = function(obj, level, options) {
	var new_entities = [];
	var old_entities = [];
	var _clone = function(obj, lvl) {
		if (typeof lvl == "undefined") lvl = Infinity;
		if (lvl == 0) return obj;
		if (typeof obj.clone == "function") return obj.clone();
		if (typeof obj == "object") return _clone(obj);
		if (typeof obj.length != "undefined") return obj.extend([]);
//		if (typeof obj == "function") return obj;
		return obj;
		var o = {};
		for (p in obj) {
			if (!options.match || p.match(options.match)) {
				o[p] = _clone(obj[p], lvl-1);
			}
		}
		return o;
	}
	return _clone(obj, level);
}