javascript - Building a nested tree of data from plain array of objects -

i have array of objects, ones:

{   "short_id": "2p45q",   "path": "/",   "name": {     "en-us": "industrialdesign"   } }  ...  {   "short_id": "2q56r",   "path": "/2p45q/",   "name": {     "en-us": "automotive"   } } 

i must iterate on each element of array , check path, find parent of element , push in new array property of parent called sub. each child can have sub property on it's own, being parent of more children. final result (for example) like:

{   "short_id": "2p45q",   "path": "/",   "name": {     "en-us": "test a"   },   "sub": [     {       "short_id": "2q56r",       "path": "/2p45q/",       "name": {         "en-us": "test a.1"       }     }   ] } 

i have 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 performance bad, because i'm querying entire array each iteration.

my question how can optimize code?

notes:

• each short_id 5 characters long.
• each character in short_id can [0-9a-z]
• path guaranteed start , end /

create tmp object hashmap, can use path , id create new key store.

logic :

1. if path '/', root, put _categories array.

2. if not, check if target parent exist in hashstore or not, if not, create fake one, , put self target sub attr.

3. for element, create key _category.path + _category.short_id + '/', , check if exist in hashstore, if exist, 1 in store should fake, sub fake. assign hashstore created key.

use key decide whether object exist in map or not should o(1). performance of function should o(n) while n 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 parent's sub       target.sub.push(_category);     }      // create key map     var key = _category.path + _category.short_id + '/';     // if fake object exist, sub;     if (typeof store[key] !== 'undefined') {       _category.sub = store[key].sub;     }     store[key] = _category;    });    return _categories; }