Tree structure

rrraptor · June 2020

I have a small problem, that I cant solve for whatever reason.

I have a tree that looks like this:

Where red dots - unavailable nodes, green dots - available nodes, purple dots - nodes with childs. Basic node structure:

{id = "whatever", available = false, parent = ..., childs= {...}}

Now the fun part. Somehow I manage to get to node with id=10 (by clicking on it or maybe loop over whole tree, it does not matter). And I know all information about this node. Now I need to look for the next possible green node. It must be 17, then 19, 16 and so on.

The simple solution is to brute force whole tree like this:

local currentNode = ...
local found = false
 
function bruteForce(node)
	for i,subNode in ipairs(node.childs) do
		-- found current
		if subNode == currentNode then 
			found = true
		-- next posible is found
		elseif found and subNode.available then 
			found = false
			return subNode
		end
		-- check childs
		if #subNode.childs > 0 then 
			local n = bruteForce(subNode)
			if n then return n end
		end
	end
end
 
bruteForce(root)

But I dont like it. There must be a better way

Any ideas?

keszegh · June 2020

you should also store the parent of a node and then you can start with the currentNode and traverse the tree in depth-first search (dfs) manner from there (as it seems that's what you want). search for dfs and tree data structures e.g. https://brilliant.org/wiki/depth-first-search-dfs/ .

btw if you don't intend to modify the tree then you can preprocess it with a dfs once and build a 'next node' table from which you can get the next node immediately. you can even update this table when a new node is added to the tree.

rrraptor · June 2020

keszegh said:
you should also store the parent of a node

Already done))

keszegh said:
and then you can start with the currentNode and traverse the tree in depth-first search (dfs) manner from there (as it seems that's what you want). search for dfs and tree data structures e.g. https://brilliant.org/wiki/depth-first-search-dfs/ .

I know how to do this. I understand how to work with trees.
Thats what I have and it gives me correct results.

function findFirstPosible(node)
	for i,c in ipairs(node.childs) do 
		if c.available then
			return c
		else
			local f = findFirstPosible(c)
			if f then return f end
		end
	end
end

The problem is how you can get from node 16 to 6?

keszegh said:
btw if you don't intend to modify the tree then you can preprocess it with a dfs

Not my case

keszegh · June 2020

16->6: well, only way is to continue dfs search, which will go up via parents to root first, and then go down to 6.

rrraptor · June 2020

keszegh said:
to root first

If it comes to root I will get 10. Cuz its first valid answer.

keszegh · June 2020

well, when from node A you go up one level to a node B you need to 'remember' where you came from (that is, A) and from B you have to go to a child that is the 'next' one after A in the order of children of B. and if there is no such child (i.e., A was the 'last' child of

then you go from B to the parent of B.
then you repeat the same process now with B instead of A. and you repeat this process until you find a green leaf.

rrraptor · June 2020

keszegh said:
well, when from node A you go up one level to a node B you need to 'remember' where you came from (that is, A) and from B you have to go to a child that is the 'next' one after A in the order of children of B. and if there is no such child (i.e., A was the 'last' child of then you go from B to the parent of B.
then you repeat the same process now with B instead of A. and you repeat this process until you find a green leaf.

Sure that will work but I dont know how to code it ))) I tried various different implementations, recursive/while loops and it just does not work

keszegh · June 2020

what i wrote is almost pseudo-code, give it a try, i think you will succeed.

keszegh · June 2020

do a next_using_dfs() function which from A finds B in the way i wrote.
and then you do not need recursion, just keep calling this on the new node it gives until you get a green node.

keszegh · June 2020

so next_using_dfs(16) will find give 12, then next_using_dfs(12) will give 5 and so on.

keszegh · June 2020

and i cheated a bit, as i wrote you need to remember 'previous place', so next_using_dfs() should have two inputs (except when you call it on a leaf, the first time).
so you first call next_using_dfs(16) then run next_using_dfs(12,16) then next_using_dfs(5,12) and so on.

keszegh · June 2020

