Thursday, January 19, 2012

Implement Text Editor with Gap Buffer

Gap Buffer is a data structure which can be used to implement text editor. The advantage is that insertion/deletion can be very efficient and the data structure is simple. The disadvantage is when cursor changes its location frequently or the gap is frequently full, there will be a lot of copying operation, which is costly. The following gives more details about gap buffer.

  • Basically gap buffer can be implemented as an array (or a dynamic array) with some pointers to differentiate three regions: the segment before the gap, the gap, the segment after the gap.
| the front segment  |   the gap  |  the back segment  |
  • The location of the cursor in the text editor decides the border between the front segment and the gap. A example is given here:
We had a [            ] big day
  • As the above example, "We had a" is the front segment, "[   ]" is the gap buffer and "big day" is in the back segment. 
  • When insertion, new text is filled in the gap buffer, the start pointer of the gap buffer also moves accordingly. If the gap is full, we need to create new gap buffer and we may also need to move all the content in the back segment backwards.
  • When deletion,  we only need to move the start pointer of the gap buffer forwards if we are deleting the text in the front segment or  the end pointer of the gap buffer backwards if we are deleting the text in the back segment.
  • If we move the cursor, for example, the cursor is between "We" and "had" now:  "We [     ] had a big day". We need to copy the "had a" which was originally in the front segment to the back segment.

1 comment:

  1. do you have any simple source code implementation for this?
    prefferably in C

    ReplyDelete