-- vim: set filetype=terra tabstop=3 noexpandtab :miv --

local terra min3(a : int, b : int, c : int)
	if a < b and a < c then
		return a
	elseif b < c then
		return b
	else
		return c
	end
end

local function levenshtein_n(length)
	length = length + 1
	return terra(a : rawstring, b : rawstring)
		var _c : int8[length]; var c = &_c[0] -- Current
		var _p : int8[length]; var p = &_p[0] -- Previous

		for j=0, length do
			c[j] = (int8)(j) -- Distance of a to empty string
		end

		var i = 0
		while true do
			p,c = c,p

			if b[i]==0 then
				return p[length-1]
			end

			c[0] = i+1 -- Distance of b to empty string

			for j=1,length do
				var deletioncost     : int = p[j]+1
				var insertioncost    : int = c[j-1]+1
				var substitutioncost : int = p[j-1]
				if a[j-1] ~= b[i] then
					substitutioncost = substitutioncost + 1
				end
				c[j] = min3(deletioncost, insertioncost, substitutioncost)
			end

			i = i + 1
		end
	end
end

local levenshtein = setmetatable({}, {__index=function(self, key)
	if type(key)=='number' then
		key = math.floor(key)
		rawset(self, key, levenshtein_n(key))
		return rawget(self, key)
	elseif type(key)=='string' then
		local l = #key
		return function(other)
			return self[l](key, other)
		end
	end
end})

print(levenshtein.kitten "sitting")
print(levenshtein.Saturday "Sunday")