Модул:family tree

--[=[

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

--]=]

local export = {}

local regular_languages = require("Модул:languages/code to canonical name")
local etymology_languages = require("Модул:etymology languages/code to canonical name")
local families = require("Модул:families/code to canonical name")

function export.find_subtree(t, code)
	for _, val in ipairs(t) do
		if val.name == code then -- "name" is really code
			return { val }
		else
			local result = export.find_subtree(val, code)
			if result then
				return result
			end
		end
	end
end

local family_icon = "F"
local etymology_language_icon = "E"
local proto_language_icon = family_icon
local family_with_proto_language_icon = family_icon
local function format_node(code, is_protolanguage_or_has_protolanguage)
	local canonical_name, category_name, class, icon, tooltip
	if regular_languages[code] then
		canonical_name = regular_languages[code]
		category_name = canonical_name .. ' језик'
		class = "familytree-lang"
		if is_protolanguage_or_has_protolanguage then
			class = class .. ' familytree-protolang'
			icon = proto_language_icon
		end
	elseif etymology_languages[code] then
		canonical_name = etymology_languages[code]
		class = "familytree-etymlang"
		icon = etymology_language_icon
		tooltip = "Etymology language"
	elseif families[code] then
		canonical_name = families[code]
		category_name = canonical_name .. " језици"
		class = "familytree-family"
		if is_protolanguage_or_has_protolanguage then
			class = class .. ' familytree-hasprotolang'
			icon = family_with_proto_language_icon
		else
			icon = family_icon
		end
		tooltip = "Језик фамилија"
	end
	
	return '<span class="' .. class .. '" '
		.. (tooltip and 'title="' .. tooltip .. '"' or '') .. '>'
		.. '[[:Категорија:' .. (category_name or canonical_name) .. '|'
		.. canonical_name
		.. ' <span class="familytree-code">(' .. code .. ')</span>]]'
		.. (icon and ' <span class="familytree-icon">' .. icon .. '</span>' or '')
		.. '</span>'
end

-- If neither options.show_all_families or options.show_etymology_languages is
-- falsy, then this function does nothing.
local function filter_nested_data(nested_data, options, protolanguage_of, is_protolanguage)
	if not nested_data then -- ???
		return nil
	else
		local name = nested_data.name
		local first_child = nested_data[1]
		
		-- This indicates that new_nested_data below should only be returned
		-- if it contains non-etymology languages.
		local check_for_non_etymology_children = false
		
		-- If `show_all_families` is false and this is a family and its only
		-- child is its proto-language, then replace the family with the
		-- proto-language.
		if options.hide_families_with_protolanguages and name and families[name]
		and first_child and not nested_data[2]
		and protolanguage_of[name] == first_child.name then
			is_protolanguage[first_child.name] = true
			return filter_nested_data(first_child, options, protolanguage_of, is_protolanguage)
		
		elseif options.hide_etymology_languages
		and etymology_languages[name] then
			if nested_data[1] then
				check_for_non_etymology_children = true
			else
				return nil
			end
		end
		
		local new_nested_data = { name = name }
		local i = 0
		for _, subtable in ipairs(nested_data) do
			subtable = filter_nested_data(subtable, options, protolanguage_of, is_protolanguage)
			if subtable then
				i = i + 1
				new_nested_data[i] = subtable
			end
		end
		
		if not check_for_non_etymology_children or new_nested_data[1] then
			return new_nested_data
		end
	end
end

local function make_node(code, is_protolanguage, protolanguage_of)
	return '</span> ' .. format_node(code,
		is_protolanguage[code] or protolanguage_of[code] ~= nil)
end

local function only_child_is_protolanguage(tree, options, protolanguage_of)
	return (options.family_under_protolanguage
		or options.protolanguage_under_family)
		and tree[1] and protolanguage_of[tree.name] == tree[1].name
end

export.are_all_children_etymology_languages = require "Модул:fun".memoize(function (nested_data)
	if not nested_data[1] then
		return nil
	end
	
	for _, child in ipairs(nested_data) do
		if not etymology_languages[child.name]
		or export.are_all_children_etymology_languages(child) == false then
			return false
		end
	end
	
	return true
end)

