根据值将对象数组转换为嵌套对象

Question

如何根据开始和结束之间的值将对象数组转换为嵌套对象？

假设我有一个这样的数组：

const array = [
  {
      "content": "_88888888888  ~*8888888888*~  *8888888*_",
      "start": 5,
      "end": 37
  },
  {
      "content": "~*88888*~",
      "start": 18,
      "end": 27
  },
  {
      "content": "*88888*",
      "start": 19,
      "end": 26
  },
  {
      "content": "*88888*",
      "start": 29,
      "end": 36
  }
]

我想将其转换为：

const array = [
  {
      "content": "_88888888888  ~*88888*~  *88888*_",
      "start": 5,
      "end": 37,
      "children": [
        {
          "content": "~*88888*~",
          "start": 18,
          "end": 27,
          "children": [
            {
              "content": "*8888888888*",
              "start": 19,
              "end": 26
            },
          ]
        },
        {
          "content": "*88888*",
          "start": 29,
          "end": 36
        }
      ]
  }
]

如您所见，在预期结果中，每个子值都有匹配起始值和结束值的父对象。

Answer 1

我将按 span-width 降序迭代数组 objects。创建一个具有无限跨度的虚拟根节点。然后将每个 object 插入该树中：

首先找出当前树节点是否有一个child可以成为object的一个parent。如果是这样，使 child 成为当前的，然后重复。
一旦没有这样的child，将object追加到当前节点的children集合中。

这是一个实现：

const array = [{"content": "_88888888888  ~*8888888888*~  *8888888*_","start": 5,"end": 37},{"content": "~*88888*~","start": 18,"end": 27},{"content": "*88888*","start": 19,"end": 26},{"content": "*88888*","start": 29,"end": 36}];

const root = {
    start: -Infinity,
    end: Infinity,
    children: []
};

// Iterate in order of descending span width
for (let obj of [...array].sort((a, b) => (b.end - b.start) - (a.end - a.start))) {
    let child = root, 
        children;
    // Find and drill down    
    do {
        children = (child.children ??= []);
        child = children.find(child => child.start <= obj.start && child.end >= obj.end);
    } while (child);
    // Insert
    children.push({...obj});
}

console.log(root.children);

Answer 2

与大多数 arbitrary-nesting 场景一样，我们可以通过一定程度的递归来做到这一点。

const excluding = (os) => (xs) =>
  xs .filter ((x) => ! os .includes (x))
  
const minBy = (fn) => (xs) =>
  xs .reduce (
    ({m, c}, x, _, __, v = fn (x)) => v < m ? {m: v, c: x} : {m, c}, 
    {m: Infinity}
  ) .c

const restructure = (
  xs, 
  o = minBy (x => x .start) (xs), 
  kids = xs .filter ((x) => x !== o && x .start >= o .start && x .end <= o .end)
) => xs .length ? [
  {...o, ...(kids .length ? {children: restructure (kids)} : {})},
  ... restructure (excluding ([o, ...kids]) (xs)) 
] : []

const array = [{content: "_88888888888  ~*8888888888*~  *8888888*_", start: 5, end: 37}, {content: "~*88888*~", start: 18, end: 27}, {content: "*88888*", start: 19, end: 26}, {content: "*88888*", start: 29, end: 36}]

console .log (restructure (array))

.as-console-wrapper {max-height: 100% !important; top: 0}

我们从辅助函数 excluding 开始，它过滤一个列表以包括所有不在另一个列表中的函数（类似于集差函数），并且minBy，它根据提供的函数的结果找到列表的最小元素。

我们的主函数通过起始值找到第一个元素，找到该元素的所有后代（基于比较起始值和结束值），在这些后代上重复创建一个 children 节点，并在剩余元素上重复查找输出的后续元素。

这与 Trincot 的回答略有不同。这里同一级别的元素按起始值递增排序。该答案通过减小范围大小对它们进行排序。

根据值将对象数组转换为嵌套对象

Convert array of objects to nested object based on values

javascript

algorithm