Tree structure

rrraptor

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

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

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

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

keszegh said:

to root first

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

keszegh

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

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

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

keszegh

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

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

keszegh

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

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

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

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

rrraptor

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

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

congratulations.