even better, make a function which from a node either points to the next child of its parent or if he is the last child then points to its parent.
and then you don't need two inputs, this function finds what you want by repeated calls.

rrraptor · June 2020

Finally I did it! @keszegh ty for help!

I guess it can be optimized but for now its ok.

-- main function
function getNext(node)
	-- try to find node in current group
	local nextNode = findNext(node)
	if nextNode then 
		return nextNode
	-- if does not exist
	else
		-- go up
		local b = goBack(node)
		if b then 
			return b
		else
			-- this is the last node, so we need to 
			-- wrap to first possible node of the root
			return findFirstPosible(root)
		end
	end
end
--
function goBack(node)
	local curr = node.__owner --< get parent of the node
	if not curr then return end
 
	local prev = curr.__owner --< get parent of a "curr" node
	if not prev then return end
 
	local n = prev:getNodeCount() --< number of childs
 
	local ind = prev:getNodeIndex(curr) --< get index in tree
	if ind + 1 <= n then --< if next node exist
		-- pick this next node
		local nextToCurr = prev:getNodeAt(ind+1)
		-- if this node is valid return it
		if nextToCurr.valid then return nextToCurr end
 
		-- if not check its childs
		local nextNode = findFirstPosible(nextToCurr)
		-- if found something return it
		if nextNode then 
			return nextNode
		else
			nextNode = findNext(nextToCurr)
			if nextNode then return nextNode end
			-- go up
			return goBack(curr)
		end
	else
		-- go up
		return goBack(curr)
	end
end
-- start from current node+1 and find first valid node
-- if not found in current group, go deeper
function findNext(node)
	local owner = node.__owner
	if not owner then return end
 
	local ind = owner:getNodeIndex(node)
	for i = ind + 1, owner:getNodeCount() do 
		local n = owner:getNodeAt(i)
		if n.valid then	
			return n
		else
			-- go deeper
			n = findFirstPosible(n)
			if n then return n end
		end
	end
end
--
function findFirstPosible(node)
	for i = 1, node:getNodeCount() do 
		local n = node:getNodeAt(i)
		if n.valid then
			return n
		else
			n = findFirstPosible(n)
			if n then return n end
		end
	end
end

Now I need same thing but In opposite direction

MoKaLux · June 2020

this may interest you?
http://forum.giderosmobile.com/discussion/comment/63302/#Comment_63302

rrraptor · June 2020

MoKaLux said:
this may interest you?
http://forum.giderosmobile.com/discussion/comment/63302/#Comment_63302

Probably not

Im still trying to create a UI lib

This is 6th generation so far xD Rewritten almost from scratch about a week ago.

P.S. the gfx taken from godot engine.

rrraptor · June 2020

Go backwards

function getPrev(node)
	local prevNode = findLast(node)
	if prevNode then return prevNode end
 
	local b = goUpBackward(node)
	if b then return b end
 
	return findLastPosible(root)
end
--
function goUpBackward(node)
	local currRoot = node.__owner 
	if not currRoot then return end
 
	local ind = currRoot:getNodeIndex(node)
	if ind - 1 > 0 then 
		local prev = currRoot:getNodeAt(ind-1)
		if prev.valid then return prev end
 
		local last = findLast(prev)
		if last then return last end
 
		last = findLastPosible(prev)
		if last then return last end
	end
	return goUpBackward(currRoot)
end
--
function findLast(node)
	local owner = node.__owner
	if not owner then return end
	local ind = owner:getNodeIndex(node)
	for i = ind - 1,1,-1 do 
		local c = owner:getNodeAt(i)
		if c.valid then return c end
		c = findLastPosible(c)
		if c then return c end
	end
end
--
function findLastPosible(node)
	for i = node:getNodeCount(), 1, -1 do 
		local c = node:getNodeAt(i)
		if c.valid then return c end
		c = findLastPosible(c)
		if c then return c end
	end
end

keszegh · June 2020

congratulations.

Howdy, Stranger!

Categories

In this Discussion

Top Posters

Tree structure

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

Tree structure

Comments