Hi
I came across this link, and thought maybe it would be interesting to some
of you.
http://www.cs.unm.edu/~crowley/papers/sds/sds.html
It's an article with the title: "Data Structures for Text Sequences", and
here's the abstract:
The data structure used ot maintain the sequence of characters is
an important part of a text editor. This paper investigates and
evaluates the range of possible data structures for text
sequences. The ADT interface to the text sequence component of a
text editor is examined. Six common sequence data structures
(array, gap, list, line pointers, fixed size buffers and piece
tables) are examined and then a general model of sequence data
structures that encompasses all six structures is presented. The
piece table method is explained in detail and its advantages are
presented. The design space of sequence data structures is
examined and several variations on the ones listed above are
presented. These sequence data structures are compared
experimentally and evaluated based on a number of criteria. The
experimental comparison is done by implementing each data
structure in an editing simulator and testing it using a synthetic
load of many thousands of edits. We also report on experiments on
the senstivity of the results to variations in the parameters used
to generate the synthetic editing load.
/Christian
--
Christian Ridderström http://www.md.kth.se/~chr
