// JavaScript Document


Math.Relation = {
	matrix : function( set, relation) {
		var matrix = [];
		for ( var i = 0, l=set.length; i < l; i++ ) {
			matrix[i] = [];
			for ( var j = 0; j<l; j++ ) {
				matrix[i][j] = Math.Relation.relationExists(set[i],set[j],relation);
			}
		}
		return matrix;
	},
	relationExists : function(a,b,rel) {
		for ( var i = 0, l = rel.length; i<l; i++ ) {
			if ( Math.oper.eq(rel[i][0],a) && Math.oper.eq(rel[i][1],b) ) {
				return 1;
			}
		}
		return 0;
	},
	isReflexive : function (set,relation) {
		var ret = true;
		for ( var i = 0, l = set.length; i<l; i++) {
			ret &= Math.Relation.relationExists(set[i],set[i],relation);
			if ( !ret ) {
				return false;
			}
		}
		return ret;
	},
	isIrreflexive : function ( set, relation ) {
		var ret = true;
		for ( var i = 0, l = set.length; i < l; i++) {
			ret &= !Math.Relation.relationExists(set[i],set[i],relation);
			if ( !ret ) {
				return false;
			}
		}
		return ret;
	},
	isSymetric : function ( set, relation ) {
		var ret = true;
		for ( var i = 0, l = set.length; i < l ; i++ ) {
			for ( var j = i; j<l; j++ ) {
				ret &= Math.Logic.iff(Math.Relation.relationExists(set[i],set[j],relation),Math.Relation.relationExists(set[j],set[i],relation));
				if ( !ret ) {
					return false;
				}
			}
		}
		return ret;
	},
	isAntiSymetric : function ( set, relation ) {
		var ret = true;
		for ( var i = 0, l = set.length; i < l; i++) {
			for ( var j = i; j<l; j++ ) {
				if ((Math.Relation.relationExists(set[i],set[j],relation) && Math.Relation.relationExists(set[j],set[i],relation))) {
					ret &= i == j;
				}
				if ( !ret ) {
					return false;
				}
			} 
		}
		return ret;
	},
	isTransitive : function ( set, relation ) {
		var ret = true;
		for ( var i = 0, l = relation.length; i<l; i++ ) {
			for ( var j = 0, sl = set.length; j<sl; j++) {
				if ( Math.Relation.relationExists(relation[i][1],set[j],relation) ) {
					ret &= Math.Relation.relationExists(relation[i][0],set[j],relation);
				}
				if ( !ret ) {
					return false;
				}
			}
		}
		return ret;
	},
	isPoset : function ( poset ) {
		return Math.Relation.isAntiSymetric(poset.set,poset.relation) &&
				Math.Relation.isReflexive(poset.set,poset.relation) &&
				Math.Relation.isTransitive(poset.set, poset.relation);
	},
	createFromFunc : function ( set, func ) {
		var ret = [];
		for ( var i = 0, l = set.length; i<l; i++ ) {
			for ( var j =0; j<l ; j++ ) {
				if ( func(set[i],set[j]) ) {
					ret[ret.length] = [set[i],set[j]];
				}
			}
		}
		return ret;
	},
	Poset : {
		leastElement : function ( poset , subset ) {
		 	subset = subset || poset.set;
			var el = null;
			for ( var i = 0, l = subset.length; i<l; i++ ) {
				el = subset[i];
				var found = true;
				for ( var j = 0; j < l ; j++ ) {
					if ( !Math.Relation.relationExists(el,subset[j],poset.relation) ) {
						found = false;
						break;
					}
				}
				if ( found ) {
					return el;
				}
			}
			return null;
		},
		greatestElement : function ( poset, subset ) {
			subset = subset || poset.set;
			var el = null;
			for ( var i = 0, l = subset.length; i<l; i++ ) {
				el = subset[i];
				var found = true;
				for ( var j = 0; j < l ; j++ ) {
					if ( !Math.Relation.relationExists(subset[j],el,poset.relation) ) {
						found = false;
						break;
					}
				}
				if ( found ) {
					return el;
				}
			}
			return null;
		},
		minimalElements : function ( poset , subset ) {
			subset = subset || poset.set;
			var ret = [];
			for ( var i = 0, l=subset.length; i < l ; i++ ) {
				var el = subset[i];
				var found = true;
				for ( var j = 0; j < l; j++ ) {
					if ( j == i ) {
						continue;
					}
					if ( Math.Relation.relationExists(subset[j],el,poset.relation) ) {
						found = false;
						break;
					}
				}
				if ( found ) {
					ret[ret.length] = el; 
				}
			}
			return ret;
		},
		maximalElements : function ( poset, subset ) {
			subset = subset || poset.set;
			var ret = [];
			for ( var i = 0, l=subset.length; i < l ; i++ ) {
				var el = subset[i];
				var found = true;
				for ( var j = 0; j < l; j++ ) {
					if ( j == i ) {
						continue;
					}
					if ( Math.Relation.relationExists(el,subset[j],poset.relation) ) {
						found = false;
						break;
					}
				}
				if ( found ) {
					ret[ret.length] = el; 
				}
			}
			return ret;
		},
		isLinearlyOrdered : function ( poset ) {
			for ( var i = 0, l=poset.set.length; i < l; i++ ) {
				for ( var j = i; j < l; j++ ) {
					if ( !Math.Relation.relationExists(poset.set[i],poset.set[j],poset.relation)
						&& !Math.Relation.relationExists(poset.set[j],poset.set[i],poset.relation) ) {
						return false;
					}
				}
			}
			return true;
		},
		isWellOrdered : function ( poset ) {
			var subsets = Math.util.getAllNonEmptySubsets(poset.set);
			for ( var i = 0, l = subsets.length; i < l ; i++ ) {
				if ( null == Math.Relation.Poset.leastElement(poset,subsets[i]) ) {
					return false;
				}
			}
			return true;
		}
	},
};

