编辑器的数据结构

我从来没有实现过任何一个编辑器。但对于这么一个我们每天都使用的工具，如何高效的实现其内部结构是一个有趣的话题。首先， 一个高效的算法，以下几点是值得考虑的重点：

1. 所占的空间大小
2. 插入，删除的效率。

最直接的方法是使用一个数组， 数组的每一个成员对应一个相应的字符。这样不需要任何冗余空间，但是缺点也是显而易见的： 每次插入和删除都要进行数组拷贝的动作。

一个初步的提高， 我们是否能够在删除的时候不做这个拷贝动作, 而使用一个特殊的字符来取代。但是我们如何避免在插入时进行数组拷贝的动作呢。这个问题将直接导致两个常用的编辑器数据结构： Gap Buffer 和 Piece Table.

Gap Buffer:
就是在插入和删除的地方使用一个buffer，这个buffer可以看成在数组中的一个空白区域。这个区域随着编辑器光标的移动而移动。 实例如下：
                           

数组：我们使用  【                          】编辑器
                            ^
插入 “文本” 
我们使用文本【                         】编辑器 
                                    ^

   移动光标至文本之前：

  我们使用【                       】文本编辑器      

                     ^                          

        删除 “文本”:

     我们使用【                           】编辑器

       Gap Buffer 相应的数据结构也很简单：

public class 



GapBuffer


{
    private int 

startGapIndex;
    private int 

endGapIndex;
    private char

[FileSystemPageSize] textBuffer;
}

      GapBuffer 在光标移动的时候要进行数组拷贝。所以在文件比较大的时候，通常我们要使用一个链表的GapBuffer来存储文本。在上述的结构中，使用文件系统的page size 来构建buffer。当然我们还需要考虑，合并和扩展buffer的操作。

GapBuffer 的使用者包括Emacs.

Piece Table:

相比较Gap Buffer, Piece Table稍显复杂一些。Piece Table的实现由两个buffer组成，一个buffer是只读的，另一个buffer是可写的 （只能添加）。每一个Piece 代表了这两个buffer中的一块内存。每一个piece可以表示如下：

public class 



Piece


{
    private int 

bufferIndex;
    private int 

bufferOffset;
    private int 

length;
}

最终的文件可以看成所有piece的合在一起。示例如下：

buffer 0:【我们使用编辑器  】                 

buffer 1:【                                 】

buffer index	offset	length
0	0	7

插入 “文本”

buffer 0:【我们使用编辑器  】                 

buffer 1:【文本                                 】

buffer index	offset	length
0	0	4
1	0	2
0	4	3

删除 “我们”:

buffer 0:【我们使用编辑器  】                 

buffer 1:【文本                                 】

buffer index	offset	length
0	0	4
1	0	2
0	4	3

在 piece table 的实现中，两个buffer的内容都不会被删除。每次添加则是在buffer 1中增加一个piece.而每次删除仅仅是改变table的内容。这样的一个好处是我们只需要记住table的变化就可以实现undo和redo了。在每一个piece中加入一些其它的描述符，我们可以记录诸如字体等信息 。 很多文本编辑器都使用这种方法。