--[[
Misspelled utilizes a slightly Lua'ified version of the Hunspell Dictionary format.
Note: Not all Dictionary sets tags are supported.

Phonetic information has been appeneded, after the affix codes, to each base word
example: "hello/GMS/HL"
A phonetic lookup set "Phonetic" exists before the base words.

Here is some rather generic documentation on that format.
From: http://sourceforge.net/docman/display_doc.php?docid=29374&group_id=143754

TRY
sets the change characters for suggestions.

REP (Replace)
sets a replacement table for multiple character corrections in suggestion mode.

The following affix file example:. �TRY� suggestions differ from the bad word with an
English letter or an apostrophe. With these REP definitions, Hunspell can suggest the
right word form, when the misspelled word contains f instead of ph and vice versa.


	TRY esianrtolcdugmphbyfvkwzESIANRTOLCDUGMPHBYFVKWZ�

	REP 2
	REP f ph
	REP ph f

	PFX A Y 1
	PFX A 0 re .

	SFX B Y 2
	SFX B 0 ed [^y]
	SFX B y ied y

There are two affix classes in the dictionary.
Class A defines a �re-� prefix. Class B defines two �-ed� suffixes.
First suffix can be added to a word if the last character of the word isn�t �y�.
Second suffix can be added to the words terminated with an �y�. (See later.)

The following dictionary file uses these affix classes.

	3
	hello
	try/B
	work/AB

All accepted words with this dictionary: "hello", "try", "tried", "work", "worked", "rework", "reworked".


Affix Compression
--------------------------------------------------------------------------
An affix is either a  prefix or a suffix attached to root words to make
other words.  For example supply -> supplied by dropping the "y" and
adding an "ied" (the suffix).

Here is an example of how to define one specific suffix borrowed
from the en_US.aff file used by the OpenOffice org spellchecker

SFX D Y 4
SFX D   0     d          e
SFX D   y     ied        [^aeiou]y
SFX D   0     ed         [^ey]
SFX D   0     ed         [aeiou]y

This file is space delimited and case sensitive.
So this information can be interpreted as follows:

The first line has 4 fields:

Field
-----
1     SFX - indicates this is a suffix
2     D   - is the name of the character which represents this suffix
3     Y   - indicates it can be combined with prefixes (cross product)
4     4   - indicates that sequence of 4 affix entries are needed to
               properly store the affix information

The remaining lines describe the unique information for the 4 affix
entries that make up this affix.  Each line can be interpreted
as follows: (note fields 1 and 2 are used as a check against line 1 info)

Field
-----
1     SFX         - indicates this is a suffix
2     D           - is the name of the character which represents this affix
3     y           - the string of chars to strip off before adding affix
                         (a 0 here indicates the NULL string)
4     ied         - the string of affix characters to add
                         (a 0 here indicates the NULL string)
5     [^aeiou]y   - the conditions which must be met before the affix
                    can be applied

Field 5 is interesting.  Since this is a suffix, field 5 tells us that
there are 2 conditions that must be met.  The first condition is that
the next to the last character in the word must *NOT* be any of the
following "a", "e", "i", "o" or "u".  The second condition is that
the last character of the word must end in "y".

require("bit")

--]]




--Local reference to Global functions for speed
local table_insert = table.insert
local string_byte = string.byte
local string_find = string.find
local string_gsub = string.gsub
local string_lower = string.lower
local string_match = string.match
local string_rep = string.rep
local string_sub = string.sub
local string_upper = string.upper
local bit_bor = bit.bor
local bit_lshift = bit.lshift
local bit_rshift = bit.rshift
local bit_band = bit.band
local bit_bnot = bit.bnot
local math_min = math.min

--WordDict_Dictionary = {}

local DICTIONARY_TO_LOAD_FROM

--split a string, at delimiter into a table
-- Compatibility: Lua-5.1
local split_t
local split_fpat
local split_last_end
local split_s, split_e, split_cap
local function split(str, pat)
   split_t = {}  -- NOTE: use {n = 0} in Lua-5.0
   split_fpat = "(.-)" .. pat
   split_last_end = 1
   split_s, split_e, split_cap = string_find(str, split_fpat, 1)
   while split_s do
      if split_s ~= 1 or split_cap ~= "" then
	 table_insert(split_t, split_cap)
      end
      split_last_end = split_e+1
      split_s, split_e, split_cap = string_find(str, split_fpat, split_last_end)
   end
   if split_last_end <= #str then
      split_cap = string_sub(str, split_last_end)
      table_insert(split_t, split_cap)
   end
   return split_t
end


--WordDict Class
WordDict = {}
WordDict = {
			baseWords = {},
			replaceChars = {},
			prefixRules = {},
			suffixRules = {},
			phoneticRules= {},
			tryChars = {},
			possibleBaseWords = {},
			suggestions= {},
			maxSuggestions = 8
			}

