local CHUNK_SIZE = 20000

local function separateNumericAndTextPortions(str)
	local result = {}
	local i, count = 1, 0
	while i <= str:len() do
		local j = i
		if str:sub(i, i) == "-" and i < str:len() then
			i = i + 1
		end
		while i <= str:len() and tonumber(str:sub(i, i)) do
			i = i + 1
		end
		if i > j then
			local num = tonumber(str:sub(j, i - 1))
			table.insert(result, num)
			count = count + 1
		end
		j = i
		while i <= str:len() and not tonumber(str:sub(i, i)) do
			i = i + 1
		end
		if i > j then
			if str:sub(i - 1, i - 1) == "-" and i <= str:len() then
				i = i - 1
			end
			if i > j then
				table.insert(result, str:sub(j, i - 1))
				count = count + 1
			end
		end
	end

	return result
end

local metatable = {
	__index = function(tbl, key)
		tbl[key] = separateNumericAndTextPortions(key)
		return tbl[key]
	end
}

local cache = setmetatable({}, metatable)

local function numericTextSort(str1, str2)
	local tokens1, tokens2
	tokens1 = cache[str1]
	tokens2 = cache[str2]

	local len1, len2 = table.maxn(tokens1), table.maxn(tokens2)

	for i = 1, math.min(len1, len2) do
		if tokens1[i] < tokens2[i] then
			return true
		elseif tokens2[i] < tokens1[i] then
			return false
		end
	end

	return len1 < len2
end

local function mixedSort(e1, e2)
	if type(e1) == type(e2) then
		if type(e1) == "string" then
			return numericTextSort(e1, e2)
		end
		return e1 < e2
	end
	return type(e1) < type(e2)
end

local function output(str)
	if str then
		io.write(str)
	end
	io.write("\n")
end

local function quotedString(str)
	return string.gsub(string.format("%q", str), "\n", "n")
end

local keywords = {
	["and"] = true,
	["break"] = true,
	["do"] = true,
	["else"] = true,
	["elseif"] = true,
	["end"] = true,
	["false"] = true,
	["for"] = true,
	["function"] = true,
	["if"] = true,
	["in"] = true,
	["local"] = true,
	["nil"] = true,
	["not"] = true,
	["or"] = true,
	["repeat"] = true,
	["return"] = true,
	["then"] = true,
	["true"] = true,
	["until"] = true,
	["while"] = true,
}

local function varName(name)
	if type(name) == "number" then
		return string.format("[%d]", name)
	elseif type(name) == "string" then
		if name:find("^%a[%w_]+$") and not keywords[name] then
			return name
		else
			return string.format("[%s]", quotedString(name))
		end
	else
		return string.format("Unhandled name type: %q", type(name))
	end
end

function sort(tbl, name, indent, incremental)
	local indentStr
	if indent then
		indentStr = string.rep("\t", indent)
	else
		indent = 0
		indentStr = ""
	end

	local indexTable = {}
	for index, value in pairs(tbl) do
		table.insert(indexTable, index)
	end
	table.sort(indexTable, mixedSort)

	if #(indexTable) > CHUNK_SIZE then
		output(string.format("%s = {}", name))
		for i = 1, #(indexTable), CHUNK_SIZE do
			output(string.format("\nlocal function chunk%d()", math.ceil(i / 20000)))
			output(string.format("\tlocal t = %s\n", name))
			for j = i, i + CHUNK_SIZE - 1 do
				local index = indexTable[j]
				if not index then
					break
				end
				local value = tbl[index]
				if type(value) == "string" then
					output(string.format("%s\tt[%s] = %s,", indentStr, quotedString(index), quotedString(value)))
				elseif type(value) == "number" then
					value = string.gsub(string.format("%f", value), "%.?0+$", "")
					output(string.format("%s\tt[%s] = %s,", indentStr, quotedString(index), value))
				elseif type(value) == "table" then
					output(string.format("%s\tt[%s] = {", indentStr, quotedString(index)))
					sort(value, nil, indent + 1, true)
				elseif type(value) == "boolean" then
					output(string.format("%s\tt[%s] = %s,", indentStr, quotedString(index), value and "true" or "false"))
				else
					output(string.format("%s\tUnhandled value type: %q", indentStr, type(value)))
				end
			end
			output("end")
		end
		output()
		for i = 1, #(indexTable), CHUNK_SIZE do
			output(string.format("chunk%d()", math.ceil(i / 20000)))
		end
	else
		if not incremental then
			output(string.format("%s%s = {", indentStr, varName(name)))
		end

		for _, index in ipairs(indexTable) do
			local value = tbl[index]
			if type(value) == "string" then
				output(string.format("%s\t%s = %s,", indentStr, varName(index), quotedString(value)))
			elseif type(value) == "number" then
				value = string.gsub(string.format("%f", value), "%.?0+$", "")
				output(string.format("%s\t%s = %s,", indentStr, varName(index), value))
			elseif type(value) == "table" then
				sort(value, index, indent + 1)
			elseif type(value) == "boolean" then
				output(string.format("%s\t%s = %s,", indentStr, varName(index), value and "true" or "false"))
			else
				output(string.format("%s\tUnhandled value type: %q", indentStr, type(value)))
			end
		end
		if indent > 0 then
			if incremental then
				output(string.format("%s}", indentStr))
			else
				output(string.format("%s},", indentStr))
			end
		else
			output("}")
		end
	end
end