/**
 * Extensões a objectos de javascript
 * Rotinas de encriptação
 * Funções matemáticas
 * @author Vítor Hugo Fernandes (a.k.a Balhau)
 * @copyright Este documento está licenciado sob os direitos do MIT license
 */

/**
 * Objecto que representa propriedades comuns aos algoritmos
 */
var ALG={};
/**
 * Número de iteracções feitas pelo algoritmo
 */
ALG.ITER=0;
/**
 * Variável que representa a chave secreta gerada pelo algoritmo de Vigénere. Isto ocorre sempre
 * que a chave não é especificada à entrada da função
 */
ALG.VIGSECRETKEY="";

/**
 * Método que troca dois elementos num array
 * @param {int} i Indice da posicao
 * @param {int} j Indice da posicao
 */
Array.prototype.troca=function(i,j){
	if((i<this.length && i>=0) && (j<this.length && j>=0)){
		var aux=this[i];
		this[i]=this[j];
		this[j]=aux;	
	}
};

Array.prototype.classpos=function(el){
	var p;
	for(var i=0;i<this.length;i++){
		p=this[i].pos(el);
		if(p!=-1)
			return i;
	}
	return -1;
}
/**
 * Método que agrupa um array de elementos bidimensionais em classes
 * @return {Array} Array de classes
 */
Array.prototype.groupclasses=function(){
	var grupos=[];
	var volta;
	var exist;
	var dif;
	var par;
	var xu=this.clona();
	while (xu.length > 0) {
		par = xu[0];
		if (par[0] != par[1]) 
			grupos[grupos.length] = par;
		else 
			grupos[grupos.length] = [par[0]];
		xu.remove(0);
		volta=true;
		while (volta) {
			volta=false;
			for (var i = 0; i < xu.length; i++) {
				dif = xu[i].less(grupos[grupos.length - 1]);
				if (dif.length == 1) {
					grupos[grupos.length-1]=grupos[grupos.length - 1].concat(dif);
					xu.remove(i);
					i--;
					volta=true;
				}else if(dif.length==0){
					xu.remove(i);
					i--;
				}
			}
		}
	}
	return grupos;
};

/**
 * Método que devolve um array com os elementos de arrA x arrB (produto de conjuntos)
 * @param {Array} arrA Array de elementos 
 * @param {Array} arrB Array de elementos
 * @return {Array} Array de elementos (a,b) onde a em arrA e b em arrB 
 */
Array.produto=function(arrA,arrB){
	var out=[];
	for(var i=0;i<arrA.length;i++){
		for(var j=0;j<arrB.length;j++){
			out[out.length]=[arrA[i],arrB[j]];
		}
	}
	return out;
}
/**
 * Método que verifica se o array parâmetro é igual ao objecto considerado
 * @param {Array} arrX Array para o qual se pretende testar a igualdade 
 * @return {Boolean} true se arrX é igual ao objecto que invoca o método, false cc
 */
Array.prototype.equal=function(arrX){
	if(this.length!=arrX.length)
		return false;
	for(var i=0;i<this.length;i++){
		if(this[i]!==arrX[i])
			return false;
	}
	return true;
}
/**
 * Verifica se o array fornecido como parâmetro é igual ao objecto que invoca o método
 * independentemente da ordem pela qual aparecem os elementos
 * @param {Array} arrX Array de comparação
 * @return {Boolean} true se arrX tem os mesmos elementos que o objecto que invoca o método,
 * false cc
 */
Array.prototype.nordequal=function(arrX){
	var arx=[];
	var arx=arrX.clona();
	if(this.length!=arrX.length)
		return false;
	for(var i=0;i<this.length;i++){
		if(!arx.has(this[i]))
			return false;
		arx.remove(arx.pos(this[i]));
	}
	return true;
}
/**
 * Devolve uma string com a descrição do conteudo no array
 * @return {String} conteúdo do array
 */
Array.prototype.toString=function(){
	var out="[";
	for(var i=0;i<this.length;i++){
		if(i!=0)
			out+=",";
		out+=this[i].toString();
	}
	out+="]";
	return out; 
};

/**
 * Devolve a diferença de elementos (diferença operação de conjuntos)
 *  entre o array considerado e o que é fornecido.
 * @param {Array} arr Array a subtrair.
 * @return {Array} Array diferença
 */
Array.prototype.less=function(arr){
	var out=[];
	var add;
	for(var i=0;i<this.length;i++){
		add=true;
		for(var j=0;j<arr.length;j++){
			if(this[i]===arr[j])
				add=false;
		}
		if(add)
			out[out.length]=this[i];
	}
	return out;
}

Array.prototype.SelectionSort=function(){
	var maximo;
	for(var i=this.length-1;i>=0;i--){
		maximo=i;
		for(var j=0;j<i;j++){
			if(this[j]>this[maximo])
				maximo=j;
		}
		this.troca(i, maximo);
	}
}

Array.prototype.ShellSort=function(){
	var n=this.length;
	var passo=Math.round(n/2);
	var j=null;
	var val=null;
	while(passo>0){
		for(var i=passo;i<n;i++){
			j=i;
			val=this[i];
			while(j>=passo && this[j-passo]>val){
				this[j]=this[j-passo];
				j-=passo;
			}
			this[j]=val;
		}
		passo=Math.round(passo/2.1);
	}
}

/**
 * Método que efectua a operação and sobre dois arrays. Devolve um array com os elementos
 * que coincidentes para cada posição
 * @param {Array} arrA Array
 * @param {Array} arrB Array
 * @return {Array} Array com os elementos que coincidem
 */
Array.and=function(arrA,arrB){
	var min=Object.min(arrA,arrB);
	var max=Object.max(arrA,arrB);
	var out=[];
	for(var i=0;i<min.length;i++){
		if(min[i]===max[i])
			out[out.length]=min[i];
	}
	return out;
};

/**
 * Verifica se um dado elemento pertence ao array
 * @param {Object} val Elemento que se pretende verificar se pertence ao array
 * @return{Boolean} bol Devolve verdadeiro caso o valor esteja no array, falso caso
 * contrário. 
 */
Array.prototype.has = function(val){
	for (var i = 0; i < this.length; i++) {
		if (this[i] == val) 
			return true;
	}
	return false;
};

/**
 * Função que devolve a intersecção entre dois arrays sem levar em conta a posição 
 * dos elementos
 * @param {Array} arrA Array A
 * @param {Array} arrB Array B
 * @return {Array} arrC Array que representa a intersecção de A com B
 */
Array.sAnd=function(arrA,arrB){
	var max=Object.max(arrA,arrB);
	var min=Object.min(arrA,arrB);
	var out=[];
	for(var i=0;i<max.length;i++){
		if( i<min.length){
			if(min.has(max[i]) && !out.has(max[i]))
				out[out.length]=max[i];
			if(max.has(min[i]) && !out.has(min[i]))
				out[out.length]=min[i];
		}
		else{
			if(min.has(max[i]) && !out.has(max[i]))
				out[out.length]=max[i];
		}
	}
	return out;
};



/**
 * Método que remove um elemento do array redimensionando-o
 * @param {int} i Indice do array que pretendemos eliminar
 * @return {Array} arr Devolve o array para efeitos de chaining
 */
Array.prototype.remove=function(i){
	if (i < 0 || i >= this.length) {
		return this;
	}
    this[i]=undefined;
    for(var j=i;j<this.length-1;j++){
    	this[j]=this[j+1];
    }
    this.length=this.length-1;
    return this;
}

Array.prototype.pos=function(el){
	var ip;
	for(var i=0;i<this.length;i++){
		if(this[i]===el)
			return i;
	}
	return -1;
}

/**
 * Extrai um subarray do array cujos valores se compreendem entre os índices indI e indF
 * @param {int} indI Indice inicial
 * @param {int} indF Indice final
 */
Array.prototype.subArray=function(indI,indF){
	var out=[];
	for(var i=indI;i<indF;i++)
		out[i]=this[i];
	return out;
};

/**
 * Método que parte o array em vários sub arrays tendo como base o valor dado
 * como entrada na função
 * @param {Object} val Valor de separação
 * @return {Array} Um array que contém os sub arrays do array original após
 * a divisão pelo elemento fornecido como parâmetro de entrada
 */
Array.prototype.divideBy=function(valor){
	var arrA=[];
	var k=0;
	var j=0;
	var arrAx=[];
	for(var i=0;i<this.length;i++){
		if (this[i] === valor) {
			arrA[k] = arrAx;
			arrAx = [];
			j = 0;
			k++;
		}
		else {
			arrAx[j] = this[i];
			j++;
		}
	}
	return arrA;
};

