local p = {}

local scripts = mw.loadData("Module:scripts/data")

local function format(code)
	local name = scripts[code].canonicalName
	if not name:find("[Ss]script$") then
		name = name .. " script"
	end
	return "<code>[[:Category:" .. name .. "|" .. scripts[code].canonicalName .. " <span style=\"color:green;\">(" .. code .. ")</span>]]</code>"
end

local function dump(data, prefix)
	if type(data) == "string" then
		return format(data)
	else
		local result = ""
		local branch = "├───"
		local next_level = prefix .. "│    "
		local current = ""
		for i,val in ipairs(data) do
			if i == #data then
				branch = "└───"
				next_level = prefix .. "     "
			end
			if #val == 0 then
				result = result .. prefix .. branch .. dump(val.name) .. "<br/>"
			else
				result = result .. "{{(!}} class=mw-collapsible style=border-collapse:collapse\n{{!}}"
				result = result .. prefix .. branch .. dump(val.name)
				result = result .. "\n{{!-}}\n{{!}}"
				result = result .. dump(val, next_level)
				result = result .. "\n{{!)}}\n"
			end	
		end	
		return result
	end	
end

local function deep_sort(current)
	local result = {}
	local is_table = {}
	for key,val in pairs(current) do
		if type(key) == "number" then
			table.insert(result, val)
		else
			is_table[key] = true
			table.insert(result, key)
		end
	end
	
	table.sort(result, function(a,b)
		return (scripts[a] or error(a)).canonicalName < (scripts[b] or error(b)).canonicalName
	end)
	
	local i = 2
	while i<#result do
		while scripts[result[i-1]] == scripts[result[i]] do
			table.remove(result,i)
		end
		i = i + 1
	end
	
	for i=1,#result do
		if is_table[result[i]] then
			local name = result[i]
			result[i] = deep_sort(current[result[i]])
			result[i].name = name
		else
			result[i] = {name = result[i]}
		end
	end
	
	return result
end

function p.show(frame)
	local children = {}
	
	local function find_ancestors(origin,key,val)
		if val.parent then
			return {val.parent}
		end
	end
	
	for key,val in pairs(scripts) do
		local ancestors = find_ancestors(key,key,val)
		if ancestors then
			for _, ancestor in ipairs(ancestors) do
				if ancestor ~= key then
					if children[ancestor] then
						table.insert(children[ancestor], key)
					else
						children[ancestor] = {key}
					end
				end
			end
		end
	end
	
	local function make_nested(data)
		local make_nil = {}
		for key,val in pairs(data) do
			if type(key) == "number" then
				if children[val] then
					data[val] = make_nested(children[val])
					table.insert(make_nil, key)
					children[val] = nil
				end
			else
				data[key] = make_nested(val)
			end
		end
		for _,key in ipairs(make_nil) do
			data[key] = nil
		end
		return data
	end
	
	local nested = make_nested(children)
	
	nested = deep_sort(nested)
	
	local result = ""
	for i=1,#nested do
		result = result .. "\n\n\n{| class=mw-collapsible style=border-collapse:collapse\n|" .. format(nested[i].name) .. "\n|-\n|"
		result = result .. dump(nested[i], "  ")
		result = result .. "\n|}"
	end
	return frame:preprocess(result)
end

return p