Building an object graph from flat object array in javascript

i have a javascript array of objects with objects that look like this:

itemId

name

parentItemId <== top level items with no parent have null value

I wa开发者_运维百科nt to build a graph where the parent items contain arrays of children and those children have arrays of children if applicable.

What is a good way to go about this?

---

function objectGraph(items)
{
    var items_by_id = {};
    var roots = [];
    var i;

    // Build an id->object mapping, so we don't have to go hunting for parents
    for (i = 0; i < items.length; ++i) {
        items_by_id[items[i].itemId] = items[i];
        items[i].children = [];
    }

    for (i = 0; i < items.length; ++i) {
        var parentId = items[i].parentItemId;
        // If parentId is null, this is a root; otherwise, it's parentId's kid
        var nodes = (parentId === null) ? roots : items_by_id[parentId].children;
        nodes.push(items[i]);
    }
    return roots;
}

Note, this code gives every node a children property, that's empty if a node has no kids. I personally find it simpler and more consistent than each node maybe-or-maybe-not having children; you can loop over children without worrying whether it exists. A leaf node will have children.length == 0.

If you can guarantee you have exactly one root, you can return roots[0]; instead of returning the array.

---

When you build a "tree builder function" you have to decide if the "top level thing" is a single item or an array of items. Since you said itemS we go with an array. The difference is the parameter you pass in and get returned back, if its an array we pass the parentId, otherwise we pass the id.

function buildTree(parentId, list) {
  var nodes = [];
  for (var i=0, l; l = list[i]; i++) {
    if (l.parentId === parentId) {
// if you need "myList" intact afterwards remove the next line at the cost of efficiency
      list.splice(i, 1); i--;  
      nodes.push({
        id: l.id
        ,parentId: l.parentId
        ,name: l.name
        ,children: buildTree(l.id, list)
      });
    }
  }
  return nodes;
}

var myTree = buildTree(null, myList);

---

This is a little rough, but it should do the job if I'm gathering your question correctly. It should return an array of top level objects that have their children correctly organized below them.

As a note, this will work for an N-level of children objects, and not just a single level.

var finalArray = [];
var YOUR_RAW_ARRAY = [];

var buildObjectGraph = function(inputArray){
    var i = 0, len = inputArray.length;
    var returnVal = [];

    for(;i<len;i++){
        if(inputArray[i].parentItemId === null){
            findChildren(inputArray[i], inputArray);
            returnVal.push(inputArray[i]);
        }
    }

    var findChildren = function(root){
        var i = 0, i2 = 0, len = rawDataArray.length, len2 = 0;

        for(;i<len;i++){
            if(inputArray[i].parentItemId === root.itemId){
                if(root.children){
                    root.children.push(inputArray[i]);
                }else{
                    root.children = [];
                    root.children.push(inputArray[i]);
                }
            }
        }

        //now call it recursively
        len2 = root.children.length;
        if(len2 > 0){
            for(;i2 < len2; i2++){
                findChildren(root.children[i2]);
            }
        }
    };
    return returnVal;
};

//Then execute it
finalArray = buildObjectGraph(YOUR_RAW_ARRAY);