/**
 * Método para concatenação de arrays
 * @param {Array} arr Array que se pretende concatenar
 * @param {Int} indini indice inicial
 * @param {Int} indfin indice final
 * @return {Array} A concatenação entre os dois arrays
 */
Array.prototype.junta=function(arr,indini,indfin){
	if(typeof(indini)=='undefined')
		indini=0;
	if(typeof(indfin)=='undefined')
		indfin=arr.length;
	var comp=this.length;
	for(var i=comp;i<comp+(indfin-indini);i++)
		this[i]=arr[indini+i-comp];
	return this;
};

var maxit=20;

/**
 * Método estático para implementação do algoritmo de quicksort
 * @param {Array} arr Array que se pretende ordenar
 * @return {Array} arrOrd Array ordenado
 */
Array.qsort = function(arr){
	if(arr.length<=1)
		return arr;
	var part = Math.floor((Math.random()*arr.length));
	var esq=[];
	var dir=[];
	ALG.ITER=0;
	for(var i=0;i<arr.length;i++){
		if(i!=part)
		{
			if(arr[i]<=arr[part])
				esq[esq.length]=arr[i];
			else
				dir[dir.length]=arr[i];
		}
		ALG.ITER++;
	}
	return Array.qsort(esq).junta([arr[part]]).junta(Array.qsort(dir));
};

/**
 * Algoritmo radix sort
 * @param {Array} arr Array para ordenação
 * @return {Object} Array ordenado a partir do algoritmo de radix sort
 */
Array.rsort=function(arr){
	
};


/**
 * Método de ordenação pelo algoritmo de quicksort wrapper do Método estático
 * @return{array} Devolve o array ordenado a partir do algoritmo de quicksort
 */
Array.prototype.qsort=function(){
	ALG.ITER=0;
	return Array.qsort(this);
};

/**
 * Método de ordenação a partir do algoritmo de bublesort
 * @return{Array} Devolve o array ordenado a partir do algoritmo de bublesort
 */
Array.prototype.bsort=function(){
	ALG.ITER=0;
	for(var i=0;i<this.length-1;i++){
		for(var j=0;j<this.length-1-i;j++){
			if(this[j]>this[j+1])
				this.troca(j,j+1);
			ALG.ITER++;
		}
	}
	return this;
};
/**
 * Método que cria um array com valores aleatórios
 * @param {int} dim Dimensão do array
 * @param {int} low Valor minimo
 * @param {int} sup Valor máximo
 * @param {bool} intarray Valor booleano indicando se o array é composto por valores inteiros ou valores decimais
 * @return {int} Array aleatório com dim elementos compreendidos entre low e sup
 */
Array.random=function(dim,low,sup,intarray){
	var arr=[];
	if(typeof(low)=='undefined')
		low=0;
	if(typeof(sup)=='undefined')
		sup=100;
	if(typeof(intarray)=='undefined')
		intarray=true;
	for(var i=0;i<dim;i++){
		if(intarray)
			arr[i]=Math.floor(Math.random()*(sup-low+1)+low);
		else
			arr[i]=Math.random()*(sup-low)+low;
	}
	return arr;
};

/**
 * Método que mistura os elementos de um array
 * @return {Array} arrayRand Devolve o array baralhado
 */
Array.prototype.randomize=function(){
	var fin=0;
	var comp=this.length;
	for(var i=0;i<comp;i++){
		fin=Math.floor(Math.random()*comp);
		this.troca(i,fin);
	}
	return this;
};

/**
 * Método que devolve um array contendo todos os codigos dos caracteres presentes na string
 * @return {Array} arr Array com os codigos dos caracteres
 */
String.prototype.toCodArray=function(){
	var arrC=[];
	for(var i=0;i<this.length;i++){
		arrC[i]=this.charCodeAt(i);
	}
	return arrC;
}

/**
 * Método que substitui um caracter numa string
 * @param {Number} index Posição do caracter
 * @param {String} chr Caracter de substituição
 */
String.prototype.setCharAt=function(index,chr) {
	if(index > this.length-1) return this;
	return this.substr(0,index) + chr + this.substr(index+1);
}
/**
 * Método que baralha a string de modo a que esta continue legível para o ser humano
 * @param {String} String para conversão 
 */
String.shuffleText=function(str){
	var arr=str.split(" ");
	var tmp="";
	var posA=0;
	var posB=0;
	for(var i=0;i<arr.length;i++){
		for(var j=0;j<arr[i].length;j++){
			if(j==0||j==arr[i].length-1)
				;
			else{
				posA=1+Math.floor(Math.random()*(arr[i].length-2));
				posB=1+Math.floor(Math.random()*(arr[i].length-2));
				tmpChar=arr[i][posA];
				arr[i]=arr[i].setCharAt(posA,arr[i][posB]);
				arr[i]=arr[i].setCharAt(posB,tmpChar);
			}
				
		}
	}
	return arr.join(" ");
}


/**
 * Método que cria uma string aleatória com caracteres alfabéticos
 * @param {Int} num Número de caracteres da string
 * @return {String} str String formada por caracteres alfabéticos aleatória
 */
String.prototype.getAlphaRandom=function(num){
	var shift=0;
	var strOut="";
	for(var i=0;i<num;i++){
		shift=Math.floor(Math.random()*26);
		strOut+=String.fromCharCode(65+shift);
	}
	return strOut;
}

/**
 * Método que devolve uma string representando o valor binário do número
 * @return {String} str String representando o número sob a numeração binária
 */
Number.prototype.toByteString=function(){
    if(parseInt(this)==0)
        return "0";
    var aux=parseInt(this);
    var strout="";
    var expaux;
    var getexp=function(val){
        var ii=0;
        while(Math.pow(2,ii)<=val){ii++;}
        if(--ii < 0)
            return 0;
        return ii;
    }
    var expmax=getexp(this);
    var expaux=expmax;
    while(aux>0)
    {
        expmax=getexp(aux);
        aux-=Math.pow(2,expmax);
        expaux=getexp(aux);
        strout+="1";
        if(aux==0 && expmax>=1){
            expmax++;    
        }
        while(--expmax>expaux){
            strout+="0";
        }
    }
return strout;
}

/**
 * Método que devolve um array contendo o código binário da string
 * @return {Array} arr Array contendo strings com a representação binária de cada um dos caractéres da string
 */
String.prototype.toByteArray=function(){
	var arr=[];
	for(var i=0;i<this.length;i++){
		arr[i]=this.charCodeAt(i).toByteString();
	}
	return arr;
}

/**
 * Método que converte uma string para uma outra string que consiste na sequência binária dos caracteres
 * @return {String} str String que contem os caracteres representados em binário concatenados.
 */
String.prototype.toByteString=function(){
	var strout="";
	for(var i=0;i<this.length;i++){
		strout+=this.charCodeAt(i).toByteString();
	}
	return strout;
}

/**
 * Método que verifica se um determinado caracter pertence ao alfabeto
 * @param {String} str String de comprimento 1 representando um caracter
 * @return {Boolean} bol Verdadeiro caso o caracter pertença ao alfabeto
 */
String.isAlphaChar=function(str){
	var m=str.toMaiuscula();
	if(m.length==str.length)
		return true;
	return false;
}

/**
 * Método que passa todas as minusculas a maiusculas
 * @return {String} O método devolve o próprio objecto
 */
String.prototype.toMaiuscula=function(){
	var pos=0;
	var posA=0;
	var str="";
	for(var i=0;i<this.length;i++){
		pos=this.charCodeAt(i);
		if(pos>=97 && pos<=122){
			posA=this.charCodeAt(i)-97;
			str+=String.fromCharCode(65+posA);
		}
		else if(pos>=65 && pos<=122){
			str+=this[i];
		}
		//se for o espaço
		else if(pos==32){
			str+=" ";
		}
	}
	return str;
}

/**
 * Método que verifica se o caracter com determinada posição na string é uma letra maiuscula
 * do alfabeto
 * @param {Int} ind Posição na string
 * @return {Bool} val Verdadeiro se o caracter for uma letra maiuscula, falso caso contrário
 */
String.prototype.maiuscula=function(ind){
	if(this.charCodeAt(ind)>=65 && this.charCodeAt(ind)<=90)
		return true;
	return false;
}

/**
 * Método que verifica se o caracter com determinada posição na string é uma letra minuscula
 * do alfabeto
 * @param {Int} ind Posição na string
 * @return {Bool} val Verdadeiro se o caracter for uma letra minuscula, falso caso contrário
 */
String.prototype.minuscula=function(ind){
	if(this.charCodeAt(ind)>=65 && this.charCodeAt(ind)<=90)
		return true;
	return false;
};

/**
 * @constructor Construtor da class
 */
var MathL=function(){};

