Recursive sequence data structures

The line span method is an older method that has little to recommend it in modern text editors.

The Fsb methods and the Piece method are both good choices for professional-quality text editors. Both methods:

• are acceptably fast if caching is used
• handle large files without slowing down
• handle many of files without slowing down
• are efficient in their use of space
• allow efficient buffer management
• provide excellent locality of buffer use

Overall however the piece table method seems to be better. It has a number of advantages:

• All buffers except one are read-only and the other buffer is append-only. (Thus the buffers are easy to cache and work well over a network.)
• The code is quite simple. (The code for Fsb is complicated by the need to balance buffers.)
• Huge files load as quickly as tiny files. (No preprocessing is required for large files so they load quickly.)
• Disk buffers are always full of data (rather than 3/4 full--on the average--as they are in the fixed buffer method). Thus disk caching is more efficient.
• Items never move once they are placed.

The last point is important. If the piece sequence is kept as a list then the pieces never move either. This allows the sequence to be pointed to by other data structures that record additional information about the sequence. For example it is fairly easy to implement ``sticky'' pointers [Reference to Fisher and Ladner] (that is, pointers that point to the content of the sequence rather than relative sequence positions). For example we might want to attach a sticky pointer to the beginning of a procedure definition. Such a facility would be useful in implementing a ``tag'' facility such as the one found in Unix[2].

As another example, the text editor Lara [8] also formats its text. It keeps the formatting state in a tree structure where pieces are the leaves of the tree. Inserts and deletes require very little bookkeeping because the items and pieces never move around when you use a piece table.