javascript - JS : Get IDs of objects in specific order

Question

我需要以正确的层次顺序获取一组对象的所有 ID。

更新:在此示例中，ID 按字母顺序排列，但它们应代表随机字符串。

[
  { _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' }
]

让我对我的数据结构做一个简短的解释: 有几个项目(类型)。在第一级中，所有项目/组都有父 mainID。

因此，第一级元素的 ID 为:['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

我需要的是从上到下顺序的ID

所以结果应该是:

['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

我首先会创建一个以 _id 值作为键的映射，其中每个条目都以一个空数组开头，需要用该父级的子级(如果它有子级)填充该数组。添加一个额外的键来代表 main 条目，即根。

然后只需迭代输入以将每个对象注入(inject)上述树结构的适当数组中。

然后最终在该树结构中执行中序遍历(使用递归)并在访问时生成对象。

以下代码假设:

• 所有对象都属于同一棵树(具有相同的 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));