java - 使用文本更改同步将一组间隔映射到 2D 文本缓冲区

Question

我有一个类似于 2D 文本的缓冲区(基本上是 List<List<Object>> )，由 (row, col) 坐标索引。每行可以有任意长度。

让pos = (row, col) .然后一个区间由 (fromPos, toPos) 定义.

可以通过插入和删除字符来修改文本缓冲区:

void addRow(int rowIndex, Row<T> newRow);

void removeRow(int rowIndex);

void insert(int row, int col, Collection<? extends T> els);

void delete(int row, int col, int count);

如何反射(reflect)间隔位置的文本变化？区间是嵌套的，但并不严格。

主要问题是区间可以为空，必须保留区间的顺序和嵌套。

例如:

0 1   2  3 4        (interval number)[a[bcd[]][][ef]gh]  (text) 0 123      45 67   (char index)

插入 X 后在第3个区间(绝对位置4)应该变成

0 1   2  3  4           (interval number)[a[bcd[]][X][ef]ghijk]  (text)

有哪些存储区间的方法能够正确有效地反射(reflect)文本的变化？

Answer 1

我会将间隔存储为成对的“游标”，然后在伸展树(Splay Tree)中维护游标的顺序。我不会直接存储每个游标的行/列，而是使用差异表示。对于一维示例，要存储游标 A-E，其中 A=1、B=2、C=3、D=5、E=7，树可能是

    B2
   / \
  /   \
 /     \
A-1     D3
       / \
      C-2 E2

现在，当在位置 4 插入一个字符时，我使用标准插入算法找到左侧的第一个光标，并在下降时沿路径求和。这是光标 C，我将其展开到顶部，每次旋转时固定数字。

      C3
     / \
    /   \
   /     \
  B-1     D2
 /         \
A-1         E2

现在我给 C 的右 child 加一。由于差异表示，这具有将整个子树递增 1 的效果。

      C3
     / \
    /   \
   /     \
  B-1     D3
 /         \
A-1         E2

其他操作是操作splay树的简单练习。