Создание вложенного дерева данных из обычного массива объектов

Question

У меня есть массив объектов, как те из них:

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

... 

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

Я должен итерацию по каждому элементу массива и проверить path, а затем найти parent элемента и нажать его в новом свойстве массива этого родителя, который называется sub. Каждый ребенок может иметь собственное свойство sub, являясь родителем большего числа детей. Конечный результат (для этого примера) будет выглядеть следующим образом:

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

У меня есть рабочий код (с помощью 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; 
} 

но производительность очень плохо, в основном потому, что я запрашивая весь массив для каждой итерации.

Мой вопрос в том, как я могу оптимизировать свой код?

Примечания:

• Каждый short_id находится ровно 5 символов.
• Каждый символ в short_id может быть [0-9a-z]
• path гарантированно начинается и заканчивается с /

Answer 1

Создайте другой объект TMP как Hashmap, так что вы можете просто использовать пути и идентификатор, чтобы создать новый ключ магазин.

Логика:

1. Если путь '/', его корень, положить в _categories массив.

2. Если нет, проверьте, существует ли родитель-мишень в hashStore или нет, если нет, создайте поддельный, а его цель для цели - sub attr.

3. Для всех элементов, создайте ключ от _category.path + _category.short_id + '/', и проверить, если его существовать в hashStore, если существует, то один в магазине должен быть поддельной, получить sub от подделки. Затем назначьте себе hashStore с помощью созданного ключа.

Используйте ключ, чтобы решить, существует ли объект на карте или нет, O (1). Таким образом, выполнение этой функции должно быть O (n), а n - число элементов в списке происхождения.

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; 
} 

Answer 2

Это решение является более гибким в том, что он не требует знания длины пути или корреляции с 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, ' '));

Answer 3

Ну, просто проверить путь каждого объекта посмотрите, куда его поместить. Вам просто нужно отобразить пути к объектам. Например.

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);