Javascript: анализ и сортировка плоской структуры JSON на вложенные массивы?

Question

Я начинаю с простого ввода JSON как такового (простой пример):

[
{id:1, value:'child1', parentId:2, sortOrder:1},
{id:2, value:'root1', parentId:null, sortOrder:1},
{id:3, value:'root2', parentId:null, sortOrder:2},
{id:4, value:'child2', parentId:1, sortOrder:2},
{id:5, value:'root3', parentId:null, sortOrder:3},
{id:6, value:'child1', parentId:2, sortOrder:1},
{id:7, value:'root4', parentId:null, sortOrder:4}
];

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

Для форматирования выходных данных можно использовать как собственный JS, так и UnderscoreJS.

Вывод будет отформатирован как структура json с базовой формой:

root1 
  child1
  child2
root2
  child1
    child1
    child2
  child2

  etc...

Где каждый элемент является объектом JSON.

Глубина вложения может быть любой, поскольку данные, скорее всего, поступают из таблицы БД с указанной выше плоской структурой.

Какие-нибудь мысли?

Answer 1

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

const flat = [
{id:1, value:'child1', parentId:2, sortOrder:1},
{id:2, value:'root1', parentId:null, sortOrder:1},
{id:3, value:'root2', parentId:null, sortOrder:2},
{id:4, value:'child2', parentId:1, sortOrder:2},
{id:5, value:'root3', parentId:null, sortOrder:3},
{id:6, value:'child1', parentId:2, sortOrder:1},
{id:7, value:'root4', parentId:null, sortOrder:4}
];

const nested = flat.filter((elt, idx, arr) => {
  const parent = arr.find(e => e.id === elt.parentId);
  if (!parent) return true;
  (parent.children = parent.children || []).push(elt);
});

console.log(nested);

Сортировка останется в качестве упражнения.

Answer 2

Я бы сделал эту работу следующим образом. Я мог бы использовать value свойства, чтобы прикрепить вложенные объекты, но вопрос был неясным на тот момент. Вместо этого я создал children свойства для построения вложенной структуры.

var flat = [
{id:1, value:'child1', parentId:2, sortOrder:1},
{id:2, value:'root1', parentId:null, sortOrder:1},
{id:3, value:'root2', parentId:null, sortOrder:2},
{id:4, value:'child2', parentId:1, sortOrder:2},
{id:5, value:'root3', parentId:null, sortOrder:3},
{id:6, value:'child1', parentId:2, sortOrder:1},
{id:7, value:'root4', parentId:null, sortOrder:4}
],
     lut = flat.sort((a,b) => a.sortOrder - b.sortOrder)
               .reduce((t,o) => { o.children === void 0 && (o.children = []);
                                  t[o.id] = t[o.id] === void 0 ? o : (o.children = t[o.id].children,o);
                                  o.parentId     !== null &&
                                  (t[o.parentId] !== void 0 ? t[o.parentId].children.push(o)
                                                            : t[o.parentId] = {id: o.parentId, children: [o]});
                                  return t;
                                },{}),
  nested = Object.keys(lut).reduce((a,k) => lut[k].parentId === null ? a.concat(lut[k]): a,[]);
console.log(nested);

Так же sort этап не будет необходимым, если вы хотите разместить дочерние объекты в родительском children свойство массива так, как вы их получаете.