Working With Array Of Objects

Question

I have an array of objects that can contain children of the same object type, like this:

var exampleArray = [
    {
        alias: 'alias1',
        children: [
            {
                alias: 'child1'
            },
            {
                alias: 'child2',
                children: [
                    {
                        alias: 'child4'
                    },
                    {
                        alias: 'child5'
                    }
                ]
            },
            {
                alias: 'child3'
            }
        ]
    },
    {
        alias: 'alias2'
    },
    {
        alias: 'alias3',
        children: [
            {
                alias: 'child6'
            },
            {
                alias: 'child7'
            }
        ]
    }
];

The base object has other properties but they are not important to the question(s) at hand. For now, lets just assume the objects can be:

{
    alias: 'string',
    children: []
}

The children are optional.

I am looking for the best methods / fastest methods for managing some things with an object like this. I have created some recursive methods to do some of the things I want, but I want to know if there are better ways to go about doing the following tasks:

1. hasAlias(arr, alias) - I need to determine if the entire object contains any object with the give alias.

Currently, I do this recursively but given that this array can grow finitely, the recursive method is eventually going to hit stack limits.

2. getParent(arr, alias) - I need to be able to obtain the parent that contains an element with the given alias. Given that alias' are unique to the entire array, there will never be two of the same alias. Again I do this recursively right now but I want to find better methods of doing this.

3. deleteObject(arr, alias) - I am unsure how to accomplish this one currently. I need to be able to pass an array and an alias and have that object (and all its children) removed from the given array. I started a recursive method of doing this but stopped and decided to post here instead.

I am using Node.js and have lodash available for faster methods of doing things. I'm still fairly new to JavaScript so I am unsure if there are better ways to go about doing things with larger scale arrays like this.

Answer 1

Back in the days of FORTRAN which didn't support recursion, one achieved similar effects by changing a data set to simulate a level of "recursion". Applying this principle to the example object structure, a function to lookup an object by its "alias" (a name or id by another word) could be written without recursion like this:

function findAlias( parent, alias) // parent object, alias value string
{   function frame( parent)
    {   return {parent: parent, children: parent.children,
        index: 0, length: parent.children.length};
    }
    var stack, tos, child, children, i;

    stack = [];
    if( parent.children)
        stack.push( frame( parent));

    search:
    while( stack.length)
    {   tos = stack.pop();  // top of generation stack
        children = tos.children;
        for( i = tos.index; i < tos.length; ++i)
        {   child = children[i]; 
            if( child.alias == alias)
            {   return { parent: tos.parent, child: child, childIndex: i}
            }
            if( child.children)
            {   tos.index = i + 1;
                stack.push(tos);  // put it back
                stack.push( frame(child));
                continue search;
            }
        }
    }
    return null;
}

In short one ends up creating a stack of smallish data objects which are pushed and popped in the same function instead of making recursive calls. The example above returns and object with parent and child object values. The child value is the one with the supplied alias property, and the parent object is the one with the child in its children array.

It returns null if the alias could not be found so can be used for hasAlias functionality. If it doesn't return null it performs the getParent functionality. You do have to create a root node however:

// create a rootnode
var rootNode = { alias: "root", children: exampleArray}; 
var found = findAlias(rootNode, "alias3");
if( found)
{  console.log("%s is a child of %s, childIndex = %s",
       found.child.alias, found.parent.alias, found.childIndex);
}
else
   console.log("not found");

---

[Edit: add childIndex to search return object, update test example code, add conclusion.]

Conclusion

Using recursive function calls when supported for a tree walking application makes sense in terms of self documenting code and maintainability. A non recursive variation may pay for itself it if it can be shown that it has significant benefits in reducing server load under volume pressure tests, but requires sound documentation.

Regardless of internal coding, a tree walking function which returns an object with details of parent, child, and child index values might contribute to overall program efficiency by reducing the total number of treewalks ever performed:

• truthiness of the search return value substitutes for an hasAlias function
• the return object from the search can be passed to update, remove or insert functions without requiring repeated tree searches in each function.

Answer 2

The guaranteed fastest way is obviously to have

- an index for the aliases (thats actually a unique id)
- have a parent backlink on each child item (if it has a parent)

You look up against the id index

var index = {}
(function build(parent) {
   index[parent.alias] = parent;
   (parent.children || []).forEach( item => {
       item.parent = parent
       build(item)
   })
})(objectRoot)


function hasAlias(alias) { return alias in index }

function getAlias(alias) { return index[alias] } 

function getParent(alias) { return index[alias] && index[alias].parent}

Deleting an alias would mean removing it and its children from the index and from the parent that still remains in the index

function deleteAlias(alias) {

   function deleteFromIndex(item) {
      delete index[item.alias]
      (item.children || []).forEach(deleteFromIndex)
   }
   var item = index[alias]
   item.parent.children.splice(item.parent.children.indexOf(item))
   deleteFromIndex(item)

}