/* globals chrome: false */
/* globals __dirname: false */
/* globals require: false */
/* globals Buffer: false */
/* globals module: false */

/**
 * Typo is a JavaScript implementation of a spellchecker using hunspell-style 
 * dictionaries.
 */

var Typo;

(function () {
"use strict";

/**
 * Typo constructor.
 *
 * @param {String} [dictionary] The locale code of the dictionary being used. e.g.,
 *                              "en_US". This is only used to auto-load dictionaries.
 * @param {String} [affData]    The data from the dictionary's .aff file. If omitted
 *                              and Typo.js is being used in a Chrome extension, the .aff
 *                              file will be loaded automatically from
 *                              lib/typo/dictionaries/[dictionary]/[dictionary].aff
 *                              In other environments, it will be loaded from
 *                              [settings.dictionaryPath]/dictionaries/[dictionary]/[dictionary].aff
 * @param {String} [wordsData]  The data from the dictionary's .dic file. If omitted
 *                              and Typo.js is being used in a Chrome extension, the .dic
 *                              file will be loaded automatically from
 *                              lib/typo/dictionaries/[dictionary]/[dictionary].dic
 *                              In other environments, it will be loaded from
 *                              [settings.dictionaryPath]/dictionaries/[dictionary]/[dictionary].dic
 * @param {Object} [settings]   Constructor settings. Available properties are:
 *                              {String} [dictionaryPath]: path to load dictionary from in non-chrome
 *                              environment.
 *                              {Object} [flags]: flag information.
 *                              {Boolean} [asyncLoad]: If true, affData and wordsData will be loaded
 *                              asynchronously.
 *                              {Function} [loadedCallback]: Called when both affData and wordsData
 *                              have been loaded. Only used if asyncLoad is set to true. The parameter
 *                              is the instantiated Typo object.
 *
 * @returns {Typo} A Typo object.
 */

Typo = function (dictionary, affData, wordsData, settings) {
	settings = settings || {};

	this.dictionary = null;
	
	this.rules = {};
	this.dictionaryTable = {};
	
	this.suffixRules = {};
	this.prefixRules = {};
	
	this.compoundRules = [];
	this.compoundRuleCodes = {};
	
	this.replacementTable = [];
	
	this.flags = settings.flags || {}; 
	
	this.memoized = {};

	this.loaded = false;
	
	var self = this;
	
	var path;
	
	// Loop-control variables.
	var i, j, _len, _jlen;
	
	if (dictionary) {
		self.dictionary = dictionary;
		
		// If the data is preloaded, just setup the Typo object.
		if (affData && wordsData) {
			setup();
		}
		// Loading data for Chrome extentions.
		else if (typeof window !== 'undefined' && 'chrome' in window && 'extension' in window.chrome && 'getURL' in window.chrome.extension) {
			if (settings.dictionaryPath) {
				path = settings.dictionaryPath;
			}
			else {
				path = "typo/dictionaries";
			}
			
			if (!affData) readDataFile(chrome.extension.getURL(path + "/" + dictionary + "/" + dictionary + ".aff"), setAffData);
			if (!wordsData) readDataFile(chrome.extension.getURL(path + "/" + dictionary + "/" + dictionary + ".dic"), setWordsData);
		}
		else {
			if (settings.dictionaryPath) {
				path = settings.dictionaryPath;
			}
			else if (typeof __dirname !== 'undefined') {
				path = __dirname + '/dictionaries';
			}
			else {
				path = './dictionaries';
			}
			
			if (!affData) readDataFile(path + "/" + dictionary + "/" + dictionary + ".aff", setAffData);
			if (!wordsData) readDataFile(path + "/" + dictionary + "/" + dictionary + ".dic", setWordsData);
		}
	}
	
	function readDataFile(url, setFunc) {
		var response = self._readFile(url, null, settings.asyncLoad);
		
		if (settings.asyncLoad) {
			response.then(function(data) {
				setFunc(data);
			});
		}
		else {
			setFunc(response);
		}
	}

	function setAffData(data) {
		affData = data;

		if (wordsData) {
			setup();
		}
	}

	function setWordsData(data) {
		wordsData = data;

		if (affData) {
			setup();
		}
	}

	function setup() {
		self.rules = self._parseAFF(affData);
		
		// Save the rule codes that are used in compound rules.
		self.compoundRuleCodes = {};
		
		for (i = 0, _len = self.compoundRules.length; i < _len; i++) {
			var rule = self.compoundRules[i];
			
			for (j = 0, _jlen = rule.length; j < _jlen; j++) {
				self.compoundRuleCodes[rule[j]] = [];
			}
		}
		
		// If we add this ONLYINCOMPOUND flag to self.compoundRuleCodes, then _parseDIC
		// will do the work of saving the list of words that are compound-only.
		if ("ONLYINCOMPOUND" in self.flags) {
			self.compoundRuleCodes[self.flags.ONLYINCOMPOUND] = [];
		}
		
		self.dictionaryTable = self._parseDIC(wordsData);
		
		// Get rid of any codes from the compound rule codes that are never used 
		// (or that were special regex characters).  Not especially necessary... 
		for (i in self.compoundRuleCodes) {
			if (self.compoundRuleCodes[i].length === 0) {
				delete self.compoundRuleCodes[i];
			}
		}
		
		// Build the full regular expressions for each compound rule.
		// I have a feeling (but no confirmation yet) that this method of 
		// testing for compound words is probably slow.
		for (i = 0, _len = self.compoundRules.length; i < _len; i++) {
			var ruleText = self.compoundRules[i];
			
			var expressionText = "";
			
			for (j = 0, _jlen = ruleText.length; j < _jlen; j++) {
				var character = ruleText[j];
				
				if (character in self.compoundRuleCodes) {
					expressionText += "(" + self.compoundRuleCodes[character].join("|") + ")";
				}
				else {
					expressionText += character;
				}
			}
			
			self.compoundRules[i] = new RegExp(expressionText, "i");
		}
		
		self.loaded = true;
		
		if (settings.asyncLoad && settings.loadedCallback) {
			settings.loadedCallback(self);
		}
	}
	
	return this;
};

Typo.prototype = {
	/**
	 * Loads a Typo instance from a hash of all of the Typo properties.
	 *
	 * @param object obj A hash of Typo properties, probably gotten from a JSON.parse(JSON.stringify(typo_instance)).
	 */
	
	load : function (obj) {
		for (var i in obj) {
			if (obj.hasOwnProperty(i)) {
				this[i] = obj[i];
			}
		}
		
		return this;
	},
	
	/**
	 * Read the contents of a file.
	 * 
	 * @param {String} path The path (relative) to the file.
	 * @param {String} [charset="ISO8859-1"] The expected charset of the file
	 * @param {Boolean} async If true, the file will be read asynchronously. For node.js this does nothing, all
	 *        files are read synchronously.
	 * @returns {String} The file data if async is false, otherwise a promise object. If running node.js, the data is
	 *          always returned.
	 */
	
	_readFile : function (path, charset, async) {
		charset = charset || "utf8";
		
		if (typeof XMLHttpRequest !== 'undefined') {
			var promise;
			var req = new XMLHttpRequest();
			req.open("GET", path, async);
			
			if (async) {
				promise = new Promise(function(resolve, reject) {
					req.onload = function() {
						if (req.status === 200) {
							resolve(req.responseText);
						}
						else {
							reject(req.statusText);
						}
					};
					
					req.onerror = function() {
						reject(req.statusText);
					}
				});
			}
		
			if (req.overrideMimeType)
				req.overrideMimeType("text/plain; charset=" + charset);
		
			req.send(null);
			
			return async ? promise : req.responseText;
		}
		else if (typeof require !== 'undefined') {
			// Node.js
			var fs = require("fs");
			
			try {
				if (fs.existsSync(path)) {
					return fs.readFileSync(path, charset);
				}
				else {
					console.log("Path " + path + " does not exist.");
				}
			} catch (e) {
				console.log(e);
				return '';
			}
		}
	},
	
	/**
	 * Parse the rules out from a .aff file.
	 *
	 * @param {String} data The contents of the affix file.
	 * @returns object The rules from the file.
	 */
	
	_parseAFF : function (data) {
		var rules = {};
		
		var line, subline, numEntries, lineParts;
		var i, j, _len, _jlen;
		
		var lines = data.split(/\r?\n/);
		
		for (i = 0, _len = lines.length; i < _len; i++) {
			// Remove comment lines
			line = this._removeAffixComments(lines[i]);
			line = line.trim();
			
			if ( ! line ) {
				continue;
			}
			
			var definitionParts = line.split(/\s+/);
			
			var ruleType = definitionParts[0];
			
			if (ruleType == "PFX" || ruleType == "SFX") {
				var ruleCode = definitionParts[1];
				var combineable = definitionParts[2];
				numEntries = parseInt(definitionParts[3], 10);
				
				var entries = [];
				
				for (j = i + 1, _jlen = i + 1 + numEntries; j < _jlen; j++) {
					subline = lines[j];
					
					lineParts = subline.split(/\s+/);
					var charactersToRemove = lineParts[2];
					
					var additionParts = lineParts[3].split("/");
					
					var charactersToAdd = additionParts[0];
					if (charactersToAdd === "0") charactersToAdd = "";
					
					var continuationClasses = this.parseRuleCodes(additionParts[1]);
					
					var regexToMatch = lineParts[4];
					
					var entry = {};
					entry.add = charactersToAdd;
					entry.removeStr = charactersToRemove === "0" ? "" : charactersToRemove;
					
					if (continuationClasses.length > 0) entry.continuationClasses = continuationClasses;
					
					if (regexToMatch !== ".") {
						if (ruleType === "SFX") {
							entry.match = new RegExp(regexToMatch + "$");
						}
						else {
							entry.match = new RegExp("^" + regexToMatch);
						}
					}
					
					if (charactersToRemove != "0") {
						if (ruleType === "SFX") {
							entry.remove = new RegExp(charactersToRemove  + "$");
						}
						else {
							entry.remove = charactersToRemove;
						}
					}
					
					entries.push(entry);
				}
				
				rules[ruleCode] = { "type" : ruleType, "combineable" : (combineable == "Y"), "entries" : entries };
				
				i += numEntries;
			}
			else if (ruleType === "COMPOUNDRULE") {
				numEntries = parseInt(definitionParts[1], 10);
				
				for (j = i + 1, _jlen = i + 1 + numEntries; j < _jlen; j++) {
					line = lines[j];
					
					lineParts = line.split(/\s+/);
					this.compoundRules.push(lineParts[1]);
				}
				
				i += numEntries;
			}
			else if (ruleType === "REP") {
				lineParts = line.split(/\s+/);
				
				if (lineParts.length === 3) {
					this.replacementTable.push([ lineParts[1], lineParts[2] ]);
				}
			}
			else {
				// ONLYINCOMPOUND
				// COMPOUNDMIN
				// FLAG
				// KEEPCASE
				// NEEDAFFIX
				
				this.flags[ruleType] = definitionParts[1];
			}
		}
		
		// Build prefix/suffix rules index (double-indexed by add and removeStr)
		this.suffixRules = {};
		this.prefixRules = {};
		for (var code in rules) {
			var rule = rules[code];
			var entries = rule.entries;
			for (var idx = 0; idx < entries.length; idx++) {
				var entry = entries[idx];
				var add = entry.add || "";
				var removeStr = entry.removeStr || "";
				var item = { code: code, rule: rule, entry: entry };
				
				if (rule.type === "SFX") {
					if (!this.suffixRules[add]) this.suffixRules[add] = {};
					if (!this.suffixRules[add][removeStr]) this.suffixRules[add][removeStr] = [];
					this.suffixRules[add][removeStr].push(item);
				} else if (rule.type === "PFX") {
					if (!this.prefixRules[add]) this.prefixRules[add] = {};
					if (!this.prefixRules[add][removeStr]) this.prefixRules[add][removeStr] = [];
					this.prefixRules[add][removeStr].push(item);
				}
			}
		}
		
		return rules;
	},
	
	/**
	 * Removes comments.
	 *
	 * @param {String} data A line from an affix file.
	 * @return {String} The cleaned-up line.
	 */
	
	_removeAffixComments : function (line) {
		// This used to remove any string starting with '#' up to the end of the line,
		// but some COMPOUNDRULE definitions include '#' as part of the rule.
		// So, only remove lines that begin with a comment, optionally preceded by whitespace.
		if ( line.match( /^\s*#/, "" ) ) {
			return '';
		}
		
		return line;
	},
	
	/**
	 * Parses the words out from the .dic file.
	 *
	 * @param {String} data The data from the dictionary file.
	 * @returns object The lookup table containing all of the words and
	 *                 word forms from the dictionary.
	 */
	
	_parseDIC : function (data) {
		data = this._removeDicComments(data);
		
		var lines = data.split(/\r?\n/);
		var dictionaryTable = {};
		
		for (var i = 1, _len = lines.length; i < _len; i++) {
			var line = lines[i];
			if (!line) continue;
			
			var parts = line.split("/", 2);
			var word = parts[0];
			
			if (parts.length > 1) {
				var ruleCodesArray = this.parseRuleCodes(parts[1]);
				if (!dictionaryTable.hasOwnProperty(word)) {
					dictionaryTable[word] = [];
				}
				dictionaryTable[word].push(ruleCodesArray);
				
				for (var j = 0; j < ruleCodesArray.length; j++) {
					var code = ruleCodesArray[j];
					if (code in this.compoundRuleCodes) {
						this.compoundRuleCodes[code].push(word);
					}
				}
			} else {
				var trimmedWord = word.trim();
				if (!dictionaryTable.hasOwnProperty(trimmedWord)) {
					dictionaryTable[trimmedWord] = [];
				}
				dictionaryTable[trimmedWord].push([]);
			}
		}
		
		return dictionaryTable;
	},
	
	
	/**
	 * Removes comment lines and then cleans up blank lines and trailing whitespace.
	 *
	 * @param {String} data The data from a .dic file.
	 * @return {String} The cleaned-up data.
	 */
	
	_removeDicComments : function (data) {
		// I can't find any official documentation on it, but at least the de_DE
		// dictionary uses tab-indented lines as comments.
		
		// Remove comments
		data = data.replace(/^\t.*$/mg, "");
		
		return data;
	},
	
	parseRuleCodes : function (textCodes) {
		if (!textCodes) {
			return [];
		}
		else if (!("FLAG" in this.flags)) {
			// The flag symbols are single characters
			return textCodes.split("");
		}
		else if (this.flags.FLAG === "long") {
			// The flag symbols are two characters long.
			var flags = [];
			
			for (var i = 0, _len = textCodes.length; i < _len; i += 2) {
				flags.push(textCodes.substr(i, 2));
			}
			
			return flags;
		}
		else if (this.flags.FLAG === "num") {
			// The flag symbols are a CSV list of numbers.
			return textCodes.split(",");
		}
		else if (this.flags.FLAG === "UTF-8") {
			// The flags are single UTF-8 characters.
			// @see https://github.com/cfinke/Typo.js/issues/57
			return Array.from(textCodes);
		}
		else {
			// It's possible that this fallback case will not work for all FLAG values,
			// but I think it's more likely to work than not returning anything at all.
			return textCodes.split("");
		}
	},
	
	/**
	 * Applies an affix rule to a word.
	 *
	 * @param {String} word The base word.
	 * @param {Object} rule The affix rule.
	 * @returns {String[]} The new words generated by the rule.
	 */
	
	_applyRule : function (word, rule) {
		var entries = rule.entries;
		var newWords = [];
		
		for (var i = 0, _len = entries.length; i < _len; i++) {
			var entry = entries[i];
			
			if (!entry.match || word.match(entry.match)) {
				var newWord = word;
				
				if (entry.remove) {
					newWord = newWord.replace(entry.remove, "");
				}
				
				if (rule.type === "SFX") {
					newWord = newWord + entry.add;
				}
				else {
					newWord = entry.add + newWord;
				}
				
				newWords.push(newWord);
				
				if ("continuationClasses" in entry) {
					for (var j = 0, _jlen = entry.continuationClasses.length; j < _jlen; j++) {
						var continuationRule = this.rules[entry.continuationClasses[j]];
						
						if (continuationRule) {
							newWords = newWords.concat(this._applyRule(newWord, continuationRule));
						}
						/*
						else {
							// This shouldn't happen, but it does, at least in the de_DE dictionary.
							// I think the author mistakenly supplied lower-case rule codes instead 
							// of upper-case.
						}
						*/
					}
				}
			}
		}
		
		return newWords;
	},
	
	/**
	 * Checks whether a word or a capitalization variant exists in the current dictionary.
	 * The word is trimmed and several variations of capitalizations are checked.
	 * If you want to check a word without any changes made to it, call checkExact()
	 *
	 * @see http://blog.stevenlevithan.com/archives/faster-trim-javascript re:trimming function
	 *
	 * @param {String} aWord The word to check.
	 * @returns {Boolean}
	 */
	
	check : function (aWord) {
		if (!this.loaded) {
			throw "Dictionary not loaded.";
		}
		
		// Remove leading and trailing whitespace
		var trimmedWord = aWord.replace(/^\s\s*/, '').replace(/\s\s*$/, '');
		
		if (this.checkExact(trimmedWord)) {
			return true;
		}
		
		// The exact word is not in the dictionary.
		if (trimmedWord.toUpperCase() === trimmedWord) {
			// The word was supplied in all uppercase.
			// Check for a capitalized form of the word.
			var capitalizedWord = trimmedWord[0] + trimmedWord.substring(1).toLowerCase();
			
			if (this.hasFlag(capitalizedWord, "KEEPCASE")) {
				// Capitalization variants are not allowed for this word.
				return false;
			}
			
			if (this.checkExact(capitalizedWord)) {
				// The all-caps word is a capitalized word spelled correctly.
				return true;
			}

			if (this.checkExact(trimmedWord.toLowerCase())) {
				// The all-caps is a lowercase word spelled correctly.
				return true;
			}
		}
		
		var uncapitalizedWord = trimmedWord[0].toLowerCase() + trimmedWord.substring(1);
		
		if (uncapitalizedWord !== trimmedWord) {
			if (this.hasFlag(uncapitalizedWord, "KEEPCASE")) {
				// Capitalization variants are not allowed for this word.
				return false;
			}
			
			// Check for an uncapitalized form
			if (this.checkExact(uncapitalizedWord)) {
				// The word is spelled correctly but with the first letter capitalized.
				return true;
			}
		}
		
		return false;
	},
	
	/**
	 * Checks whether a word exists in the current dictionary.
	 *
	 * @param {String} word The word to check.
	 * @returns {Boolean}
	 */
	
	checkExact : function (word) {
		if (!this.loaded) {
			throw "Dictionary not loaded.";
		}

		// 1. Direct check in dictionary table
		if (this.dictionaryTable.hasOwnProperty(word)) {
			return true;
		}

		// 2. Check suffix rules using double index
		for (var len = 0; len <= word.length; len++) {
			var suffix = word.substring(word.length - len);
			var removeGroup = this.suffixRules[suffix];
			if (removeGroup) {
				for (var removeStr in removeGroup) {
					var stem = word.substring(0, word.length - suffix.length) + removeStr;
					
					// Fast dictionary check first!
					if (!this.dictionaryTable.hasOwnProperty(stem)) continue;
					
					// Only if the stem exists do we check the individual rules
					var items = removeGroup[removeStr];
					var stemRulesArrays = this.dictionaryTable[stem];
					
					for (var i = 0; i < items.length; i++) {
						var item = items[i];
						var entry = item.entry;
						var code = item.code;
						
						if (entry.match && !entry.match.test(stem)) continue;
						
						// Check if stem has this rule code
						for (var rIdx = 0; rIdx < stemRulesArrays.length; rIdx++) {
							if (stemRulesArrays[rIdx].indexOf(code) !== -1) {
								return true;
							}
						}
					}
				}
			}
		}

		// 3. Check prefix rules using double index
		for (var len = 0; len <= word.length; len++) {
			var prefix = word.substring(0, len);
			var removeGroup = this.prefixRules[prefix];
			if (removeGroup) {
				for (var removeStr in removeGroup) {
					var stem = removeStr + word.substring(prefix.length);
					
					// Fast dictionary check first!
					if (!this.dictionaryTable.hasOwnProperty(stem)) continue;
					
					var items = removeGroup[removeStr];
					var stemRulesArrays = this.dictionaryTable[stem];
					
					for (var i = 0; i < items.length; i++) {
						var item = items[i];
						var entry = item.entry;
						var code = item.code;
						
						if (entry.match && !entry.match.test(stem)) continue;
						
						for (var rIdx = 0; rIdx < stemRulesArrays.length; rIdx++) {
							if (stemRulesArrays[rIdx].indexOf(code) !== -1) {
								return true;
							}
						}
					}
				}
			}
		}

		// 4. Combined PFX + SFX rules
		for (var len = 0; len <= word.length; len++) {
			var suffix = word.substring(word.length - len);
			var sRemoveGroup = this.suffixRules[suffix];
			if (sRemoveGroup) {
				for (var sRemoveStr in sRemoveGroup) {
					var midWord = word.substring(0, word.length - len) + sRemoveStr;
					
					var sItems = sRemoveGroup[sRemoveStr];
					var sMatches = [];
					for (var i = 0; i < sItems.length; i++) {
						var item = sItems[i];
						if (item.rule.combineable) {
							if (!item.entry.match || item.entry.match.test(midWord)) {
								sMatches.push(item.code);
							}
						}
					}
					if (sMatches.length === 0) continue;
					
					for (var pLen = 0; pLen <= midWord.length; pLen++) {
						var prefix = midWord.substring(0, pLen);
						var pRemoveGroup = this.prefixRules[prefix];
						if (pRemoveGroup) {
							for (var pRemoveStr in pRemoveGroup) {
								var stem = pRemoveStr + midWord.substring(pLen);
								
								// Fast dictionary check first!
								if (!this.dictionaryTable.hasOwnProperty(stem)) continue;
								
								var pItems = pRemoveGroup[pRemoveStr];
								var stemRulesArrays = this.dictionaryTable[stem];
								
								for (var j = 0; j < pItems.length; j++) {
									var pItem = pItems[j];
									if (!pItem.rule.combineable) continue;
									
									var pEntry = pItem.entry;
									var pCode = pItem.code;
									
									if (pEntry.match && !pEntry.match.test(stem)) continue;
									
									for (var rIdx = 0; rIdx < stemRulesArrays.length; rIdx++) {
										var rules = stemRulesArrays[rIdx];
										if (rules.indexOf(pCode) !== -1) {
											for (var sIdx = 0; sIdx < sMatches.length; sIdx++) {
												if (rules.indexOf(sMatches[sIdx]) !== -1) {
													return true;
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}

		return false;
	},
	
	/**
	 * Looks up whether a given word is flagged with a given flag.
	 *
	 * @param {String} word The word in question.
	 * @param {String} flag The flag in question.
	 * @return {Boolean}
	 */
	 
	hasFlag : function (word, flag, wordFlags) {
		if (!this.loaded) {
			throw "Dictionary not loaded.";
		}

		if (flag in this.flags) {
			if (typeof wordFlags === 'undefined') {
				wordFlags = Array.prototype.concat.apply([], this.dictionaryTable[word] || []);
			}
			
			if (wordFlags && wordFlags.indexOf(this.flags[flag]) !== -1) {
				return true;
			}
		}
		
		return false;
	},
	
	/**
	 * Returns a list of suggestions for a misspelled word.
	 *
	 * @see http://www.norvig.com/spell-correct.html for the basis of this suggestor.
	 * This suggestor is primitive, but it works.
	 *
	 * @param {String} word The misspelling.
	 * @param {Number} [limit=5] The maximum number of suggestions to return.
	 * @returns {String[]} The array of suggestions.
	 */
	
	alphabet : "",
	
	suggest : function (word, limit) {
		if (!this.loaded) {
			throw "Dictionary not loaded.";
		}

		limit = limit || 5;

		if (this.memoized.hasOwnProperty(word)) {
			var memoizedLimit = this.memoized[word]['limit'];

			// Only return the cached list if it's big enough or if there weren't enough suggestions
			// to fill a smaller limit.
			if (limit <= memoizedLimit || this.memoized[word]['suggestions'].length < memoizedLimit) {
				return this.memoized[word]['suggestions'].slice(0, limit);
			}
		}
		
		if (this.check(word)) return [];
		
		// Check the replacement table.
		for (var i = 0, _len = this.replacementTable.length; i < _len; i++) {
			var replacementEntry = this.replacementTable[i];
			
			if (word.indexOf(replacementEntry[0]) !== -1) {
				var correctedWord = word.replace(replacementEntry[0], replacementEntry[1]);
				
				if (this.check(correctedWord)) {
					return [ correctedWord ];
				}
			}
		}
		
		if (!this.alphabet) {
			// Use the English alphabet as the default. Problematic, but backwards-compatible.
			this.alphabet = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
			
			// Any characters defined in the affix file as substitutions can go in the alphabet too.
			// Note that dictionaries do not include the entire alphabet in the TRY flag when it's there.
			// For example, Q is not in the default English TRY list; that's why having the default
			// alphabet above is useful.
			if ( 'TRY' in this.flags ) {
				this.alphabet += this.flags['TRY'];
			}
			
			// Plus any additional characters specifically defined as being allowed in words.
			if ( 'WORDCHARS' in this.flags ) {
				this.alphabet += this.flags['WORDCHARS'];
			}
			
			// Remove any duplicates.
			var alphaArray = this.alphabet.split("");
			alphaArray.sort();

			var alphaHash = {};
			for ( var i = 0; i < alphaArray.length; i++ ) {
				alphaHash[ alphaArray[i] ] = true;
			}
			
			this.alphabet = '';
			
			for ( var i in alphaHash ) {
				this.alphabet += i;
			}
		}
		
		var self = this;

		/**
		 * Returns a hash keyed by all of the strings that can be made by making a single edit to the word (or words in) `words`
		 * The value of each entry is the number of unique ways that the resulting word can be made.
		 *
		 * @arg mixed words Either a hash keyed by words or a string word to operate on.
		 * @arg bool known_only Whether this function should ignore strings that are not in the dictionary.
		 */
		function edits1(words, known_only) {
			var rv = {};
			var alphabetLength = self.alphabet.length;
			
			if (typeof words == 'string') {
				var w = words;
				words = {};
				words[w] = true;
			}

			for (var w in words) {
				for (var i = 0, _len = w.length + 1; i < _len; i++) {
					var s = [ w.substring(0, i), w.substring(i) ];
				
					// Remove a letter.
					if (s[1]) {
						var _edit = s[0] + s[1].substring(1);

						if (!known_only || self.check(_edit)) {
							rv[_edit] = (rv[_edit] || 0) + 1;
						}
					}
					
					// Transpose letters
					if (s[1].length > 1 && s[1][1] !== s[1][0]) {
						var _edit = s[0] + s[1][1] + s[1][0] + s[1].substring(2);

						if (!known_only || self.check(_edit)) {
							rv[_edit] = (rv[_edit] || 0) + 1;
						}
					}

					if (s[1]) {
						// Replace a letter with another letter.
						var lettercase = (s[1].substring(0,1).toUpperCase() === s[1].substring(0,1)) ? 'uppercase' : 'lowercase';

						for (var j = 0; j < alphabetLength; j++) {
							var replacementLetter = self.alphabet[j];

							// Set the case of the replacement letter to the same as the letter being replaced.
							if ( 'uppercase' === lettercase ) {
								replacementLetter = replacementLetter.toUpperCase();
							}

							// Eliminate replacement of a letter by itself
							if (replacementLetter != s[1].substring(0,1)){
								var _edit = s[0] + replacementLetter + s[1].substring(1);

								if (!known_only || self.check(_edit)) {
									rv[_edit] = (rv[_edit] || 0) + 1;
								}
							}
						}
					}

					if (s[1]) {
						// Add a letter between each letter.
						for (var j = 0; j < alphabetLength; j++) {
							// If the letters on each side are capitalized, capitalize the replacement.
							var lettercase = (s[0].substring(-1).toUpperCase() === s[0].substring(-1) && s[1].substring(0,1).toUpperCase() === s[1].substring(0,1)) ? 'uppercase' : 'lowercase';

							var replacementLetter = self.alphabet[j];

							if ( 'uppercase' === lettercase ) {
								replacementLetter = replacementLetter.toUpperCase();
							}

							var _edit = s[0] + replacementLetter + s[1];

							if (!known_only || self.check(_edit)) {
								rv[_edit] = (rv[_edit] || 0) + 1;
							}
						}
					}
				}
			}
			
			return rv;
		}

		function correct(word) {
			// Get the edit-distance-1 forms of this word.
			var ed1 = edits1(word);
			var weighted_corrections = {};
			var ed1_matches = 0;
			
			for (var ed1word in ed1) {
				if (self.check(ed1word)) {
					weighted_corrections[ed1word] = ed1[ed1word];
					ed1_matches++;
				}
			}
			
			// Disabled edit-distance 2 to ensure maximum UI performance without freezes.
			
			var sorted_corrections = [];
			
			for (var i in weighted_corrections) {
				sorted_corrections.push([ i, weighted_corrections[i] ]);
			}

			function sorter(a, b) {
				var a_val = a[1];
				var b_val = b[1];
				if (a_val < b_val) return -1;
				if (a_val > b_val) return 1;
				return b[0].localeCompare(a[0]);
			}
			
			sorted_corrections.sort(sorter).reverse();

			var rv = [];
			var capitalization_scheme = "lowercase";
			
			if (word.toUpperCase() === word) {
				capitalization_scheme = "uppercase";
			}
			else if (word.substr(0, 1).toUpperCase() + word.substr(1).toLowerCase() === word) {
				capitalization_scheme = "capitalized";
			}
			
			var working_limit = limit;

			for (var i = 0; i < Math.min(working_limit, sorted_corrections.length); i++) {
				var suggestion = sorted_corrections[i][0];
				if ("uppercase" === capitalization_scheme) {
					suggestion = suggestion.toUpperCase();
				}
				else if ("capitalized" === capitalization_scheme) {
					suggestion = suggestion.substr(0, 1).toUpperCase() + suggestion.substr(1);
				}
				
				if (!self.hasFlag(suggestion, "NOSUGGEST") && rv.indexOf(suggestion) == -1) {
					rv.push(suggestion);
				}
				else {
					// If one of the corrections is not eligible as a suggestion , make sure we still return the right number of suggestions.
					working_limit++;
				}
			}

			return rv;
		}
		
		this.memoized[word] = {
			'suggestions': correct(word),
			'limit': limit
		};

		return this.memoized[word]['suggestions'];
	}
};
})();

// Support for use as a node.js module.
if (typeof module !== 'undefined') {
	module.exports = Typo;
}
