Сортировать плоский массив по parentId javascript

Question

Каждый родительский элемент должен содержать общее количество всех подкатегорий.Будет очень хорошо, если решение будет использовать только методы объекта Array и не использовать циклы while.

Это пример базовой структуры:

const base = [
  { id: 1, count: 2, parentId: null },
  { id: 2, count: 4, parentId: 1 },
  { id: 3, count: 0, parentId: 2 },
  { id: 6, count: 8, parentId: 3 },
  { id: 7, count: 8, parentId: 3 },
  { id: 8, count: 2, parentId: 7 },
  { id: 4, count: 2, parentId: null },
  { id: 5, count: 1, parentId: 4 },
];

Вот как это должно выглядеть:

const expected = [
  { id: 1, count: 2, total: 24, parentId: null },
  { id: 2, count: 4, total: 22, parentId: 1 },
  { id: 3, count: 0, total: 18, parentId: 2 },
  { id: 6, count: 8, total: 8, parentId: 3 },
  { id: 7, count: 8, total: 10, parentId: 3 },
  { id: 8, count: 2, total: 2, parentId: 7 },
  { id: 4, count: 2, total: 3, parentId: null },
  { id: 5, count: 1, total: 1, parentId: 4 },
];

Вот мой текущий код.Я думаю, что здесь как-то мне нужно перейти на последний уровень, а затем начать с последнего элемента до верхнего уровня конкатенации с текущим уровнем count значения проп, поэтому я сделал имя IIFE.

let c = a.map(cat => {
  const top = a.filter(v => cat.id === v.parentId);
  let test;
  return ({
    ...cat,
    total: (test = categs => {
      return categs.reduce((acc, val) => {
         /* ??? */
         return acc + val.count
      }, cat.count);
    })(top)
  })
})

Answer 1

Если ваша коллекция уже отсортирована и нужно только рассчитать общую сумму.Я пришел с reduceRight, чтобы сохранить номера петли и избежать мутации.

const base = [
  { id: 1, count: 2, parentId: null },
  { id: 2, count: 4, parentId: 1 },
  { id: 3, count: 0, parentId: 2 },
  { id: 6, count: 8, parentId: 3 },
  { id: 7, count: 8, parentId: 3 },
  { id: 8, count: 2, parentId: 7 },
  { id: 4, count: 2, parentId: null },
  { id: 5, count: 1, parentId: 4 },
];

const rs = base.reduceRight((acc, o) => {
  const total = acc.filter(n => n.parentId === o.id).reduce((x, y) => x + y.total, 0)
  return acc.concat({...o, total: total + o.count})
}, [])

console.log(rs.reverse());

Answer 2

Вот удар:

const base = [
  { id: 1, count: 2, parentId: null },
  { id: 2, count: 4, parentId: 1 },
  { id: 3, count: 0, parentId: 2 },
  { id: 6, count: 8, parentId: 3 },
  { id: 7, count: 8, parentId: 3 },
  { id: 8, count: 2, parentId: 7 },
  { id: 4, count: 2, parentId: null },
  { id: 5, count: 1, parentId: 4 },
];

const getDescendants = ({ id }) =>
  base.reduce((acc, n) => n.parentId === id ? [...acc, n, ...getDescendants(n)] : acc, []);
const expected =
  base.map(record => ({
    ...record,
    total: getDescendants(record).reduce((acc, cur) => acc + cur.count, record.count)
  }));

console.log(expected);

Реальный трюк здесь - функция getDescendants.Он получает массив всех элементов, чья parentId prop равна id текущей записи, объединенной со всеми потомками этого узла, как определено рекурсивным применением функции.

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

---

Вот другой подход, рекурсивно модифицирующий исходный массив:

const base = [
  { id: 1, count: 2, parentId: null },
  { id: 2, count: 4, parentId: 1 },
  { id: 3, count: 0, parentId: 2 },
  { id: 6, count: 8, parentId: 3 },
  { id: 7, count: 8, parentId: 3 },
  { id: 8, count: 2, parentId: 7 },
  { id: 4, count: 2, parentId: null },
  { id: 5, count: 1, parentId: 4 },
];

const addToTotal = (id, count) => id !== null && base.forEach(n => {
  if (n.id === id) {
    n.total = (n.total || 0) + count;
    addToTotal(n.parentId, count);
  }
});
base.forEach(n => {
  n.total = (n.total || 0) + n.count;
  addToTotal(n.parentId, n.count);
});

console.log(base);