This is exactly what I described. You make a gap buffer and move it into the original text. As typing happens, the size of the buffer is effectively decreased. You move the cursor/point, and need to move what is left of the gap. This is the same as rotating it.
To be clear, memcopy to move the buffer without using extra memory is the same as rotating.
If you don't believe me. Try it. Move some memory of arbitrary size using constant memory and see what algorithms you find. :)
I can only repeat what abecedarius said: it's nothing like a rotation because you don't care about the bytes in the gap.
It's a pretty tortured way to think about it; after googling I finally figured out what you meant. Sounds like the kind of algorithm I would never, ever ask about in a programming interview!
It is exactly like a rotation. Think of it this way. You have a file. Contents "this is the start". You copy it to memory. (Or map it. Doesn't matter.)
Now the cursor just after the word "the". How do you get the gap you did there? You likely started with: "this is the startGAP". You want "this is theGAP start". Look at only " startGAP" and see that getting "GAP start" is just a rotation.
Could you see this another way? Almost certainly. However, as a mutable algorithm, probably tough to beat using this way.
Finally.... Where did I say this was an interview question? Might be a fun discussion. Terrible fact based question.
We were just pointing out that changing "startGAP" to "GAPstart" is doing extra work; it's just as good to end up with "stastart"; we don't care what's in the bytes that you're writing as "GAP". The location of the gap is typically represented with a couple of pointers or ints.
Which didn't help your point. You don't care what is in the gap. But you do care what is in either side of it. So, you have to move those.
Edit:. Curse my phone typing. I am still contemplating this and see roughly what you are getting at. Didn't mean to post. I do challenge some of this. But still thinking. Apologies for posting early.
Edit2: on the assumption that I don't care what is in the gap,i think I fully agree with you and I was wrong. I challenge that some, but would have to think longer. Basically, my challenge is that undo and redo are more than a bit easier if you take care of the contents of the gap.
Here's a gap buffer in Lua. The code for inserting and deleting: https://github.com/darius/dole/blob/master/text.lua#L171
(The representation is documented at the start of the file. Some of the code in this function is only for assertions.)
The part that moves the gap is https://github.com/darius/dole/blob/master/text.lua#L178 and it's just a memmove. There's nothing like the permutation algorithm Bentley wrote about, his rotating by double reversal. If I'm missing your point, I'm sorry this is so troublesome -- maybe it's not worth the bother of correcting me.
(Added: I wrote the above before your edit. I hope this helps; probably there are better sources to read, but I picked this one because I wrote it.)
Yeah, apologies for the edits. I meant to hold on the thought some last time.
And it is absolutely no bother. Thanks for discussing it! Again, I would never dream of this as an interview thing. Fun discussion, though.
Some day I may dive into a text editor. Many of the data structures that are supposedly used there don't leap to me as obvious wins nowadays. They often pass the"appealing argument" test, but I have grown very weary of that.