WordDict.AffixUtility = {}

function WordDict.AffixUtility:EncodeConditions(conditionText)
	local Condition = {}

	local group = false  	--Group indicator
	local groupend = false	--end contition indicator
	local neg = false -- complement indicator
	local ConditionCount = 0 -- number of conditions

	local memberChars = {}
	local numMember = 0		-- number of member in groupend

	--local BeginningOnly = false
	--local EndOnly = false
	local ConditionCount = 0
	local ReplaceMode = false


	--print("conditionText", conditionText)

	for j=0,255 do
		Condition[j] = 0
	end

	if conditionText == "." then
		ConditionCount = 0
		return ConditionCount, Condition
	end

	for i = 1, #conditionText do
		local cond = string_sub(conditionText, i, i)
		--print("i", i, "cond", cond)

		--parse member group
		if cond == "[" then
			group = true   --start a group
		elseif cond == "^" and group == true then
			neg = true  --negative group
		elseif cond == "]" then
			endgroup = true  -- end of a group
		elseif group == true then
			--add chars to group
			memberChars[numMember] = cond
			numMember = numMember + 1
		else
			endgroup = true --no group
		end

		--set condition
		if endgroup == true then
			if group == true then
				if neg == true then
					--turn all chars on
					for j=0,255 do
						if Condition[j] == nil then
							Condition[j] = 0
						end
						Condition[j] = bit_bor(Condition[j], bit_lshift(1, ConditionCount))
					end
					--turn off chars in member groupend
					for j = 0, numMember -1 do
						local charCode = string_byte(memberChars[j])
						Condition[charCode] = bit_band(Condition[charCode], bit_bnot(bit_lshift(1, ConditionCount)))
					end
				else
					--turn on chars in member group
					for j = 0,numMember -1 do
						local charCode = string_byte(memberChars[j])
						Condition[charCode] = bit_bor(Condition[charCode], bit_lshift(1, ConditionCount))
					end
				end
				group = false
				neg = false
				numMember = 0
			else
				if cond == "." then
					--wild char character, turn all chars on
					for j=0, 255 do
						Condition[j] = bit_bor(Condition[j], bit_lshift(1, CounditionCount))
					end
				else
					--turn on char
					local charCode = string_byte(cond)
					if Condition[charCode] == nil then
						Condition[charCode] = 0
					end
					Condition[charCode] = bit_bor(Condition[charCode], bit_lshift(1, ConditionCount))
				end
			end
			endgroup = false
			ConditionCount = ConditionCount + 1
		end
	end

	--Condition["ConditionCount"] = ConditionCount
	return ConditionCount, Condition
end

