7 ms·

There exists a phenomenal paper comparing ropes, gap buffers, and piece chains I cannot recall. There is a lua editor called Vis that uses piece chains which t

There exists a phenomenal paper comparing ropes, gap buffers, and piece chains I cannot recall. There is a lua editor called Vis that uses piece chains which the paper suggests is best.

taeric 10y ago
I would be very interested in if you could find that paper. Briefly reading on piece chains, I can't see how they would be the preferred way, sadly. (I'm assuming the failing is on me, hence the sadly.) Even gap buffers seem somewhat odd to me. I'm assuming the gap is only created/inserted when text is typed. Not just on moving of the point/cursor. That, or thinking longer, I suppose that the contents of the file can be out of sync while the buffer is not saved. So, probably possible to easily insert and shift a gap periodically into the text, as needed. (I'm envisioning the rotate memory code from Programming Pearls to keep the gap where you want it.) Similarly, the piece chain (which, I should add that googling that was a piece of hilarity), if it is possible to "snapshot" the base of the piece chain every so often to what is on disk, it would just mean inverting some of the change pieces. Which doesn't sound too hard.
- abecedarius 10y ago
  You don't need to rotate memory, because you don't care about the contents of the gap.
  - taeric 10y ago
    My thinking: You load a file. All text is one giant buffer. You make a gap buffer and need it somewhere in the original buffer. Otherwise... How does this work? You want to move the gap to a new location. Which is the same as originally moving it in. This is effectively rotating part of the buffer.
    - greglindahl 10y ago
      https://en.wikipedia.org/wiki/Gap_buffer https://en.wikipedia.org/wiki/Gap_buffer has a good explanation. You allocate extra space and do memmove() to open/move/close the gap.
      - taeric 10y ago
        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. :)
        greglindahl 10y ago
        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!
        taeric 10y ago
        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.
        abecedarius 10y ago
        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.
gbrown_ 10y ago
Data Structures for Text Sequences by Charles Crowley? https://www.cs.unm.edu/~crowley/papers/sds.pdf https://www.cs.unm.edu/~crowley/papers/sds.pdf I recall coming across this when hearing about vis.
- greglindahl 10y ago
  This paper only discusses editing.
- codygman 10y ago
  Yes! I believe that was it. If not it's very similar.

There exists a phenomenal paper comparing ropes, gap buffers, and piece chains I cannot recall. There is a lua editor called Vis that uses piece chains which the paper suggests is best.

taeric 10y ago

I would be very interested in if you could find that paper. Briefly reading on piece chains, I can't see how they would be the preferred way, sadly. (I'm assuming the failing is on me, hence the sadly.) Even gap buffers seem somewhat odd to me. I'm assuming the gap is only created/inserted when text is typed. Not just on moving of the point/cursor. That, or thinking longer, I suppose that the contents of the file can be out of sync while the buffer is not saved. So, probably possible to easily insert and shift a gap periodically into the text, as needed. (I'm envisioning the rotate memory code from Programming Pearls to keep the gap where you want it.) Similarly, the piece chain (which, I should add that googling that was a piece of hilarity), if it is possible to "snapshot" the base of the piece chain every so often to what is on disk, it would just mean inverting some of the change pieces. Which doesn't sound too hard.

abecedarius 10y ago
You don't need to rotate memory, because you don't care about the contents of the gap.
- taeric 10y ago
  My thinking: You load a file. All text is one giant buffer. You make a gap buffer and need it somewhere in the original buffer. Otherwise... How does this work? You want to move the gap to a new location. Which is the same as originally moving it in. This is effectively rotating part of the buffer.
  - greglindahl 10y ago
    https://en.wikipedia.org/wiki/Gap_buffer https://en.wikipedia.org/wiki/Gap_buffer has a good explanation. You allocate extra space and do memmove() to open/move/close the gap.
    - taeric 10y ago
      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. :)
      - greglindahl 10y ago
        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!
        taeric 10y ago
        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.
        abecedarius 10y ago
        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.

gbrown_ 10y ago

Data Structures for Text Sequences by Charles Crowley? https://www.cs.unm.edu/~crowley/papers/sds.pdf https://www.cs.unm.edu/~crowley/papers/sds.pdf I recall coming across this when hearing about vis.

greglindahl 10y ago
This paper only discusses editing.
codygman 10y ago
Yes! I believe that was it. If not it's very similar.