javascript 优化算法合并带装饰的文本节点

v2g6jxz6 于 2023-09-29 发布在 Java

关注(0)|答案(1)|浏览(92)

我需要你帮我弄清楚如何合并两个带有装饰的节点数组。我有一个非常低效的算法，工作，但我需要更好的东西或任何想法。
我有两个这样的文本节点数组。一般来说，每个节点由文本和文本装饰（颜色、字体样式等）以及from、to索引组成。我想合并这两个数组，这样文本就保持不变，但装饰将被合并。
下面是我目前的算法，它迭代内容中的每个字母，检查字母是否有任何装饰，并为带有所有装饰的字母创建一个单独的节点：

const getDecorationsByIndex = (nodes, index) => {
  const foundNodes: any[] = [];

  nodes.forEach(node => {
    if (index >= node.from && index < node.to) {
      foundNodes.push(node);
    }
  });

  return foundNodes.flatMap(node => node.textData?.decorations || []);
};

const mergeNodes = (nodes1, nodes2, content) => {
  const mergedNodes = [...content].map((s, index) => {
    const decorations1 = getDecorationsByIndex(nodes1, index);
    const decorations2 = getDecorationsByIndex(nodes2, index);

    return {
      id: '',
      nodes: [],
      type: Node_Type.TEXT,
      textData: {
        decorations: [...decorations1, ...decorations2],
        text: s,
      },
    };
  });

  return mergedNodes;
};

作为一个例子，让我们采取一个简单的文本def有各种装饰，从颜色到字体粗细。
每个数组都完全表示文本。这一条增加了一些大胆：

[
  {
      "type": "TEXT",
      "id": "",
      "nodes": [],
      "textData": {
          "text": "de",
          "decorations": [
              {
                  "type": "BOLD",
                  "fontWeightValue": 700
              }
          ]
      },
      "from": 0,
      "to": 2
  },
  {
      "type": "TEXT",
      "id": "",
      "nodes": [],
      "textData": {
          "text": "f",
          "decorations": []
      },
      "from": 2,
      "to": 3
  }
]

第二个数组添加颜色：

[
  {
      "id": "",
      "nodes": [],
      "type": "TEXT",
      "textData": {
          "decorations": [
              {
                  "type": "COLOR",
                  "colorData": {
                      "foreground": "#d73a49"
                  }
              }
          ],
          "text": "def"
      },
      "from": 0,
      "to": 3
  }
]

结果应为：

[
  {
      "type": "TEXT",
      "id": "",
      "nodes": [],
      "textData": {
          "text": "de",
          "decorations": [
              {
                  "type": "BOLD",
                  "fontWeightValue": 700
              },{
                  "type": "COLOR",
                  "colorData": {
                      "foreground": "#d73a49"
                  }
              }
          ]
      },
      "from": 0,
      "to": 2
  },
  {
      "type": "TEXT",
      "id": "",
      "nodes": [],
      "textData": {
          "text": "f",
          "decorations": [{
                  "type": "COLOR",
                  "colorData": {
                      "foreground": "#d73a49"
                  }
              }]
      },
      "from": 2,
      "to": 3
  }
]

结果应该是这些节点的一个数组，最终将具有相同的文本和所有的装饰。帮助我优化我的算法或指出正确的方向，我应该如何处理合并这些节点。谢谢

JavaScript

来源：https://stackoverflow.com/questions/77187698/optimize-the-algorithm-to-merge-text-nodes-with-decorations

1条答案

按热度按时间

ubby3x7f1#

您可以使用from/to信息按索引对节点进行排序（因此需要复制节点，一次用于获取其from属性，一次用于to属性）。然后排序，并按此顺序迭代，以跟踪哪些装饰是活动的或不活动的。
在开始之前，您还可以收集子字符串并从中重建字符串。然后，这可以在主算法中使用，以再次将其切片。

const Node_Type = { TEXT: 3 };

// Helper function to toggle a set member
const toggle = (set, member) => !set.delete(member) && set.add(member);

const extractText = (nodes) =>
    // Reconstruct text from the nodes (there should be no inconsistency)
    nodes.reduce((acc, node) => {
        acc.length = Math.max(acc.length, node.from);
        acc.splice(node.from, node.to - node.from, ...node.textData.text);
        return acc;
    }, []).map(ch => ch ?? " ").join("");

const mergeNodes = (nodes1, nodes2) => {
    const nodes = nodes1.concat(nodes2);
    const text = extractText(nodes);
    const activeNodes = new Set;
    return nodes.flatMap(node => [[node.from, node], [node.to, node]])
                 .sort(([a], [b]) => a - b)
                 .map(([from, node], i, toggles) => {
        toggle(activeNodes, node); // Activate or deactivate a decoration
        const to = toggles[i+1]?.[0] ?? text.length;
        if (from === to || !activeNodes.size) return; // Nothing to generate here
        return {
            id: '',
            nodes: [],
            type: Node_Type.TEXT,
            textData: {
               decorations: Array.from(activeNodes, ({textData: {decorations}}) => decorations).flat(), 
               text: text.slice(from, to),
            },
            from,
            to
        };
    }).filter(Boolean); // Exclude the undefined entries
}

// Sample input
const a = [{
    "type": "TEXT", "id": "", "nodes": [],
    "textData": { "text": "de", "decorations": [{"type": "BOLD","fontWeightValue": 700}] },
    "from": 0, "to": 2
}, {
    "type": "TEXT", "id": "", "nodes": [],
    "textData": { "text": "f someFoo", "decorations": []},
    "from": 2, "to": 11
}];

const b = [{
    "id": "", "nodes": [], "type": "TEXT",
    "textData": {
        "decorations": [{"type": "COLOR","colorData": {"foreground": "#d73a49"}}],
        "text": "def"
    },
    "from": 0, "to": 3
}, {
    "id": "", "nodes": [], "type": "TEXT",
    "textData": { "decorations": [], "text": " "},
    "from": 3, "to": 4
}, {
    "id": "", "nodes": [], "type": "TEXT",
    "textData": {
        "decorations": [{"type": "COLOR", "colorData": {"foreground": "#6f42c1"}}],
        "text": "someFoo"
    },
    "from": 4, "to": 11
}];

console.log(mergeNodes(a, b));

请注意，共享的装饰并没有被克隆，因此一些节点在它们的decorations数组中将具有相同的对象引用。这意味着如果你改变一个装饰，它将应用于所有共享它的节点。如果你想让它以不同的方式工作，你应该在这个过程中克隆装饰。

赞(0）回复(0）举报 2023-09-29

我来回答

javascript 优化算法合并带装饰的文本节点

1条答案

相关问题

热门标签

最新问答