data-structureslogictext-editorropes

Using rope in text editors

enter image description here

I was reading up on how I would go about making a text editor from scratch. I came across various different data structures like gap buffers, piece tables, and rope. I can understand how the others would work in practice, and I understand the benefits of rope and how it works logistically. However, I do not understand how an editor would actually utilize rope. Let me explain.

Let's say I have a new file and enter "Hello world!". I would imagine every key press the editor would deal with each character. However, from the program logic side, I don't see the obvious way to handle each new character. From what I understand, rope is useful due to how the tree structure allows for relatively low-cost search, insert, append, and deletion. However, if I am handling input character-by-character am I expected to have:

  1. Each node be a single character
  2. Have every node hold X amount of characters
  3. Each node is a full word and the nodes break by whitespace
  4. Every character typed every X amount of time goes to a node
  5. Something I have not yet thought of

The first option while easy enough to implement, does not seem to make much sense and I do not believe makes the best use of the rope structure. The second option seems to only half-use ropes by appending to the string inside the node until it reaches the X length. The third option has the same problem as the second option, but at least does not break the string at some set length. Option 4 would give similar results to what I see in most example graphs for ropes, but seems like a nightmare at the implementation level.

TL;DR: When using ropes in a text editor, what is ideally supposed to happen between pressing a key and that character showing up in the tree? Either pseudo-code or just a high-level explanation will suffice here.

Solution

  • As I saw implementation of ROPE, it follows option 2. You can check below implementation. (Its not exact Text editor implementation) https://www.geeksforgeeks.org/ropes-data-structure-fast-string-concatenation/

    I would recommend to check below link and check piece table data structure for text editor. http://www.averylaird.com/programming/the%20text%20editor/2017/09/30/the-piece-table/