--!native
--!optimize 2
-- Compiled with roblox-ts v3.0.0
local TS = _G[script]
local CharAt = TS.import(script, script.Parent.Parent, "Utils", "CharAt")
local function DamerauLevenshteinDistanceScore(term, query)
	local m = #term
	local n = #query
	local _exp = table.create(m + 1, 0)
	-- ▼ ReadonlyArray.map ▼
	local _newValue = table.create(#_exp)
	local _callback = function()
		return table.create(n + 1, 0)
	end
	for _k, _v in _exp do
		_newValue[_k] = _callback(_v, _k - 1, _exp)
	end
	-- ▲ ReadonlyArray.map ▲
	local matrix = _newValue
	-- Initialize matrix
	do
		local i = 0
		local _shouldIncrement = false
		while true do
			if _shouldIncrement then
				i += 1
			else
				_shouldIncrement = true
			end
			if not (i <= m) then
				break
			end
			matrix[i + 1][1] = i
		end
	end
	do
		local j = 0
		local _shouldIncrement = false
		while true do
			if _shouldIncrement then
				j += 1
			else
				_shouldIncrement = true
			end
			if not (j <= n) then
				break
			end
			matrix[1][j + 1] = j
		end
	end
	do
		local i = 1
		local _shouldIncrement = false
		while true do
			if _shouldIncrement then
				i += 1
			else
				_shouldIncrement = true
			end
			if not (i <= m) then
				break
			end
			do
				local j = 1
				local _shouldIncrement_1 = false
				while true do
					if _shouldIncrement_1 then
						j += 1
					else
						_shouldIncrement_1 = true
					end
					if not (j <= n) then
						break
					end
					local cost = if CharAt(term, i - 1) == CharAt(query, j - 1) then 0 else 1
					matrix[i + 1][j + 1] = math.min(matrix[i][j + 1] + 1, matrix[i + 1][j] + 1, matrix[i][j] + cost)
					-- Check for transposition (Damerau extension)
					if i > 1 and j > 1 and CharAt(term, i - 1) == CharAt(query, j - 2) and CharAt(term, i - 2) == CharAt(query, j - 1) then
						matrix[i + 1][j + 1] = math.min(matrix[i + 1][j + 1], matrix[i - 1][j - 1] + 1)
					end
				end
			end
		end
	end
	return matrix[m + 1][n + 1]
end
return {
	DamerauLevenshteinDistanceScore = DamerauLevenshteinDistanceScore,
}