Suggestion for tracking lines does not work

[p-e-w]

On the subject of "How do I keep track of row, col information?", the README suggests:

The best way is to use a linebuffer data structure in conjunction with the Rope:

type Foo struct{
	*skiprope.Rope
	linebuf []int
}

The linebuf is essentially a list of offsets to a newline character.

This doesn't work. More precisely, it technically works, but doing this negates the advantages of using a rope in the first place. The reason is that maintaining the linebuf array when the rope is modified is an O(n) operation in the average case, where n is the number of lines. Under standard assumptions (bounded line length), this makes inserting into and deleting from the rope an O(n) operation in the length of the text – and we are back to zero. At this point, the "rope" is just a very complicated string.

Rope implementations designed for line-based editing store line count information directly in the binary tree's nodes, in addition to the fragment length. This allows for line operations with a complexity of O(log(n)). Of course, instead of a line array as suggested, one could use a binary tree to externally track lines, but that would entail mirroring the rope's internal structure outside of it, which is extremely ugly.

It appears, then, that the correct answer to the question "How do I keep track of row, col information?" is currently "Use a different package", which is rather unfortunate because all other rope implementations written in Go that I am aware of suffer from the same shortcoming (unlike e.g. ropey, which gets this right).

[chewxy]

Rope implementations designed for line-based editing store line count information directly in the binary tree's nodes, in addition to the fragment length. This allows for line operations with a complexity of O(log(n)).

So this issue is solvable with a bit of sacrifice to heap mem? Would you like to put a PR in?

[p-e-w]

I have since found a more suitable solution for my original problem than using a rope, so I won't be adding this myself. But I did think about it some more and realized that because this package is built around a skip list rather than a binary tree, line tracking might not be as straightforward as it is for conventional rope implementations. It's unclear how storing line counts in the skip node hierarchy would provide the same guarantees as doing so with tree nodes. I'm sure it's still possible somehow, but not necessarily easy.