//Functions for doing search.
// Coded by Atom (http://www.atomthaimmortal.com) for The Evolutionary Informatics Lab.

//***************** Constants ********************************
var SearchTypes = new Array("Ev Search", "Rachet Search", "Hamming Search", "Undirected Search: Random Input", "Undirected Search: Random Output");
var NeutFitnessModes = new Array('Partially-Neutral: Simple Sum Distance','Partially-Neutral: Anagram','Partially-Neutral: CRC32','Simple Sum','CRC32','Wave Interference', 'Custom Fitness Function');

//*************** Search Object ********************
function SearchObject(target, allowedChars) {
	//Const values
	this.HistoryLimit = 500;

	//Vars
	this.TargetPhrase = target;
	this.AllowedCharAlpha = allowedChars;
	this.PartHistory = new Array();
	this.ProxHistory = new Array();
	this.NeutHistory = new Array();
	this.DetHistory = new Array();
	this.RandomHistory = new Array();
	this.QueryCountPart = 0;
	this.QueryCountDet = 0;
	this.QueryCountRandom = 0;
	this.QueryCountProx = 0;
	this.QueryCountNeut = 0;
	this.DetSearchSuffledAlphabet = null;
	this.DetSearchIndex = null;
	this.ProxChildrenPerGeneration = 50;
	this.ProxMutationRate = 1;
	this.ProxFixedSingleMutation = false;
	this.NeutChildrenPerGeneration = 50;
	this.NeutMutationRate = 2;
	this.DisabledAlgorithms = new Array();
	this.CustomFitnessFunction = "function diff(str,trg) {\n\tvar err = 0;\n\tfor (var i = 0; i < str.length; i++){\n" +
								"\t\terr += (str.charAt(i) != trg.charAt(i));\n\t}\n\treturn err;\n}\n\naError = diff(a, target);\nbError = diff(b, target);";
	this.CustomFitnessMessage = "";
	this.CustomFitnessMessageDetail = "";

	//Utility Methods
	this.shuffle = function(arr, convertToString) {
		convertToString = convertToString || false;
		var ind, tmp;

		if (arr.length > 0 && typeof arr == "string") arr = arr.split('');

		for (i = arr.length; i >= 0; --i) {
			ind = parseInt(Math.random() * i);
			tmp = arr[i];
			arr[i] = arr[ind];
			arr[ind] = tmp;
		}

		return (convertToString ? arr.join('') : arr);
	}

	this.stringSum = function(str) {
		sum = 0;
		for (var i = str.length - 1; i >= 0; i--) {
			sum += str.charCodeAt(i);
		}
		return sum;
	}

	this.differentLetters = function(str, target) {
		var difference = 0;
		var strMatches = 0;
		var targetMatches = 0;
		var uniqueLetters = '';

		for (var i = 0; i < target.length; i++) {
			if (uniqueLetters.indexOf(target.charAt(i)) == -1) {
				uniqueLetters += target.charAt(i);
				strMatches = str.split(target.charAt(i)).length - 1;
				targetMatches = target.split(target.charAt(i)).length - 1;
				difference += Math.abs(targetMatches - strMatches);
			}
		}

		return difference;
	}

	
	//Methods
	this.GetMedianNumberOfQueries = function(phrase, allowedChars) {
		var L = phrase.length;
		var N = allowedChars.length;
		var arrMeds = new Array();
		var p = 1 - (Math.pow(2, (-1 / L)));
		
		var Num = Math.log(p);
		var Den = Math.log((1 - (1 / N)));
		var RandDen = (Math.pow(N, L) <= 100000) ? Math.log((1 - (Math.pow(N, -L))))  : -(Math.pow(N, -L)); 

		arrMeds['Part'] = Math.round((Num / Den));
		arrMeds['Prox'] = 0.0;
		arrMeds['Det'] = Math.round((N * (Math.pow(2, (-1 / L)))));
		var rand = new Number((Math.round((-(Math.log(2)) / RandDen))));
		arrMeds['Random'] = rand.toPrecision(3);

		return arrMeds;
	}

	this.GetFormattedCurrentStringOutput = function(current) {
		var output = '';
		for (var i = 0; i < this.TargetPhrase.length; i++) {
			output += (current.charAt(i) == this.TargetPhrase.charAt(i) ? '<span class="Match">' + current.charAt(i) + '</span>' : current.charAt(i));
		}

		return output;
	}

	this.GetHistoryHTML = function(arrHistory) {
		var arrOutput = new Array();
		for (var j = 0; j < arrHistory.length; j++) {
			arrOutput[j] = (j + 1) + ". " + this.GetFormattedCurrentStringOutput(arrHistory[j]);
		}

		return arrOutput.join("<br />");
	}

	this.GetRandomLetter = function(allowedChars) {
		var r = Math.random();
		var index = Math.floor(r * allowedChars.length);
		return allowedChars.charAt(index);	
	}

	this.GetRandomString = function(stringLength, allowedChars) {
		var output = '';
		for (p = 0; p < stringLength; p++) {
			output += this.GetRandomLetter(allowedChars);
		}
		return output;
	}

	this.GetMutatedString = function(currentString, allowedChars, mutationRate, isFixed) {
		if (currentString == '') return '';

		var arrCS = currentString.split('');
		var shouldMutateLetter;
		var randLetter;
		var index;

		//Either change exactly one letter (if fixed), or change n letters probabilistically
		//depending on the mutation rate.
		if (isFixed) {
			//Single mutation
			randLetter = this.GetRandomLetter(allowedChars);
			index = Math.floor(Math.random() * arrCS.length);
			arrCS[index] = randLetter;
		} else {
			//Probabilistic number of  mutations
			for (var i = 0; i < currentString.length; i++) {
				shouldMutateLetter = (Math.random() * 100.00) <= (mutationRate * 1);
				arrCS[i] = shouldMutateLetter ? this.GetRandomLetter(allowedChars) : arrCS[i];
			}
		}

		return arrCS.join('');
	}

	this.GenerateNextPartStep = function(currentString, allowedChars, target) {
		currentString = ((!currentString || currentString.length != target.length) ? this.GetRandomString(target.length, allowedChars) : currentString);

		var randLetter;
		var arrCS = currentString.split('');

		//Go through getting new rand for every position that does not currently match
		for (var i = 0; i < target.length; i++) {
			randLetter = this.GetRandomLetter(allowedChars);
			if (currentString.charAt(i) != target.charAt(i)) arrCS[i] = randLetter;
		}

		return arrCS.join('');
	}

	this.GenerateNextProxStep = function(currentString, allowedChars, target) {
		currentString = ((!currentString || currentString.length != target.length) ? this.GetRandomString(target.length, allowedChars) : currentString);

		//Generate population of N randomized strings
		var currentBest = '';
		var currentCompetitor = currentString;
		for (var i = 0; i < this.ProxChildrenPerGeneration; i++) {
			currentCompetitor = this.GetMutatedString(currentString, allowedChars, this.ProxMutationRate, this.ProxFixedSingleMutation);
			currentBest = this.ProxGetClosestString(currentCompetitor, currentBest, target);
		}

		return currentBest;
	}

	this.ProxGetClosestString = function(a, b, target) {
		var aError = 0;
		var bError = 0;
		for (var i = 0; i < target.length; i++) {
			aError += (a.charAt(i) != target.charAt(i));
			bError += (b.charAt(i) != target.charAt(i));
		}
		
		return (aError <= bError ? a : b);
	}

	this.GenerateNextNeutStep = function(currentString, allowedChars, target, alg) {
		currentString = ((!currentString || currentString.length != target.length) ? this.GetRandomString(target.length, allowedChars) : currentString);

		//Generate population of N randomized strings
		var currentBest = null;
		var currentCompetitor = currentString;

		for (var i = 0; i < this.NeutChildrenPerGeneration; i++) {
			currentCompetitor = this.GetMutatedString(currentString, allowedChars, this.NeutMutationRate, false);
			currentBest = currentBest == null ? currentCompetitor : this.NeutGetClosestString(currentCompetitor, currentBest, target, alg);
		}

		return currentBest;
	}

	this.NeutGetClosestString = function(a, b, target, mode) {
		var aError = 0;
		var bError = 0;

		switch (NeutFitnessModes[mode]) {
			case 'Simple Sum':
				aError = Math.abs(Math.sin(this.stringSum(a)) * target.length);
				bError = Math.abs(Math.sin(this.stringSum(b)) * target.length);
				break;
			case 'CRC32':
				aError = Math.abs((Math.sin(Math.round(crc32(a))) * target.length));
				bError = Math.abs((Math.sin(Math.round(crc32(b))) * target.length));
				break;
			case 'Wave Interference':
				var sumA = this.stringSum(a);
				var sumB = this.stringSum(b);
				var sumAB = sumA + sumB;
				aError = (Math.sin(sumA) + Math.sin((sumAB / 7) + 2)) * target.length;
				bError = (Math.sin(sumB) + Math.sin(((sumA * sumB) / sumAB) + 2)) * target.length;
				break;
			case 'Custom Fitness Function': 
				try {
					eval(this.CustomFitnessFunction);
					this.CustomFitnessMessage = "";
					this.CustomFitnessMessageDetail = "";
				} catch(e) {
					this.CustomFitnessMessageDetail = e.name + ": " + e.message;
					this.CustomFitnessMessage = "Error: Invalid Javascript In Custom Function";
				}
				break;
			case 'Partially-Neutral: CRC32': 
				var crcTarget = Math.round(crc32(target));
				aError = Math.abs(crcTarget - Math.round(crc32(a)));
				bError = Math.abs(sumTarget - Math.round(crc32(b)));
				break;
			case 'Partially-Neutral: Simple Sum Distance':
				var sumTarget = this.stringSum(target);
				aError = Math.abs(sumTarget - this.stringSum(a));
				bError = Math.abs(sumTarget - this.stringSum(b));
				break;
			case 'Partially-Neutral: Anagram':
			default:
				aError = this.differentLetters(a, target);
				bError = this.differentLetters(b, target);
				break;
		}

		return (aError <= bError ? a : b);
	}

	this.GetDetSearchShuffledAlphabet = function(allowedChars) {
		return this.shuffle(allowedChars, true);
	}

	this.GenerateNextDetStep = function(currentString, shuffledAlpha, index, target) {
		currentString = ((!currentString || currentString.length != target.length) ? this.GetRandomString(target.length, allowedChars) : currentString);

		var nextLetter = shuffledAlpha.charAt(index);
		var arrCS = currentString.split('');

		for (var i = 0; i < target.length; i++) {
			if (target.charAt(i) == nextLetter) arrCS[i] = nextLetter;
		}

		//Update index
		this.DetSearchIndex += 1;

		return arrCS.join('');
	}

	this.GenerateNextRandomStep = function(currentString, allowedChars) {
		return this.GetRandomString(this.TargetPhrase.length, allowedChars);
	}

	this.ResetSearchArrays = function() {
		this.PartHistory = new Array();
		this.ProxHistory = new Array();
		this.NeutHistory = new Array();
		this.DetHistory = new Array();
		this.RandomHistory = new Array(); 
		this.DetSearchSuffledAlphabet = null;
		this.DetSearchIndex = null;
		this.QueryCountPart = 0;
		this.QueryCountDet = 0;
		this.QueryCountRandom = 0;
		this.QueryCountProx = 0;
		this.QueryCountNeut = 0;
	}

	this.StepForward = function(allowedChars, algNeut) {
		this.DetSearchSuffledAlphabet = this.DetSearchSuffledAlphabet || this.GetDetSearchShuffledAlphabet(allowedChars);
		this.DetSearchIndex = this.DetSearchIndex || 0;
		var arrReturn = new Array();

		//Take step forward for each type of algorithm
		if (!this.DisabledAlgorithms['Part'] && (this.PartHistory.length == 0 || this.PartHistory[this.PartHistory.length - 1] != this.TargetPhrase)) {
			var nextPartStep = this.GenerateNextPartStep((this.PartHistory.length == 0 ? "" : this.PartHistory[this.PartHistory.length - 1]), allowedChars, this.TargetPhrase);
			this.PartHistory.push(nextPartStep);
			this.QueryCountPart++;
			arrReturn['PartUpdated'] = true;
			arrReturn['Part'] = this.GetFormattedCurrentStringOutput(this.PartHistory[this.PartHistory.length - 1]);
		}

		if (!this.DisabledAlgorithms['Prox'] && (this.ProxHistory.length == 0 || this.ProxHistory[this.ProxHistory.length - 1] != this.TargetPhrase)) {
			var nextProxStep = this.GenerateNextProxStep((this.ProxHistory.length == 0 ? "" : this.ProxHistory[this.ProxHistory.length - 1]), allowedChars, this.TargetPhrase);
			this.ProxHistory.push(nextProxStep);
			this.QueryCountProx += this.ProxChildrenPerGeneration;
			arrReturn['ProxUpdated'] = true;
			arrReturn['Prox'] = this.GetFormattedCurrentStringOutput(this.ProxHistory[this.ProxHistory.length - 1]);
		}

		if (!this.DisabledAlgorithms['Neut'] && (this.NeutHistory.length == 0 || this.NeutHistory[this.NeutHistory.length - 1] != this.TargetPhrase)) {
			var nextNeutStep = this.GenerateNextNeutStep((this.NeutHistory.length == 0 ? "" : this.NeutHistory[this.NeutHistory.length - 1]), allowedChars, this.TargetPhrase, algNeut);
			this.NeutHistory.push(nextNeutStep);
			this.QueryCountNeut += this.NeutChildrenPerGeneration;
			arrReturn['NeutUpdated'] = true;
			arrReturn['Neut'] = this.GetFormattedCurrentStringOutput(this.NeutHistory[this.NeutHistory.length - 1]);
		}

		if (!this.DisabledAlgorithms['Det'] && (this.DetHistory.length == 0 || this.DetHistory[this.DetHistory.length - 1] != this.TargetPhrase)) {
			this.DetHistory.push(this.GenerateNextDetStep((this.DetHistory.length == 0 ? "" : this.DetHistory[this.DetHistory.length - 1]), this.DetSearchSuffledAlphabet, this.DetSearchIndex, this.TargetPhrase));
			this.QueryCountDet++;
			arrReturn['DetUpdated'] = true;
			arrReturn['Det'] = this.GetFormattedCurrentStringOutput(this.DetHistory[this.DetHistory.length - 1]);
		}

		if (!this.DisabledAlgorithms['Random'] && (this.RandomHistory.length == 0 || this.RandomHistory[this.RandomHistory.length - 1] != this.TargetPhrase)) {
			this.RandomHistory.push(this.GenerateNextRandomStep((this.RandomHistory.length == 0 ? "" : this.RandomHistory[this.RandomHistory.length - 1]), allowedChars));
			this.QueryCountRandom++;
			arrReturn['RandomUpdated'] = true;
			arrReturn['Random'] = this.GetFormattedCurrentStringOutput(this.RandomHistory[this.RandomHistory.length - 1]);
		}

		//Keep only the most recent N history items. If goes over, delete the first in queue.
		if (this.PartHistory.length > this.HistoryLimit) this.PartHistory.shift();
		if (this.ProxHistory.length > this.HistoryLimit) this.ProxHistory.shift();
		if (this.NeutHistory.length > this.HistoryLimit) this.NeutHistory.shift();
		if (this.DetHistory.length > this.HistoryLimit) this.DetHistory.shift();
		if (this.RandomHistory.length > this.HistoryLimit) this.RandomHistory.shift();

		return arrReturn;
	}

	//Load
	this.MedianNumberOfQueries = this.GetMedianNumberOfQueries(target, allowedChars);
}