local customcollapsible_number = 0
local customcollapsible_prefix = "familytree"
local function get_customcollapsible_id()
	customcollapsible_number = customcollapsible_number + 1
	return customcollapsible_prefix .. customcollapsible_number
end

local no_break_space = "\194\160"
local level_separator = (no_break_space):rep(3)
local expandtext, collapsetext = "[+]─", "[-]┬"
local function make_tree(data, is_protolanguage, protolanguage_of, options, prefix)
	local result = {}
	local function ins(val)
		table.insert(result, val)
	end
	
	-- This tag is closed in the node generated by make_node.
	prefix = prefix or '<span class="familytree-linedrawing">'
	
	local branch = "├"
	local next_level = prefix .. "│" .. level_separator
	local length = #data
	for i, val in ipairs(data) do
		if i == length then
			branch = "└"
			next_level = prefix .. level_separator .. no_break_space
		end
		
		local code = val.name
		local language_or_family_node =
			make_node(code, is_protolanguage, protolanguage_of)
		
		if not val[1] then
			ins('<li>' .. prefix .. branch .. options.sterile_branch_text
				.. language_or_family_node .. '</li>')
		else
			local customcollapsible_id = get_customcollapsible_id()
			
			ins('<li>' .. prefix .. branch
				.. '<span class="familytree-toggle mw-customtoggle-'
				.. customcollapsible_id .. '">───┬</span>')
			
			-- name me!
			local flag = (options.family_under_protolanguage
				or options.protolanguage_under_family)
				and only_child_is_protolanguage(val, options, protolanguage_of)
			
			local top_node
			if flag then
				code = val[1].name
				val = val[1]
				
				top_node = make_node(code, is_protolanguage, protolanguage_of)
				if options.protolanguage_under_family then
					top_node, language_or_family_node =
						language_or_family_node, top_node
				end
			end
				
			local all_children_are_etymology_languages =
				export.are_all_children_etymology_languages(val)
			
			local collapsible_ul = '<ul class="mw-collapsible'
				.. (all_children_are_etymology_languages
					and ' familytree-only-etym-children'
					or '') .. '" '
				.. 'id="mw-customcollapsible-' .. customcollapsible_id
				.. '" data-expandtext="' .. expandtext
				.. '" data-collapsetext="' .. collapsetext .. '">'
			
			if flag then
				ins(top_node
					.. collapsible_ul .. '<li>' .. prefix
					.. (i == length and no_break_space or "│")
					.. level_separator .. "│")
			end
			
			ins(language_or_family_node)
			
			if not flag then
				ins(collapsible_ul)
			end
			
			-- Can't get default collapsibility script to apply the data-expandtext
			-- and data-collapsetext attribute values to the custom toggle,
			-- so have to have a custom script do it.
			ins(make_tree(val, is_protolanguage, protolanguage_of, options, next_level))
			ins('</ul></li>')
		end
	end
	return table.concat(result)
end

local function get_number_parameter_in_range(args, arg, low, high)
	local val = args[arg]
	
	if val == "" or val == nil then
		val = nil
	else
		val = tonumber(val)
		if not (type(val) == "number"
		and 0 <= val and val <= 6) then
			error("Expected nothing or number between " .. low .. " and "
				.. high .. " in parameter |" .. arg .. "=.")
		end
	end
	
	return val
end

function export.show(frame)
	local args = frame.args
	
	local descendants_of = args[1]
	
	local to_boolean = require("Модул:yesno")
	
	-- Determines whether families that have proto-languages will be shown.
	local show_all_families = to_boolean(args[2] or args.fam)
	
	-- Determines whether all etymology languages will be shown.
	local show_etymology_languages = to_boolean(args[3] or args.etym)
	
	-- help! parameter name too long!
	local sterile_branch_length = get_number_parameter_in_range(args, "sterile_branch_length", 0, 6)
	
	-- Determines whether (if all families are shown) a family will be shown
	-- on a line directly under and at the same level as its proto-language,
	-- or the proto-language on a line directly under and at the same level as
	-- its family.
	local family_under_protolanguage = to_boolean(args.famunderproto)
	local protolanguage_under_family = to_boolean(args.protounderfam)
	if family_under_protolanguage and protolanguage_under_family then
		error("Kindly choose between proto-language under family and family under proto-language.")
	end
	
	return export.print_children(descendants_of, {
		hide_families_with_protolanguages = not show_all_families,
		hide_etymology_languages = not show_etymology_languages,
		family_under_protolanguage = family_under_protolanguage,
		protolanguage_under_family = protolanguage_under_family,
		sterile_branch_length = sterile_branch_length,
		collapsed = require("Модул:yesno")(args.collapsed)
	})