/**
 * Expansão do número segundo o problema de Collatz Syracuse Ulam (CSU)
 * @param Numero inteiro
 * @return Array Sequência de inteiros até encontrar o valor 1
 */
MathL.CSUExpansion=function(n){
	var a=n;
	var out=[a];
	while(a!=1){
		a=(a%2==0)?a/2:a*3+1;
		out[out.length]=a;
	}
	return out;
};

/**
 * @constructor Construtor do objecto CMarkov que representa uma cadeia de Markov
 * @param {Array} lstats Lista com os labels dos estados associados à cadeia de markov
 * @param {Array} pobj Representa a matriz de probabilidades da cadeia de markov
 * @param {Array} inip Representa o vector de probabilidades inicial para a cadeia de markov
 */
MathL.CMarkov=function(lstats,pobj,inip){
	if(lstats.length*lstats.length!=pobj.length || lstats.length!=inip.length){
		throw "As dimensões do número de estados não corresponde à dimensão da matriz de probabilidades ou à dimensão do vector de probabilidades iniciais";
	}
	this.lbels=lstats;
	this.mp=MathL.Matriz.ArrayToMatriz(lstats.length,lstats.length,pobj);
	this.auxmit=MathL.Matriz.ArrayToMatriz(1,lstats.length,inip);
	this.initm=MathL.Matriz.ArrayToMatriz(1,lstats.length,inip);
};

MathL.CMarkov.prototype.iterate=function(){
	this.auxmit=MathL.Matriz.multMatriz(this.auxmit,this.mp);
};

MathL.CMarkov.prototype.restart=function(){
	this.auxmit=this.initm;
};

MathL.CMarkov.prototype.printIteration=function(){
	var std="[";
	for(var i=0;i<this.lbels.length;i++){
		if(i!=0)
			std+=",";
		std+=this.lbels[i]+":"+this.auxmit.getValor(0,i);
	}
	std+="]";
	return std;
};
/**
 * Devolve uma string com o valor de n iteracções da cadeia de markov
 * @param {Number} n Número de iteracções a efectuar
 * @return {String} String com as iteracções até n
 */
MathL.CMarkov.prototype.printit=function(n){
	var itres="";
	for(var i=0;i<n;i++){
		this.iterate();
		itres+=this.printIteration()+"\n";
	}
	return itres;
}
/**
 * Método que calcula a raiz de um valor para um dado expoente com uma determinada precisão
 * @param {Object} val Valor do valor na base
 * @param {Object} exp Valor do expoente
 * @param {Object} err Numere de casas de precisão
 */
MathL.sqrtF=function(val,exp,prec){
	if(typeof(prec)=='undefined'){
		prec=3;
	}
	var xi=val/2;
	var xa=val;
	var err=1/Math.pow(10,prec);
	ALG.ITER=0;
	while(Math.abs(xi-xa)>err){
		xa=xi;
		xi=xi-(Math.pow(xi,exp)-val)/(exp*xi);
		ALG.ITER++;
	}
	return xi;
};

/**
 * Método de Simpson para cálculo de integrais
 * @param {Function} f Função que se pretende integrar
 * @param {Number} min Minimo do intervalo de integração
 * @param {Number} max Maximo do intervalo de integração
 * @param {Number} n Número de intervalos
 * @return {Number} Integral de Simpson
 */
MathL.SimpsonInt=function(f,min,max,n){
	n=n*2;
	var sint=f(min);
	var passo=(max-min)/n;
	var fact=0;
	var xi;
	for(var i=1;i<=n;i++){
		//determina o factor para cada iteracção
		fact=(i==n)?1:(i%2==0)?2:4;
		xi=min+passo*i;
		sint+=fact*f(xi);
	}
	return sint*(passo/3);
}
/**
 * Determinação do integral da função f a partir do método do trapézio
 * @param {Function} f Função a integrar
 * @param {Number} min Intervalo minimo de integração
 * @param {Number} max Intervalo máximo de integração
 * @param {Number} n Número de intervalos para integração
 * @return {Number} Integral de f entre min e max
 */
MathL.TrapzInt=function(f,min,max,n){
	var passo=(max-min)/n;
	var strap=f(min);
	var fact;
	var xi;
	for(var i=1;i<=n;i++){
		fact=(i==n)?1:2;
		xi=min+passo*i;
		strap+=fact*f(xi);
	}
	return strap*(passo/2);
}
/**
 * Determina o integral de um intervalo de valores e respectivas imagens a partir do 
 * algoritmo do trapézio
 * @param {Array} arrx array de coordenadas
 * @param {Array} arry array das imagens das coordenadas
 */
MathL.TrapzCInt=function(arrx,arry){
	if(arrx.length!=arry.length)
		return Number.NaN;
	var soma=0;
	for(var i=1;i<arrx.length;i++){
		soma+=(arrx[i]-arrx[i-1])*(arry[i]+arry[i-1]);
	}
	return soma/2;
}
/**
 * Aplica o array a uma função. O resultado consiste nas imagens obtidas a partir da aplicação
 * da função aos elementos do array
 * @param {Function} f Função que mapeia o array
 * @return {Array} Array mapeado pela função f.
 */
Array.prototype.MapF=function(f){
	var arro=[];
	for(var i=0;i<this.length;i++){
		arro[i]=f(this[i]);
	}
	return arro;
}
/***
 * Método que cria um array com os valores entre min e máx
 * @param {Number} min Valor mínimo do intervalo
 * @param {Number} max Valor máximo do intervalo
 * @param {Number} passo Passo entre os sucessivos valores
 * @return {Array}  Array com os valores compreendidos entre min e max.
 */
Array.map=function(min,max,passo){
	var ps;
	if(passo)
		ps=passo;
	else
		ps=1;
	var out=[];
	for(var i=0;i<max;i+=ps){
		out[out.length]=min+i;
	}
	return out;
}

/**
 * Método que determina a distância de Hamming para duas Strings 
 * @param {String} str1 String A
 * @param {String} str2 String B
 * @return {Number} dist Distância entre A e B
 */
MathL.hammingDistance=function(str1,str2){
	var diff=Math.abs(str1.length-str2.length);
	var cmin=Math.min(str1.length,str2.length);
	var hdist=diff;
	for(var i=0;i<cmin;i++){
		if(str1.charAt(i)!=str2.charAt(i))
			hdist++;
	}
	return hdist;
}

/**
 * Objecto matriz disponibiliza um conjunto de métodos para manipular matrizes
 * @param {int} m Numero de linhas
 * @param {int} n Numero de colunas
 * @param {int} val Valor por defeito nos campos da matriz
 * @classDescription Classe que pretende representar uma matriz
 */
MathL.Matriz=function(m,n,val){
	var nlinhas=3;
	var ncolunas=3;
	var valdef=0;
	if(typeof(m)!='undefined')
		nlinhas=m;
	if(typeof(m)!='undefined')
		ncolunas=n;
	if(typeof(val)!='undefined')
		valdef=val;
	this._initVal(nlinhas,ncolunas,valdef);
};

/**
 * Método que devolve a matriz transposta
 * @return {MathL.Matriz} mat Matriz transposta
 */
MathL.Matriz.prototype.transposta=function(){
	var nlinhas=this._matriz.length;
	var ncolunas=this._matriz[0].length;
	var mt=new MathL.Matriz(ncolunas,nlinhas);
	for(var i=0;i<nlinhas;i++){
		for(j=0;j<ncolunas;j++){
			mt.setValor(j,i,this.getValor(i,j));
		}
	}
	return mt;
}

/**
 * Método que devolve a submatriz excluindo a linha i e a coluna j
 * @param {Int} i Índice da linha que se pretende excluir
 * @param {Int} j Índice da coluna que se pretende excluir
 * @return {MathL.Matriz} mt Matriz
 */
MathL.Matriz.prototype.subMatriz=function(i,j){
	var ii=0;
	var jj=0;
	var ik=0;
	var jk=0;
	var m=new MathL.Matriz(this._matriz.length-1,this._matriz[0].length-1);
	for(ii=0;ii<this._matriz.length;ii++){
		jk=0;
		if (ii != i) {
			for (jj = 0; jj < this._matriz[0].length; jj++) {
				if(jj!=j){
					m.setValor(ik,jk,this._matriz[ii][jj]);
					jk++;
				}
			}
			ik++;
		}
	}
	return m;
}

/**
 * Verifica se uma dada matriz é simétrica
 * @return {Boolean} bol Valor booleano indicando se a matriz é simétrica ou não
 */
