Module:Tree
Jump to navigation
Jump to search
This module implements Template:Tree, please see the documentation there.
Code
local p = {}
--[[
-- External dependendies
--]]
local log = mw.log
local split = mw.text.split
local tag = mw.text.tag
local function getFrame(frame)
return frame or mw.getCurrentFrame()
end
local _IntLang -- internal cache, use the following accessor instead
local function getLang(frame)
local lang = frame.args.lang
if not lang or lang == '' then
if not _IntLang then
local ok
ok, _IntLang = frame and pcall(frame:preprocess('{{Int:Lang}}'))
if not ok or not _IntLang or _IntLang == '' then
_IntLang = 'en' -- safe default, don't recall preprocess
end
end
lang = _IntLang
end
return lang
end
local getEntityObject = mw.wikibase.getEntityObject -- getEntityObject(itemId) is a costly function call
local wikidata = require('Module:Wikidata')
local getClaims = wikidata.getClaims -- getClaims{item = itemId, options...} is a costly function call
local formatEntity = wikidata.formatEntity -- formatEntity(entity, {options...})
local _formatStatements = wikidata._formatStatements -- _formatStatements{entity = entity, options...}
local getmainid = wikidata.getmainid
local getDate = wikidata.getDate
local comparedate = wikidata.comparedate
local getLabel = require('Module:Wikidata label')._getLabel
local compactdaterange = require('Module:Daterange').compactdaterange
local inparentheses = require('Module:Linguistic').inparentheses
--[[
-- Internal implementation
--]]
-- Function that when called several times will generate a sequence of strings.
-- If g = generator('0', '1', '2'), then g() successively returns '0', '1', '2', '10', '11', '12', '20'...
-- See http://lua-users.org/wiki/LuaCoroutinesVersusPythonGenerators for lua doc.
local function Generator(...)
local SYMSET = type(...) == 'array' and ... or { ... }
local BASE = #SYMSET; assert(BASE > 1, 'not enough base symbols')
local INT, COUNT = math.floor, 0
return function()
local symbol, value = '', COUNT
COUNT = COUNT + 1
repeat
local quotient = INT(value / BASE)
symbol = SYMSET[value - quotient * BASE + 1] .. symbol
value = quotient
until value <= 0
return symbol
end
end
local function outputTree(query, rootItemId, maxdepth, lang, formatting)
-- Topological sort and meta data of the DAG (https://en.wikipedia.org/wiki/Topological_sorting)
-- while there are unmarked nodes do
-- select an unmarked node n
-- visit(n)
-- function visit(node n)
-- if n has a temporary opened mark then stop (not a DAG)
-- if n is not marked (i.e. has not been visited yet) then
-- mark n temporarily as opened
-- for each node m with an edge from n to m do
-- visit(m)
-- unmark n permanently
-- add n to head of L
local data, SYMBOL, NPARENTS, LOOP, DEEPEST = {}, 1, 2, 3, 4
local function setdata(itemId, key, val)
if data[itemId] == nil then data[itemId] = {} end
data[itemId][key] = val
end
local function getdata(itemId, key, defval)
return data[itemId] and data[itemId][key] or defval
end
maxdepth = maxdepth or 10
local children = {}
-- This function visits and builds the tree, DAG or graph, annotated by:
-- * deepest (depth of their deepest node, stopping at looping nodes or maxdepth)
-- * nparent (number of nodes pointing to it, for generating link symbols)
local visiting = {}
local function visit(itemId, depth) -- Recursive function
if visiting[itemId] then -- don't query children again, just adjust the deepest level
setdata(itemId, LOOP, true)
local deepest = getdata(itemId, DEEPEST, 0)
if depth > deepest then
deepest = depth
setdata(itemId, DEEPEST, deepest)
end
return deepest
end
-- This node may have already been visited from another parent (possibly as a LOOP or incomplete)
log(string.rep('│', depth - 2) .. (depth > 0 and '├' or '') .. '┐ visiting ' .. itemId .. ':')
visiting[itemId] = true
if children[itemId] then -- already visited and complete, just adjust the deepest level
local deepest = getdata(itemId, DEEPEST, 0)
if depth > deepest then
deepest = depth
setdata(itemId, DEEPEST, deepest)
end
elseif depth <= maxdepth then
-- first visit, query children, increment their number of parents
local childIds = {}
local deepest = getdata(itemId, DEEPEST, depth)
query.entity = itemId
local claims = getClaims(query) -- getClaims(query) is a costly call
if claims then
for _, claim in pairs(claims) do
local childId = 'Q' .. claim.mainsnak.datavalue.value['numeric-id']
table.insert(childIds, childId)
setdata(childId, NPARENTS, getdata(childId, NPARENTS, 0) + 1)
end
end
for _, childId in ipairs(childIds) do
local deep = visit(childId, depth + 1) -- visit() is recursive
if deep > deepest then
deepest = deep
end
end
setdata(itemId, DEEPEST, deepest)
children[itemId] = childIds
end -- else leave incomplete (childrens[itemId] remains nil)
log(string.rep('│', depth - 1) .. '┘')
visiting[itemId] = nil
return depth + 1
end
visit(rootItemId, 1) -- visit() is recursive
if type(formatting) ~= 'function' then
if type(formatting) == 'table' then
formatting = function(entity)
return tag('span', { style = formatting, }, formatEntity(entity, { lang = lang, }))
end
else
formatting = function(entity)
return formatEntity(entity, { lang = lang, })
end
end
end
local content = formatting(getEntityObject(rootItemId)) -- getEntityObject(itemId) is a costly call
local genSymbol = Generator(
'@', '#', '%', '+', '●', '¤', '§', '⁋', '¶', '†', '‡', '◊', '⋔', '℧', '∇', '❖', '⁂'
--[[these symbols have font/size problems (too small and difficult to distinguish, or too large, or not well supported)
, '*', ※', '⌘', '⦾', '⦿', '★', '☆', '✴'
]]
)
local function formatSymbol(symbol) -- link inside tree
return tag('bdi', { class = 'Unicode', }, tag('small', {}, '(' .. (symbol or 'missing symbol') .. ')'))
end
local function genAnchor(itemId)
return tag('i', { id = rootItemId .. itemId, }, '')
end
local function anchorLink(itemId, content)
return '[[#' .. rootItemId .. itemId .. '|' .. content .. ']]'
end
local function fmtTreeLinks(content)
return tag('sup', {}, content)
end
local alreadyOuted = {}
local arrow = mw.language.new(lang):getArrow()
local function renderTree(itemId) -- recursive function
local content = formatting(getEntityObject(itemId))
-- log('render ' .. itemId)
if getdata(itemId, NPARENTS, 0) > 1 and getdata(itemId, SYMBOL) == nil then
setdata(itemId, SYMBOL, genSymbol())
end
if getdata(itemId, LOOP) then
if getdata(itemId, LOOP) == true then
setdata(itemId, LOOP, 1) -- treated
content = fmtTreeLinks(' ∞') .. ' ' .. content .. genAnchor(itemId)
else
return content .. fmtTreeLinks('∞ ↑ ' .. anchorLink(itemId, formatSymbol(getdata(itemId, SYMBOL))))
end
end
local childIds = children[itemId]
if not childIds then
return content .. ' ' .. fmtTreeLinks('…') -- incomplete
end
local nChildIds = #childIds
if nChildIds == 0 then
-- has no children? display as leaf
return ' ' .. content .. ' ⊸ ' -- U+22B8: multijection symbol from maths, an horizontal stroke ended by a ring to the right
end
setdata(itemId, NPARENTS, getdata(itemId, NPARENTS, 0) - 1)
if not alreadyOuted[itemId] then
-- sort children topologycally
table.sort(childIds, function(a, b) return getdata(a, DEEPEST, 0) < getdata(b, DEEPEST, 0) end)
local childItems = {}
for i, childId in ipairs(childIds) do
table.insert(childItems,
tag('li', i == nChildIds and { class = 'lastline', } or {}, renderTree(childId))) -- renderTree() is recursive
end
alreadyOuted[itemId] =
(getdata(itemId, NPARENTS, 0) > 0 and
fmtTreeLinks(
genAnchor(itemId) ..
arrow --[[linked from up]] ..
formatSymbol(getdata(itemId, SYMBOL))
) .. ' '
or ''
) .. ' ' .. content .. tag('ul', {}, table.concat(childItems))
end
if getdata(itemId, NPARENTS, 0) > 0 then
return ' ' .. content .. ' ' ..
fmtTreeLinks(
anchorLink(itemId,
formatSymbol(getdata(itemId, SYMBOL)) ..
arrow --[[linked to down]]
)
)
end
return alreadyOuted[itemId]
end
return tag('li', {}, renderTree(rootItemId)) -- renderTree() is recursive
end
local treeviewStylesDone
local function treeviewStyles(frame)
frame = getFrame(frame)
if treeviewStylesDone or not frame then
return ''
end
treeviewStylesDone = true
return frame.extensionTag and frame:extensionTag('templatestyles', '', { src = 'Tree/styles.css', }) or ''
end
--[[
-- Exported functions
--]]
function p._outputForest(query, itemIds, maxdepth, styles, lang, formatting)
if tonumber(query.property) then --legacy format
query.property = 'P' .. tostring(query.property)
end
query.excludespecial = true
local trees = {}
for _, itemId in ipairs(itemIds) do
table.insert(trees, outputTree(query, itemId, maxdepth, lang, formatting))
end
return styles .. tag('div', { class = 'treeview', }, tag('ul', {}, table.concat(trees)))
end
function p.familytree(frame)
local lang = getLang(frame)
local treeStyle = treeviewStyles(frame)
local itemIds = split(frame.args[1], ' ')
if #itemIds == 0 then
return 'No items passed as parameter'
end
local recursion = tonumber(frame.args.maxdepth) or 3
local dates = {} -- cache for keeping the comparable date values below during sort
local query = {
property = 'P40', -- Property:Child
sorttype = function(entity1, entity2) -- sort by birth date
-- this is *memory* intensive there should be a way to desactive sorting above some number of nodes
if not dates[entity1] then
dates[entity1] = getDate(getmainid(entity1)) or ''
end
if not dates[entity2] then
dates[entity2] = getDate(getmainid(entity2)) or ''
end
if dates[entity1] == '' then
return false
elseif dates[entity2] == '' then
return true
else
return comparedate(dates[entity1], dates[entity2])
end
end,
}
local function formatting(entity)
local val = formatEntity(entity, { lang = lang, })
local birthyear
if entity.claims and entity.claims.P569 and entity.claims.P569[1].mainsnak.snaktype == 'value' then
birthyear = entity.claims.P569[1].mainsnak.datavalue.value
end
local deathyear
if entity.claims and entity.claims.P570 and entity.claims.P570[1].mainsnak.snaktype == 'value' then
deathyear = entity.claims.P570[1].mainsnak.datavalue.value
end
if birthyear or deathyear then
val = val .. ' ' inparentheses(
compactdaterange({ startpoint = birthyear, endpoint = deathyear, }, lang)
, lang)
end
local desc = _formatStatements{ entity = entity, lang = lang, property = { 'P39', 'P106' }, }
if desc then
val = val .. ' ' .. tag('small', {}, desc)
end
-- local gender = _formatStatements{ entity = entity, lang = lang, property = 'P21', numval = 1, displayformat = 'raw', }
return tag('span', {
--[==[
style = 'background:' .. (
--[[male]] gender == 'Q6581097' and '#069' or
--[[female]] gender == 'Q6581072' and '#900' or
--[[neutral]] '#888'
) .. 'color:#FFF;border:thin solid #AAA',
--]==]
}, val)
end
return p._outputForest(query, itemIds, recursions, treeStyle, lang, --[=[]=]formatting)
end
function p.outputTreeFromTemplate(frame)
local lang = getLang(frame)
local treeStyle = treeviewStyles(frame)
local query = frame.args
if not query or not query.items then
frame = frame.getParent and frame:getParent() or frame
query = frame.args
end
local itemIds = query and type(query.items) == 'string' and split(query.items, ' ') or {}
query.items = nil
if #itemIds == 0 then
return 'No items passed as parameter'
end
local recursion = tonumber(query.recursion) or 10
query.recursion = nil
local formatting = nil
if query.show_id then
formatting = function (entity)
return getLabel(entity, lang, 'wikidata', 'none', 1)
end
end
return p._outputForest(query, itemIds, recursion, treeStyle, lang, formatting)
end
return p