Hacker News Reader

Comment by celeritascelery | Hacker News Reader

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?

View on HN

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.

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...

Reply on news.ycombinator.com