MathL.Matriz.prototype.simetrica=function(){
	if(this._matriz.length!=this._matriz[0].length){
		return false;
	}
	for(var i=0;i<this._matriz.length;i++){
		for(var j=i;j<this._matriz.length;j++){
			if(this._matriz[j][i]!=this._matriz[i][j]){
				return false;
			}
		}
	}
	return true;
}
/**
 * Determina a matriz das covariâncias
 * @param {Array} Um conjunto de um ou mais arrays com os valores das amostras
 * @return {MathL.Matriz} Matriz das covariâncias
 */
MathL.Matriz.MCov=function(){
	if(arguments.length==0)
		return new MathL.Matriz(1,1,0);
	var nargs=arguments.length;
	var m=new MathL.Matriz(nargs,nargs,0);
	for(var i=0;i<nargs;i++){
		for(var j=0;j<nargs;j++){
			m.setValor(i,j,Array.cov(arguments[i],arguments[j]));
		}
	}
	return m;
}

/**
 * * Método que inicializa a matriz com os campos assinados a um determinado valor
 * @param {Number} valor Valor por defeito na matriz
 * @param {Int} nlinhas Numero de linhas da matriz
 * @param {Int} ncolunas Numero de colunas da matriz
 */
MathL.Matriz.prototype._initVal=function(nlinhas,ncolunas,valor){
	this._matriz=[];
	for(var i=0;i<nlinhas;i++){
		this._matriz[i]=[];
		for(var j=0;j<ncolunas;j++){
			this._matriz[i][j]=valor;
		}
	}
};

/**
 * Devolve uma string com a descrição da matriz
 * @return {String} String representando a matriz
 */
MathL.Matriz.prototype.toString=function(){
	var strO="";
	for(var i=0;i<this._matriz.length;i++){
		strO+="\n|";
		for(var j=0;j<this._matriz[i].length;j++){
			strO+=this._matriz[i][j];
			if(j!=this._matriz[i].length-1)
				strO+=",";
		}
		strO+="|";
	}
	return strO;
};

/**
 * Método que efectua o parsing de um array bidimensional para a estrutura de Matriz
 * @param {array} array Array bidimensional contendo os valores da matriz
 * @return {MathL.Matriz} matriz Objecto do tipo matriz com os valores existentes no array
 */
MathL.Matriz.fromArray=function(array){
	var m=new MathL.Matriz(array.length,array[0].length);
	for(var i=0;i<array.length;i++){
		for(var j=0;j<array[0].length;j++){
			m.setValor(i,j,array[i][j]);
		}
	}
	return m;
};
/**
 * Método que cria um objecto matriz a partir de um array
 * @param {Number} dimx Número de linhas
 * @param {Number} dimy Número de colunas
 * @param {Array} arr Com os valores da matriz sob a forma de array
 * @return {MathL.Matriz} Matriz 
 */
MathL.Matriz.ArrayToMatriz=function(dimx,dimy,arr){
	var mout=new MathL.Matriz(dimx,dimy,0);
	for(var i=0;i<dimx;i++){
		for(var j=0;j<dimy;j++){
			mout.setValor(i,j,arr[i*dimy+j]);
		}
	}
	return mout;
}

/**
 * Método que especifica o valor da matriz na posição (i,j)
 * @param {int} i Indice de linha
 * @param {int} j Indice de coluna
 * @param {Number} val Valor da celula
 */
MathL.Matriz.prototype.setValor=function(i,j,val){
	this._matriz[i][j]=val;
};

/**
 * Método que devolve o valor da matriz na posicao (i,j)
 * @param {int} i Indice de linha
 * @param {int} j Indice de coluna
 * @return {Number} Valor da matriz na celula especificada
 */
MathL.Matriz.prototype.getValor=function(i,j){
	return this._matriz[i][j];
};

/**
 * Método que devolve uma linha da matriz sob a forma de array
 * @param {int} indice Indice da linha
 * @return {array} Array contendo os valores de uma determinada linha
 */
MathL.Matriz.prototype.getLinha=function(indice){
	var arrL=[];
	for(var i=0;i<this._matriz[indice].length;i++){
		arrL[i]=this.getValor(indice,i);
	}
	return arrL;
};

/**
 * Método que efectua a troca entre duas linhas da matriz
 * @param {int} i Índice de linha
 * @param {int} j Índice de linha
 * @return{MathL.Matriz} mat Devolve a matriz para permitir chaining
 */
MathL.Matriz.prototype.trocaLinhas=function(i,j){
	var ii=0;
	var aux;
	var comp=this._matriz[0].length;
	for(ii=0;ii<comp;ii++)
	{
		aux=this._matriz[i][ii];
		this._matriz[i][ii]=this._matriz[j][ii];
		this._matriz[j][ii]=aux;
	}
	return this;
}

/**
 * Método que efectua a troca entre duas colunas da matriz
 * @param {int} i Índice de coluna
 * @param {int} j Índice de coluna
 * @return{MathL.Matriz} mat Devolve a matriz para permitir chaining
 */
MathL.Matriz.prototype.trocaColunas=function(i,j){
	var ii=0;
	var aux;
	var comp=this._matriz.length;
	for(ii=0;ii<comp;ii++)
	{
		aux=this._matriz[ii][i];
		this._matriz[ii][i]=this._matriz[ii][j];
		this._matriz[ii][j]=aux;
	}
	return this;
}

/**
 * Método que adiciona uma coluna à matriz
 * @param  {Array} arr Array com os valores da coluna que se pretende adicionar
 * @return {MathL.Matriz} Devolve o próprio objecto para efeitos de chaining
 */
MathL.Matriz.prototype.adColuna=function(arr){
	if(arr.length!=this._matriz.length){
		return this;
	}
	var coln=this._matriz[0].length;
	for(var i=0;i<this._matriz.length;i++){
		this._matriz[i][coln]=arr[i];
	}
}

/**
 * Método que adiciona linhas à Matriz
 * @param {Array} arr Array com os valores da linha que se pretende adicionar à matriz
 * @return {MathL.Matriz} obj Devolve o próprio objecto para efeitos de chaining
 */
MathL.Matriz.prototype.adLinha=function(arr){
	if(arr.length!=this._matriz[0].length){
		return this;
	}
	var linc=this._matriz.length;
	this._matriz[linc]=[];
	for(var i=0;i<linc;i++){
		this._matriz[linc][i]=arr[i];
	}
}

/**
 * Método que remove uma linha da matriz
 * @param {int} ind indice da linha da matriz que pretendemos ver removido
 * @return {MathL.Matriz} mat O proprio objecto matriz, para chaining
 */
MathL.Matriz.prototype.rmLinha=function(ind){
	if(ind<0 || ind >=this._matriz.length){
		return this;
	}
	this._matriz.remove(ind);
	return this;
};

/**
 * Método que remove uma coluna da matriz
 * @param {Int} ind Índice da matriz que pretendemos remover
 * @return {MathL.Matriz} mat O próprio objecto matriz, para chaining
 */ 
MathL.Matriz.prototype.rmColuna=function(ind){
	if(ind<0 || ind >=this._matriz[0].length){
		return this;
	}
	for(var i=0;i<this._matriz[0].length;i++){
		this._matriz[i].remove(ind);
	}
	return this;
}

/**
 * Método que devolve uma coluna da matriz sob a forma de array
 * @param {int} indice Índice da coluna
 * @return {array} Array contendo os valores de uma determinada coluna
 */
MathL.Matriz.prototype.getColuna=function(indice){
	var arrC=[]
	for(var i=0;i<this._matriz.length;i++){
		arrC[i]=this._matriz[i][indice];
	}
	return arrC;
};

/**
 * Método que cria uma matriz quadrada identidade de dimensões (nxn)
 * @param {int} n Número de linhas
 * @param {int} m Número de colunas
 * @return {MathL.Matriz} Matriz identidade
 */
MathL.Matriz.identidade=function(n,m){
	if(typeof(m)=='undefined')
		m=n;
	var m=new MathL.Matriz(n,m,0);
	for(var i=0;i<n;i++){
		m.setValor(i,i,1);
	}
	return m;
};

/**
 * Método que multiplica uma linha por um determinado valor
 * @param {Int} ind Índice da linha
 * @param {Number} val Valor pelo qual se pretende multiplicar uma linha da matriz
 * @return {MathL.Matriz} mat Objecto para efeitos chaining
 */
MathL.Matriz.prototype.MLinha=function(ind,val){
	if(ind<0 || ind>this._matriz.length){
		return null;
	}
	var ncol=this._matriz[0].length;
	for(var i=0;i<ncol;i++){
		this._matriz[ind][i]*=val;
	}
	return this;
}

MathL.Matriz.prototype.MColuna=function(ind,val){
	if(i<0 || i>this._matriz[0].length){
		return this;
	}
	var nlin=this._matriz.length;
	for(var i=0;i<nlin;i++){
		this._matriz[i][ind]*=val;
	}
	return this;
}

