Hacker News Reader

Comment by celeritascelery | Hacker News Reader

hmm. What happens when you move the gap from the front to the end of the text (or vice versa)? wouldn't that require you to update all the line boundaries? And wouldn't finding the position of the Nth line be O(n).

View on HN

Moving the gap from front to end - it takes O(n) time to do that both on the text (gap) buffer and the line-tracking (gap) buffer, so you're only a small constant factor worse.

Find the position of the Nth line is O(1) because N is either before the gap, in which case you just look up the Nth entry in the line-tracking buffer to get the position in the text buffer (which can be similarly mapped back to a position not including the gap in constant time if that's what you need), or N after the gap and you adjust the arithmetic to include the size of the gap.

This does seem like a really neat trick I have not heard of before. I am still confused about moving the gap in the line-tracking buffer. It seems to me the only way you could make look-up O(1) is if you updated all the line indexes you passed over when you moved the gap. Because they are pointing to absolute positions (right?). So moving the line-tracking gap would technically be O(n), but you couldn't use memmove, and instead would need to iterate over one and add or subtract the gap size. Am I misunderstanding?

The trick is to decouple the concept of 'position' in the text, that is independent of the gap, from 'pointer' into the buffer. If you keep track of line beginnings as positions, you can immediately get the pointers:

  ptr = pos if pos<=gapstart else pos + gapsize

Replying to myself: it's actually a bad idea because you have to update all indices at each inserted char! Forget about it...

The contents of the line-tracking buffer (ignoring its gap for a moment, which you could move anywhere) only change when the text-buffer's gap moves. When that happens, each time a line break moves across the gap, you need to update its index in the line tracking buffer.

It doesn't directly matter where the gap is in the line-tracking buffer except ideally it's positioned consistent with the user's cursor so that if they insert a bunch of new lines, they're inserted into the line-tracking gap.

The position of the line-tracking gap doesn't effect the values stored on either side of it gap, so you can still use memmove there.

Reply on news.ycombinator.com