next up previous
Next: The gap method Up: Basic Sequence Data Previous: Basic Sequence Data

The array method (one span in one buffer)

This is the most obvious sequence data structure. In this method there is one span and one buffer. Two descriptors are needed: one for the span and one for the buffer. (See Figure 2gif)

Figure 2: The array method  

The buffer contains the items of the sequence in physically contiguous order. Deletes are handled by moving all the items following the deleted item to fill in the hole left by the deleted item. Inserts are handled by moving all the items that will follow the item to be inserted in order to make room for the new item. ItemAt is an array reference. The buffer can be extended as much as necessary to hold the data.

Clearly this would not be an efficient data structure if a lot of editing was to be done are large files. It is a useful base case and is a reasonable choice in situations where few inserts and deletes are made (e.g., a read-only sequence) or the sequences are relatively small (e.g., a one-line text editor). This data structure is sometimes used to hold the sequence of descriptors in the more complex sequence data structure, for example, an array of line pointers (see section 6).

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