Math.Set = {
	union : function ( setA, setB ) {
		//
		var ret = [];
		var al = setA.length;
		for ( var i = 0; i< al; i++) {
			ret[i] = setA[i];
		}
		for ( var i = 0, bl = setB.length; i < bl; i++ ) {
			var add_it = true;
			for ( var j = 0; j < al; j++ ) {
				if ( Math.oper.eq(setA[j],setB[i]) ) {
					add_it = false;
					break;
				}
			}
			if ( add_it ) {
				ret[ret.length] = setB[i];
			}
		}
		return ret;
	},
	intersect : function ( setA, setB ) {
		var ret = [];
		for ( var i = 0, al = setA.length; i<al; i++ ) {
			var add_it = false;
			for ( var j = 0, bl = setB.length; j<bl; j++ ) {
				if ( Math.oper.eq(setA[i],setB[j]) ) {
					add_it = true;
					break;
				}
			}
			if ( add_it ) {
				ret[ret.length] = setA[i];
			}
		}
		return ret;
	},
	cartesianProduct : function( ) {
		var cartesianFirst = function ( setA, setB ) {
			var ret = [];
			var cntr = 0;
			var bl = setB.length;
			for ( var i = 0, l = setA.length ; i<l; i++ ) {
				for ( var j = 0; j < bl; j++ ){
					ret[cntr++] = [setA[i],setB[j]];
				}
			}
			return ret;
		};
		var cartesianMerge = function ( partialProduct, setC ) {
			var ret = [];
			var cntr = 0;
			var cl = setC.length;
			for ( var i = 0, l = partialProduct.length; i < l; i++ ) {
				//var ppi = partialProduct[i];
				var ppl = partialProduct[i].length;
				for ( var j = 0; j<cl; j++ ) {
					//ppi[ppl] = setC[j];
					var rt = [];
					for ( var k = 0; k<ppl; k++ ) {
						rt[k] = partialProduct[i][k];
					}
					rt[ppl] = setC[j];
					ret[cntr++] = rt;//ppi.splice(0);
				}
			}
			return ret;
		};
		var ret = [];
		var cntr = 0;
		if ( arguments.length == 0 ) {
			return [];
		} 
		if ( arguments.length == 1 ) {
			return arguments[0];
		}
		if ( arguments.length == 2 ) {
			return cartesianFirst(arguments[0],arguments[1]);
		}
		ret = cartesianFirst(arguments[0],arguments[1]);
		for ( var i = 2, l = arguments.length; i < l; i++ ) {
			ret = cartesianMerge(ret,arguments[i]);
		}
		return ret;
	},
	
}

