Mapping a set of intervals to 2D text buffer with text change synchronization

I have a 2D text-like buffer (basically List<List<Object>>), indexed by (row, col) coordinates. Each row can have arbitrary length.

Let pos = (row, col). Then an interval is defined by (fromPos, toPos).

The text buffer can be modified by inserting and deleting characters:

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);

How do I reflect changes in the text in position of intervals? Intervals are nested, but not strictly.

The main problem is that intervals can be empty and the 开发者_开发问答ordering and nesting of intervals must be preserved.

For example:

0 1   2  3 4        (interval number)

[a[bcd[]][][ef]gh]  (text)

 0 123      45 67   (char index)

after insert of X in the 3rd interval (absolute position 4) should become

0 1   2  3  4           (interval number)

[a[bcd[]][X][ef]ghijk]  (text)

What are some ways to store intervals to be able to reflect changes of the text correctly and efficiently?

---

I would store intervals as pairs of "cursors" and then maintain the order of the cursors in a splay tree. Rather than store the row/column of each cursor directly, I would use a difference representation. For a 1D example, to store cursors A-E with A=1, B=2, C=3, D=5, E=7, the tree might be

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

Now, when inserting a character at position 4, I use the standard insertion algorithm to find the first cursors to the left, summing along the path as I descend. This is cursor C, which I splay to the top, fixing the numbers with each rotate.

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

Now I add one to C's right child. Because of the difference representation, that has the effect of incrementing the whole subtree by one.

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

The other operations are simple exercises in manipulating splay trees.