JS: Получить идентификаторы объектов в определенном порядке

Question

Мне нужно получить все идентификаторы набора объектов в правильном иерархическом порядке.

Обновление: В этом примере идентификаторы расположены в алфавитном порядке, но они должны представлять случайные строки.

[
  { _id: 'abc', parent: 'mainID', main: 'mainID', order: 1, type: 'item' },
  { _id: 'def', parent: 'mainID', main: 'mainID', order: 2, type: 'item' },
  { _id: 'ghi', parent: 'mainID', main: 'mainID', order: 3, type: 'group' },
  { _id: 'jkl', parent: 'ghi', main: 'mainID', order: 1, type: 'item' },
  { _id: 'mno', parent: 'ghi', main: 'mainID', order: 2, type: 'group' },
  { _id: 'pqr', parent: 'mno', main: 'mainID', order: 1, type: 'item' },
  { _id: 'stu', parent: 'mainID', main: 'mainID', order: 4, type: 'item' }
]

Позвольте мне дать краткое объяснение моей структуры данных: Есть несколько пунктов (type).На первом уровне все элементы / группы имеют родительский элемент mainID.

Таким образом, для элементов первого уровня идентификаторы: ['abc','def','ghi','stu'].Третий элемент (ghi) представляет собой элемент group , который имеет еще два подэлемента - которые имеют родительский элемент ghi.

Второй подэлемент ('mno') также является группой, который имеет один подэлемент.

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

Таким образом, исходный массив также может выглядеть следующим образом:

[
  { _id: 'ghi', parent: 'mainID', main: 'mainID', order: 3, type: 'group' },
  { _id: 'jkl', parent: 'ghi', main: 'mainID', order: 1, type: 'item' },
  { _id: 'mno', parent: 'ghi', main: 'mainID', order: 2, type: 'group' },
  { _id: 'pqr', parent: 'mno', main: 'mainID', order: 1, type: 'item' },
  { _id: 'stu', parent: 'mainID', main: 'mainID', order: 4, type: 'item' },
  { _id: 'abc', parent: 'mainID', main: 'mainID', order: 1, type: 'item' },
  { _id: 'def', parent: 'mainID', main: 'mainID', order: 2, type: 'item' }
]

В лучшем визуальном виде объекты представляют эту структуру:

abc
def
ghi
  jkl
  mno
    pqr
stu

Что мне нужно, это идентификаторы в порядке сверху вниз

Таким образом, результат должен быть:

['abc', 'def', 'ghi', 'jkl', 'mno', 'pqr', 'stu']

Моя попытка не работает из-за вложенной структуры:

(elements) => {
  const result = []
  elements
    .filter(item => (item.parent === item.main))
    .forEach(elm => {
      result.push(elm._id)
      if (elm.type === 'group') {
        getOrderedId(elements, elm._id)
      }
    })
  return result
}

Answer 1

Я бы сначала создал Map, используя значения _id, где каждая запись начинается с пустого массива, который должен быть заполнен дочерними элементами этого родителя (если у него есть дочерние элементы).Добавлен дополнительный ключ для представления записи main, то есть корня.

Затем просто выполните итерацию ввода, чтобы внедрить каждый объект в соответствующий массив вышеуказанной древовидной структуры.

Затем, наконец,выполнить обход в порядке (используя рекурсию) в этой древовидной структуре и получить объекты по мере их посещения.

В следующем коде предполагается, что:

• Все объекты принадлежат одному и тому же объекту.дерево (имеет то же свойство main).
• Значения order не оставляют пробелов и начинаются с 1.

Свойство type не используется - это избыточная информация.

function ordered(elements) {
    if (!elements.length) return [];
    const rootId = elements[0].main;
    const children = new Map(elements.map(e => [e._id, []])).set(rootId, []);
    elements.forEach(e => children.get(e.parent)[e.order-1] = e);
    return [...(function * visit(id) {
        if (!children.has(id)) return;
        for (let child of children.get(id)) {
            yield child;
            yield * visit(child._id);
        }
    })(rootId)];
}

const elements = [{ _id: 'ghi', parent: 'mainID', main: 'mainID', order: 3, type: 'group' }, { _id: 'jkl', parent: 'ghi', main: 'mainID', order: 1, type: 'item' }, { _id: 'mno', parent: 'ghi', main: 'mainID', order: 2, type: 'group' }, { _id: 'pqr', parent: 'mno', main: 'mainID', order: 1, type: 'item' }, { _id: 'stu', parent: 'mainID', main: 'mainID', order: 4, type: 'item' }, { _id: 'abc', parent: 'mainID', main: 'mainID', order: 1, type: 'item' }, { _id: 'def', parent: 'mainID', main: 'mainID', order: 2, type: 'item' }];

console.log(ordered(elements));