//*************** Multi Run Objects *****************
function RunResult(obj, iteration, alphaTypes) {
	//New
	this.Target = obj.TargetPhrase;
	this.SearchType = alphaTypes[obj.AllowedCharAlpha];
	this.Iteration = iteration;
	this.Results = new Array();
	this.Results['Part'] = (obj.DisabledAlgorithms['Part'] ? 0 : obj.QueryCountPart);
	this.Results['Prox'] = (obj.DisabledAlgorithms['Prox'] ? 0 : obj.QueryCountProx);
	this.Results['Neut'] = (obj.DisabledAlgorithms['Neut'] ? 0 : obj.QueryCountNeut);
	this.Results['Det'] = (obj.DisabledAlgorithms['Det'] ? 0 : obj.QueryCountDet);
	this.Results['Random'] = (obj.DisabledAlgorithms['Random'] ? 0 : obj.QueryCountRandom);

	//Methods
	this.GetRunHTML = function(includeHeaderRow) {
		var output = "";

		if (includeHeaderRow) {
			output += "<tr class=\"Headers\">\n" +
						"\t<th>&nbsp;</th>\n" +
						"\t<th>Partitioned</th>\n" +
						"\t<th>Deterministic</th>\n" +
						"\t<th>Random</th>\n" +
						"\t<th>Prox Reward</th>\n" +
						"\t<th>Prox Neutral</th>\n" +
					"</tr>\n"; 
		}

		output += "<tr>\n" +
					"\t<td>" + (this.Iteration + 1) + ")</td>\n" +
					"\t<td>" + (this.Results['Part'] == 0 ? '' : this.Results['Part']) + "\t</td>\n" +
					"\t<td>" + (this.Results['Det'] == 0 ? '' : this.Results['Det']) + "\t</td>\n" +
					"\t<td>" + (this.Results['Random'] == 0 ? '' : this.Results['Random']) + "\t</td>\n" +
					"\t<td>" + (this.Results['Prox'] == 0 ? '' : this.Results['Prox']) + "\t</td>\n" +
					"\t<td>" + (this.Results['Neut'] == 0 ? '' : this.Results['Neut'])+ "\t</td>\n" +
				"</tr>\n"; 
		
		return output;
	}
	
	this.GetRunCSV = function(includeHeaderRow) {
		var output = "";

		if (includeHeaderRow) {
			output += "Partitioned,Deterministic,Random,Prox Reward,Prox Neutral\n"; 
		}

		output += (this.Results['Part'] == 0 ? '' : this.Results['Part']) +
				"," + (this.Results['Det'] == 0 ? '' : this.Results['Det']) + 
				"," + (this.Results['Random'] == 0 ? '' : this.Results['Random']) + 
				"," + (this.Results['Prox'] == 0 ? '' : this.Results['Prox']) + 
				"," + (this.Results['Neut'] == 0 ? '' : this.Results['Neut'])+ "\n"; 
		
		return output;
	}

}

