next up previous
Next: Conclusions and Recommendations Up: Comparison of Sequence Previous: Basic sequence data

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:

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

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.


next up previous
Next: Conclusions and Recommendations Up: Comparison of Sequence Previous: Basic sequence data

Charlie Crowley
Thu Jun 27 15:36:10 MDT 1996