I use angular-bootstrap-nav-tree
I have Array that i get from self-reference table Like this:
var obj = [
{id:1,label:"Animal"},
{id:2,label:"Vigitable"},
{id:3,label:"Cats",parent:1},
{id:4,label:"black cat",parent:3},
{id:5,label:"orange",parent:2},
];
I want to convert it to be nested like this:
var convrted = [
{id:1,label:"Animal",children[
{id:3,label:"Cats",parent:1,children[{id:4,label:"black cat",parent:3}]}
]},
{id:2,label:"Vigitable",children[
{id:5,label:"orange",parent:2}
]}
];
I want it to work unlimited levels dynamic.
This will do the job:
function nest (array) {
nested = [];
for (var i = 0; i < array.length; i++) {
var parent = array[i].parent;
if (!parent) {
nested.push(array[i]);
} else {
// You'll want to replace this with a more efficient search
for (var j = 0; j < array.length; j++) {
if (array[j].id === parent) {
array[j].children = array[j].children || [];
array[j].children.push(array[i]);
}
}
}
}
return nested;
}
The second for loop is an inefficient way of finding the parent; if you ever have more than a few items to nest, you'll want to replace it with something that doesn't scan the entire array.
This is one instance of a general class of operations known as data transformation, which can be really fun and useful. My overall approach would be to write recursive search and remove tree functions that can be utilized in the main transformation function. In general, recursive functions are not as performant as their equivalent iterative implementations, but they can be easier to write and understand. As an example, here's the search function I used:
function getById(tree, id) {
var len = tree.length;
for (var i = 0; i < len; i++) {
if (tree[i].id === id) {
return tree[i];
}
}
for (var i = 0; i < len; i++) {
if (tree[i].children) {
var node = getById(tree[i].children, id);
if (node) {
return node;
}
}
}
return null;
}
This is an example of a breadth-first search, where I first hope to find the element in the top level of the tree. If I don't, I will then call the search function on the .children member of each top level node, if it exists. Failing that, I return null to indicate a failure to find the node.
Next, I want a recursive removal function that works like Javascript's splice function. The idea is to pluck the node with the given ID out of the tree so that I can reinsert it as a child of its parent.
function removeFromTree(tree, id) {
var node = getById(tree, id);
if (node) {
if (node.parent) {
var parent = getById(tree, node.parent);
if (parent && parent.children) {
var index = indexInTree(parent.children, id);
if (index != -1) {
return parent.children.splice(index, 1)[0];
}
}
}
var index = indexInTree(tree, id);
return tree.splice(index, 1)[0];
}
return null;
}
You can see that I use splice to do the actual "plucking", but splice requires an index, so I wrote a function to retrieve the index given a known parent node:
function indexInTree(tree, id) {
var len = tree.length;
for (var i = 0; i < len; i++) {
if (tree[i].id === id) {
return i;
}
}
return -1;
}
That's a pretty simple operation that works pretty much the same way as the indexof function on arrays, only we are just matching IDs and not whole objects.
With these helper functions in place, the transformation function is pretty straightforward:
function myTransform(array) {
var tree = array.concat([]);
var len = array.length;
for (var i = 0; i < len; i++) {
if (array[i].parent && (array[i].parent !== array[i].id)) {
var objToMove = removeFromTree(tree, array[i].id);
if (objToMove) {
var parent = getById(tree, objToMove.parent);
if (parent) {
if (!parent.children) {
parent.children = [];
}
parent.children.push(objToMove);
}
}
}
}
return tree;
}
First, I copy the original array using concat([]). Then I iterate over the original array. Whenever I come across an object with a parent ID, I use my removal function to pluck the object from the copy. Then, I use my breadth-first search function to find the correct parent object. Finally, I insert the object into the parent's children list.
This, along with some simple test code to verify that it works, can be found on JSFiddle.
Inspired by Andrew Larson, I decided to try an implementation that builds an object rather than an array copy to make searching by id an O(1) operation. Well, it is O(1) assuming that accessing object properties by key is O(1) internally to the Javascript runtime.
function otherTransform(originalArray) {
var array = {}; // Create the object
var len = originalArray.length;
for (var i = 0; i < len; i++) {
array[originalArray[i].id] = originalArray[i]; // Store by id
}
var nested = [];
for (var i in array) { // Using "in" syntax to iterate over object keys
var parent = array[i].parent;
if (!parent) {
nested.push(array[i]);
} else {
array[parent].children = array[parent].children || [];
array[parent].children.push(array[i]);
}
}
return nested;
}
Now the question is whether you really wanted your data transformed into the array-style tree in the first place. It seems like a nested tree of this new form would be more useful in general.
