Module:family tree/nested data

---

The following documentation is located at Module:family tree/nested data/documentation. ^[edit]

Useful links: root page • root page’s subpages • links • transclusions • testcases • sandbox (diff)

Generates the data that is transformed into a tree by Module:family tree.

--[=[

Authors: [[User:kc_kennylau]], [[User:JohnC5]], [[User:Erutuon]], [[User:Suzukaze-c]], [[User:Theknightwho]]

--]=]
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[key] = true
			table.insert(result, key)
		end
	end
	
	table.sort(result, function(code1, code2)
		return names[code1] < names[code2]
	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

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:getCode()] = descendants_of:getProtoLanguageCode()
	end
	
	local memoized = {}
	local get = function(code, func, ...)
		local ret = memoized[code] or func(...)
		if code then
			memoized[code] = 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_code] = 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[parent:getCode()], descendant_code)
						break
					end
				end
				if #ancestors > 0 then
					for _, ancestor in ipairs(ancestors) do
						table.insert(children[ancestor], descendant_code)
					end
					break
				end
			else
				local protolang = descendant:getProtoLanguageCode()
				protolanguage_of[descendant_code] = protolang
				if protolang and descendant:hasAncestor(protolang) then
					table.insert(children[protolang], 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[family] then
					protolanguage_of[family] = protolang and protolang:getCode()
				end
				if protolang and protolang:inFamily(family) and protolang:getCode() ~= descendant_code then
					table.insert(children[protolang:getCode()], descendant_code)
				else
					table.insert(children[family:getCode()], 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[code] = children[code]
	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[val] then
				data[val] = make_nested(children[val], children)
				table.insert(make_nil, key)
			end
		else
			data[key] = make_nested(val, children)
		end
	end
	if make_nil[2] 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