在文本编辑器中使用rope

Question

​

​

我正在阅读如何从头开始做一个文本编辑器。我遇到了各种不同的数据结构，如间隙缓冲器、块表和绳子。我能理解其他人在实践中是如何工作的，我也理解绳子的好处以及它在后勤上的运作方式。然而，我不明白编辑如何实际使用绳子。让我解释一下。

假设我有一个新文件并输入“！”。我可以想象编辑的每一个按键都会处理每个角色。但是，从程序逻辑方面来看，我看不到处理每个新字符的明显方法。据我所知，由于树结构允许相对低成本的搜索、插入、附加和删除，rope是有用的。但是，如果我处理的是逐个字符的输入，那么我需要：

1. 每个节点都是单个字符。
2. 让每个节点保存X个字符
3. 每个节点都是一个完整的单词，节点按空格分隔。
4. 键入的每一个字符，每X次的时间，都会到达一个节点
5. 一些我还没有想到的事情

第一个方案虽然很容易实施，但似乎没有多大意义，我不认为最能利用绳子的结构。第二个选项似乎只有一半使用绳子，通过附加到节点内的字符串，直到它达到X长度。第三个选项与第二个选项有相同的问题，但至少不会在一定长度处中断字符串。选项4将给出与我在大多数示例图表中看到的类似的结果，但在实现级别上似乎是一场噩梦。

TL;DR:在文本编辑器中使用绳子时，在按下键和显示在树中的字符之间应该发生什么？无论是伪代码还是高层解释，在这里都足够了。

Answer 1

正如我看到的那样，它遵循选项2，您可以在下面检查实现。(它不是精确的文本编辑器实现) https://www.geeksforgeeks.org/ropes-data-structure-fast-string-concatenation/

我建议检查下面的链接和检查表格数据结构的文本编辑器。http://www.averylaird.com/programming/the%20text%20editor/2017/09/30/the-piece-table/

Answer 2

在查看了rope的现有实现之后，看起来选项2是如何在文本编辑器中实际使用它的。