Модуль:Wikidata/FamilyTree

Пример вызова:

Всеволод Юрьевич Большое Гнездо

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q348689}}

Лотарь I

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q150735}}

София Николаевна Меренберг

Дерево по умолчанию

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q63012}}

Горизонтальное дерево

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q63012|mode=horizontal}}

Глубокое дерево

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q63012|descendants=6|ancestors=6}}

Митридат VI

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q185126|ancestors=4|descendants=0}}

Путин

Дерево по умолчанию

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q7747}}

Глубокое дерево

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q7747|descendants=9|ancestors=9}}

Пушкин

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q7200}}

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q7200|descendants=9|ancestors=9}}

Сталин

• {{#invoke:Wikidata/FamilyTree|drawTree|entityId=Q855|descendants=9|ancestors=9}}

---

local p = {};

local ELEMENT_WIDTH = 5;
local ELEMENT_HEIGHT = 5;
local DEFAULT_MODE = "vertical"; -- horizontal
local DEFAULT_DECORATE = "none"; -- by-generation

local BUSY = 'X';

local EMPTY_TABLE = {};

local MISSING_LABEL_LINK = function( entityId )
	return '[[:d:' .. entityId .. '|' .. entityId .. ']]<span style="border-bottom: 1px dotted; cursor: help; white-space: nowrap" title="В Тептар-данных нет подписи к элементу. Вы можете помочь, указав вариант подписи.">?</span>';
end
local RED_LINK_F = function( entityId, label )
	local templateText = "{{Универсальная карточка|" .. entityId .. "}}%0A'''" .. label .. "''' — %0A%0A== Примечания ==%0A{{примечания}}%0A";
	local templateText = templateText .. "[[Категория:Тептар:Карточки с явно указанным элементом Тептар-данных|" .. entityId .. "]]";
	local preloadUrl = tostring( mw.uri.canonicalUrl( label, 'action=edit&preload=Ш:Preload/Тептар-данные&preloadparams[]=' .. templateText ));
	local redLink = mw.getCurrentFrame():expandTemplate{ title='цветная ссылка', args = { '#ba0000', preloadUrl, label }};
	return '<span class="plainlinks">' .. redLink .. '</span><sup>[[:d:' .. entityId .. '|[d]]]</sup>';
end

local function copyTo( obj, target, skipEmpty )
	for k, v in pairs( obj ) do
		if skipEmpty ~= true or ( v ~= nil and v ~= '' ) then
			target[k] = v;
		end
	end
	return target;
end

local function expectString( var, name )
	if (type(var) ~= 'string') then
		error("Expected string but have " .. type(var) .. " of argument " .. name);
	end
end

local function getEntityIdsFromClaims( claims )
	if ( claims == nil ) then return EMPTY_TABLE end
	local result = {};
	for _, claim in pairs( claims ) do
		local id = (((claim.mainsnak or EMPTY_TABLE).datavalue or EMPTY_TABLE).value or EMPTY_TABLE).id or nil;
		if ( id ~= nil ) then
			result[id] = id;
		end
	end
	return result;
end

local function createNode( entityId, generation )
	expectString( entityId, "entityId" );

	local node = {};
	node.entityId = entityId;
	node.generation = generation;
	return node;
end

local function populateRelation( relationType, propertyId, line, node, newGeneration )
	expectString( relationType, "relationType" );
	expectString( propertyId, "propertyId" );

	local relativesIds = getEntityIdsFromClaims( mw.wikibase.getBestStatements( node.entityId, propertyId ) );

	local propertyKey = relationType .. 'Nodes';
	for _, relativeId in pairs( relativesIds ) do
		if ( node[propertyKey] == nil ) then node[propertyKey] = {} end

		local relativeNode = createNode( relativeId, newGeneration );
		table.insert( line, relativeNode );
		table.insert( node[propertyKey], relativeNode );
	end
end

local function max( a, b )
	return a > b and a or b;
end
local function min( a, b )
	return a < b and a or b;
end

local function copyRendered( src, dst, dstPosX, dstPosY, width, height )
	if ( #src < height ) then error( "Need " .. (height) .. " lines in src; have only " .. #src ); end
	if ( #dst < dstPosY + height - 1 ) then error( "Need " .. (dstPosY + height - 1) .. " lines in dst; have only " .. #dst ); end

	for y=1, height do
		local srcLine = src[ y ];
		local dstLine = dst[ dstPosY + y - 1 ];
		for x=1, width do
			local newValue = srcLine[ x ];
			if (newValue ~= nil) then
				dstLine[ dstPosX + x - 1 ] = newValue;
			end
		end
	end
end

function willOverride( src, dst, dstPosX, dstPosY, width, height )
	for y=1, height do
		local srcLine = src[ y ];
		local dstLine = dst[ dstPosY + y - 1 ];
		if ( srcLine == nil ) then error( "Missing line " .. y .. " in src" ); end
		if ( dstLine == nil ) then error( "Missing line " .. ( dstPosY + y - 1 ) .. " in dst" ); end
		for x=1, width do
			local hasInSrc = srcLine[ x ] ~= nil;
			local hasInDst = dstLine[ dstPosX + x - 1 ] ~= nil;
			if ( hasInSrc and hasInDst ) then
				return true;
			end
		end
	end
	return false;
end

function p.generateLineUp( )
	local result = '{';
	for i1, n in ipairs( {false, true} ) do
		for i2, e in ipairs( {false, true} ) do
			for i3, s in ipairs( {false, true} ) do
				for i4, w in ipairs( {false, true} ) do
					if ( n or e or s or w ) then
						local srcVarName = ( n and 'N' or '') .. ( e and 'E' or '') .. ( s and 'S' or '') .. ( w and 'W' or '');
						local dst = 'N' .. ( e and 'E' or '') .. ( s and 'S' or '') .. ( w and 'W' or '');
						result = result .. srcVarName .. '="' .. dst .. '",';
					end
				end
			end
		end
	end
	return result .. '}';
end

local APPEND_LINE_UP = {W="NW",S="NS",SW="NSW",E="NE",EW="NEW",ES="NES",ESW="NESW",N="N",NW="NW",NS="NS",NSW="NSW",NE="NE",NEW="NEW",NES="NES",NESW="NESW",};

function p.generateLineDown( )
	local result = '{';
	for i1, n in ipairs( {false, true} ) do
		for i2, e in ipairs( {false, true} ) do
			for i3, s in ipairs( {false, true} ) do
				for i4, w in ipairs( {false, true} ) do
					if ( n or e or s or w ) then
						local srcVarName = ( n and 'N' or '') .. ( e and 'E' or '') .. ( s and 'S' or '') .. ( w and 'W' or '');
						local dst = ( n and 'N' or '') .. ( e and 'E' or '') .. 'S' .. ( w and 'W' or '');
						result = result .. srcVarName .. '="' .. dst .. '",';
					end
				end
			end
		end
	end
	return result .. '}';
end

local APPEND_LINE_DOWN = {W="SW",S="S",SW="SW",E="ES",EW="ESW",ES="ES",ESW="ESW",N="NS",NW="NSW",NS="NS",NSW="NSW",NE="NES",NEW="NESW",NES="NES",NESW="NESW",};

function findFirstIndex( arr, length )
	for i=1, length do
		if ( arr[i] ~= nil ) then
			return i;
		end
	end
	error('first element not found');
end

function findLastIndex( arr, length )
	for i=length,1,-1 do
		if ( arr[i] ~= nil ) then
			return i;
		end
	end
	error('last element not found');
end

local function parentsAreSame( node1, node2 )
	if (not node1.parentNodes) then return false; end
	if (not node2.parentNodes) then return false; end

	local firstGrandParentCount = 0;
	local firstGrandParentIds = {};
	for _, grandParent in pairs( node1.parentNodes ) do
		firstGrandParentIds[ grandParent.entityId ] = true;
		firstGrandParentCount = firstGrandParentCount + 1;
	end

	if ( firstGrandParentCount ~= #node2.parentNodes ) then
		return false
	end
	for _, grandParent in pairs( node2.parentNodes ) do
		if ( not firstGrandParentIds[ grandParent.entityId ] ) then
			return false;
		end
	end

	return true;
end

local function putEntity( result, yStart, xStart, node )
	for y=yStart, yStart + ELEMENT_HEIGHT - 1 do
		for x=xStart, xStart + ELEMENT_WIDTH - 1 do
			result[y][x] = BUSY;
		end
	end
	result[yStart][xStart] = {
		entityId = node.entityId,
		generation = node.generation
	};
end

local function renderSingle( node, connectToFirstLine )
	node.resultWidth = ELEMENT_WIDTH;
	node.resultHeight = ELEMENT_HEIGHT;
	node.renderResult = {};
	for y=1,ELEMENT_HEIGHT do node.renderResult[y] = {}; end
	putEntity( node.renderResult, 1, 1, node );
	node.lineConnectionY = connectToFirstLine and 1 or ELEMENT_HEIGHT;
	node.lineConnectionX = math.ceil( ELEMENT_WIDTH / 2 );
end

local renderWithParents;
local renderInterleaveWithParents;

local function renderFakeParentsNodeWithoutChild( options, parentNodes, leftParentTailOnly, rightParentTailOnly )
	-- fake node
	local node = {};
	local lineStartConnectFrom = 99999;
	local lineEndConnectTo = 0;

	local resultWidth = 0; -- self
	local resultHeight = 0;

	local commonParentsResult = nil;
    -- we shall not interleave different incests... in can be bad, in all sences
	if ( not options.interleave and leftParentTailOnly == nil and rightParentTailOnly == nil ) then
		-- check if right corner of left parent is the same as left corner of right parent
	    if (#parentNodes == 2) then
	    	local leftRoot = parentNodes[1];
	    	local rightRoot = parentNodes[2];
	    	while (leftRoot ~= nil and rightRoot ~= nil) do
	    		if (parentsAreSame( leftRoot, rightRoot )) then
	    			leftParentTailOnly = leftRoot.entityId;
	    			rightParentTailOnly = rightRoot.entityId;
	    			commonParentsResult = renderFakeParentsNodeWithoutChild( options, leftRoot.parentNodes, nil, nil );
	    			break;
	    		end
	    		if (leftRoot.parentNodes ~= nil and #leftRoot.parentNodes ~= 0) then
	    			leftRoot = leftRoot.parentNodes[ #leftRoot.parentNodes ];
	    		else
	    			leftRoot = nil;
	    		end
	    		if (rightRoot.parentNodes ~= nil and #rightRoot.parentNodes ~= 0) then
	    			rightRoot = rightRoot.parentNodes[1];
	    		else
	    			rightRoot = nil;
	    		end
	    	end
	    end
    end

	for _, parentNode in pairs( parentNodes ) do
		if ( options.interleave ) then
			renderInterleaveWithParents( options, parentNode );
		else
			if (commonParentsResult == nil) then
				local parentLeftParentTailOnly = nil;
				local parentRightParentTailOnly = nil;
				if ( _ == 1 ) then parentLeftParentTailOnly = leftParentTailOnly; end;
				if ( _ == #parentNodes ) then parentRightParentTailOnly = rightParentTailOnly; end;
				renderWithParents( options, parentNode, parentLeftParentTailOnly, parentRightParentTailOnly );
			else
				local parentLeftParentTailOnly = nil;
				local parentRightParentTailOnly = nil;
				if ( _ == #parentNodes ) then parentLeftParentTailOnly = rightParentTailOnly; end;
				if ( _ == 1 ) then parentRightParentTailOnly = leftParentTailOnly; end;
				renderWithParents( options, parentNode, parentLeftParentTailOnly, parentRightParentTailOnly );
			end
		end
		resultHeight = max( resultHeight, parentNode.resultHeight );
	end
	resultHeight = resultHeight + 1; -- lines

	local result = {};
	for y=1,resultHeight do result[y]={} end;

	local commonParentsHorPosition = nil;
	local commonParentsVerPosition = nil;
	local verPositions = {};
	local horPositions = {};
	for _, parentNode in pairs( parentNodes ) do
		local mergeTailsHere = _ == 2 and commonParentsResult ~= nil;
		if (mergeTailsHere) then
			commonParentsHorPosition = resultWidth + 2;

			-- need to find connection points of tails in parents
			if ( parentNodes[1].resultTails == nil ) then error("Need parent tails to present in left parent result") end;
			if ( parentNodes[2].resultTails == nil ) then error("Need parent tails to present in right parent result") end;
			local tailY = parentNodes[1].resultTails[ leftParentTailOnly ].y + ( horPositions[1] - 1 );
			commonParentsVerPosition = tailY - commonParentsResult.resultHeight - 1;

			while ( commonParentsHorPosition > 4 ) do
				if ( willOverride( commonParentsResult.renderResult, result, commonParentsHorPosition - 2, commonParentsVerPosition, commonParentsResult.resultWidth, commonParentsResult.resultHeight ) ) then
					break;
				end
				commonParentsHorPosition = commonParentsHorPosition - 1;
			end

			copyRendered( commonParentsResult.renderResult, result, commonParentsHorPosition, commonParentsVerPosition, commonParentsResult.resultWidth, commonParentsResult.resultHeight );
			resultWidth = max( resultWidth, commonParentsHorPosition + commonParentsResult.resultWidth - 1 );
		end

		-- position by horizontal of current element
		local blockPosition = _ ~= 1 and resultWidth + 2 or 1;
		local parentStartLine = resultHeight - 1 - parentNode.resultHeight + 1;

		-- check if we have empty space in result to shift parent block to left
		while ( blockPosition > 2 ) do
			if ( not willOverride( parentNode.renderResult, result, blockPosition - 2, parentStartLine, parentNode.resultWidth, parentNode.resultHeight ) ) then
				blockPosition = blockPosition - 1;
			else
				break;
			end
		end

		horPositions[_] = blockPosition;
		verPositions[_] = parentStartLine;

		local parentWidth = parentNode.resultWidth;
		local parentHeight = parentNode.resultHeight;

		-- define how parent horizontal line need to be drawn
		lineStartConnectFrom = min( lineStartConnectFrom, blockPosition + parentNode.lineConnectionX - 1 )
		lineEndConnectTo = max( lineEndConnectTo, blockPosition + parentNode.lineConnectionX - 1 )

		resultWidth = max( resultWidth, blockPosition + parentNode.resultWidth - 1 );
		copyRendered( parentNode.renderResult, result, blockPosition, parentStartLine, parentNode.resultWidth, parentNode.resultHeight )

		if ( parentNode.resultTails ~= nil ) then
			if ( node.resultTails == nil) then node.resultTails = {}; end;
			for tailId, resultTail in pairs( parentNode.resultTails ) do
				node.resultTails[ tailId ] = { x = blockPosition + resultTail.x - 1, y = parentStartLine + resultTail.y - 1 };
			end
		end
	end
	node.resultWidth = resultWidth;
	node.resultHeight = resultHeight;

	-- connect tails of left and right tree with common parents part
	if ( commonParentsResult ~= nil ) then
		local x1 = parentNodes[1].resultTails[leftParentTailOnly].x + ( horPositions[1] - 1 );
		local x2 = parentNodes[2].resultTails[rightParentTailOnly].x + ( horPositions[2] - 1 );

		local y1 = parentNodes[1].resultTails[leftParentTailOnly].y + ( verPositions[1] - 1 );
		local y2 = parentNodes[2].resultTails[rightParentTailOnly].y + ( verPositions[2] - 1 );

		if ( y1 ~= y2 ) then
			mw.log( 'different vertical positions of parent tails in tree:' .. y1 .. ' vs ' .. y2 );
		else
			result[y1][x1]='ES';
			for x=(x1 + 1),(x2 - 1) do
				result[y1][x] = "EW";
			end
			result[y1][x2]='SW';
		end

		local lineConnectionX = commonParentsResult.lineConnectionX + commonParentsHorPosition - 1;
		local lineConnectionY = commonParentsResult.lineConnectionY + commonParentsVerPosition - 1;
		result[lineConnectionY][lineConnectionX] = 'ESW';

		if ( x1 > lineConnectionX or x2 < lineConnectionX ) then
			local center = x1 + math.floor((x2 - x1) / 2);
			local from = min( center, lineConnectionX );
			local to = max( center, lineConnectionX );
			result[lineConnectionY+1][from] = "E";
			for x=(from + 1),(to - 1) do
				result[lineConnectionY+1][x] = "EW";
			end
			result[lineConnectionY+1][to] = "W";

			result[lineConnectionY+0][lineConnectionX] = APPEND_LINE_DOWN[ result[lineConnectionY+0][lineConnectionX] ];
			result[lineConnectionY+1][lineConnectionX] = APPEND_LINE_UP[ result[lineConnectionY+1][lineConnectionX] ];
			result[lineConnectionY+1][center] = APPEND_LINE_DOWN[ result[lineConnectionY+1][center] ];
			result[lineConnectionY+2][center] = APPEND_LINE_UP[ result[lineConnectionY+2][center] ];
		else
			result[lineConnectionY+1][lineConnectionX] = 'NS';
			result[lineConnectionY+2][lineConnectionX] = APPEND_LINE_UP[ result[lineConnectionY+2][lineConnectionX] ];
		end
	end

	-- local center = math.ceil( resultWidth / 2 );
	local center = lineStartConnectFrom + math.floor((lineEndConnectTo - lineStartConnectFrom) / 2);
	if ( center < 3 ) then error( "center < 3" ) end

	lineStartConnectFrom = min( lineStartConnectFrom , center );
	lineEndConnectTo = max( lineEndConnectTo , center );

	-- shift child a bit to center of line
	if ( center == lineStartConnectFrom and lineEndConnectTo - lineStartConnectFrom >= 2 ) then center = center + 1; end
	if ( center == lineEndConnectTo and lineEndConnectTo - lineStartConnectFrom >= 2 ) then center = center - 1; end
	if ( center < 3 ) then error( "center < 3" ) end

	local parentConnectionLine = resultHeight;

	-- draw parent connection line
	if ( lineStartConnectFrom == lineEndConnectTo) then
		result[parentConnectionLine][lineStartConnectFrom] = "NS";
	else
		result[parentConnectionLine][lineStartConnectFrom] = "E";
		for x=(lineStartConnectFrom + 1),(lineEndConnectTo - 1) do
			result[parentConnectionLine][x] = "EW";
		end
		result[parentConnectionLine][lineEndConnectTo] = "W";
	end

	-- draw line up to parents
	for _, parentNode in pairs( parentNodes ) do
		local parentConnectionIndex = horPositions[_] - 1 + parentNode.lineConnectionX;
		result[parentConnectionLine][parentConnectionIndex] = APPEND_LINE_UP[ result[parentConnectionLine][parentConnectionIndex] ];
	end

	node.renderResult = result;
	node.lineConnectionY = resultHeight;
	node.lineConnectionX = center;
	return node;
end

renderWithParents = function( options, node, leftParentTailOnly, rightParentTailOnly )
	if ( not node.parentNodes or #node.parentNodes == 0) then
		renderSingle( node, true );
		return;
	end

	local fakeParentsNode = renderFakeParentsNodeWithoutChild( options, node.parentNodes, leftParentTailOnly, rightParentTailOnly );
	local center = fakeParentsNode.lineConnectionX;
	
	local resultWidth = fakeParentsNode.resultWidth;
	local resultHeight = fakeParentsNode.resultHeight + 2 + ELEMENT_HEIGHT;
	local result = {};
	for y=1,resultHeight do result[y]={} end;

	local parentConnectionLine = fakeParentsNode.resultHeight;

	if ( node.entityId ~= leftParentTailOnly and node.entityId ~= rightParentTailOnly ) then
		copyRendered( fakeParentsNode.renderResult, result, 1, 1, fakeParentsNode.resultWidth, fakeParentsNode.resultHeight )
		node.resultTails = fakeParentsNode.resultTails;

		-- draw line down to child
		result[parentConnectionLine][center] = APPEND_LINE_DOWN[ result[parentConnectionLine][center] ];
		result[parentConnectionLine + 1][center] = "NS";
		result[parentConnectionLine + 2][center] = "N";
	else
		if ( node.resultTails == nil ) then node.resultTails = {}; end
		node.resultTails[ node.entityId ] = { x = center, y = parentConnectionLine + 2};
	end

	node.resultWidth = resultWidth;
	node.resultHeight = resultHeight;

	-- line to child
	result[parentConnectionLine + 2][center] = APPEND_LINE_DOWN[ result[parentConnectionLine + 2][center] ] or 'S';
	putEntity( result, parentConnectionLine + 3, center - math.floor( ELEMENT_WIDTH / 2 ), node );

	node.renderResult = result;
	node.lineConnectionY = resultHeight;
	node.lineConnectionX = center;
end

renderInterleaveWithParents = function( options, node )
	local hasFathers = node.fatherNodes and #node.fatherNodes > 0;
	local hasMothers = node.motherNodes and #node.motherNodes > 0;

	if ( (not hasFathers) and (not hasMothers) ) then
		renderSingle( node, true );
		return;
	end

	local renderHeight = ELEMENT_HEIGHT;
	local renderWidth = ELEMENT_WIDTH;

	local fakeFatherNode;
	local heightWithFathers = ELEMENT_HEIGHT;
	local widthOfFathers = 0

	if ( hasFathers ) then
		fakeFatherNode = renderFakeParentsNodeWithoutChild( options, node.fatherNodes, EMPTY_TABLE );
		heightWithFathers = fakeFatherNode.resultHeight + 2;
		widthOfFathers = fakeFatherNode.resultWidth + 1;
	end

	local fakeMotherNode;
	local heightWithMothers = ELEMENT_HEIGHT;
	local widthOfMothers = 0

	if ( hasMothers ) then
		fakeMotherNode = renderFakeParentsNodeWithoutChild( options, node.motherNodes, EMPTY_TABLE );
		heightWithMothers = fakeMotherNode.resultHeight + 2;
		widthOfMothers = fakeMotherNode.resultWidth + 1;
	end

	local resultHeight = max( heightWithFathers, heightWithMothers );
	local resultWidth = widthOfFathers + ELEMENT_WIDTH + widthOfMothers;

	local result = {};
	for y=1,resultHeight do result[y]={} end;

	if ( hasFathers ) then
		local fathersX = 1;
		local fathersY = resultHeight - heightWithFathers + 1;
		copyRendered( fakeFatherNode.renderResult, result, fathersX, fathersY, fakeFatherNode.resultWidth, fakeFatherNode.resultHeight );

		-- draw line
		local lineY = fathersY + fakeFatherNode.resultHeight;
		local lineStart = fakeFatherNode.lineConnectionX;
		local lineEnd = fakeFatherNode.resultWidth + 1;
		result[lineY][lineStart] = "NE";
		for x=(lineStart+1),lineEnd do
			result[lineY][x] = "EW";
		end
		result[lineY - 1][lineStart] = APPEND_LINE_DOWN[ result[lineY - 1][lineStart] ]
	end

	local selfX = hasFathers and (widthOfFathers + 1) or 1;
	local selfY = resultHeight - ELEMENT_HEIGHT + 1;
	putEntity( result, selfY, selfX, node );

	if ( hasMothers ) then
		local mothersX = selfX + ELEMENT_WIDTH + 1;
		local mothersY = resultHeight - heightWithMothers + 1;
		copyRendered( fakeMotherNode.renderResult, result, mothersX, mothersY, fakeMotherNode.resultWidth, fakeMotherNode.resultHeight );

		-- draw line
		local lineY = mothersY + fakeMotherNode.resultHeight;
		local lineStart = mothersX - 1;
		local lineEnd = mothersX + fakeMotherNode.lineConnectionX - 1;
		result[lineY][lineEnd] = "NW";
		for x=lineStart,(lineEnd-1) do
			result[lineY][x] = "EW";
		end
		result[lineY - 1][lineEnd] = APPEND_LINE_DOWN[ result[lineY - 1][lineEnd] ]
	end

	node.renderResult = result;
	node.resultHeight = resultHeight;
	node.resultWidth = resultWidth;
	node.lineConnectionX = selfX + math.floor( ELEMENT_WIDTH / 2 );
	node.lineConnectionY = resultHeight;
end

local function renderWithChildren( options, node )
	if ( not node.childNodes or #node.childNodes == 0) then
		renderSingle( node, false );
		return;
	end

	local lineStartConnectFrom = 99999;
	local lineEndConnectTo = 0;

	local resultWidth = 0; -- self
	local resultHeight = 0;

	for _, childNode in pairs( node.childNodes ) do
		renderWithChildren( options, childNode );
		resultHeight = max( resultHeight, childNode.resultHeight );
	end
	resultHeight = resultHeight + 3 + ELEMENT_HEIGHT;

	local result = {};
	for y=1,resultHeight do result[y]={} end;

	local horPositions = {};
	for _, childNode in pairs( node.childNodes ) do
		-- position by horizontal of current element
		local blockPosition = _ ~= 1 and resultWidth + 2 or 1;

		local childWidth = childNode.resultWidth;
		local childHeight = childNode.resultHeight;

		-- check if we have empty space in result to shift child block to left
		while (blockPosition > 2) do
			if ( not willOverride( childNode.renderResult, result, blockPosition - 2, 5, childWidth, childHeight ) ) then
				blockPosition = blockPosition - 1;
			else
				break;
			end
		end
		horPositions[_] = blockPosition;

		-- define how parent horizontal line need to be drawn
		local blockLineConnectionX = blockPosition + childNode.lineConnectionX - 1;
		lineStartConnectFrom = min( lineStartConnectFrom, blockLineConnectionX )
		lineEndConnectTo = max( lineEndConnectTo, blockLineConnectionX )

		resultWidth = max(resultWidth, blockPosition + childWidth - 1);
		copyRendered( childNode.renderResult, result, blockPosition, ELEMENT_HEIGHT + 3 + 1, childNode.resultWidth, childNode.resultHeight )
	end

	node.resultWidth = resultWidth;
	node.resultHeight = resultHeight;

	-- local center = max( math.floor( (resultWidth + 1) / 2 ), 1 );
	local center = lineStartConnectFrom + math.floor( (lineEndConnectTo - lineStartConnectFrom) / 2 )
	if ( center < 3 ) then error( "center < 3" ) end
	lineStartConnectFrom = min( lineStartConnectFrom , center );
	lineEndConnectTo = max( lineEndConnectTo , center );

	if (lineStartConnectFrom > lineEndConnectTo) then
		error('lineStartConnectFrom > lineEndConnectTo');
	end

	local childConnectionLine = ELEMENT_HEIGHT + 3;
	-- draw child connection line
	if ( lineStartConnectFrom == lineEndConnectTo) then
		result[childConnectionLine][lineStartConnectFrom] = "NS";
	else
		result[childConnectionLine][lineStartConnectFrom] = "E";
		for x=(lineStartConnectFrom + 1),(lineEndConnectTo - 1) do
			result[childConnectionLine][x] = "EW";
		end
		result[childConnectionLine][lineEndConnectTo] = "W";
	end
	
	-- draw line down to children
	for _, childNode in pairs( node.childNodes ) do
		local childConnectionIndex = horPositions[_] - 1 + childNode.lineConnectionX;
		result[childConnectionLine][ childConnectionIndex ] = APPEND_LINE_DOWN[ result[childConnectionLine][ childConnectionIndex ] ];
	end

	-- draw line up to parent
	result[childConnectionLine][center] = APPEND_LINE_UP[ result[childConnectionLine][center] ];
	result[childConnectionLine-1][center] = "NS";
	result[childConnectionLine-2][center] = "NS";
	putEntity( result, 1, center - math.floor( ELEMENT_WIDTH / 2 ), node );

	node.renderResult = result;
	node.lineConnectionX = center;
	node.lineConnectionY = resultHeight;
end

local function renderRoot( options, node )
	-- render with parents first
	if ( options.interleave ) then
		renderInterleaveWithParents( options, node );
	else
		renderWithParents( options, node, nil, nil );
	end
	local withParentsResult = node.renderResult;
	local withParentsWidth = node.resultWidth;
	local withParentsHeight = node.resultHeight;
	local withParentsConnectionX = node.lineConnectionX;
	local withParentsConnectionY = node.lineConnectionY;
	
	node.renderResult = nil;
	node.resultWidth = nil;
	node.resultHeight = nil;
	node.lineConnectionX = nil;
	node.lineConnectionY = nil;
	
	-- render with children
	renderWithChildren( options, node );
	local withChildrenResult = node.renderResult;
	local withChildrenWidth = node.resultWidth;
	local withChildrenHeight = node.resultHeight;
	local withChildrenConnectionX = node.lineConnectionX;
	local withChildrenConnectionY = node.lineConnectionY;

	node.renderResult = nil;
	node.resultWidth = nil;
	node.resultHeight = nil;
	node.lineConnectionX = nil;
	node.lineConnectionY = nil;

	local shiftParents = max(withChildrenConnectionX - withParentsConnectionX, 0);
	local shiftChildren = max(withParentsConnectionX - withChildrenConnectionX, 0);

	local resultWidth = max( withParentsWidth + shiftParents, withChildrenWidth + shiftChildren );
	local resultHeight = withParentsHeight + withChildrenHeight - ELEMENT_HEIGHT;

	local result = {};
	for y=1,resultHeight do result[y]={} end;

	copyRendered( withChildrenResult, result, 1 + shiftChildren, withParentsHeight - ELEMENT_HEIGHT + 1, withChildrenWidth, withChildrenHeight )
	copyRendered( withParentsResult, result, 1 + shiftParents, 1, withParentsWidth, withParentsHeight )

	node.renderResult = result;
	node.resultWidth = resultWidth;
	node.resultHeight = resultHeight;
end

local function printEntityLabel( entityId )
	if ( type(entityId) ~= 'string' ) then error( 'Expected type of entityId to be string, but was ' .. type(entityId) ) end

	local label = mw.wikibase.getLabel( entityId );
	local link = mw.wikibase.sitelink( entityId )

	if link then
		-- link shall be prefixed with ':' to prevent category inclusion instead of link
		if label then
			return link == label and ('[[:' .. link .. '|' .. link .. ']]') or '[[:' .. link .. '|' .. label .. ']]';
		else
			return '[[:' .. link .. '|' .. link .. ']]';
		end
	end

	if label then
		-- красная ссылка
		local title = mw.title.new( label );
		if title and not title.exists then
			return RED_LINK_F( entityId, label);
		end

		-- TODO: перенести до проверки на существование статьи
		local sup = '<sup class="plainlinks noprint">[//www.wikidata.org/wiki/' .. entityId .. '?uselang=ru [d&#x5d;]</sup>'

		-- одноимённая статья уже существует - выводится текст и ссылка на ВД
		return '<span class="iw" data-title="' .. label .. '">' .. label .. sup .. '</span>'
	end

	-- сообщение об отсутвии локализованного названия
	-- not good, but better than nothing
	return MISSING_LABEL_LINK( entityId );
end

local function splitISO8601(str)
	if 'table' == type(str) then
		if str.args and str.args[1] then
			str = '' .. str.args[1]
		else
			return 'unknown argument type: ' .. type( str ) .. ': ' .. table.tostring( str )
		end
	end
	local Y, M, D = (function(str)
		local pattern = "(%-?%d+)%-(%d+)%-(%d+)T"
		local Y, M, D = mw.ustring.match( str, pattern )
		return tonumber(Y), tonumber(M), tonumber(D)
	end) (str);
	return {year=Y, month=M, day=D};
end

local function parseYearFromValue( value )
	local s = splitISO8601( value.time );
	if (not s) then return nil; end
	local precision = value.precision;

	if ( precision >= 0 and precision <= 8 ) then
		local powers = { 1000000000 , 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10 }
		local power = powers[ precision + 1 ];
		local left = s.year - ( ( s.year - 1 ) % power );
		return left, left - 1 + power / 2;
	end

	return s.year, s.year;
end

local function parseTimeValues( entityId, propertyId )
	local claims = mw.wikibase.getBestStatements( entityId, propertyId );
	if ( not claims ) then return nil; end

	local hasAnyValue = false;
	local values = {};
	for _, claim in pairs(claims) do
		local value = (((claim or EMPTY_TABLE).mainsnak or EMPTY_TABLE).datavalue or EMPTY_TABLE).value;
		if ( value ~= nil ) then
			local left, year = parseYearFromValue( value );
			if (year ~= nil) then
				values[year] = {
					precision = value.precision,
					year = year,
					left = left
				};
				hasAnyValue = true;
			end
		end
	end
	return hasAnyValue and values or nil;
end

local function getAnyValue( src )
	for _, value in pairs( src ) do
		return value;
	end
	return nil;
end

local function compareEntitiesByBirthDate( node1, node2 )
	local bYear1 = (getAnyValue( parseTimeValues( node1.entityId, 'P569' ) or EMPTY_TABLE) or EMPTY_TABLE).year or 9999;
	local bYear2 = (getAnyValue( parseTimeValues( node2.entityId, 'P569' ) or EMPTY_TABLE) or EMPTY_TABLE).year or 9999;
	return bYear1 < bYear2;
end

local function formatCentury( year )
	local moduleRoman = require( "Module:RomanNumber" )
	if ( year < 0 ) then
		local century = math.floor( (math.abs( year ) - 1) / 100 ) + 1;
        local infix = ' в ';
        if century == 2 then infix = ' во '; end;
		if ( moduleRoman ) then
			century = moduleRoman.toRomanNumber( century );
		end
		return century .. ' в. до н. э.'
	else
		local century = math.floor( ( year - 1) / 100 ) + 1;
        local infix = ' в ';
        if (century == 2) then infix = ' во ' end;
		if ( moduleRoman ) then
			century = moduleRoman.toRomanNumber( century );
		end
		return century .. ' в.'
	end
end

local function formatParsedTimeValue( parsedValue )
	if ( parsedValue == nil ) then
		return nil;
	elseif ( parsedValue.precision > 8 ) then
		if ( parsedValue.year >= 0 ) then
			return parsedValue.year;
		else
			return ( 0 - parsedValue.year ) .. ' до н.э.';
		end
		return parsedValue.year;
	elseif ( parsedValue.precision == 8) then
		if ( parsedValue.year >= 0 ) then
			return (parsedValue.left - 1) .. '-е';
		else
			return (0 - (parsedValue.left - 1) ) .. '-е до н.э.';
		end
	elseif ( parsedValue.precision == 7) then
		return formatCentury( parsedValue.year );
	else
		mw.log( 'Unsupported precision: ' .. parsedValue.precision );
		mw.log( parsedValue );
		return 'unsupported';
	end
end

local function compareAsStrings( a, b )
	return ('' .. a) < ('' .. b);
end

local function concat( parsedTimeValuesTable )
	local tmp = {};
	for _, value in pairs( parsedTimeValuesTable ) do
		table.insert( tmp , formatParsedTimeValue(value) );
	end
	table.sort( tmp, compareAsStrings );
	return table.concat( tmp, ' / ' );
end

local function printLifespan( entityId )
	local birth = parseTimeValues( entityId, 'P569' );
	local death = parseTimeValues( entityId, 'P570' );

	if (birth == nil and death == nil) then return nil end
	if (birth ~= nil and death == nil) then return 'р. ' .. concat( birth ) end
	if (birth == nil and death ~= nil) then return '? — ' .. concat( death ) end
	if (birth ~= nil and death ~= nil) then
		local bString = concat( birth );
		local dString = concat( death );
		if (bString == dString) then
			return bString;
		else
			return bString .. ' — ' .. dString;
		end
	end

	return nil;
end

local function printEntity( options, entityId )
	local html = printEntityLabel( entityId );
	if ( options.years == "label-line" ) then
		local lifespan = printLifespan( entityId );
		if ( lifespan ~= nil) then html = html .. ' <span class="years">(' .. lifespan .. '</span>)' end
	end
	if ( options.descriptions ) then
		local description = mw.wikibase.getDescription( entityId );
		if ( description ) then
			if ( options.descriptions == true or options.descriptions == "next-line" or options.descriptions == "new-line" ) then
				html = html .. '<br>'
			else
				html = html .. ', ';
			end
			html = html .. '<span class="descriptions">' .. description .. '</span>';
		end
	end
	if ( options.years == true or options.years == "next-line" or options.years == "new-line" ) then
		local lifespan = printLifespan( entityId );
		if ( lifespan ~= nil) then html = html .. '<br><div class="years">' .. lifespan .. '</div>' end
	end
	return html;
end

local function printEntityCell( options, attrs, node )
	local entityId = node.entityId;
	local generation = node.generation;
	return '<td class="Q gen' .. generation ..'" ' .. attrs .. '>'.. printEntity( options, entityId ) ..'</td>';
end

local ROTATE = {W="N",S="E",E="S",N="W"};
local INVERT_HORIZONTAL = {W="E",S="S",E="W",N="N"};

function renderHtmlHorizontal( options, node )
	local invert = options.invert;
	local resultHeight = node.resultHeight;
	local resultWidth = node.resultWidth;
	if (type(resultHeight) ~= 'number') then error("node.resultHeight expected to be number"); end
	if (type(resultWidth) ~= 'number') then error("node.resultWidth expected to be number"); end
	local renderResult = node.renderResult;

	local yStart = invert and resultHeight or 1;
	local yEnd = invert and 1 or resultHeight;
	local yStep = invert and -1 or 1;

	local html = '<div class="wikidata-familyTree wikidata-familyTree-horizontal wikidata-familyTree-decorate-' .. options.decorate .. '"><table role="presentation">\n'
	for x=1,resultWidth do
		html = html .. '<tr><td></td>'

		for y=yStart,yEnd,yStep do

			local cell = renderResult[y][x];
			if (cell == nil) then

				if ( y ~= yStart and renderResult[y - yStep][x] == nil ) then
					-- skip, because handled by next block
				elseif ( renderResult[y][x] == nil ) then
					local colspan = 0;
					for yToSpan = y, yEnd, yStep do
						if ( renderResult[ yToSpan ][x] == nil ) then
							colspan = colspan + 1;
						else
							break;
						end
					end
					if (colspan == 1) then
						html = html .. '<td class=Z ></td>';
					else
						html = html .. '<td colspan=' .. colspan .. ' class=Z ></td>';
					end
				end

			elseif ( cell == BUSY ) then
				-- just skip
			elseif ( cell ~= nil and cell.entityId ) then
				html = html .. printEntityCell( options, 'colspan=' .. ELEMENT_HEIGHT .. ' rowspan=' .. ELEMENT_WIDTH, cell );
			else
				html = html .. '<td class="line ' .. cell .. '">';
				for p = 1,string.len(cell) do
					local lineClass = ROTATE[string.sub(cell, p, p)];
					if ( invert ) then lineClass = INVERT_HORIZONTAL[lineClass] end
					html = html .. '<span class=' .. lineClass .. '></span>';
				end
				html = html .. '</td>';
			end
		end
		html = html .. '<td></td></tr>\n'
	end
	html = html .. '</table></div>'
	return html;
end

function renderHtmlVertical( options, node )
	local resultHeight = node.resultHeight;
	local resultWidth = node.resultWidth;
	if (type(resultHeight) ~= 'number') then error("node.resultHeight expected to be number"); end
	if (type(resultWidth) ~= 'number') then error("node.resultWidth expected to be number"); end
	local renderResult = node.renderResult;

	local html = '<div class="wikidata-familyTree wikidata-familyTree-vertical wikidata-familyTree-decorate-' .. options.decorate .. '"><table>\n'
	for y=1,resultHeight do
		local renderLine = renderResult[y];
		html = html .. '<tr>'
		for x=1,resultWidth do
			local cell = renderLine[x];
			if (cell == nil) then
				html = html .. '<td class=Z></td>';
			elseif ( cell == BUSY ) then
				-- just skip;
			elseif ( cell ~= nil and cell.entityId ) then
				html = html .. printEntityCell( options, 'colspan=' .. ELEMENT_WIDTH .. ' rowspan=' .. ELEMENT_HEIGHT, cell );
			else
				html = html .. '<td class="line ' .. cell .. '">';
				for p = 1,string.len(cell) do
					html = html .. '<span class=' .. string.sub(cell, p, p) .. '></span>';
				end
				html = html .. '</td>';
			end
		end
		html = html .. '</tr>\n'
	end
	html = html .. '</table></div>'
	return html;
end

function p.drawTree( frame )
	local args = frame.args or EMPTY_TABLE;
	return p.drawTreeImpl( args );
end

local function toBoolean( valueToParse, defaultValue )
	if ( valueToParse ~= nil ) then
		if valueToParse == false or valueToParse == '' or valueToParse == 'false' or valueToParse == '0' then
			return false
		end
		if valueToParse == true or valueToParse == 'true' or valueToParse == '1' then
			return true
		end
	end
	return defaultValue;
end

function p.drawTreeImpl( args )
	-- проброс всех параметров из шаблона {wikidata} и параметра from откуда угодно
	local p_frame = mw.getCurrentFrame();
	while p_frame do
		if p_frame:getTitle() == mw.site.namespaces[10].name .. ':Wikidata/FamilyTree' then
			copyTo( p_frame.args, args, true );
		end
		if p_frame.args and p_frame.args.from and p_frame.args.from ~= '' then
			args.entityId = p_frame.args.from;
		end
		p_frame = p_frame:getParent();
	end

	-- p.drawTreeImpl( { entityId="Q7200" } );
	local entityId = args.entityId;
	if (entityId == "" or entityId == nil) then entityId = mw.wikibase.getEntityIdForCurrentPage(); end
	if (entityId == "" or entityId == nil) then return "Не задан идентификатор сущности entityId (страница не связана с Викиданными)"; end

	local options = {
		mode = args.mode or DEFAULT_MODE,
		invert = toBoolean( args.invert, false ),
		interleave = toBoolean( args.interleave, false ),
		ancestors = args.ancestors or ( ( args.mode or DEFAULT_MODE ) == "horizontal" and 2 or 3),
		descendants = args.descendants or ( ( args.mode or DEFAULT_MODE ) == "horizontal" and 2 or 3),
		compactParents = args.compactParents or ( ( args.mode or DEFAULT_MODE ) == "horizontal"),
		compactChildren = args.compactChildren or true,
		years = toBoolean( args.years, args.years ),
		descriptions = toBoolean( args.descriptions, args.descriptions ),
		decorate = args.decorate or DEFAULT_DECORATE,
	}

	local lines = {};
	lines[0] = {};

	local root = createNode(entityId, 0);
	table.insert( lines[0], root );

	for i=1,options.ancestors do
		lines[0 - i] = {};
		for _, node in pairs( lines[0 - i + 1] ) do
			if ( options.interleave ) then
				populateRelation( 'father', 'P22', lines[0 - i], node, node.generation - 1);
				populateRelation( 'mother', 'P25', lines[0 - i], node, node.generation - 1);
			else
				populateRelation( 'parent', 'P22', lines[0 - i], node, node.generation - 1);
				populateRelation( 'parent', 'P25', lines[0 - i], node, node.generation - 1);
			end
		end
	end

	for i=1,options.descendants do
		lines[0 + i] = {};
		for _, node in pairs( lines[0 + i - 1] ) do
			populateRelation( 'child', 'P40', lines[0 + i], node, node.generation + 1);
			if ( node.childNodes and #node.childNodes > 1 ) then
				table.sort( node.childNodes, compareEntitiesByBirthDate );
			end
		end
	end

	renderRoot( options, root );

	local html;
	if (options.mode == "horizontal") then
		html = renderHtmlHorizontal( options, root );
	else 
		html = renderHtmlVertical( options, root );
	end
	return html;
end

return p