Плоский JSON для иерархии с повторяющимися узлами

Question

Я строю иерархическую структуру объекта из плоской. Пока все работало нормально, но у меня проблема с элементами, которые имеют одинаковый родительский идентификатор. Например:

{
   'id': 9,
   'parentid': 7
 }, {
   'id': 9,
   'parentid': 8
 }, {
   'id': 10,
   'parentid': 9
 }

Насколько я понимаю, правильно, что элемент с идентификатором 9 появляется как под родителем 7, так и под родителем 8. И в то же время элемент с идентификатором 10 появляется под обоими экземплярами идентификатора 9. Итак, я в основном хочу это:

{
    "id": 7,
    "parentid": 1,
    "children": [
     {
      "id": 9,
      "parentid": 7,
      "children": [
       {
        "id": 10,
        "parentid": 9,
        "children": []
       },
{
    "id": 8,
    "parentid": 1,
    "children": [
     {
      "id": 9,
      "parentid": 8,
      "children": [
       {
        "id": 10,
        "parentid": 9,
        "children": []
       }

Но я получаю это вместо этого. Когда идентификатор был назначен один раз, возможные новые появления этого идентификатора игнорируются.

  {
    "id": 8,
    "parentid": 1,
    "children": [
     {
      "id": 9,
      "parentid": 8,
      "children": [
       {
        "id": 10,
        "parentid": 9,
        "children": []
       }

Это функция, которую я использую:

 function unflatten(arr) {
   var tree = [],
     mappedArr = {},
     arrElem,
     mappedElem;

   // First map the nodes of the array to an object -> create a hash table.
   for (var i = 0, len = arr.length; i < len; i++) {
     arrElem = arr[i];
     mappedArr[arrElem.id] = arrElem;
     mappedArr[arrElem.id]['children'] = [];
   }


   for (var id in mappedArr) {
     if (mappedArr.hasOwnProperty(id)) {
       mappedElem = mappedArr[id];
       // If the element is not at the root level, add it to its parent array of children.
       if (mappedElem.parentid) {
         mappedArr[mappedElem['parentid']]['children'].push(mappedElem);
       }
       // If the element is at the root level, add it to first level elements array.
       else {
         tree.push(mappedElem);
       }
     }
   }
   return tree;
 }

 var tree = unflatten(arr);

Я не понимаю, что нужно, чтобы рассмотреть все появления удостоверения личности, а не только в первый раз. Какую идею я должен исследовать дальше?

Answer 1

Неудобно иметь идентификатор объекта, но при этом хотеть иметь версию этого объекта с одним значением для parentid и другим с другим значением для parentid. Логически, идентификатор должен идентифицировать один объект, и один объект не может иметь два разных значения для одного и того же свойства одновременно.

Обратите внимание, как это заставляет ваш код работать неправильно в этой строке:

mappedArr[arrElem.id] = arrElem;

Так как один и тот же идентификатор встречается несколько раз, вы перезаписываете одну и ту же запись тем, какой последний объект (версия) вы назначаете здесь, теряя предыдущий (ые) объект (ы), у которого были другие значения для парентиды.

Вам следует рассмотреть возможность создания свойства parentIds во множественном числе и присвоить ему массив значений родительского идентификатора. Таким образом, вы можете поддерживать ситуацию, когда один объект имеет несколько родителей.

Обратите внимание, что граф, в котором узлы могут не только иметь несколько дочерних элементов, но и иметь нескольких родителей, - это не дерево (имя вашей переменной вводит в заблуждение), а (направленный) граф.

Начиная с вашего кода, я изменил его так:

function unflatten(arr) {
    var node,
        graph = [], // it is not a tree
        mapped = [];
    
    // 1. combine nodes with the same id:
    arr.forEach( function (node) {
        (mapped[node.id] || (mapped[node.id] = {
            id: node.id,
            parentIds: [],
            children: []
        })).parentIds.push(node.parentid);
    });
    
    // 2. assign children:
    mapped.forEach(function (node) {
        // Add as child to each of the parents 
        node.parentIds.forEach(function (parentid) {
            if (mapped[parentid]) {
                mapped[parentid]['children'].push(node);
            } else {
                // If parent does not exist as node, create it at the root level, 
                // and add it to first level elements array.
                graph.push(mapped[parentid] = {
                    id: parentid,
                    parentids: [],
                    children: [node]
                });
            }
        });
    });
    return graph;
}
// Sample data
var arr = [{
   'id': 9,
   'parentid': 7
}, {
   'id': 9,
   'parentid': 8
}, {
   'id': 10,
   'parentid': 9
}];
// Convert:
var graph = unflatten(arr);
console.log(JSON.stringify(graph, null, 4));

.as-console-wrapper { max-height: 100% !important; top: 0; }