大约刚上大二的时候，想做一个编辑器控件。不是一个用Scintilla套上外壳的编辑器，而是一个能被套上外壳的控件。当然它最后也成为了我众多流产了的练手项目中的一员，不过人人黑历史里还留存着当时的一张截图
那段时间也对编辑器所使用的数据结构非常感兴趣。我们需要一种数据结构，能够支持字符串高效地索引、遍历、插入和删除。当时找的一些论文和书还躺在硬盘里一直没删，如今拿出来再嚼一嚼。下面介绍几种在编辑器中常见的数据结构。
朴素一维数组
不用说，效率比较低，几乎没有人会直接采用这种方式。把整篇文档看做一个字符串，即便我们预留了空间，也会在字符串头插入字符时暴毙。
不过，虽然这种方式无法满足需求，把它稍加改进却能够得到一个非常不错的结构。
Gap Buffer
Gap Buffer是朴素的一维数组的改进版本，它将“空白”（指字符串没有填满Buffer的部分）移动到了Buffer中间。如下图所示：
简而言之，当我们执行插入或删除动作的时候，Buffer中的空白（Gap）随之移动。例如，下面一句话中，初始情况下空白在Buffer的最后：
This is a smple txt.[ ]
我们使用中括号[ ]来表示空白。然后当我想要在smple中插入a时，编辑器首先把空白移动到s后面：
This is a s[ ]mple txt.
然后在s后面插入a：
This is a sa[ ]mple txt.
如果我想在txt中插入一个e，则需要同样的步骤：
This is a sample t[ ]xt.
This is a sample te[ ]xt.
这种方法所基于的假设是，编辑文本时通常为连续作战，而打游击的时候并不会连续工作。
Linked Line
文本通常是一种二维结构，同时“行”这个概念在文档渲染等方面又有着不一样的意义，因此把它们单独做一层抽象也比较合理。在每一行内部，直接使用字符串或者Gap Buffer都可以。
Piece Table Buffer
Piece Table Buffer是一种效率更高的结构，但是会浪费更多的内存。Piece Table Buffer的核心思想是：在字符串末尾添加字符的代价很低（我们预留了空间），字符的移动代价很高。因此它会尽可能避免字符串的移动操作。
Piece Table Buffer由两部分Buffer组成。第一个Buffer保存的是原始的文件内容，这个Buffer是只读的。另一个Buffer用于新加入的内容，它只能进行Append操作。同时，用一张表（Piece Table）来表明当前文档的组成。例如：
Original Buf: This is a smple txt.
Append Buf: [Empty]
Piece Table:
| buffer | from | to | content |
|---|---|---|---|
| original | 0 | 21 | This is a smple txt. |
首先我将smple删掉，则它们变成了：
Original Buf: This is a smple txt.
Append Buf: [Empty]
Piece Table:
| buffer | from | to | content |
|---|---|---|---|
| original | 0 | 11 | This is a |
| original | 16 | 21 | txt. |
则此时的句子为This is a txt.。随后，我在原来smple处又插入了new，则
Original Buf: This is a smple txt.
Append Buf: new
Piece Table:
| buffer | from | to | content |
|---|---|---|---|
| original | 0 | 11 | This is a |
| append | 0 | 4 | new |
| original | 16 | 21 | txt. |
句子就变为了This is a new txt.。
Piece Buffer的好处还在于能够比较轻松地实现Redo/Undo，不需要额外的Buffer记录修改过的字符串，因为所有编辑过的历史信息都存在两个Buffer中。
Rope
Rope是一种二叉树结构，如下图所示：
其中Rope的叶子节点存储字符串，内部节点存储叶子节点中字符串的长度。为了避免树的深度过深的问题，可以采用一定的平衡策略。
编辑器们都用了哪种数据结构？
部分Emacs使用了Gap Buffer，包括古老的 Emacs on TECO[1]、现代的GNU/Emacs[8]及其前辈Gosling Emacs[2]。Scintilla (即包括Code::Blocks在内的很多IDE/编辑器使用的代码编辑控件) 也使用了Gap Buffer。[4]
Emacs进入由Lisp实现的时代后，一些Emacs版本使用了LinkedLine[1]。
Vim使用的是一种基于行的数据结构[5]，但行与行之间不是简单地使用链表连接，而是用一种树结构进行管理[6]。
KDE的Okteta 16进制编辑器使用了Piece Table Buffer。[7]
本文开头的示例编辑器也使用了Piece Table Buffer
。
Reference
- The Craft of Text Editing, Craig A. Finseth, 1991.
- Data Structures in the Andrew Text Editor, Wilfred J. Hansen, 1986.
- Data Structures for Text Sequences, CharlesCrowley, 1998.
- Scintilla CVS CellBuffer.h
- NeoVim Wiki Page Architectural musing and ideas
- Vim memline.c
- Okteta repo folder
- GNU Emacs Lisp Reference Manual