Отображение набора интервалов в 2D текстовый буфер с синхронизацией изменения текста

Question

У меня есть 2D текстоподобный буфер (в основном List<List<Object>>), проиндексированный координатами (строка, столбец). Каждая строка может иметь произвольную длину.

Пусть 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);

Как мне отразить изменения в тексте в позиции интервалов? Интервалы являются вложенными, но не строго.

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

Например:

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)

Какими способами можно хранить интервалы, чтобы иметь возможность корректно и эффективно отражать изменения текста?

Answer 1

Я бы сохранял интервалы в виде пар «курсоров», а затем поддерживал бы порядок курсоров в дереве отображения. Вместо того, чтобы хранить строку / столбец каждого курсора напрямую, я бы использовал представление разницы. Например, для хранения курсоров 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

Теперь я добавляю один к правильному ребенку Си. Из-за различий, это приводит к увеличению целого поддерева на единицу.

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

Другие операции - это простые упражнения по манипуляции с деревьями сплайнов.