Module:family tree/nested data

--[=[

Authors: ], ], ], ], ]

--]=]
local export = {}
local m_languages = require("Module:languages")
local m_table = require("Module:table")

local make_auto_subtabler = require("Module:auto-subtable")

local names = {}

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 = true
			table.insert(result, key)
		end
	end
	
	table.sort(result, function(code1, code2)
		return names < names
	end)
	
	for i = 1, #result do
		if is_table] then
			local name = result
			result = deep_sort(current])
			result.name = name
		else
			result = { name = result }
		end
	end
	
	return result
end

local protolanguage_of = {}

local function make_parent_to_children_map(descendants_of)
	local children = make_auto_subtabler{}
	
	local descendants = descendants_of:getDescendantCodes()
	table.insert(descendants, descendants_of:getCode())
	
	if descendants_of:hasType("family") then
		protolanguage_of = descendants_of:getProtoLanguageCode()
	end
	
	local memoized = {}
	local get = function(code, func, ...)
		local ret = memoized or func(...)
		if code then
			memoized = ret
		end
		return ret
	end
	
	for _, descendant_code in ipairs(descendants) do
		-- Inner loop allows break to work like continue.
		for _, descendant_code in ipairs{descendant_code} do
			local descendant = get(descendant_code, m_languages.getByCode, descendant_code, nil, true, true, true)
			names = descendant:getCanonicalName():gsub("Proto%-", "")
			if descendant:hasType("language") then
				local ancestors = m_table.shallowcopy(descendant:getAncestorCodes())
				local parent_code = descendant:getParentCode()
				if parent_code and descendant:hasType("etymology-only") then
					local parent = get(parent_code, descendant.getParent, descendant)
					if m_table.deepEquals(parent:getAncestorCodes(), ancestors) and
						descendant:getFamilyCode() == parent:getFamilyCode() then
						table.insert(children, descendant_code)
						break
					end
				end
				if #ancestors > 0 then
					for _, ancestor in ipairs(ancestors) do
						table.insert(children, descendant_code)
					end
					break
				end
			else
				local protolang = descendant:getProtoLanguageCode()
				protolanguage_of = protolang
				if protolang and descendant:hasAncestor(protolang) then
					table.insert(children, descendant_code)
					break
				end
			end
			local family_code = descendant:getFamilyCode()
			if family_code then
				local family = get(family_code, descendant.getFamily, descendant)
				local protolang = get(family:getProtoLanguageCode(), family.getProtoLanguage, family)
				if not protolanguage_of then
					protolanguage_of = protolang and protolang:getCode()
				end
				if protolang and protolang:inFamily(family) and protolang:getCode() ~= descendant_code then
					table.insert(children, descendant_code)
				else
					table.insert(children, descendant_code)
				end
			end
		end
	end
	
	-- No more auto subtabling needed.
	children = children:un_auto_subtable()
	
	-- Copy to new table, to filter out unwanted ancestors from descendants with multiple ancestors, where some are not descendants of the target language.
	local true_children = {}
	for _, code in ipairs(descendants) do
		true_children = children
	end
	
	return true_children
end

local function reverse_comp(a, b)
	return a > b
end

local function make_nested(data, children)
	local make_nil = {}
	for key, val in pairs(data) do
		if type(key) == "number" then
			if children then
				data = make_nested(children, children)
				table.insert(make_nil, key)
			end
		else
			data = make_nested(val, children)
		end
	end
	if make_nil then -- Make sure larger keys are removed first.
		table.sort(make_nil, reverse_comp)
	end
	for _, key in ipairs(make_nil) do
		table.remove(data, key)
	end
	return data
end

function export.main(descendants_of)
	descendants_of = m_languages.getByCode(descendants_of, nil, true, true, true)
	
	local parent_to_children_map = make_parent_to_children_map(descendants_of)
	
	local nested = make_nested(parent_to_children_map, parent_to_children_map)
	
	nested = deep_sort(nested)
	
	return { nested = nested, protolanguage_of = protolanguage_of }
end

return export