Work with an array of objects

Question

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

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 for the question (s). For now, let's just assume that objects can be:

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

Children are optional.

I am looking for the best methods / fastest methods for managing some things with such an object. I created some recursive methods to accomplish some of the things I want, but I want to know if there are ways to solve the following problems:

• hasAlias ​​(arr, alias) - I need to determine if the entire object contains an object with the give alias.

I am currently doing this recursively, but given that this array can grow permanently, the recursive method will eventually hit the stacks.

2. getParent (arr, alias) - I need to be able to get the parent element containing the element with the given alias. Given that the alias is unique to the entire array, there will never be two aliases alike. Again, I am doing this recursively right now, but I want to find the best methods for this.

3. deleteObject (arr, alias) - I'm not sure how to do this at this time. I need to be able to pass an array and an alias and remove this object (and all its children) from this array. I started a recursive method for this, but stopped and decided to post here.

I use Node.js and have lodash for faster methods of doing things. I'm still pretty new to JavaScript, so I'm not sure if there are ways to do something with larger arrays like this.

Answer 1

Returning to FORTRAN days that did not support recursion, one achieved similar effects by modifying the data set to mimic the level of “recursion”. Applying this principle to the approximate structure of an object, the function of searching for an object by its "pseudonym" (name or identifier in another word) can be written without recursion as follows:

 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, it creates a stack of small data objects that are popped and popped into the same function instead of making recursive calls. The above example returns an object with parent and child objects. The child value is the value with the alias provided, and the parent with the child in the children array.

It returns null if the alias cannot be found, so it can be used for hasAlias . If it does not return null, it executes the getParent functionality. However, you need to create a root node:

 // 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 for the return object, update the sample code example, add output.]

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 option may pay for this if it can be shown that it has significant advantages in reducing server load during volume pressure tests, but requires sound documentation.

Regardless of internal coding, the tree-walking function, which returns an object with details of the values ​​of the parent, child, and child indexes, can contribute to the overall efficiency of the program by reducing the total number of triples performed:

• the validity of the returned search value replaces the hasAlias function
• a return from search object can be transferred to update, delete, or insert functions without having to search the trees in each function again.

Answer 2

The guaranteed quick way, obviously, is to

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

You are viewing 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} 

Removing an alias means removing it and its children from the index and 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) } 

Answer 3

I can approach your main array a little differently and save it as a flat array, which refers to other elements, but does not include them completely.

 var flat = [ { alias : "str1", children : [ flat[1], flat[2] ], parent : null }, { alias : "str1", children : [], parent : flat[0] }, { alias : "str1", children : [], parent : flat[0] } ] 

This is a kind of " linked list ." There are pros and cons to linked lists, but you can quickly sort through all the items.