/**
 * Método que adiciona valores a uma linha da matriz
 * @param {Int} ind Índice da linha
 * @param {Array} arrV Array contendo os valores que se pretendem adicionar à matriz
 * @return {MathL.Matriz} mat O próprio objecto para efeitos de chaining
 */
MathL.Matriz.prototype.AddToLinha=function(ind,arrV){
	var ncol=this._matriz[0].length;
	if(arrV.length!=ncol){
		return this;
	}
	for(var i=0;i<ncol;i++){
		this._matriz[ind][i]+=arrV[i];
	}
	return this;
}

/**
 * Método que adiciona valores a uma coluna da matriz
 * @param {Int} ind Índice da coluna
 * @param {Array} arrV Array com os valores a adicionar à coluna
 * @return {MathL.Matriz} mat O próprio objecto para efeitos de chaining
 */
MathL.Matriz.prototype.AddToColuna=function(ind,arrV){
	var nlin=this._matriz.length;
	if(arrV.length!=nlin){
		return this;
	}
	for(var i=0;i<ncol;i++){
		this._matriz[i][ind]+=arrV[i];
	}
	return this;
}


/**
 * Método que efectua a multiplicação de duas matrizes A, B
 * @param {MathL.Matriz} mat1 Matriz A
 * @param {MathL.Matriz} mat2 Matriz B
 * @return {MathL.Matriz} mat3 O resultado da multiplicação das matrizes A,B
 */
MathL.Matriz.multMatriz=function(mat1,mat2){
	if(mat1._matriz[0].length!=mat2._matriz.length)
		return null;
	var ma=new MathL.Matriz(mat1._matriz.length,mat2._matriz[0].length,0);
	var valcel=0;
	for(var i=0;i<mat2._matriz[0].length;i++){
		for(var j=0;j<mat1._matriz.length;j++){
			valcel=0;
			for(var k=0;k<mat1._matriz[0].length;k++){
				valcel+=mat1._matriz[j][k]*mat2._matriz[k][i];
			}
			ma.setValor(j,i,valcel);
		}
	}
	return ma;
};

/**
 * Método que efectua a redução da matriz a triangular inferior
 * @return {MathL.Matriz} mat Devolve a matriz triangular inferior a partir do processo de Gauss Jordan
 */
MathL.Matriz.prototype.RTriangular=function(){
	var k=0;
	var i=0;
	var j=0;
	var laux;
	var colmax=0;
	var nlinhas=this._matriz.length;
	var ncolunas=this._matriz[0].length;
	var inv=MathL.Matriz.identidade(nlinhas,ncolunas);
	var mac=this.clone();
	var auxP;
	//Iteracção sobre as colunas
	for(i=0;i<ncolunas;i++){
		if (i < nlinhas) {
			//Procura a linha com o valor maximo para a dada coluna
			linmax = i;
			for (k = i; k < nlinhas; k++) {
				if (mac._matriz[linmax][i] < mac._matriz[k][i]) {
					linmax = k;
				}
			}
			mac.trocaLinhas(i,linmax);
			//Actualiza as linhas
			for(j=0;j<mac._matriz.length;j++){
				if (j != i) {
					auxP=mac._matriz[j][i];
					//actualiza os valores da linha
					for(k=i;k<mac._matriz[0].length;k++){
						mac._matriz[j][k]+=-mac._matriz[i][k]*(auxP/mac._matriz[i][i]);
					}
				}
			}
		}
	}
	return mac;
}

/**
 * Método que resolve um sistema de equações lineares a partir do algoritmo de eliminação de Gauss
 * @param {MathL.Matriz} mat Matriz de coeficientes
 * @return {MathL.Matriz} matsol Matriz solução do sistema
 */
MathL.Matriz.ResolveSistema=function(mat){
	var ms=mat.RTriangular();
	var j;
	var k;
	var aux;
	var i;
	for(i=ms._matriz.length-1;i>=0;i--){
		if(ms._matriz[i][i]!=0){
			ms.MLinha(i,1/ms._matriz[i][i]);
			for(j=i-1;j>=0;j--){
				aux=ms._matriz[j][i];
				for(k=i;k<ms._matriz[0].length;k++){
					ms._matriz[j][k]+=-ms._matriz[j][k]*(aux/ms._matriz[i][i]);
				}
			}
		}
	}
	var so="{";
	var nlinhas=ms._matriz.length;
	var ncolunas=ms._matriz[0].length;
	var sol;
	for(var i=0;i<ms._matriz.length;i++){
		if (ms._matriz[i][i] != 0) {
			sol = ms._matriz[i][ncolunas - 1] / ms._matriz[i][i];
		}
		else{
			sol=0;
		}
		if(i==0){
			so+='"x'+i+'":'+sol;
		}
		else{
			so+=',"x'+i+'":'+sol;
		}
		
	}
	so+="}";
	return eval('('+so+')');
}

/**
 * Método que devolve a factorização LU da matriz
 * @return {Object} obj Objecto composto por duas matrizes L e U representando
 * a factorização da matriz contida no objecto que efectua a chamada da função.
 */
MathL.Matriz.prototype.FactLU=function(){
	var k=0;
	var i=0;
	var j=0;
	var laux;
	var colmax=0;
	var nlinhas=this._matriz.length;
	var ncolunas=this._matriz[0].length;
	var inv=MathL.Matriz.identidade(nlinhas,ncolunas);
	var U=this.clone();
	var L=MathL.Matriz.identidade(nlinhas,ncolunas);
	var auxP;
	//Iteracção sobre as colunas
	for(i=0;i<ncolunas;i++){
		if (i < nlinhas) {
			//Actualiza as linhas
			for(j=0;j<U._matriz.length;j++){
				if (j != i) {
					auxP=U._matriz[j][i];
					//actualiza os valores da linha
					for(k=i;k<U._matriz[0].length;k++){
						U._matriz[j][k]+=-U._matriz[i][k]*(auxP/U._matriz[i][i]);
						L._matriz[j][k]+=-U._matriz[i][k]*(auxP/U._matriz[i][i]);
					}
				}
			}
		}
	}
	var obj={"L":L,"U":U};
	return obj;
}

/**
 * Método que multiplica a matriz por um determinado valor escalar
 * @param {Number} val Escalar
 * @return {MathL.Matriz} Matriz Devolve a propria matriz para possibilitar o chaining na invocacao
 * dos Métodos
 */
MathL.Matriz.prototype.multEscalar=function(val){
	for(var i=0;i<this._matriz.length;i++)
		for(var j=0;j<this._matriz[0].length;j++)
			this._matriz[i][j]*=val;
	return this;
};

/**
 * Método que efectua o clone do objecto matriz
 * @return {MathL.Matriz} A cópia do objecto matriz
 */
MathL.Matriz.prototype.clone=function(){
	return MathL.Matriz.fromArray(this._matriz);
};

/**
 * Construtor do objecto Vector2D.
 * @param {double} vx
 * @param {double} vy
 * @classDescription Este objecto implementa um objecto que representa vectores de duas dimensões,
 * utilizado para computar operações gráficas no plano
 */
MathL.Vector2D=function(vx,vy){
	this.x=vx;
	this.y=vy;
};

/**
 * Método que faz uma copia do objecto
 * @return {MathL.Vector2D} Objecto do tipo Vectord2D
 */
MathL.Vector2D.prototype.clone=function(){
	return new MathL.Vector2D(this.x,this.y);
};

MathL.Vector2D.prototype.toString=function(){
	return "["+this.x+","+this.y+"]";
}

/**
 * Método que multiplica o vector por um escalar
 * @param {Double} esc Número escalar
 * @return {Vector2D} vec Devolve o próprio vector para permitir chaining
 */
MathL.Vector2D.prototype.multEscalar=function(esc){
	this.x*=esc;
	this.y*=esc;
	return this;
};

/**
 * Método que soma dois vectores
 * @param {MathL.Vector2D} vecA Primeiro Vector2D 
 * @param {MathL.Vector2d} vecB Segundo Vector2D
 * @return {MathL.Vector2D} vecR Vector2D soma resultante
 */
MathL.Vector2D.somaVec=function(vecA,vecB){
	return new MathL.Vector2D(vecA.x+vecB.x,vecA.y+vecB.y);
};
/**
 * Método que efectua o produto interno entre dois vectores 
 * @param {MathL.Vector2D} vecA Primeiro Vector2D
 * @param {MathL.Vector2D} vecB Segundo Vector2D
 * @return {Double} prodint Número representando o produto interno entre dois vectores
 */
MathL.Vector2D.prodInt=function(vecA,vecB){
	return vecA.x*vecB.x+vecA.y*vecB.y;
};