Math.util = {
	matrixToString : function ( matrix ) {
		var rows = [];
		for ( var i = 0, l = matrix.length; i< l ; i++ ) {
			rows[i] = matrix[i].join(' ');
		}
		return rows.join("\n");
	},
	getAllNonEmptySubsets : function ( set ) {
		var ret = [];
		var setl = set.length;
		for ( var i = 1, l = Math.pow(2,setl); i < l; i++ ) {
			var subset = [];
			var end = Math.ceil(Math.log(i+1)/Math.log(2));
			for ( var j = 0; j<end; j++ ) {
				if ( Math.pow(2,j) & i ) {
					subset[subset.length] = set[j];
				}
			}
			ret[ret.length] = subset;
		}
		return ret;
	},
	pnpwr : function ( item, oper, factor ) {
		var ret = item;
		for ( var i = 1; i<factor; i++ ) {
			ret = oper(ret,item);
		}
		return ret;
	},
	matrixToMathematicaString : function (matrix) {
		var rows = [];
		for ( var i = 0, l = matrix.length; i< l ; i++ ) {
			rows[i] = '{'+matrix[i].join(',')+'}';
		}
		return '{'+rows.join(",")+'}';
	},
	mathematicaMatrixToArray: function(ms) {
		var ret = [];
		var rows = ms.substr(2,ms.length-4).split('},{');
		for ( var i = 0, l = rows.length; i<l;i++ ) {
			ret[i] = rows[i].split(',');
		} 
		return ret;
	}
};

Math.oper = {
	eq : function (a,b) {
		if ( typeof(a) != typeof(b) ) {
			return false;
		}
		if ( typeof(a) == typeof([]) ) {
			var la = a.length, lb = b.length;
			if ( la != lb ) {
				return false;
			}
			for ( var i = 0; i<la; i++ ) {
				if ( !Math.oper.eq(a[i],b[i]) ) {
					return false;
				}
			}
			return true;
		}
		//default
		return a == b;
	}
};

Math.Logic = {
	follows : function(a,b){
		return !a || a && b;		
	},
	iff : function(a,b){
		return (!a && !b) || (a && b);
	},
	truthTable : function( f ){
		var header_str = '';
		var parcount = f.length;
		var ret = [];
		/*
		for ( var i = 0; i < parcount; i++ ) {
			header_str = header_str + 'x'+i + ' | ';
		}
		header_str = header_str + ' f() ';
		console.log(header_str);*/
		for ( var i = 0; i < Math.pow(2,parcount) ; i++ ) {
			//var curstr = '';
			ret[i] = [];
			var val = 0;
			var paramstr = 'val = f(';
			var and = '';
			for ( var j = 0 ; j < parcount; j++ ) {
				curp = i & Math.pow(2,j);
				ret[i][j] = (curp?1:0);
				//curstr = curstr + ' '+(curp?'t':'f')+' | ';
				paramstr =  paramstr + and + (curp?'1':'0');
				and = ','; 
			}
			paramstr = paramstr + ');';
			eval(paramstr);
			//curstr = curstr + (val?'t':'f');
			ret[i][ret[i].length] = (val?1:0);
			//console.log(curstr);
			//ret &= val;
		}
		return ret;
	}
}