function MultiRunObject() {
	//Vars
	this.CurrentlyOn = false;
	this.Runs = new Array();
	this.Alphas = new Array();
	this.Alphas[EnglishCharacters] = 'English Phrase';
	this.Alphas[BinaryCharacters] = 'Binary';
	this.Alphas[NucleotideCharacters] = 'Nucleotides (ACGT)';

	//Methods
	this.SaveRunResults = function(obj) {
		this.Runs.push((new RunResult(obj, this.Runs.length, this.Alphas)));
	}

	this.GetHistoryHTML = function() {
		var output = "<table id=\"MultiRunResults\" cellspacing=\"0\">\n";
		var currentTarget = null;
		var includeHeader = false;

		for (var i = 0; i < this.Runs.length; i++) {
			includeHeader = false;

			if (currentTarget != this.Runs[i].Target) {
				output += "\t<tr class=\"Target\"><th colspan=\"6\">Target: <span>" + this.Runs[i].Target + "</span></th></tr>\n";
				output += "\t<tr class=\"SearchType\"><th colspan=\"6\">Search Type: <span>" + this.Runs[i].SearchType + "</span></th></tr>\n";
				currentTarget = this.Runs[i].Target;
				includeHeader = true;
			}
			
			output += "\t" + this.Runs[i].GetRunHTML(includeHeader) + "\n";
		}

		return output + "\n</table>" ;
	}

	this.GetHistoryCSV = function() {
		var output = "<textarea style=\"height:98%; width:99%\" rows=\"31\" cols=\"49\">";
		var currentTarget = null;
		var includeHeader = false;

		for (var i = 0; i < this.Runs.length; i++) {
			includeHeader = false;

			if (currentTarget != this.Runs[i].Target) {
				output += "\nTarget: " + this.Runs[i].Target + "\n";
				output += "Search Type: " + this.Runs[i].SearchType + "\n";
				currentTarget = this.Runs[i].Target;
				includeHeader = true;
			}
			
			output += this.Runs[i].GetRunCSV(includeHeader);
		}

		return output += "</textarea>";
	}
}
//**************************************************/