/**
 * Método que devolve a norma de um Vector2D
 * @return {double} num Norma do vector
 */
MathL.Vector2D.prototype.norma=function(){
	return Math.sqrt(this.x*this.x+this.y*this.y);
};
/**
 * Devolve informação sobre o vector sob a forma de string
 * @return {string} str String contendo a descrição do vector
 */
MathL.Vector2D.prototype.toString=function(){
	return "["+this.x+","+this.y+"]";
};



/**
 * Método que devolve o objecto Matriz equivalente ao Vector2D
 * @return {MathL.Matriz}
 */
MathL.Vector2D.prototype.toMatriz=function(){
var vm=new MathL.Matriz(1,2);
vm.setValor(0,0,this.x);
vm.setValor(0,1,this.y);
return vm;	
};

/**
 * Máximo divisor comum a partir do algoritmo de euclides
 * @param {int} a Valor inteiro A
 * @param {int} b Valor inteiro B
 * @return {int} O máximo divisor entre A e B
 */
MathL.mdc=function(a,b){
	ALG.ITER=0;
	if(a==0)
		return b;
	if(b==0)
		return a;
	var ax=Math.max(a,b);
	var bx=Math.min(a,b);
	var m=0;
	if((ax%bx)==0)
		return bx;
	//algoritmo de euclides...
	while(bx!=0){
		ALG.ITER++;
		m=ax%bx;
		ax=bx;
		bx=m;
	}
	return ax;
};

/**
 * Função para o factorial de um numero
 * @param {int} a Numero inteiro
 * @return {int} Factorial de um número
 */
MathL.factorial=function(a){
	var b=Math.abs(a);
	var fact=1;
	for(var i=1;i<=b;i++)
		fact*=i;
	return fact;
};

/**
 * Método que devolve os primos existentes menor que um dado numero n
 * @param {int} n Número máximo dos valores primos
 * @return {Array} Array contendo os valores primos
 */
MathL.PrimosAte=function(n){
	var primos=[1,2];
	var primo;
	for(i=3;i<=n;i++){
		primo=true;
		for(j=1;j<primos.length;j++){
			if(primos[j]>Math.sqrt(i))
				break;
			if((i%primos[j])==0)
				primo=false;
		}
		if(primo)
			primos[primos.length]=i;
	}
	return primos;
};

/**
 * Determina a média dos valores contidos no array, aqui assume-se que o array 
 * é preenchido com valores numéricos
 */
Array.prototype.media=function(){
	var cmp=this.length;
	var m=0;
	for(var i=0;i<cmp;i++)
		m+=this[i];
	return m/cmp;
}

/**
 * Determina a variância dos valores contidos no array
 * @return {Number}
 */
Array.prototype.variancia=function(){
	if(this.length<2)
		return 0;	
	var cmp=this.length;
	var dp=0;
	var md=this.media();
	for(var i=0;i<cmp;i++){
		dp+=(this[i]-md)*(this[i]-md);
	}
	return dp/(cmp-1);
}
/**
 * Determina o desvio padrão dos dados contidos no array
 * @return {Number}
 */
Array.prototype.desPad=function(){
	return Math.sqrt(this.variancia());
}

/**
 * Determina a covariância entre duas amostras representadas sob a forma de 
 * arrays. As duas amostras devem ter a mesma dimensão
 * @param {Array} X Array de valores numéricos
 * @param {Array} Y Array de valores numéricos
 * @return {Number} Valor da covariância entre a amostra X e a amostra Y
 */
Array.cov=function(X,Y){
	if(X.length!=Y.length)
		return 0;
	if(X.length<2)
		return 0;
	var cmp=X.length;
	var xM=X.media();
	var yM=Y.media();
	var c=0;
	for(var i=0;i<cmp;i++){
		c+=(X[i]-xM)*(Y[i]-yM);
	}
	return c/(X.length-1);
}

Array.prototype.soma=function(){
	var s=0;
	var cmp=this.length;
	for(var i=0;i<cmp;i++){
		s+=this[i];
	}
	return s;
}

Array.sub=function(arrA,arrB){
	var mx=Object.max(arrA,arrB);
	var mi=Object.max(arrA,arrB);
	var out=[];
	for(var i=0;i<mx.length;i++){
		if(i<mi.length)
			out[out.length]=arrA[i]-arrB[i];
		else{
			if(arrA[i])
				out[out.length]=arrA[i];
			else
				out[out.length]=-arrB[i];
		}
	}
	return out;
}

Array.prototype.clona=function(){
	var cmp=this.length;
	var out=[];
	for(var i=0;i<cmp;i++)
		out[out.length]=this[i];
	return out;
}

Array.prototype.subE=function(esc){
	var cmp=this.length;
	for(var i=0;i<cmp;i++){
		this[i]=this[i]-esc;
	}
	return this;
}

Array.prototype.somaE=function(esc){
	var cmp=this.length;
	for(var i=0;i<cmp;i++){
		this[i]=this[i]-esc;
	}
	return this;
}

Array.soma=function(arrA,arrB){
	var mx=Object.max(arrA,arrB);
	var mi=Object.max(arrA,arrB);
	var out=[];
	for(var i=0;i<mx.length;i++){
		if(i<mi.length)
			out[out.length]=arrA[i]+arrB[i];
		else{
			if(arrA[i])
				out[out.length]=arrA[i];
			else
				out[out.length]=arrB[i];
		}
	}
	return out;
}



/**
 * Método que devolve os primeiros n primos
 * @param {int} n Numero de primos que pretendemos ver devolvidos
 * @return {Array} arrayPrimos Array com os numeros primos
 */
MathL.PPrimos = function(n){
	if (typeof(n) == 'undefined') 
		n = 20;
	var primos = [1, 2];
	var primo;
	var i=3;
	ALG.ITER=0;
	while (primos.length < n) {
		primo = true;
		for (j = 1; j < primos.length; j++) {
			if (primos[j] > Math.sqrt(i)) 
				break;
			if ((i % primos[j]) == 0) 
				primo = false;
			ALG.ITER++;
		}
		if (primo) 
			primos[primos.length] = i;
		i++;
	}
	return primos;
};

/**
 * Método que devolve o valor de combinações (n,k)
 * @param {int} n Inteiro (n k) --> n
 * @param {int} k Inteiro (n k) --> k
 * @return {int} com Inteiro número de combinações 
 */
MathL.comb=function(n,k){
	var res=1;
	for(var i=1;i<=k;i++){
		res*=(n+1-i)/i;
	}
	return res;
};



var COOkie={};

COOkie.setCookie=function(cookieName,cookieValue,minutos) {
 var today = new Date();
 var expire = new Date();
 if (minutos==null || minutos==0) minutos=1;
 expire.setTime(today.getTime() + 60000*minutos);
 document.cookie = cookieName+"="+escape(cookieValue)
                 + ";expires="+expire.toGMTString();
};


var Crypto=function(){
};
/**
 * Função que implementa a criptografia de Ceaser
 * @param {string} str string a criptografar
 * @param {int} shift Número de deslocamentos
 * @return {string} strC String criptografada
 */
Crypto.cesar=function(str,shift){
	var i;
	var strO="";
	var chcod;
	for(i=0;i<str.length;i++){
		if (str.charAt(i) != " ") {
			chcod = str.charCodeAt(i);
			strO += String.fromCharCode(chcod + shift);
		}
		else
			strO+=" ";
	}
	return strO;
};

/**
 * Método que gera uma chave aleatória de vigénere
 * @param {Int} comp Comprimento da chave
 * @return {String} str A string que representa a chave para o algoritmo de vigénere
 */
Crypto.vigenereRandomKey=function(comp){
	var str="";
	if(typeof(comp)=='undefined'){
		comp=10;
	}
	for(var i=0;i<comp;i++){
		str+=String.fromCharCode(Math.floor(Math.random()*26 + 65));
	}
	return str;
}

Crypto.Hash={};

Crypto.Hash.md5=function(str){
	this.senc=str;
};



/**
 * Criptanalise à cifra de cesar a partir de força bruta
 * @param {String} str string a ser decriptada
 * @param {int} maxiter Maximo de iterações
 * @return {String} strO String contendo as várias tentativas de decriptação a partir de força bruta
 */
Crypto.cesarBruteForceAttack=function(str,maxiter){
	var i;
	var iter=0;
	var strO="";
	while (iter < maxiter) {
		strO+="\n";
		for (i = 0; i < str.length; i++) {
			strO+=String.fromCharCode(str.charCodeAt(i)-iter);
		}
		iter++;
	}
	return strO;
};

/**
 * Ataque por frequências
 * @param {string} str String que se pretende inspeccionar
 * @return {String} strO string contendo a informação sobre as frequências dos vários caracteress
 */
