local p = {}
local wikidata = require('Module:Wd:Wikidata')
-- generator, see http://lua-users.org/wiki/LuaCoroutinesVersusPythonGenerators for lua doc
-- definition a function that when called several times will generate a sequence of strings
 
-- gensymbols = create_gensymbols("ABC")
-- gensymbols() == "A" 
-- gensymbols() == "B" g
-- gensymbols() == "C" 
-- gensymbols() == "AA" '
-- gensymbols() == "BABBA"
-- ...
function p.gensymbols(chars)
	local i = 0
	local charset = chars
 
	local generator = function ()
		local symbol = ""
		local rest
 
		rest = i
 
		repeat
			local j 
			j = rest % string.len(charset)
			rest = math.floor(rest / string.len(charset))
			symbol = symbol .. string.sub(charset, j+1, j+1)
		until rest <= 0
		i = i + 1
		return symbol
	end
	return generator
end
 
---------------------------------------------------
 
--Only support items
function p.getPageName( id )
    if type( id ) == 'table' then
        return 'Q' .. id[2]
    else
        return id:upper()
    end
end
 
function p.children(query, itemId)
	mw.log(itemId)
    local childrens = {}
    local x = 1
    query.item = itemId
	local claims = wikidata.getClaims(query) 
	if not claims then
		return {}
	end
	for  _,claim in pairs( claims ) do
		local value = claim.mainsnak.datavalue.value
		local nextitem = 'Q' .. value['numeric-id']
		childrens[x] = nextitem
        x = x + 1
    end
 
    return childrens
end
 
