Building a nested tree of data from plain array of objects

Question

I have an array of objects, like those ones:

{
  "short_id": "2p45q",
  "path": "/",
  "name": {
    "en-US": "IndustrialDesign"
  }
}

...

{
  "short_id": "2q56r",
  "path": "/2p45q/",
  "name": {
    "en-US": "Automotive"
  }
}

I must iterate over each element of the array and check the path, then find the parent of the element and push it in a new array property of that parent called sub. Each child can have a sub property on it's own, thus being a parent of more children. The final result (for this example) would look like:

{
  "short_id": "2p45q",
  "path": "/",
  "name": {
    "en-US": "Test A"
  },
  "sub": [
    {
      "short_id": "2q56r",
      "path": "/2p45q/",
      "name": {
        "en-US": "Test A.1"
      }
    }
  ]
}

I have a working code (using this jsonpath lib):

function(categories) {
    var _categories = [];

    angular.forEach(angular.copy(categories), function(_category) {
        if (_category.path === "/") {
            _categories.push(_category);
        } else {
            var _path = _category.path.split("/");
            _path.pop();
            var _parent = _path.pop();

            jsonpath.apply(_categories, "$..[?(@.short_id=='" + _parent + "')]", function(obj) {
                if(!obj.hasOwnProperty("sub")) {
                    obj.sub = [];
                }
                obj.sub.push(_category);
                return obj;
            });
        }
    });

    return _categories;
}

but the performance is really bad, mainly because I'm querying the entire array for each iteration.

My question is how can I optimize my code?

Notes:

Each short_id is exactly 5 characters long.
Each character in short_id can be [0-9a-z]
path is guaranteed to start and end with a /

fuyushimoya · Accepted Answer · 2015-07-21 08:10:08Z

1

Create another tmp object as Hashmap, so you can just use path and id to create a new key to store.

Logic :

If path is '/', its root, put to the _categories array.
If not, check if the target parent is exist in the hashStore or not, if not, create a fake one, and put it self to target is sub attr.
For all element, create a key by _category.path + _category.short_id + '/', and check if its exist in the hashStore, if exist, the one in store should be a fake, get sub from fake. Then assign itself to the hashStore by created key.

Use a key to decide whether the object exist in the map or not should be O(1). So the performance of the this function should be O(n) while n is the number of element in origin list.

function buildTree(categories) {
  var _categories = [];
  var store = {};

  angular.forEach(angular.copy(categories), function(_category) {
    if (_category.path === '/') {
      _categories.push(_category);
    } else {
      var target;
      // If parent exist
      if (typeof store[_category.path] !== 'undefined') {

        // Check parent have sub or not, if not, create one.
        target = store[_category.path];
        if (typeof store[_category.path].sub === 'undefined') {
          target.sub = [];
        }

      } else {
        // Create fake parent.
        target = {sub: []};
        store[_category.path] = target;
      }

      // Push to parent's sub
      target.sub.push(_category);
    }

    // Create key map
    var key = _category.path + _category.short_id + '/';
    // If fake object exist, get its sub;
    if (typeof store[key] !== 'undefined') {
      _category.sub = store[key].sub;
    }
    store[key] = _category;

  });

  return _categories;
}

edited Jul 21, 2015 at 8:10

answered Jul 21, 2015 at 7:55

fuyushimoya

9,8133 gold badges30 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Alexander Nestorov Over a year ago

I'm not sure I understand how this works. short_id is unique, so the store will never have the key (path + short_id).

fuyushimoya Over a year ago

Assume we have a parent with path / and id 2p45q, we create one key as /2p45q/ and use it to store in the hashmap, so when a child has path /2p45q/, we know that store['/2p45q/'] is its parent.

Alexander Nestorov Over a year ago

Oh, ok, it makes sense now. Thank you!

fuyushimoya Over a year ago

The key is created by combining your rule, starts with path, then its id, and add a '/' at the end, its and you can just use store[key] = _category to assign the element to the store with that key, no matter store[key] is previously exist or not.

Amit · Accepted Answer · 2015-07-21 09:15:20Z

This solution is more flexible in that it doesn't require knowledge of path length or correlation with short_id

var source = [{
  "short_id": "2p45q",
  "path": "/",
  "name": {
    "en-US": "IndustrialDesign"
  }
}, {
  "short_id": "2q56r",
  "path": "/2p45q/",
  "name": {
    "en-US": "Automotive"
  }
}];

function buildTree(arr) {
  var source = arr.slice();
  source.sort(function(a, b) {
    return a.path.length <= b.path.length;
  });
  var tree = source.splice(0, 1)[0];
  tree.subo = {};

  source.forEach(function(i) {
    var re = /[^\/]*\//g;
    var context = tree;
    while ((m = re.exec(i.path.substr(1))) !== null) {
      if (context.subo[m[0]] === undefined) {
        context.subo[m[0]] = i;
        i.subo = {};
        return;
      }
      context = context.subo[m[0]];
    }
  });

  (function subOsub(i) {
    var keys = Object.keys(i.subo);
    if (keys.length > 0) {
      i.sub = [];
      for (var j = 0; j < keys.length; j++) {
        i.sub.push(i.subo[keys[j]]);
        subOsub(i.subo[keys[j]]);
      }
    }
    delete i.subo;
  })(tree);
  return tree;
}

alert(JSON.stringify(buildTree(source), null, '  '));

1983 · Accepted Answer · 2015-07-21 10:14:56Z

Well, just examine the path of each object to see where to put it. You just need a mapping of paths to objects. E.g.

var objs = [
    {
        "short_id": "2p45q",
        "path": "/",
        "name": {
            "en-US": "IndustrialDesign"
        }
    },
    {
        "short_id": "blah",
        "path": "/2p45q/foo/",
        "name": {
            "blah": "blah"
        }
    },
    {
        "short_id": "2q56r",
        "path": "/2p45q/",
        "name": {
            "en-US": "Automotive"
        }
    }
];

// map paths to objects (one iteration)
var path_to_obj = {};
objs.forEach(function(obj){
    path_to_obj[obj.path] = obj;
});

// add objects to the sub array of their parent (one iteration)
objs.forEach(function(obj){
    var parentpath = obj.path.replace(/[^\/]*\/$/, '');
    var parent = path_to_obj[parentpath];
    if(parent){
        parent.sub = parent.sub || [];
        parent.sub.push(obj);
    }
});

var pre = document.createElement('pre');
pre.innerHTML = 'Result:\n' + JSON.stringify(path_to_obj['/'], null, 4);
document.body.appendChild(pre);

Collectives™ on Stack Overflow

Building a nested tree of data from plain array of objects

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related