Crypto.frequenceAttack=function(str){
	var tbfreq=[];
	var pos;
	var i;
	var strO="";
	var existeCar=function(car){
		var existe=-1;
		for(var i=0;i<tbfreq.length;i++){
			if(car==tbfreq[i][0])
				existe=i;
		}
		return existe;
	};
	//calcula as frequencias
	for(i=0;i<str.length;i++){
		pos=existeCar(str.charAt(i));
		if(pos==-1){
			tbfreq[tbfreq.length]=[str.charAt(i),1];
		}
		else{
			tbfreq[pos][1]++;
		}
	}
	//devolve os resultados
	var freq=0;
	for(i=0;i<tbfreq.length;i++){
		freq=(tbfreq[i][1]*100)/str.length;
		strO+="\n";
		strO+="Car:|"+tbfreq[i][0]+"|--> "+freq+"%";
	}
	return strO;
};

/**
 * Método que encripta uma string a partir da chave de Vigénere. Este método encripta somente
 * strings que contenham caracteres do alfabeto
 * @param {String} str String a encriptar 
 * @param {String} chave Chave encriptadora
 * @return {String} enc Chave encriptada a partir do algoritmo de vigénere
 * 
 */
Crypto.VEncripta=function(str,chave){
	if(typeof(chave)=='undefined'){
		chave=Crypto.vigenereRandomKey();
		ALG.VIGSECRETKEY=chave;
	}
	else{
		chave=chave.toMaiuscula();
		ALG.VIGSECRETKEY=chave;
	}
	//Se a string a codificar não for válida sai com valor nulo
	if(!String.isAlphaChar(str)){
		return null;
	}
	var chcomp=chave.length;
	var chcod=0;
	var deslocamentochave=0;
	var strOut="";
	var offset=0;
	var k=0;
	str=str.toMaiuscula();
	for(var i=0;i<str.length;i++){
		if (str.charCodeAt(i) == 32) {
			strOut+=" ";
		}
		else {
			deslocamentochave = k % chcomp;
			chchave = chave.charCodeAt(deslocamentochave) - 65;
			chcod = str.charCodeAt(i) - 65;
			offset = (chcod + chchave) % 26;
			strOut += String.fromCharCode(65 + offset);
			k++;
		}
	}
	return strOut;
}

/**
 * Método que efectua a desencriptação de uma string codificada a partir do algoritmo de Vigénere
 * @param {String} stre String codificada
 * @param {String} chave Chave de encriptação
 * @return {String} strd String descodificada
 */
Crypto.VDecripta=function(str,chave){
	if(typeof(chave)=='undefined'){
		chave=ALG.VIGSECRETKEY;
	}
	else{
		chave=chave.toMaiuscula();
	}
	var chcomp=chave.length;
	var chcod=0;
	var deslocamentochave=0;
	var strOut="";
	var offset=0;
	var k=0;
	str=str.toMaiuscula();
	for(var i=0;i<str.length;i++){
		if (str.charCodeAt(i) == 32) {
			strOut+=" ";
		}
		else {
			deslocamentochave = k % chcomp;
			chchave = chave.charCodeAt(deslocamentochave) - 65;
			chcod = str.charCodeAt(i) - 65;
			offset =(chcod - chchave) % 26;
			if(offset<0)
				offset=26+offset;
			strOut += String.fromCharCode(65 + offset);
			k++;
		}
	}
	return strOut;
}

/**
 * @constructor Namspace que representa os algoritmos de compressão de dados
 */
var Compressao=function(){};

Compressao.HuffmanEncodingTree=function(str){
	//Transforma o objecto de frequências em num array dicionario
	var strO=Utils.charFreq(str);
	var arrO=strO.toDicArray();
	var arrA=[];
	var indA1;
	var indA2;
	var noAux1;
	var noAux2;
	var noRaiz;
	//Função que detecta o elemento com valor mínimo e devolve o seu índice do array de árvores
	var getIndMinFreqObj=function(arrA){
		if(arrA.length==0){
				return null;
			}
		var k=0;
		for(var ii=0;ii<arrA.length;ii++){
			if(arrA[k].key>arrA[ii]){
				k=ii;
			}
		}
		return k;
	};
	
	//Criar os nós para cada um dos valores
	for(var i=0;i<arrO.length;i++){
		if (typeof(arrO[i][1]) == 'number') {
			arrA[i] = new noarvore(arrO[i][1], arrO[i][0]);
		}
	}
	if(arrA.length==1){
		noRaiz=new noarvore(1,null);
		noRaiz.esq=arrA[0];
		return noRaiz;
	}
	//Fundir as árvores até só sobrar uma no array de árvores
	while(arrA.length>1){
		indA1=getIndMinFreqObj(arrA);
		noAux1=arrA[indA1];
		arrA.remove(indA1);
		indA2=getIndMinFreqObj(arrA);
		noAux2=arrA[indA2];
		arrA.remove(indA2);
		noRaiz=new noarvore(noAux1.key+noAux2.key,null);
		noRaiz.esq=noAux1;
		noRaiz.dir=noAux2;
		arrA[arrA.length]=noRaiz;
	}
	return noRaiz;
};

/**
 * Método que devolve os códigos dos caracteres a partir da árvore de códigos
 * @param {noarvore} arvore Árvore contendo a codificação dos caracteres a partir do algoritmo de Huffman
 * @param {Object} obj Objecto do tipo dicionário que irá conter os códigos de cada um dos caracteres presentes na
 * arvore de Huffman
 * @param {Object} str String que será sempre inicializada a vazio, necessária para recorrencia
 */
Compressao.getTreeCodes = function(arvore,obj,str){
	if (arvore != null) {
		Compressao.getTreeCodes(arvore.esq,obj,str+"1");
		Compressao.getTreeCodes(arvore.dir,obj,str+"0");
		if (arvore.val != null) {
			obj[arvore.val] = str;
		}
	}
	return obj;
}

/**
 * Algoritmo de Huffman para compressão de dados
 * @param {Object} Obj Objecto representando a árvore de huffman necessária para a compressão e descompressão dos dados
 */
Compressao.HuffmanEncoding=function(str){
	var arv=Compressao.HuffmanEncodingTree(str);
	var objC=Compressao.getTreeCodes(arv,new Object(),"");
	var strO="";
	var cod="";
	for(var i=0;i<str.length;i++){
		strO+=objC[str[i]];
	}
	return strO;
};

/**
 * @constructor Class que contém um conjunto de funções utilitárias
 */
var Utils=function(){};

Utils.prototype.ghost=function(){};

/**
 * Método que cria um objecto do tipo dicionário contendo os caracteres da string dada como entrada
 * @param {String} str 
 * @return {Object} obj Objecto do tipo dicionário contendo os caracteres presentes na string e a correspondente
 * frequência associada.
 */
Utils.charFreq=function(str){
	var objfr=new Object();
	var comp=str.length;
	for(var i=0;i<comp;i++){
		if (typeof(objfr[str.charAt(i)]) == "undefined") {
			objfr[str[i]] = 1 / comp;
		}
		else {
			objfr[str[i]]+=1/comp;
		}
	}
	return objfr;
};

/**
 * @constructor Construtor do objecto autómato
 * @param {Number} nest Número de estados 
 * @param {Array} alf Array de letras que representam o alfabeto do autómato 
 */
var Automato=function(nest,alf){
	this.estados=Array.map(1,nest);
	this.transicoes=[];
	this.finais=[];
	this.iniciais=[];
	this.alfabeto=alf;
};
/**
 * Método que adiciona uma transição no autómato
 * @param {Number} esta Numero do estado
 * @param {Number} estb Numero do estado
 * @param {Object} letra
 */
Automato.prototype.atrans=function(esta,estb,letra){
	this.transicoes[this.transicoes.length]=[esta,estb,letra];
};

/**
 * Método que devolve o automato minimo a partir de um conjunto de classes de equivalencia
 * @private
 * @param {Array} gclass Array de classes de estados
 */
Automato.prototype._gmin=function(gclass){
	var amin=new Automato(gclass.length,this.alfabeto.clona());
	var ef;
	for(var i=0;i<gclass.length;i++){
		for(var j=0;j<this.alfabeto.length;j++){
			ef=this.trans(gclass[i][0],this.alfabeto[j]);
			console.log(ef);
			if(ef!=-1)
				amin.atrans(i+1,gclass.classpos(ef)+1,this.alfabeto[j]);
		}
	}
	amin.iniciais=this._iniciais(gclass);
	amin.finais=this._finais(gclass);
	return amin;
};

/**
 * Devolve a classe de equivalencia inicial
 * @param {Array} gclass Classes de estados
 */
