4 ms·

Ropes are inherently a binary tree. From what I can understand you can implement piece tables both as a double linked list and a b-tree. Furthermore in ropes ev

Ropes are inherently a binary tree. From what I can understand you can implement piece tables both as a double linked list and a b-tree. Furthermore in ropes every leaf spans one character, in piece tables, pieces have different lengths. Furthermore with ropes, every operation returns a new rope data structure, that means ropes are immutable. If you want to implement undo, you only keep references to the former ropes. There is no inserting or adding via looking up the changes in an undo list. I think maybe if you implemented a piece table, where every piece spans one character, used a binary tree and made it immutable, you'd get a ropes data structure. For more information about persistence vs immutability this link might help: https://stackoverflow.com/questions/10034537/persistent-vs-immutable-data-structure https://stackoverflow.com/questions/10034537/persistent-vs-i...

deathanatos 9y ago
> Furthermore in ropes every leaf spans one character, The Boehm paper on ropes[1] (which is about the only academic literature on the subject that I know of) does not do that (and explicitly suggests one should not), nor does any real-world implementation, (e.g., the Boehm implementation, SGI's impl) do that. It would be incredibly inefficient, and for no real gain. A good rope implementation will store an array of characters/bytes in the leaves, up to some threshold. > Furthermore with ropes, every operation returns a new rope data structure, that means ropes are immutable. There is nothing inherently immutable about ropes, and it is certainly possible to mutate a rope. (For example, appending a single character to a leaf with space is much quicker if the rope as a whole is mutable.) Look at the SGI implementation for an example here; their reference docs[2] contain sufficient details to see that the rope itself is mutable. Now, a rope typically just describes a sequence of characters. It is entirely possible for a leaf node in a specialized rope to reference on-disk content, and other leaves to reference in-memory content. In that regards, it can be like a piece table. Implementing an undo/redo on top of a rope is less straight-forward; whereas a piece table's undo history can essentially share large portions of the linked list (see the lovely diagrams here[3]) I'm not sure the same can be done on a Rope's tree, due to the tree's need to balance and re-balance. That is, without copying the tree, since that kind of defeats a lot of the benefits that a piece table has — not needing to copy the entire "file", even if that's just a bunch of spans. Now, one could make the leaves in a rope ref-counted (so they could be shared) and then copy the Concat nodes for undo/redo levels. Keeping the concat nodes as copies means the copies can balance independently, and since concat nodes are small (~2 pointers for left/right and a depth, IIRC) that isn't too much copying (the bulk of the data, the text, is refcounted in the leaves). But the simplicity of the piece table really starts to shine at this point. [1]: http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9... [2]: http://www.sgi.com/tech/stl/Rope.html http://www.sgi.com/tech/stl/Rope.html [3]: http://www.catch22.net/tuts/piece-chains http://www.catch22.net/tuts/piece-chains
- terminalcommand 9y ago
  I stand corrected, thanks for the thorough answer. My interest in ropes was arisen from the "data structures for text editors" post here on HN. Most resources were haskell implementations. IBM Developerworks had an article about ropes and a corresponding java library, the article stated ropes were immutable. https://www.ibm.com/developerworks/library/j-ropes/index.html https://www.ibm.com/developerworks/library/j-ropes/index.htm... I admit being wrong on every node storing a single character, that misconception stems from a graph I saw representing ropes on yesterday's article. Undoing with immutable ropes is very straightforward I think. You don't copy the whole file, but just the references. I admit it is heavier on the memory, but you could store an arbitrary amount of previous "states" or versions in ram. The benchmark on the Java library may prove this point. I will try to read the original article to gain more insight. Thanks again for the resources.

deathanatos 9y ago

> Furthermore in ropes every leaf spans one character, The Boehm paper on ropes[1] (which is about the only academic literature on the subject that I know of) does not do that (and explicitly suggests one should not), nor does any real-world implementation, (e.g., the Boehm implementation, SGI's impl) do that. It would be incredibly inefficient, and for no real gain. A good rope implementation will store an array of characters/bytes in the leaves, up to some threshold. > Furthermore with ropes, every operation returns a new rope data structure, that means ropes are immutable. There is nothing inherently immutable about ropes, and it is certainly possible to mutate a rope. (For example, appending a single character to a leaf with space is much quicker if the rope as a whole is mutable.) Look at the SGI implementation for an example here; their reference docs[2] contain sufficient details to see that the rope itself is mutable. Now, a rope typically just describes a sequence of characters. It is entirely possible for a leaf node in a specialized rope to reference on-disk content, and other leaves to reference in-memory content. In that regards, it can be like a piece table. Implementing an undo/redo on top of a rope is less straight-forward; whereas a piece table's undo history can essentially share large portions of the linked list (see the lovely diagrams here[3]) I'm not sure the same can be done on a Rope's tree, due to the tree's need to balance and re-balance. That is, without copying the tree, since that kind of defeats a lot of the benefits that a piece table has — not needing to copy the entire "file", even if that's just a bunch of spans. Now, one could make the leaves in a rope ref-counted (so they could be shared) and then copy the Concat nodes for undo/redo levels. Keeping the concat nodes as copies means the copies can balance independently, and since concat nodes are small (~2 pointers for left/right and a depth, IIRC) that isn't too much copying (the bulk of the data, the text, is refcounted in the leaves). But the simplicity of the piece table really starts to shine at this point. [1]: http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9... [2]: http://www.sgi.com/tech/stl/Rope.html http://www.sgi.com/tech/stl/Rope.html [3]: http://www.catch22.net/tuts/piece-chains http://www.catch22.net/tuts/piece-chains

terminalcommand 9y ago
I stand corrected, thanks for the thorough answer. My interest in ropes was arisen from the "data structures for text editors" post here on HN. Most resources were haskell implementations. IBM Developerworks had an article about ropes and a corresponding java library, the article stated ropes were immutable. https://www.ibm.com/developerworks/library/j-ropes/index.html https://www.ibm.com/developerworks/library/j-ropes/index.htm... I admit being wrong on every node storing a single character, that misconception stems from a graph I saw representing ropes on yesterday's article. Undoing with immutable ropes is very straightforward I think. You don't copy the whole file, but just the references. I admit it is heavier on the memory, but you could store an arbitrary amount of previous "states" or versions in ram. The benchmark on the Java library may prove this point. I will try to read the original article to gain more insight. Thanks again for the resources.