--Removes the affix suffix rule entry for the word if valid
function WordDict.AffixUtility:RemoveSuffix(word, entry)
	local tempLength = #word - #entry.AddChars
	if (tempLength > 0)
		and (tempLength + #entry.StripChars >= entry.ConditionCount)
		and (string_match(word, entry.AddChars .. "$") ~= nil) then  --word ends with suffix

		--word with out affix
		local tempWord = string_sub(word, 1, tempLength)
		--add back strip chars
		tempWord = tempWord .. entry.StripChars
		--check that this is valid
		local passCount = 0
		for i = 0, entry.ConditionCount - 1 do
			local charCode = string_byte(string_sub(tempWord, #tempWord - (entry.ConditionCount -i) + 1))
			--if entry.Conditions[charCode] == nil then
 			--	entry.Conditions[charCode] = 0
 			--end
			if bit_band(entry.Conditions[charCode], bit_lshift(1, i)) == bit_lshift(1 , i) then
				passCount = passCount + 1
			end
		end
		if passCount == entry.ConditionCount then
			return tempWord
		end
	end
	return word
end

--Removes the affix prefix rule entry for the word if valid
function WordDict.AffixUtility:RemovePrefix(word, entry)
	local tempLength = #word - #entry.AddChars
	local tempWord
	local charCode
	local passCount
	if (tempLength > 0)
		and (tempLength + #entry.StripChars >= entry.ConditionCount)
		and (string_match(word, "^" .. entry.AddChars) ~= nil) then  --word ends with

		--word with out affix
		tempWord = string_sub(word, #entry.AddChars+1)
		--add back strip chars
		tempWord = entry.StripChars .. tempWord
		--check that this is valid
		passCount = 0
		for i = 0, entry.ConditionCount -1 do
			charCode = string_byte(string_sub(tempWord, i+1, i+1))

			if bit_band(entry.Conditions[charCode], bit_lshift(1, i)) == bit_lshift(1 , i) then
				passCount = passCount + 1
			end
		end
		if passCount == entry.ConditionCount then
			return tempWord
		end
	end

	return word
end

--Adds a suffix to a word
--Returns the word with the suffix added
function WordDict.AffixUtility:AddSuffix(word, rule)
	local passCount
	local charCode
	local tempLen
	local tempWord
	for i, entry in ipairs(rule.AffixEntries) do
		--check if this entry is valid
		if #word >= entry.ConditionCount then
			passCount = 0
			for i=0, entry.ConditionCount -1 do
				charCode = string_byte(string_sub(word, #word - (entry.ConditionCount -i)+1,#word - (entry.ConditionCount -i)+1))

				if bit_band(entry.Conditions[charCode], bit_lshift(1, i)) == bit_lshift(1 , i) then
					passCount = passCount + 1
				else
					break
				end
			end
			if passCount == entry.ConditionCount then
				tempLen = #word - #entry.StripChars
				tempWord = string_sub(word, 1, tempLen)
				tempWord = tempWord .. entry.AddChars
				return tempWord
			end
		end
	end
	return word
end

--Adds a prefix to a word
--Returns the word with the prefix added
function WordDict.AffixUtility:AddPrefix(word, rule)
	local passCount
	local charCode
	local tempLen
	local tempWord
	for i, entry in ipairs(rule.AffixEntries) do
		--check if this entry is valid
		if #word >= entry.ConditionCount then
			passCount = 0
			for i=0, entry.ConditionCount -1 do
				charCode = string_byte(string_sub(word, i+1, i+1))

				if bit_band(entry.Conditions[charCode], bit_lshift(1, i)) == bit_lshift(1 , i) then
					passCount = passCount + 1
				else
					break
				end
			end
			if passCount == entry.ConditionCount then
				tempLen = #word - #entry.StripChars
				tempWord = string_sub(word, 1, tempLen)
				tempWord = entry.AddChars .. tempWord
				return tempWord
			end
		end
	end
	return word
end


function WordDict:LoadPrefixRules()
	local row = 1 --row pointer
	local rowCount = #DICTIONARY_TO_LOAD_FROM.Prefix

	local header
	local hpart1
	local hpart2
	local hpart3
	local rulecount
	local rule1
	local rule2
	local rule3
	local rule4
	local AllowCombine = false
	local entry
	local parsedEntry
	local condCount
	local conditions

	local p = DICTIONARY_TO_LOAD_FROM.Prefix

	while row < rowCount do
			header = p[row]
			-- headers are in 3 parts
			-- Part 1 = affix key
			hpart1 = string_match(header, "^%a+")
			-- Part 2 = Allow combine flag
			hpart2 = string_gsub(string_match(header, "%s%a+"),"%s+","")
			-- Part 3 = rule count, not used
			hpart3 = string_match(header, "%d+$")
			--determin how many parts there are to this prefix
			rulecount = tonumber(hpart3 )
			--print("header", hpart1, hpart2, hpart3)

			--Add header parts 1 & 2 to PrefixRules collection
			self.prefixRules[hpart1] = {["Combine"]=hpart2, ["Rules"]={}}

			--Rules have 4 parts
			--Part1: affix(prefix/suffix) key
			--Part2: strip char
			--Part3: add chars
			--Part4: conditions

			AllowCombine = false
			if hpart2 == "Y" then AllowCombine = true end

			--Add header parts 1 & 2 to PrefixRules collection
			self.prefixRules[hpart1] = {["AllowCombine"]=AllowCombine, ["AffixEntries"]={}}

			for x = 1, rulecount do
				row = row + 1
				entry = p[row]
				parsedEntry = split(entry, "%s+")
				self.prefixRules[hpart1]["AffixEntries"][x] = {}
				--part 2 - strip char
				if parsedEntry[2] == "0" then
					self.prefixRules[hpart1]["AffixEntries"][x]["StripChars"] = ""
				else
				    self.prefixRules[hpart1]["AffixEntries"][x]["StripChars"] = parsedEntry[2]
				end
				--part 3 - add chars
				self.prefixRules[hpart1]["AffixEntries"][x]["AddChars"] = parsedEntry[3]
				--part 4 - conditions
				condCount = nil
				conditions = nil
				condCount, conditions = WordDict.AffixUtility:EncodeConditions(parsedEntry[4])
				self.prefixRules[hpart1]["AffixEntries"][x]["ConditionCount"] = condCount
				self.prefixRules[hpart1]["AffixEntries"][x]["Conditions"] = conditions
			end
			row = row + 1
	end

end

function WordDict:LoadSuffixRules()
	local row = 1 --row pointer
	local rowCount = #DICTIONARY_TO_LOAD_FROM.Suffix

	local header
	local hparts
	local hpart1
	local hpart2
	local hpart3
	local rulecount
	local rule1
	local rule2
	local rule3
	local rule4
	local AllowCombine = false
	local entry
	local parsedEntry
	local condCount
	local conditions

	local s = DICTIONARY_TO_LOAD_FROM.Suffix

	while row < rowCount do
			header = s[row]
			-- headers are in 3 parts
			hparts = split(header, "%s+")
			hpart1 = hparts[1]
			hpart2 = hparts[2]
			hpart3 = hparts[3]

--~ 			-- Part 1 = affix key
--~ 			hpart1 = string_match(header, "^%a+")
--~ 			-- Part 2 = combine flag
--~ 			hpart2 = string_gsub(string_match(header, "%s%a+"),"%s+","")
--~ 			-- Part 3 = rule count, not used
--~ 			hpart3 = string_match(header, "%d+$")
			--determin how many parts there are to this prefix
			rulecount = tonumber(hpart3)
			--print("header", hpart1, hpart2, hpart3, "##")

			AllowCombine = false
			if hpart2 == "Y" then AllowCombine = true end

			--Add header parts 1 & 2 to SuffixRules collection
			self.suffixRules[hpart1] = {["AllowCombine"]=AllowCombine, ["AffixEntries"]={}}

			--Rules have 4 parts
			--Part1: affix(prefix/suffix) key
			--Part2: strip char
			--Part3: add chars
			--Part4: conditions

			for x = 1, rulecount do
				row = row + 1
				entry = s[row]
				parsedEntry = split(entry, "%s+")
				self.suffixRules[hpart1]["AffixEntries"][x] = {}
				--part 2 - strip char
				if parsedEntry[2] == "0" then
					self.suffixRules[hpart1]["AffixEntries"][x]["StripChars"] = ""
				else
				    self.suffixRules[hpart1]["AffixEntries"][x]["StripChars"] = parsedEntry[2]
				end
				--part 3 - add chars
				self.suffixRules[hpart1]["AffixEntries"][x]["AddChars"] = parsedEntry[3]
				--part 4 - conditions
				condCount = nil
				conditions = nil
				condCount, conditions = WordDict.AffixUtility:EncodeConditions(parsedEntry[4])
				self.suffixRules[hpart1]["AffixEntries"][x]["ConditionCount"] = condCount
				self.suffixRules[hpart1]["AffixEntries"][x]["Conditions"] = conditions
			end
			row = row + 1
	end

end

WordDict.PhoneticUtility = {}

function WordDict.PhoneticUtility:EncodeRule(ruleText)
	local group = false  	--Group indicator
	local groupend = false	--end contition indicator

	local memberChars = {}
	local numMember = 0		-- number of member in groupend

	local BeginningOnly = false
	local EndOnly = false
	local ConsumeCount = 0
	local ReplaceMode = false
	local Priority = 0
	local ConditionCount = 0
	local cond
	local charCode

	local Rule = {}
	Rule["Condition"] = {}
	Rule["ConsumeCount"] = 0

	--for j = 0, 255 do
	--	RuleCondition[j] = 0
	--end

	--print("ruletext", ruleText)

	for i = 1, #ruleText do
		cond = string_sub(ruleText, i, i)
		--print("i", i, "cond", cond)

		if cond == "(" then group = true
		elseif cond == ")" then endgroup = true
		elseif cond == "^" then
			BeginningOnly = true
			Rule["BeginningOnly"] = true
		elseif cond == "$" then
			EndOnly = true
			Rule["EndOnly"] = true
		elseif cond == "-" then
			ConsumeCount = ConsumeCount + 1
			Rule["ConsumeCount"] = ConsumeCount
		elseif cond == "<" then
			ReplaceMode = true
			Rule["ReplaceMode"] = true
		--local p = tonumber(cond)
		elseif tonumber(cond) ~= nil then
			Priority = tonumber(cond)
			Rule["Priority"] = Priority
		else
			if group == true then
				--add chars to group
				memberChars[numMember] = cond
				numMember = numMember + 1
			else
				endgroup = true
			end
		end
		if endgroup == true then
			if group == true then
				--turn on chars in member group
				for j = 0, numMember - 1 do
					charCode = string_byte(memberChars[j])
					if Rule["Condition"][charCode] == nil then
						Rule["Condition"][charCode] = 0
					end
					Rule["Condition"][charCode] = bit_bor(Rule["Condition"][charCode], bit_lshift(1, ConditionCount))
				end
				group = false
				numMember = 0
			else
				--turn on char
				charCode = string_byte(cond)
				if Rule.Condition[charCode] == nil then
					Rule.Condition[charCode] = 0
				end
				Rule["Condition"][charCode] = bit_bor(Rule["Condition"][charCode], bit_lshift(1, ConditionCount))
			end
			endgroup = false
			ConditionCount = ConditionCount + 1
			Rule["ConditionCount"] = ConditionCount
		end
	end
	return Rule
end

function WordDict:LoadPhoneticRules()
	local pr = DICTIONARY_TO_LOAD_FROM.Phonetic

	--Phonetic rules are in 2 parts
	--Part1: Encoded Rule
	--Part2: ReplaceString
	for i, v in ipairs(pr) do
		parsedrule = split(v, "%s+")
		--self.phoneticRules[i]= {parsedrule[1], parsedrule[2]}
		self.phoneticRules[i] = WordDict.PhoneticUtility:EncodeRule(parsedrule[1])
		self.phoneticRules[i]["ReplaceString"] = parsedrule[2]

	end
end

function WordDict:LoadWords()
	local w = DICTIONARY_TO_LOAD_FROM.Words

	local baseWord
	local affixKeys
	local phoneticCode
	local parse = {}

	for i, v in ipairs(w) do
		-- split word input line into its parts
		--Part1: base word
		--Part2: affix keys
		--Part3: phonetic code
		--       Note: Some languanges don't have phonetic info,
		--		 and just use the Generic Phonetic method.
		parse = split(v, "/")
		baseWord = parse[1]
		if parse[2] ~= nil then
			affixKeys = parse[2]
		else
			affixKeys = ""
		end
		if parse[3] ~= nil then
			phoneticCode = parse[3]
		else
			phoneticCode = ""
		end

		--(r18) Don't store the affixKeys and phoneticCode in a sub table
		--Saves 6MB of memory.
		--self.baseWords[baseWord] = {affixKeys, phoneticCode}
		self.baseWords[baseWord] = affixKeys .."/" .. phoneticCode
	end
end

--Generates a phonetic code of how the word sounds
--Input: word (string)
--Return: a code of how the word sounds
function WordDict:PhoneticCode(word)
	local tempWord = string_upper(word)
	local prevWord = ""
	local code = ""

	local begining
	local ending
	local passCount
	local charCode
	local ruleCondition

	while #tempWord > 0 do
		--save previous word
		prevWord = tempWord

		for i,v in ipairs(self.phoneticRules) do
			begining = false
			ending = false
			if #tempWord == #word then
				begining = true
			end
			if v.ConditionCount == #tempWord then
				ending = true
			end

			if ((v.BeginningOnly == begining or not v.BeginningOnly)
				and (v.EndOnly == ending or not v.EndOnly)
				and (v.ConditionCount <= #tempWord)) then

				passCount = 0
				-- loop through conditions
				for i = 1, v.ConditionCount do
					charCode = string_byte(string_sub(tempWord, i, i))
					ruleCondition = v.Condition[charCode]
					if ruleCondition == nil then
						ruleCondition = 0
					end
					if bit_band(ruleCondition, bit_lshift(1, i-1)) == bit_lshift(1, i-1) then
						passCount = passCount + 1 -- condition passed
					else
						break -- rule fails if on condition fails
					end
				end
				-- if all conditions passed
				if passCount == v.ConditionCount then
					if v.ReplaceMode == true then
						tempWord = v.ReplaceString .. string_sub(tempWord, v.ConditionCount - v.ConsumeCount + 1, -1)
					else
						if v.ReplaceString ~= "_" then
							code = code .. v.ReplaceString
						end
						tempWord = string_sub(tempWord, v.ConditionCount - v.ConsumeCount + 1)
					end
					break
				end
			end
		end

		-- if no match consume one char
		if #prevWord == #tempWord then
			tempWord = string_sub(tempWord, 2, -1)
		end
	end
	return code
end

--Searched all containted word lists for word
function WordDict:Contains(word)
	--clean up possible base word lists
	self.possibleBaseWords = {}

	--Step1: search userwords

	--Step2: search BaseWords
	if self.baseWords[word] ~= nil then
		return true
	end

	--Step3: Remove suffix, then search basewords
	-- save suffixed words for use when removing prefix
	local suffixWords = {}

	suffixWords[word] = 1

	--tprint(self.suffixRules)
	local tempWord
	local baseWordTemp
	local affixKeys
	for key, rule in pairs(self.suffixRules) do
		--print("suffix rule: ", key)
		for x, entry in ipairs(rule.AffixEntries) do
			--print("AffixEntry addchars",entry.AddChars)
			--tprint(entry)

			tempWord = WordDict.AffixUtility:RemoveSuffix(word, entry)
			if tempWord ~= word then
				baseWordTemp = self.baseWords[tempWord]
				if baseWordTemp ~= nil then
					affixKeys = string_sub(baseWordTemp, 1, (string_find(baseWordTemp, "/") -1))
					--make sure base word has this affix key
					if string_find(affixKeys, key) ~= nil then
						return true --word found
					end
				end
			end

			if rule.AllowCombine == true then
				-- saving word to check if it is a word after prefix is removed
				suffixWords[tempWord] = 1
			else
				-- saving possible base words for use in generating suggestions
				self.possibleBaseWords[tempWord] = 1
			end
		end
	end
	--save possible base words for use in generating suggestions
	for k, v in pairs(suffixWords) do
		self.possibleBaseWords[k] = 1
	end

	--Step4: Remove prefix, then search basewords
	for key, rule in pairs(self.prefixRules) do
		for x, entry in ipairs(rule.AffixEntries) do
			for suffixWord, y in pairs(suffixWords) do
				tempWord = WordDict.AffixUtility:RemovePrefix(suffixWord, entry)
				if tempWord ~= suffixWord then
					baseWordTemp = self.baseWords[tempWord]
					if baseWordTemp ~= nil then
						--make sure base work has this affix keys
						affixKeys = string_sub(baseWordTemp, 1, (string_find(baseWordTemp, "/") -1))

						if string_find(affixKeys, key) ~= nil then
							return true --word found
						end
					end

					--save possible base workd for use in generating suggestions
					self.possibleBaseWords[tempWord] = 1
				end
			end
		end
	end

	return false
end

--Expands an affix compressed base word
--takes in a base word entry with coresponsind affix & phonetic info
--returns a table of the expanded words
function WordDict:ExpandWord(word, affixKeys)
	local suffixWords = {}
	local words = {}

	--add word to the suffixWords table
	suffixWords[word] = 1
	local prefixKeys = ""

	-- check suffix keys first
	local key
	local rule
	local tempWord
	for x=1, #affixKeys do
		key = string_sub(affixKeys, x, x)
		if WordDict.suffixRules[key] ~= nil then
			rule = WordDict.suffixRules[key]
			tempWord = WordDict.AffixUtility:AddSuffix(word, rule)
			if tempWord ~= word then
				if rule.AllowCombine == true then
					suffixWords[tempWord] = 1
				else
					words[tempWord] = 1
				end
			end
		elseif WordDict.prefixRules[key] ~= nil then
			prefixKeys = prefixKeys..key
		end
	end

	--apply prefixes
	for x = 1, #prefixKeys do
		key = string_sub(prefixKeys, x, x)
		rule = WordDict.prefixRules[key]
		for suffixWord,v in pairs(suffixWords) do
			tempWord = WordDict.AffixUtility:AddPrefix(suffixWord, rule)
			if tempWord ~= suffixWord then
				words[tempWord] = 1
			end
		end
	end

	for key,v in pairs(suffixWords) do
		words[key] = 1
	end
	return words
end

--Calculated the minimum number of changes, inserts of deletes
--required to change the firstWord into the secondWord
--PositionPriority: set to true if the first and last char should have priority
function WordDict:EditDistance(source, target)
	local m = #source
	local n = #target

	if n == 0 then return m end
	if m == 0 then return n end

	local rows = {}
	rows[0] = {[0]=0}

	for x=0, m+1 do
		rows[x] = {[0]=0}
		for y=0,n do
			rows[x][y] = 0
		end
	end

	--tprint(rows)

	for i=0,m do
		rows[i][0] = i
	end

	for j=0,n do
		rows[0][j] = j
	end



	--tprint(rows)
	local subsitutionCost
	local insertion
	local deletion
	local subsitution
	for i=1, m do
		for j=1,n do
			if string_lower(string_sub(source, i, i)) == string_lower(string_sub(target, j, j)) then
				subsitutionCost = 0
			else
				subsitutionCost = 1
			end

			insertion = rows[i-1][j] + 1
			deletion = rows[i][j-1] + 1
			subsitution = rows[i-1][j-1] + subsitutionCost

			rows[i][j] = math_min(insertion, deletion, subsitution)
		end
	end

	local dist = rows[m][n]

	-- extra edit on first and last chars if position Priority is important
	if string_sub(source, 1, 1) ~= string_sub(target, 1, 1) then
		dist = dist + 1
	end

	if string_sub(source, -1) ~= string_sub(target, -1) then
		dist = dist +1
	end

	--tprint(rows)

	return dist
end

--returns true if word or lower(word) are in baseWords
function WordDict:TestWord(word)
	if word == nil then
		return false
	end

	if #word == 0 then
		return false
	end

	if self.baseWords[word] ~= nil then
		return true
	end

	if self.baseWords[string_lower(word)] ~= nil then
		return true
	end

	return false
end


--suggestions for a typical fault of spelling, that
--differs with more, than 1 letter from the right form.
function WordDict:ReplaceChars(CurrentWord)
	local suggestions = {}

	for i = 1, #self.replaceChars do
		local r
		local key
		local replacement
		local tempWord
		r = split(self.replaceChars[i], " ")
		key = r[1]
		replacement = r[2]

		local pos = string_find(CurrentWord, key)

		while pos ~= nil do
			tempWord = string_sub(CurrentWord, 0, pos -1)
			tempWord = tempWord .. replacement
			tempWord = tempWord .. string_sub(CurrentWord, pos + #key)
			if self.baseWords[tempword] ~= nil then
				suggestions[tempWord] = self:EditDistance(CurrentWord, tempWord)
			elseif self.baseWords[string_lower(tempWord)] ~= nil then
				suggestions[string_lower(tempWord)] = self:EditDistance(CurrentWord, string_lower(tempWord))
			end

			pos = string_find(CurrentWord, key, pos+1)
		end
	end

	return suggestions
end


--swap out each char one by one and try all the tryme
--chars in its place to see if that makes a good word
function WordDict:BadChar(CurrentWord)
	local suggestions = {}

	local tempWord
	local tryme
	local testWord
	for i=1, #CurrentWord do
		tempWord = {}
		tryme = self.tryChars

		for x=1, #CurrentWord do
			tempWord[x] = string_sub(CurrentWord, x, x)
		end

		for x=1,#tryme do
			tempWord[i] = string_sub(tryme, x-1, x-1)
			testWord = table.concat(tempWord)

			if self.baseWords[tempword] ~= nil then
				suggestions[tempWord] = self:EditDistance(CurrentWord, tempWord)
			elseif self.baseWords[string_lower(tempWord)] ~= nil then
				suggestions[string_lower(tempWord)] = self:EditDistance(CurrentWord, string_lower(tempWord))
			end
		end
	end

	return suggestions
end

--try omitting one char of word at a time
function WordDict:ExtraChar(CurrentWord)
	local suggestions = {}
	local tempWord

	if #CurrentWord > 1 then
		for i=1, #CurrentWord do
			tempWord = string_sub(CurrentWord, 0, i-1) .. string_sub(CurrentWord, i+1)

			if self:TestWord(tempWord) == true then
				suggestions[tempWord] = self:EditDistance(CurrentWord, tempWord)
			end
		end
	end

	return suggestions
end


--try inserting a tryme character before every letter
function WordDict:ForgotChar(CurrentWord)
	local suggestions = {}
	local tempWord
	local tryme = self.tryChars

	for i=1, #CurrentWord do
		for i=0, #CurrentWord do
			for x=1, #tryme do
				tempWord = string_sub(CurrentWord, 0, i) .. string_sub(tryme, x, x) .. string_sub(CurrentWord, i+1)
				if self.baseWords[tempword] ~= nil then
					suggestions[tempWord] = self:EditDistance(CurrentWord, tempWord)
				elseif self.baseWords[string_lower(tempWord)] ~= nil then
					suggestions[string_lower(tempWord)] = self:EditDistance(CurrentWord, string_lower(tempWord))
				end
			end
		end
	end

	return suggestions
end

--try swapping adjacent chars one by one
function WordDict:SwapChar(CurrentWord)
	if #CurrentWord <= 1 then
		return {}
	end

	local suggestions = {}
	local tempWord = {}
	local swap
	local testWord

	for i=1,#CurrentWord - 1 do
		tempWord = {}
		for x=1, #CurrentWord do
			tempWord[x] = string_sub(CurrentWord, x, x)
		end

		swap = tempWord[i]
		tempWord[i] = tempWord[i+1]
		tempWord[i+1] = swap

		testWord = table.concat(tempWord)

		if self.baseWords[testWord] ~= nil then
			suggestions[testWord] = self:EditDistance(CurrentWord, testWord)
		elseif self.baseWords[string_lower(testWord)] ~= nil then
			suggestions[string_lower(testWord)] = self:EditDistance(CurrentWord, string_lower(testWord))
		end
	end

	return suggestions
end


--split the string into two pieces after every char
--if both pieces are good words make them a suggestion
function WordDict:TwoWords(CurrentWord)
	local suggestions = {}

	if #CurrentWord < 3 then
		return suggestions
	end

	local firstWord
	local secondWord
	local tempWord

	for i=1, #CurrentWord -2 do
		firstWord = string_sub(CurrentWord, 1, i)
		secondWord = string_sub(CurrentWord, i+1)

		if self:TestWord(firstWord) == true then
			if self:TestWord(secondWord) == true then
				tempWord = firstWord .. " " .. secondWord
				suggestions[tempWord] = self:EditDistance(CurrentWord, tempWord) + 0.5
			end
		end
	end

	return suggestions
end


function WordDict:Suggest(currentWord)

	tempSuggestion = {}

	-- generate phonetic code for possible root word
	local codes = {}
	local tempCode

	for tempWord, v in pairs(WordDict.possibleBaseWords) do
		if tempWord ~= nil and tempWord ~= 1 then
			tempCode = WordDict:PhoneticCode(tempWord)
			if #tempCode > 0 and codes[tempCode] == nil then
				codes[tempCode] = 1
			end
		end
	end

	local codeCount = 0
	for k,v in pairs(codes) do
		codeCount = codeCount + 1
	end

	local words = {}
	local editDistance
	local affixKeys
	local pCode

	if codeCount > 0 then
		--search root words for phonetic codes
		for word, v in pairs(WordDict.baseWords) do
			--check if this word's phonetic code matches a phonetic stored in codes
			affixKeys = string_sub(v, 1, (string_find(v, "/") -1))
			pCode = string_sub(v, (string_find(v, "/") + 1))
			if codes[pCode] ~= nil then
				words = {}
				words = WordDict:ExpandWord(word, affixKeys)
				--add expanded words
				for expandedWord,v in pairs(words) do
					editDistance = WordDict:EditDistance(currentWord, expandedWord)
					tempSuggestion[expandedWord] = editDistance
				end
			end
		end
	end

	--Obtain additional suggestions

	--check if a char was typed in place of a replacementChar
	for sWord, editDistance in pairs(self:ReplaceChars(currentWord)) do
		tempSuggestion[sWord] = editDistance
	end

	--swap out each char on by one and try all the tryme
	--chars in htis' place to see if that makes a good word
	for sWord, editDistance in pairs(self:ReplaceChars(currentWord)) do
		tempSuggestion[sWord] = editDistance
	end

	--try ommitting one char of word at a time
	for sWord, editDistance in pairs(self:ExtraChar(currentWord)) do
		tempSuggestion[sWord] = editDistance
	end

	--try inserting a tryme character before every letter
	for sWord, editDistance in pairs(self:ForgotChar(currentWord)) do
		tempSuggestion[sWord] = editDistance
	end

	--split the string into two pieces after every char
	--if both pieces are good words mak them a suggestions
	for sWord, editDistance in pairs(self:TwoWords(currentWord)) do
		tempSuggestion[sWord] = editDistance
	end

	--try swapping adjcent chars on by one
	for sWord, editDistance in pairs(self:SwapChar(currentWord)) do
		tempSuggestion[sWord] = editDistance
	end


	--can't sort an associative table using table.sort
	--table.sort(tempSuggestion)

	local sorted = {}
	for w, d in pairs(tempSuggestion) do
		table_insert(sorted, {Word = w, EditDistance = d})
	end
	table.sort(sorted, function(A, B) return A.EditDistance < B.EditDistance end)

	--print("Sorted Table:")
	--tprint(sorted)

	WordDict.suggestions = {}


	for i, v in ipairs(sorted) do
		table_insert(WordDict.suggestions, {Word = v.Word, EditDistance = v.EditDistance})

		if #self.suggestions >= self.maxSuggestions then
			break
		end
	end

	return self.suggestions
end

function WordDict:Init()
	--Load the dict
	--If we don't have a languange specific dictionary, load the US English dictionary
	if GetLocale() == "deDE" then
		DICTIONARY_TO_LOAD_FROM = WordDict_GetDictionary_deDE()
	elseif GetLocale() == "esES" then
		DICTIONARY_TO_LOAD_FROM = WordDict_GetDictionary_esES()
	elseif GetLocale() == "enUS" then
		DICTIONARY_TO_LOAD_FROM = WordDict_GetDictionary_enUS()
	else
		DICTIONARY_TO_LOAD_FROM = WordDict_GetDictionary_enUS()
	end

	--set the dictionary functions to nil to free memory
	WordDict_GetDictionary_deDE = nil
	WordDict_GetDictionary_esES = nil
	WordDict_GetDictionary_enUS = nil


	--Load the tryChars
	self.tryChars = DICTIONARY_TO_LOAD_FROM.Try[1]

	--Load the replaceChars
	for i, v in ipairs(DICTIONARY_TO_LOAD_FROM.Replace) do
		table_insert(self.replaceChars, v)
	end

	--Load Affix Rules
	self:LoadPrefixRules()
	self:LoadSuffixRules()

	--Load Phonetic Rules
	self:LoadPhoneticRules()

	--Load the Base Words
	self:LoadWords()

	--Free the table we loaded the dictionary from
	DICTIONARY_TO_LOAD_FROM = nil

	--Collect Garbage to free up memory
	collectgarbage("collect")
end

---[[
--testing

function tprint (t, indent, done)
  -- in case we run it standalone
  local Note = Note or print
--  local Tell = Tell or io.write

  -- show strings differently to distinguish them from numbers
  local function show (val)
    if type (val) == "string" then
      return '"' .. val .. '"'
    else
      return tostring (val)
    end -- if
  end -- show
  -- entry point here
  done = done or {}
  indent = indent or 0
  for key, value in pairs (t) do
    print(string_rep (" ", indent)) -- indent it
    if type (value) == "table" and not done [value] then
      done [value] = true
      Note (show (key), ":");
      tprint (value, indent + 2, done)
    else
      print(show (key), "=")
      print (show (value))
    end
  end
end

--function GetLocale() return "deDE" end
function GetLocale() return "esES" end
--function GetLocale() return "enUS" end


--require("bit")
require("Dict\\Dic_deDE")
require("Dict\\Dic_enUS")
require("Dict\\Dic_esES")
WordDict:Init()
print(WordDict:Contains("tailoring"))
print("len:", #"hermanó")
print(WordDict:Contains("hermanó"))
print(WordDict:Contains("hermanos"))
tprint(WordDict:Suggest("hermanó"))

print("Memory:", collectgarbage("count"))
---]]
