Как переделать массив объектов?

Question

[Антон]

Есть данные в виде массива объектов следующего вида:

[
  {
    "id": 1,
    "parent": null,
    "name": "Ange Quittonden",
  },
  {
    "id": 2,
    "parent": 1,
    "name": "Bobina Pascow"
  },
  {
    "id": 3,
    "parent": 1,
    "name": "Hashim Stein"
  },
  {
    "id": 4,
    "parent": 1,
    "name": "Bernadene Gillum"
  },
  {
    "id": 5,
    "parent": 1,
    "name": "Yale Masedon"
  },
  {
    "id": 6,
    "parent": 1,
    "name": "Ellissa Cayton"
  },
  {
    "id": 7,
    "parent": 1,
    "name": "Marybelle Kelston"
  },
  {
    "id": 8,
    "parent": 1,
    "name": "Vevay Cowern"
  },
  {
    "id": 9,
    "parent": 1,
    "name": "Bondy Ridolfo"
  },
  {
    "id": 10,
    "parent": 1,
    "name": "Valenka Macguire"
  },
  {
    "id": 11,
    "parent": 7,
    "name": "Irene Prodrick"
  },
  {
    "id": 12,
    "parent": 7,
    "name": "Ella Kilpin"
  },
  {
    "id": 13,
    "parent": 7,
    "name": "Raeann Regenhardt"
  },
  {
    "id": 14,
    "parent": 7,
    "name": "Emile Jobbins"
  },
  //...
]

Необходимо на выходе получить новый массив, в котором у каждого элемента появится поле(массив) "children", если дети существуют, в котором должны находиться все дети. Пример:

[
  {
    "id": 1,
    "parent": null,
    "name": "Ange Quittonden",
    "children": [
      {
        "id": 2,
        "parent": 1,
        "name": "Bobina Pascow"
      },
      {
        "id": 3,
        "parent": 1,
        "name": "Hashim Stein"
      },
      {
        "id": 4,
        "parent": 1,
        "name": "Bernadene Gillum"
      },
      {
        "id": 5,
        "parent": 1,
        "name": "Yale Masedon"
      },
      {
        "id": 6,
        "parent": 1,
        "name": "Ellissa Cayton"
      },
      {
        "id": 7,
        "parent": 1,
        "name": "Marybelle Kelston",
        "children": [
          {
            "id": 11,
            "parent": 7,
            "name": "Irene Prodrick"
          },
          {
            "id": 12,
            "parent": 7,
            "name": "Ella Kilpin"
          },
          {
            "id": 13,
            "parent": 7,
            "name": "Raeann Regenhardt"
          },
          {
            "id": 14,
            "parent": 7,
            "name": "Emile Jobbins"
          }
        ]
      }
    ]
  },
  //...
]

Подскажите идеи, варианты, как это сделать максимально эффективно?

Comments

[Пашенька]

Максимально правильно - это когда на выходе у вас получается массив объектов полностью соответствующий вашим ожиданиям. А вот максимально эффективно - это выполнить предыдущее требование за минимальное количество итераций.

[Антон]

Пашенька, согласен, не верно выразился

Answer 1

[Aetae]

Один проход, но в каждом узле будет children даже если пустой:

function unFlatten(array) {
  const childrenMap = Object.create(null);
	for(const item of array) {
    if(item.parent in childrenMap) 
      childrenMap[item.parent].push(item);
    else
      childrenMap[item.parent] = [item];  
    
    if(!childrenMap[item.id]) childrenMap[item.id] = []; 
    
    item.children = childrenMap[item.id];
  };
  return childrenMap[null]
}

Один-два прохода, как повезёт, но children только там где нужны.

function unFlatten(array) {
  const childrenMap = Object.create(null);
  const secondPass = [];
	for(const item of array) {
    if(item.parent in childrenMap) 
      childrenMap[item.parent].push(item);
    else
      childrenMap[item.parent] = [item];  
    
    if(item.id in childrenMap) 
      item.children = childrenMap[item.id];
    else
      secondPass.push(item)
  };	
  for(const item of secondPass) {
    if(item.id in childrenMap) 
      item.children = childrenMap[item.id];
  };
  return childrenMap[null]
}

Или от обратного:

function unFlatten(array) {
  const map = Object.create(null);
  const secondPass = [];
  for(const item of array) {
    map[item.id] = item;
    if(item.parent in map) {
      if('children' in map[item.parent])
        map[item.parent].children.push(item)
      else
        map[item.parent].children = [item];
    } else {
      secondPass.push(item);
    }
  };
  for(const item of secondPass) {
    if(item.parent in map) {
      if('children' in map[item.parent])
        map[item.parent].children.push(item)
      else
        map[item.parent].children = [item];
    }
  };
  return secondPass
}

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