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

Question

[Владимир Допустим]

Всем привет! Допустим, существует вот такая коллекция:

var cats = [
{ id: 1, parent_id: 0, title: 'Кино' },
{ id: 2, parent_id: 0, title: 'Музыка' },
{ id: 3, parent_id: 1, title: 'Зарубежное кино' },
{ id: 4, parent_id: 2, title: 'Зарубежная музыка' },
{ id: 5, parent_id: 3, title: 'Новое' },
{ id: 6, parent_id: 3, title: 'Топ10' },
{ id: 7, parent_id: 4, title: 'Новое' },
{ id: 8, parent_id: 4, title: 'Топ10' },
{ id: 9, parent_id: 0, title: 'Софт' }
];

Нужно сделать так:

var catsExtended = [
{ id: 1, parent_id: 0, childs: [ 3, 5, 6 ], title: 'Кино' },
{ id: 2, parent_id: 0, childs: [ 4, 7, 8 ], title: 'Музыка' },
{ id: 3, parent_id: 1, childs: [ 5, 6 ], title: 'Зарубежное кино' },
{ id: 4, parent_id: 2, childs: [ 7, 8 ], title: 'Зарубежная музыка' },
{ id: 5, parent_id: 3, childs: [], title: 'Новое' },
{ id: 6, parent_id: 3, childs: [], title: 'Топ10' },
{ id: 7, parent_id: 4, childs: [], title: 'Новое' },
{ id: 8, parent_id: 4, childs: [], title: 'Топ10' },
{ id: 9, parent_id: 0, childs: [], title: 'Софт' }
];

Answer 1

[Владимир Допустим]

Всем спасибо, ответ нашелся на stackoverflow: stackoverflow.com/questions/38208245/how-to-genera...

Answer 2

[Дмитрий Беляев]

1) преобразуете массив в объект с помощью _.indexBy из lodash/underscore при этом так как внутри массива объекты, то полученый объект будет содержать ссылки на те же объекты
2) пробегаем исходный массив и отмечаем в childs у родителя

UPD: писал с телефона в дороге, дополню кодом
Простой вариант, как описано мною выше:

var catsIndex = _.indexBy(cats, 'id');
cats.forEach(function(el) {
  if(!catsIndex[el.parent_id]) return;
  if(!catsIndex[el.parent_id].childs) catsIndex[el.parent_id].childs = [];
  catsIndex[el.parent_id].childs.push(el.id);
});
console.log(cats);

Оптимизированный вариант, в один проход:

var catsChilds = {};
for(var i = cats.length; i--;) {
  if(catsChilds[cats[i].id]) {
    cats[i].childs = catsChilds[cats[i].id];
  } else {
    cats[i].childs = catsChilds[cats[i].id] = [];
  }
  if(!catsChilds[cats[i].parent_id]) {
    catsChilds[cats[i].parent_id] = [];
  }
  catsChilds[cats[i].parent_id].push(cats[i].id);
}
console.log(cats);

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

Comments

[Владимир Допустим]

Спасибо за ваш ответ, интересный подход, но это не решает задачу. Кстати, _.indexBy из lodash/underscore переименован в keyBy (версия 4.0.0) https://github.com/lodash/lodash/wiki/Changelog

[Дмитрий Беляев]

Владимир Допустим: может тогда я не понял задачу, распишите поподробнее
Насчет lodash давно уже не использую, ибо таскать ее из-за пары функций реализуемых за 5-10 минут, просто глупо

[Владимир Допустим]

В результате у меня регистируются все потомки, включая потомков этих потомков. Т.е. 5 и 6 - потомки для 3

Answer 3

[theWaR_13]

oskarhane.com/create-a-nested-array-recursively-in...

Comments

[Владимир Допустим]

Спасибо за ваш ответ, но это не решает задачу

[theWaR_13]

Владимир Допустим: а что именно не решает задачу? У меня недавно по работе была один в один задача, все сделал с помощью алгоритма по ссылке, немного поменяв названия полей объектов.

[Владимир Допустим]

theWaR_13: такой результат для меня получить было не трудно, но меня заинтесовало, как можно получить именно тот результат, который я представил в условии задачи. Т.е. запись ID всех потомков в массиве, включая потомков этих потомков