Automato.prototype._iniciais=function(gclass){
	var out=[];
	for(var i=0;i<gclass.length;i++){
		if(gclass[i].less(this.iniciais).length!=gclass[i].length)
			out[out.length]=i+1;
	}
	return out;
}

/**
 * Devolve as classes de estados finais
 * @param {Array} gclass Classes de estados
 */
Automato.prototype._finais=function(gclass){
	var out=[];
	for(var i=0;i<gclass.length;i++){
		if(gclass[i].less(this.finais).length!=gclass[i].length)
			out[out.length]=i+1;
	}
	return out;
}

/**
 * Calcula o automato mínimo. Assume-se que o autómato é um AFD
 * @return {Automato} Objecto automato mínimo
 */
Automato.prototype.minimo=function(){
	var i=this.iniciais.clona();
	var f=this.finais.clona();
	var nf=this.estados.less(this.finais);
	var e1=Array.produto(nf,nf).concat(Array.produto(this.finais,this.finais));
	var e2=Array.produto(this.estados,this.estados);
	while(e1.length!=e2.length){
		e2=e1.clona();
		for(var i=0;i<e1.length;i++){
			for(var j=0;j<this.alfabeto.length;j++){
				if(this.trans(e1[i][0],this.alfabeto[j])!=this.trans(e1[i][1],this.alfabeto[j]))
					e1.remove(i);
			}
		}
	}
	cl=e1.groupclasses();
	return this._gmin(cl);
};


/**
 * Devolve o estado transitado
 * @param {Number} estado Estado
 * @param {Object} letra Letra do alfabeto
 * @return {Number} numero do estado transitado, -1 caso não haja transição possivel
 */
Automato.prototype.trans=function(estado,letra){
	for(var i=0;i<this.transicoes.length;i++){
		if(this.transicoes[i][0]===estado && this.transicoes[i][2]===letra)
			return this.transicoes[i][1];
	}
	return -1;
}

/***
 * Atribui final ou nao final a um estado
 * @param {Number} esta Estado
 * @param {Boolean} bool true-> final, false-> nao final
 */
Automato.prototype.sfinal=function(esta,bool){
	var b;
	if(typeof(bool)!='undefined')
		b=bool;
	else
		b=true;
	if(b){
		if(this.finais.has(esta))
			return;
		this.finais[this.finais.length]=esta;
	}
	else{
		if(!this.finais.has(esta))
			return;
		this.finais.remove(this.finais.pos(esta));
	}
};

/***
 * Atribui final ou nao inicial a um estado
 * @param {Number} esta Estado
 * @param {Boolean} bool true-> inicial, false-> nao inicial
 */
Automato.prototype.sinicial=function(esta,bool){
	var b;
	if(typeof(bool)!='undefined')
		b=bool;
	else
		b=true;
	if(b){
		if(this.iniciais.has(esta))
			return;
		this.iniciais[this.iniciais.length]=esta;
	}
	else{
		if(!this.iniciais.has(esta))
			return;
		this.iniciais.remove(this.iniciais.pos(esta));
	}
};

/**
 * Método que devolve uma string com a descrição do autómato
 * @return {String} descrição com as transições do autómato
 */
Automato.prototype.toString=function(){
	var out="Alfabeto: "+this.alfabeto.toString()+"\n";
	out+="Estados: "+this.estados.toString()+"\n";
	out+="Iniciais: "+this.iniciais.toString()+"\n";
	out+="Finais: "+this.finais.toString()+"\n";
	out+="Transições: "+this.transicoes.toString()+"\n";
	return out;
};

var noarvore=function(key,val){
	this.esq=null;
	this.dir=null;
	this.key=key;
	this.val=val;
}



var Tree=function(){
	this.raiz=new noarvore(null,null);
};

/**
 * Método que insere 
 * @param {Número} key Chave numérica
 * @param {Object} val Objecto que representa o valor que se encontra nos nós da árvore
 */
Tree.prototype.insertElement=function(key,val){
	//caso a árvore esteja vazia insere imediatamente no lado esquerdo da árvore
	var elaux=this.dir;
	if(this.esq==null){
		this.esq=new noarvore(key,val);
	}
	else{
		//Enquanto não estivermos numa folha da árvore
		while(elaux.dir!=null){
			//Se a chave à direita for maior que a chave inserida então percorremos a árvore pela sua folha esquerda
			if(elaux.key>key){
				elaux=elaux.esq;
			}
			else{
				elaux=elaux.dir;
			}		
		}
	}
}


COOkie.getCookie=function(c_name)
{
if (document.cookie.length>0)
  {
  c_start=document.cookie.indexOf(c_name + "=");
  if (c_start!=-1)
    {
    c_start=c_start + c_name.length+1;
    c_end=document.cookie.indexOf(";",c_start);
    if (c_end==-1) c_end=document.cookie.length;
    return unescape(document.cookie.substring(c_start,c_end));
    }
  }
return "";
};

/**
 * Método que devolve uma string contendo as propriedades deste objecto
 * @return {string} str String contendo informação sobre as propriedades do objecto
 */
Object.prototype.inspect=function(){
	var str="";
	var filho;
	for(filho in this){
		if(typeof(this[filho])=='function')
			str+="Função: "+filho+"\n";
		else
			str+="Variável: "+filho+"-->"+this[filho]+"\n";
	}
	return str;
};

/**
 * Método privado que devolve uma string com a representação JSON do objecto
 * @param {Object} obj Objecto que se pretende exportar para JSON
 * @private
 */
Object._toJSONString=function(obj){
	var str="";
	var e;
	console.log(typeof(obj));
	if(obj==null)
		return "null";
	if(typeof(obj)=='number'){
			str+=obj;
			return str;
	}
	else if(typeof(obj)=='string'){
			str+="'"+obj+"'";
			return str;
	}
	else if (typeof(obj) == 'object') {
		if (typeof(obj.length) == "undefined") {
			str += "{";
			var k = 0;
			for (e in obj) {
				if (typeof(obj[e]) != "function") {
					if (k != 0) {
						str += ",";
					}
					str +='"'+e+'":'+ Object._toJSONString(obj[e]);
					k++;
				}
			}
			str += "}";
		}
		else {
			str += "[";
			for (var i = 0; i < obj.length; i++) {
				if (typeof(obj[i]) != "function") {
					if (i != 0) {
						str += ",";
					}
					str += Object._toJSONString(obj[i]);
				}
			}
			str += "]";
		}
	}
	
	return str;
}

/**
 * Método que devolve uma string representando o objecto
 * @return {String} str string contendo a representação JSON do objecto
 */
Object.prototype.toJSONString=function(){
	return Object._toJSONString(this);
}
/**
 * Método que transforma um objecto do tipo dicionário num array binário
 * @return {Array} arr Array binário contendo os valores do objecto dicionário
 */
Object.prototype.toDicArray=function(){
	var arr=[];
	var i=0;
	for(e in this){
		arr[i]=[];
		arr[i][0]=e;
		arr[i][1]=this[e];
		i++;
	}
	return arr;
};

/**
 * Método que devolve uma string contendo o nome de todos os métodos existentes no objecto
 * @return {string} strm String com a descrição dos métodos
 */
Object.prototype.getMetodos=function(){
	var str="";
	for(var filho in this){
		if(typeof(this[filho])=='function')
			str+="Função: "+filho+"\n";
	}
	return str;
};


/**
 * Método que devolve uma string contendo o nome e valor de todas as propriedades existentes
 * no objecto
 * @return {string} strp String com a descrição dos valores do objecto
 */
Object.prototype.getPropriedades=function(){
	var str="";
	for(var filho in this){
		if(typeof(this[filho])!='function')
			str="Variavel: "+this[filho];
	}
	return str;
};

Object.min=function(strA,strB){
	return strB.length>strA.length?strA:strB;
};

Object.max=function(strA,strB){
	return strA.length>=strB.length?strA:strB;
};

/**
 * Devolve um array com os caracteres que constituem a string
 * @return {Array}
 */
String.prototype.alphabet=function(){
	var out=[];
	var ext={};
	for(var i=0;i<this.length;i++){
		if(!ext[this.charAt(i)]){
			ext[this.charAt(i)]=true;
			out[out.length]=this.charAt(i);
		}
	}
	return out;
};

/**
 * Método que devolve a intersecção entre duas strings
 * @param {String} strA String A
 * @param {String} strB String B
 * @return {String} out String intersecção
 */
String.and=function(strA,strB){
	var min=String.min(strA,strB);
	var max=String.max(strA,strB);
	var out="";
	for(var i=0;i<min.length;i++){
		if(min.charAt(i)==max.charAt(i))
			out+=max.charAt(i);
	}
	return out;
};