[Closed] Getting the Parent Root of a hierarchy

Hi Guibou, here is a function to get the root of a node hierarchy. Feed it with a node and it returns the root, the node itself if it has no parent.

function getNodeRoot theNode =
(
    if (isValidNode theNode) do
    (
        local theParent = theNode.parent

        while (theParent != undefined) do
        (
            theNode = theParent
            theParent = theNode.parent
        )
    )
    
    return theNode
)

• Enrico

What Enrico writes is absolutely right. It can be a little shorter/faster though:

function getNodeRoot theNode =
(
    local theParent = theNode;
    while (isValidNode theParent.parent) do
    (
       theParent = theParent.parent;
    )
    theParent; --return value;
)

Hey Pier, I like your optimization. I’m always intrigued by compact code. I run some performance tests on our functions, with a structure I wrote some time ago, and even if yours saves some typing, they provide the same results in terms of execution speed, milliseconds difference is irrelevant and variable.

Test Structure:

struct PerformanceTester
(
    iStartTime = 0,
    iStartMem = 0,

    iStopTime = 0,
    iStopMem = 0,
    iStopMemDelta = 0,

    iCycle = 0,

    iResTime = 0,
    iResMem = 0,
    iResMemDelta = 0,

    function start =
    (
        gc()
        iCycle += 1
        iStartTime = timeStamp()
        iStartMem = heapSize - heapFree
    ),

    function stop =
    (
        iStopTime = timeStamp()
        iResTime += (iStopTime - iStartTime) / 1000.0

        iStopMem = heapSize - heapFree
        iResMem += (iStopMem - iStartMem) / 1024.0

        gc()
        iStopMemDelta = heapSize - heapFree
        iResMemDelta += (iStopMemDelta - iStartMem) / 1024.0
    ),

    function report =
    (
        format "Average processing on % iteration(s) took:
" iCycle
        format "% seconds
" (iResTime / iCycle)
        format "% Kbytes used
" (iResMem / iCycle)
        format "% Kbytes delta

" (iResMemDelta / iCycle)

        iCycle = 0
        iResTime = 0
        iResMem = 0
        iResMemClean = 0
    )
)

Tests:

(
    function getNodeRoot1 theNode =
    (
        if (isValidNode theNode) do
        (
            local theParent = theNode.parent

            while (theParent != undefined) do
            (
                theNode = theParent
                theParent = theNode.parent
            )
        )

        return theNode
    )

    function getNodeRoot2 theNode =
    (
        local theParent = theNode;
        while (isValidNode theParent.parent) do
        (
           theParent = theParent.parent;
        )
        theParent; --return value;
    )

    local theWatch = PerformanceTester()


    local theSpheres = #()
    local iNumSpheres = 2000

    for i = 1 to iNumSpheres do
        append theSpheres (Sphere pos:[i*10, 0, 0])

    for i = iNumSpheres to 2 by -1 do
        theSpheres[i].parent = theSpheres[i-1]


    for i = 1 to 100 do
    (
        theWatch.start()
        getNodeRoot1 theSpheres[iNumSpheres]
        theWatch.stop()
    )
    theWatch.report()

    for i = 1 to 100 do
    (
        theWatch.start()
        getNodeRoot2 theSpheres[iNumSpheres]
        theWatch.stop()
    )
    theWatch.report()


    for s in theSpheres do
        delete s
)

Results:

Average processing on 100 iteration(s) took:
0.00263 seconds
0.226563 Kbytes used
-0.105469 Kbytes delta

Average processing on 100 iteration(s) took:
0.0028 seconds
0.226563 Kbytes used
-0.213125 Kbytes delta

• Enrico

p.s.
I’m eagerly waiting your Outliner 2.0!

edit: nm

If you write the code out over multiple lines it may become more clear:

fn getRoot node = (
  --Check if the node passed to the function is a valid node.
  if isvalidnode node do 
  (
    --Loop through the hierarchy until the current node's parent is undefined (i.e. rootnode)
    while node.parent != undefined do node = node.parent; 
    --Return the rootnode
    node
  )
)

This just declares a function, which gives the ‘OK’ you mentioned. To call it, just do something like:

getRoot $Sphere01

fn getRoot node = if isvalidnode node.parent then getRoot node.parent else node

i like recursion

I also like your way with the exception of the validation part

you probably have to know that any recursive function has a limit by the stack of recursions. usually the size of this stack defined by the system (compiler, etc.) . i don’t very well know about the limits but in MXS the stack is about ~500 recursions. it might be less or more for different situations, but never less than 200 and never more than 1000…

here is a sample where my method without recursion works well, but the recursive function crashes the max:

(
	delete objects
	count = 400 -- (400 still works, but 800 crashes)
	local node 
	for k=1 to count do in node (node = box name:(k as string))
	gc()
)

fn getRoot node = if isvalidnode node do 
(
	while node.parent != undefined do node = node.parent
	node
)
 
fn getRootRecursive node = if isvalidnode node and isvalidnode node.parent then getRootRecursive node.parent else node
	
/*

getRoot objects[objects.count]

getRootRecursive objects[objects.count]

*/

well, as you’re veteran and i continue to learn new things from you, (from this thread for example, i see that the limit of recursion is more lower than i expected), so somehow cannot imagine that you’re not aware about the evil behind this practice.
(no hidden offence to you here, i whish to know)

so i’ll post some brief explanation about, not to you, but for the all folks who are new to the programming at all.

1st to say that the good programming practice rules are too complex, they’re linked to each other and intersect each other. so any isolated explanation of concrete rule is not easy, nor yet very correct. for example, in our case, to not using validation of passed params/arguments within the function is just a small part of more bigger rule saying “do not make mixin responsibility inside reusable code”. skipping pre-validation (outside of the function) is an other bad habits, and so on.

well, unlikely i’m good in such explanations, but lets i try anyway…

so if we pre-validate already, that come as redundant code and redundant calculation. but if we plan to omit pre-validation, what happens then when invalid argument come? the function will not fail, but will return invalid result. its not something local to the concrete function. i’m pretty sure no one will inclide validaion in simple function like: “fn add n1 n2 = (n1 + n2)”. but if we do that, how this will improve the output result? what it will return in case n1 or n2 are not numeric values? how we’ll use that result after all?

ok, back to GetRoot example where we expect object as result. in maxscript no void functions (w/o result), and maybe in case the result of the function is not important… but once we start to make exceptions…

ok, no extra scopes. here we need the result, and can we use it without post-validation (outside of the function)? if doing this may put well hidden bug. shortly, post-validation is bad style (or bad idea, if this sound better). and omission of pre-validation is bad habit as well even in simple stay alone solutions.

i hope all this make sense (in the way i write it)