end

function export.print_children(descendants_of, options)
	local m_languages = require("Модул:languages")
	local m_table = require("Модул:table")
	local make_auto_subtabler = require("Модул:auto-subtable")
	
	descendants_of = m_languages.getByCode(descendants_of, nil, true, true, true)
	
	local names = {}
	local protolanguage_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 "repeat until true" loop allows break to work like continue, as it will always only run once.
		repeat
			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
		until true
	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 parent_to_children_map = {}
	for _, code in ipairs(descendants) do
		parent_to_children_map[code] = children[code]
	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, function (a, b) return a > b end)
		end
		for _, key in ipairs(make_nil) do
			table.remove(data, key)
		end
		return data
	end
	
	local nested = make_nested(parent_to_children_map, parent_to_children_map)
	
	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
	
	nested = deep_sort(nested)
	
	data = { nested = nested, protolanguage_of = protolanguage_of }
	
	local nested_data, protolanguage_of = data.nested, data.protolanguage_of
	
	nested_data = export.find_subtree(nested_data, descendants_of:getCode())
	
	-- Return nil instead of a tree with only the root node.
	if options.must_have_descendants and (#nested_data == 0 or nested_data[1] and #nested_data[1] == 0) then
		return nil
	end
	
	local is_protolanguage = {}
	if options.hide_families_with_protolanguages or options.hide_etymology_languages then
		nested_data = filter_nested_data(nested_data, {
			hide_families_with_protolanguages = options.hide_families_with_protolanguages,
			hide_etymology_languages = options.hide_etymology_languages,
		}, protolanguage_of, is_protolanguage)
	end
	
	if not nested_data or not next(nested_data) then
		return nil
	end
	
	local result = {'<div class="familytree"><ul>'}
	local function ins(val)
		table.insert(result, val)
	end
	
	local tree_options = {
		sterile_branch_text = '<span class="familytree-branch">'
			.. ("─"):rep(options.sterile_branch_length or 4)
			.. '</span>',
		family_under_protolanguage = options.family_under_protolanguage,
		protolanguage_under_family = options.protolanguage_under_family,
	}
	
	local collapsetext, expandtext = 'Collapse', 'Expand'
	for i, subtable in ipairs(nested_data) do
		-- top language name
		ins('<li>')
		
		-- name me!
		local flag = (options.family_under_protolanguage
			or options.protolanguage_under_family)
			and only_child_is_protolanguage(subtable, options, protolanguage_of)
		local top_node = format_node(subtable.name)
		local next_node
		
		if flag then
			subtable = subtable[1]
			next_node = format_node(subtable.name)
			if options.family_under_protolanguage then
				top_node, next_node = next_node, top_node
			end
		end
		
		ins(top_node)
		
		-- top toggle
		local customcollapsible_id = get_customcollapsible_id()
		ins('<span class="familytree-toptoggle mw-customtoggle-'
				.. customcollapsible_id .. '" style="display: none;">')
		ins(options.collapsed and expandtext or collapsetext)
		ins('</span>')
		
		if flag then
			ins('<li>')
			ins(next_node)
		end
		
		-- tree
		ins('<ul class="mw-collapsible')
		if options.collapsed then
			ins(' mw-collapsed')
		end
		ins('" id="mw-customcollapsible-' .. customcollapsible_id)
		ins('" data-expandtext="' .. expandtext)
		ins('" data-collapsetext="' .. collapsetext .. '">')
		ins(make_tree(subtable, is_protolanguage, protolanguage_of, tree_options, nil))
		if flag then
			ins('</li>')
		end
		ins('</ul></li>')
	end
	
	ins('</ul></div>')
	ins(require("Модул:TemplateStyles")("Модул:family tree/style.css"))
	
	return table.concat(result)
end

return export