function p.outputTree( query, firstItemId, maxdepth, itemOutput, lang )
		----- topological sort and meta data of the DAG ( https://en.wikipedia.org/wiki/Topological_sorting )
	function firstPass( query, firstItemId, item_repr )
		--while there are unmarked nodes do
		--    select an unmarked node n
		--    visit(n) 
		--function visit(node n)
		--    if n has a temporary mark then stop (not a DAG)
		--    if n is not marked (i.e. has not been visited yet) then
		--        mark n temporarily
		--        for each node m with an edge from n to m do
		--            visit(m)
		--        mark n permanently
		--        add n to head of L
 
	    local firstItem = mw.wikibase.getEntityObject(firstItemId)
	    local content = itemOutput( firstItem )
 
	    local opened = 1
	    local closed = 2
	    local incomplete = 3
 
	    local marks = {}
	    local datas = {}
		local childrens = {}
 
 
		function setdata(n, key, val)
			if datas[n] == nil then
				datas[n] = {}
			end
			datas[n][key] = val
		end
		function getdata(n, key, defval)
			if  datas[n] == nil or datas[n][key] == nil then
				return defval
			else
				return datas[n][key] 
			end
		end
 
		-- this function 
		-- * visits and builds the tree, DAG or graph,
		-- * in the same pass, computes a topological ordering for the DAG
		-- * annotates the nodes with informations
	    function visit(n, depth, rank)
	    	mw.log(	depth ..  ">=" .. maxdepth) 
 
			mw.log(n .. " " .. tostring(marks[n]))
			if marks[n] == opened then 
				setdata(n, "status", "loop")
				setdata(n, "rank", rank)
				return rank
			elseif marks[n] ~= closed then
				marks[n] = opened
 
				childrens[n] = p.children(query, n)
 
				for _, node in ipairs(childrens[n]) do
					setdata(node, "nparents", 
						getdata(node, "nparents", 0) + 1
					) 
					if depth <= maxdepth then
						rank = visit(node, depth + 1, rank + 1)
					end
				end
 
				if depth <= maxdepth then
					if getdata(n, "status", "complete") ~= "loop" then
						setdata(n, "status", "complete")
					end
					marks[n] = closed
				else
					setdata(n, "status", "incomplete")
					marks[n] = incomplete
				end
 
				setdata(n, "rank", rank)
			end
			return rank + 1
		end
		setdata(firstItemId, "nparents", 0)
		visit(firstItemId, 1, 0)
 
		return datas, childrens
	end

	local langobj = mw.language.new(lang)
	-- link inside tree 
	function formatSymbol(prefix)
		return '<span class="Unicode"><small>(' .. prefix .. ")</small></span>"
	end
	function genAnchor(id)
		return '<span id="' .. firstItemId .. id .. '"></span>' 
	end
	function anchorLink(id, content)
		return "[[#" .. firstItemId .. id .. "|" .. content .. "]]"
	end
	function fmtTreeLinks(content)
		return mw.text.tag("sup", {}, content)
	end
 
	function renderTree( itemId, datas, children, itemOutput, alreadyOuted, gs )
		local item = mw.wikibase.getEntityObject(itemId)
		local content = itemOutput( item )
		local state
 
		if datas[itemId]["status"] ~= nil then
			state = datas[itemId]["status"] 
		end
		mw.log(itemId .. " " .. state )
 
		if 	datas[itemId] ["nparents"] > 1 and datas[itemId]["symbol"] == nil then
			setdata(itemId, "symbol", gs() )
		end
		-- prevent infinite loops in non DAGs
		if state == "loop" then
			if datas[itemId]["looped"] == nil then
				datas[itemId]["looped"] = "treated"
				content =  fmtTreeLinks(" ∞") .. " " .. content .. genAnchor(itemId)
			else
				return content ..  fmtTreeLinks("∞" ..	" ↑ " .. anchorLink(itemId, formatSymbol( datas[itemId]["symbol"] )))
			end
		elseif state == "incomplete" or state == "unvisited" then
			content = content .. " " .. fmtTreeLinks("…")
			return content
		end
 
		-- has no chilren ? display as leaf
		if children[itemId] ~= nil and table.getn(children[itemId]) == 0 then
			return " " .. content .. " • " -- would be great to use "🍁", but font problem
		end
 
 
		datas[itemId] ["nparents"] = datas[itemId]["nparents"] - 1
 
	    local parts = {}
 
		-- sort children topologycally
		if alreadyOuted[itemId] == nil then
			order = children[itemId]
	    	table.sort(order, function (a, b) return datas[a]["rank"] < datas[b]["rank"] end )
 
		    for i, childId in ipairs(order) do
		        table.insert( parts, renderTree( childId, datas, children, itemOutput , alreadyOuted, gs ) )
		    end
 
 
		    local l = table.maxn( parts )
		    for i = 1,(l - 1) do
		        parts[i] = mw.text.tag( 'li', {}, parts[i] )
		    end
		    parts[l] = mw.text.tag( 'li', { class = 'lastline' }, parts[l] )
 			local langobj = mw.language.new(lang)
		    local prefix = " "
		    if datas[itemId] ["nparents"] > 0 then
		    	local arrow = langobj:getArrow()
		    	prefix = fmtTreeLinks(genAnchor(itemId) .. " " .. arrow .. " " .. formatSymbol(datas[itemId]["symbol"]))
	    	end
 
		    alreadyOuted[itemId] = prefix .. " " .. content  .. mw.text.tag( 'ul', {}, table.concat( parts ) )
		end
 
		if datas[itemId] ["nparents"] <= 0 or state == "loop" then
			return alreadyOuted[itemId]
		else 
			return content .. " " .. fmtTreeLinks(anchorLink(itemId, formatSymbol(datas[itemId]["symbol"])) .. " " .. langobj:getArrow(forward))
		end
	end
 
	-- gen = p.gensymbols("⦿⦾")
	-- gen = p.gensymbols("12")
	-- gen = p.gensymbols("★☆✴")
	gen = p.gensymbols("@*#") 
 
	local datas
	local children 
	datas, children = firstPass( query, firstItemId, gen)
	local alreadyOuted = {}
	rendering = {}
	return  renderTree( firstItemId, datas, children, itemOutput, alreadyOuted, gen)
end
 
 
function p.outputForest( query, firstItemsId, maxdepth, itemOutput, lang )
    local content = ''
    mw.log(maxdepth)
 
    for _, item in pairs( firstItemsId ) do
       content = content .. mw.text.tag( 'li', {}, p.outputTree( query, item, maxdepth, itemOutput, lang ) )
    end
    res =  mw.text.tag( 'div', { class = 'treeview' }, mw.text.tag( 'ul', {}, content ) )
    return res
    -- return ""
end

function p._outputTree(query, firstItemsId, maxdepth, lang, formatting)
	if not maxdepth then
		maxdepth = 10
	end
	query.excludespecial = true
	if tonumber(query.property) then --legacy format
		query.property = 'P'.. tostring(query.property)
	end
	local itemOutput
	if formatting and type(formatting) == 'function' then
		itemOutput = function( item ) return  formatting(item, lang) end
	elseif formatting and type(formatting) == 'table' then
		itemOutput = function(item) return mw.create.html('span'):css(formatting):wikitext(wikidata.formatEntity(item,{lang=lang})):done() end
	else
		itemOutput = function(item) return wikidata.formatEntity(item, {lang=lang}) end
	end
    return p.outputForest( query, firstItemsId, maxdepth, itemOutput, lang )
end

function p._familytree(item, lang, maxdepth)
	if not maxdepth then maxdepth = 3 end
	local birthvals = {}
	return p._outputTree( --query, firstItemsId, maxdepth, lang, formatting
		{ -- Define query
			property = 'P40', -- Property:Child
			sorttype = function(A, B) -- sort by birth Date 
				-- this is *memory* intensive there should be a way to desactive sorting above some number of nodes
				local personA, personB = wikidata.getmainid(A), wikidata.getmainid(B)
				local birthA, birthB = wikidata.getDate(personA), wikidata.getDate(personB)
				return wikidata.comparedate(birthA, birthB)
			end
		}, 
		{item},
		maxdepth,
		lang,
		function(item) -- Define displayformat
			local val =  wikidata.formatEntity(item, {lang=lang})
			local bgcolor = '#888888'
			local gender = wikidata._formatStatements{entity = item, property = 'P21', numval = 1, displayformat='raw', lang = lang}
			if gender == 'Q6581097' then
				bgcolor = '#006699'
			elseif gender == 'Q6581072' then
				bgcolor = '#990000'
			end
			if item.claims and item.claims.P569 and item.claims.P569[1].mainsnak.snaktype == 'value' then
				birthyear = item.claims.P569[1].mainsnak.datavalue.value
			end
			if item.claims and item.claims.P570 and item.claims.P570[1].mainsnak.snaktype == 'value' then
				deathyear = item.claims.P570[1].mainsnak.datavalue.value
			end

			if birthyear or deathyear then
				local daterange = require('Module:Wd:Daterange').compactdaterange({startpoint = birthyear, endpoint = deathyear}, lang)
				val = val .. ' ' .. require('Module:Wd:Linguistic').inparentheses(daterange,lang)
			end
			local desc = wikidata._formatStatements({entity = item, property = {'P39', 'P106'} , lang=lang}) or ''
			val = val .. ' <small>' .. desc .. '</small>'
			local val = mw.html.create('span')
				:css({ ['border-style'] = solid, ['border-width'] = medium}) --, ['background-color'] = bgcolor, ['color'] = '#FFF'
				:wikitext(val)
				:done()
			return tostring(val)
	end) 
end

function p.outputTreeFromTemplate( frame )
    local frame = frame:getParent()
    local query = frame.args
 
    local firstItemsId = mw.text.split( frame.args.items, ' ' )
    if table.maxn( firstItemsId ) == 0 then
        return 'No items passed as parameter'
    end
    if frame.args.recursion and frame.args.recursion ~= '' then
    	maxdepth = tonumber( frame.args.recursion )
    end
	if frame.args.lang and frame.args.lang ~= ''then
		lang = frame.args.lang
	else
		lang = frame:preprocess('{{CONTENTLANG}}')
	end
	return p._outputTree(query, firstItemsId, maxdepth, lang)
end

function p.familytree(frame)
	local lang = frame.args.lang
	if not lang or lang == '' then
		lang = frame:preprocess('{{CONTENTLANG}}')
	end
	return p._familytree(frame.args[1], lang, tonumber(frame.args.maxdepth))
end 
return p