Math.Matrix = {
	transpose : function(A) {
		var ret = [];
		for ( var i = 0, n = A.length; i<n; i++) {
			for ( var j = 0, m = A[i].length; j<m; j++ ) {
				if ( typeof(ret[j]) == 'undefined' ) {
					ret[j] = [];
				}
				ret[j][i] = A[i][j];
			}
		}
		return ret;
	},
	GaussianTransform : function(A) {
		var ret = [];
		var o = 0;
		for ( var i = 0, l= A.length; i<l; i++ ) {
			if ( A[i].length < l ) {
				return null;
			}
			if ( typeof(ret[i]) == 'undefined' ) { 
				ret[i] = Math.Vector.scale(A[i],A[i][i]!=0?1/A[i][i]:1);
			} else {
				while ( ret[i][i+o] == 0 ) {
					o++;
				}
				ret[i] = Math.Vector.scale(ret[i],1/ret[i][i+o]);
			}
			for ( var j = i+1; j<l; j++ ) {
				if ( typeof(ret[j]) == 'undefined' ) {
					ret[j] = Math.Vector.scale(A[j],1); //copy
				}
				ret[j] = Math.Vector.add(ret[j],Math.Vector.scale(ret[i],-1*ret[j][i+o]));
			}
		}
		return ret;
	},
	add : function (A,B) {
		if (A.length != B.length) {
			return null;
		}
		var ret = [];
		for ( var i = 0, l=A.length; i<l; i++ ) {
			if ( A[i].length != B[i].length ) {
				return null;
			}
			ret[i] = [];
			for ( var j = 0, jl = A[i].length; j<jl; j++ ) {
				ret[i][j] = A[i][j] + B[i][j];
			}
		}
		return ret;
	},
	scale : function ( A, fac ) {
		var ret = [];
		for ( var i = 0, l = A.length; i<l; i++ ) {
			ret[i] = [];
			for ( var j = 0, jl = A[i].length; j<jl; j++ ) {
				ret[i][j] = A[i][j] * fac;
			} 
		}
		return ret;
	} ,
	multiply : function (A,B) {
		var n = B.length;
		var ret = [];
		for ( i = 0, m = A.length; i<m; i++ ) {
			if ( A[i].length != n ) {
				return null;
			}
			ret[i] = [];
			for ( var j = 0, k = B[0].length; j<k; j++ ) {
				ret[i][j] = 0;
				for ( var s = 0; s < n; s++ ) {
					ret[i][j] += A[i][s]*B[s][j];
				}
			}
		}
		return ret;
	},
	inverse : function(A) {
		var ret = [];
		for ( var i = 0, l=A.length; i<l; i++ ){
			ret[i] = [];
			for ( var j =0, jl = A[i].length; j<jl; j++) {
				ret[i][j] = ((i+j)%2?-1:1)*Math.Matrix.determinant(Math.Matrix.getMinor(A,i,j));
			}
		}
		return Math.Matrix.transpose(Math.Matrix.scale(ret,1/Math.Matrix.determinant(A)));
	},
	determinant:function(A){
		var l = A.length;
		if ( l != A[0].length ) {
			return null;
		}
		if ( A.length == 1 ) {
			return A[0][0];
		}
		var ret = 0;
		for ( var i = 0; i<l; i++ ) {
			var tmp =(i%2==0?1:-1)*A[0][i]*Math.Matrix.determinant(Math.Matrix.getMinor(A,0,i));
			//alert(tmp);
			ret+=tmp; 
		}
		return ret;
	},
	getMinor:function(A,n,m) {
		var ret = [];
		var ri = 0;
		var rj = 0;
		for ( var i = 0, l = A.length; i<l;i++ ) {
			if ( i == n ) {
				continue;
			}
			rj = 0;
			ret[ri] = [];
			
			
			for ( var j = 0, jl = A[i].length; j<jl; j++ ) {
				if ( j == m ) {
					continue;
				}
				ret[ri][rj] = A[i][j];
				rj++;
				 
			}
			ri++;
		}
		return ret;
	}
}

Math.Vector = {
	add : function(A,B) {
		var ret = [];
		var l = A.length;
		if ( B.length != A.length ) {
			return null;
		}
		for ( var i = 0; i<l; i++ ) {
			ret[i] = A[i]+B[i];
		}
		return ret;
	},
	
	scalarMultiply:function(A,B) {
		if ( A.length != B.length ){
			return null;
		}
		var ret = [];
		for ( var i = 0, l = A.length; i<l; i++) {
			ret[i] = A[i]*B[i];
		}
		return ret;
	},
	
	angle : function ( A, B ) {
		B = B || null;
		if ( B == null ) {
			B = [1];
			for (var i = 1; i< A.length; i++ ) {
				B[i] = 0;
			}
		}
		return Math.acos(Math.Vector.sum(Math.Vector.scalarMultiply(A,B))/(Math.Vector.modulo(A)*Math.Vector.modulo(B)));
	},
	
	scale : function(V,coef) {
		var ret = [];
		for ( var i = 0, l=V.length; i<l; i++){
			ret[i] = V[i]*coef;
		}
		return ret;
	},
	
	sum : function(V) {
		var ret = 0;
		for ( var i = 0, l = V.length; i<l; i++ ) {
			ret+=V[i];
		}
		return ret;
	},
	
	areCollinear : function ( A, B ) {
		if ( A.length != B.length ) {
			return null;
		}
		var ratio = A[0]/B[0];
		for ( var i = 0, l = A.length; i<l; i++ ) {
			if ( A[i]/B[i] != ratio ) {
				return false;
			}
		}
		return true;
	},
	
	modulo : function ( A ) {
		var sum = 0;
		for ( var i = 0, l=A.length; i<l; i++ ){
			sum += A[i]*A[i];
		}
		return Math.sqrt(sum);
	},
	
	crossProduct:function(A,B) {
		if ( A.length != 3 && B.length != 3 ) {
			return null;
		}
		return [Math.Matrix.determinant( [ [A[1],A[2]], [B[1],B[2] ] ]),
				-1*Math.Matrix.determinant( [ [A[0],A[2]], [B[0],B[2] ] ]),
				Math.Matrix.determinant( [ [A[0],A[1]], [B[0],B[1] ] ])
				];
	}

}