Gap buffer
Encyclopedia
A gap buffer In computer science
is a dynamic array
that allows efficient insertion and deletion operations clustered near the same location. Gap buffers are especially common in text editor
s, where most changes to the text occur at or near the current location of the cursor
. The text is stored in a large buffer in two contiguous segments, with a gap between them for inserting new text. Moving the cursor involves copying text from one side of the gap to the other (sometimes copying is delayed until the next operation that changes the text). Insertion adds new text at the end of the first segment. Deletion increases the size of the gap.
s (such as linked list
s) is that the text is represented simply as two literal strings, which take very little extra space and which can be searched and displayed very quickly.
over the more common cheap operations.
possible that an editing operation is close to the preceding one, measured as the difference
in positions in the sequence. These technical things led towards implementation of the editable sequences as a gap buffer.
Initial state:
This is the way [ ]out.
User inserts some new text:
This is the way the world started [ ]out.
User moves the cursor before "started"; system moves "started " from the first buffer to the second buffer.
This is the way the world [ ]started out.
User adds text filling the gap; system creates new gap:
This is the way the world as we know it [ ]started out.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
is a dynamic array
Dynamic array
In computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is a random access, variable-size list data structure that allows elements to be added or removed...
that allows efficient insertion and deletion operations clustered near the same location. Gap buffers are especially common in text editor
Text editor
A text editor is a type of program used for editing plain text files.Text editors are often provided with operating systems or software development packages, and can be used to change configuration files and programming language source code....
s, where most changes to the text occur at or near the current location of the cursor
Cursor (computers)
In computing, a cursor is an indicator used to show the position on a computer monitor or other display device that will respond to input from a text input or pointing device. The flashing text cursor may be referred to as a caret in some cases...
. The text is stored in a large buffer in two contiguous segments, with a gap between them for inserting new text. Moving the cursor involves copying text from one side of the gap to the other (sometimes copying is delayed until the next operation that changes the text). Insertion adds new text at the end of the first segment. Deletion increases the size of the gap.
Advantages
The advantage of using a gap buffer over more sophisticated data structureData structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s (such as linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
s) is that the text is represented simply as two literal strings, which take very little extra space and which can be searched and displayed very quickly.
Disadvantages
The disadvantage is that operations at different locations in the text and ones that fill the gap (requiring a new gap to be created) require re-copying most of the text, which is especially inefficient for large files. The use of gap buffers is based on the assumption that such recopying occurs rarely enough that its cost can be amortizedAmortized analysis
In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...
over the more common cheap operations.
Text Editing with Gap Buffer
Editable sequences are useful, in particular in interactive applications such as text editors, word processors, score editors, and much more. In such kind of applications, it is highlypossible that an editing operation is close to the preceding one, measured as the difference
in positions in the sequence. These technical things led towards implementation of the editable sequences as a gap buffer.
Example
Below are some examples of operations with buffer gaps. The gap is represented pictorially by the empty space between the square brackets. This representation is a bit misleading: in a typical implementation, the endpoints of the gap are tracked using pointers or array indices, and the contents of the gap are ignored; this allows, for example, deletions to be done by adjusting a pointer without changing the text in the buffer. It is a common programming practice to use a semi-open interval for the gap pointers, i.e. the start-of-gap points to the invalid character following the last character in the first buffer, and the end-of-gap points to the first valid character in the second buffer (or equivalently, the pointers are considered to point "between" characters).Initial state:
This is the way [ ]out.
User inserts some new text:
This is the way the world started [ ]out.
User moves the cursor before "started"; system moves "started " from the first buffer to the second buffer.
This is the way the world [ ]started out.
User adds text filling the gap; system creates new gap:
This is the way the world as we know it [ ]started out.
See also
- Dynamic arrayDynamic arrayIn computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is a random access, variable-size list data structure that allows elements to be added or removed...
, the special case of a gap buffer where the gap is always at the end - Zipper (data structure)Zipper (data structure)A zipper is a technique of representing an aggregate data structure so that it is convenient for writing programs that traverse the structure arbitrarily and update its contents, especially in purely functional programming languages. The zipper was described by Gérard Huet in 1997...
, conceptually a generalization of the gap buffer. - Linked listLinked listIn computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
- Circular bufferCircular bufferA circular buffer, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end.This structure lends itself easily to buffering data streams.-Uses:...
- Rope (computer science)Rope (computer science)In computer programming a rope, or cord, is a data structure for efficiently storing and manipulating a very long string. For example, a text editing program may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done...
External references
- Overview and implementation in .NET/C#
- Brief overview and sample C++ code
- Implementation of a cyclic sorted gap buffer in .NET/C#
- Use of gap buffer in early editor. (First written somewhere between 1969 and 1971)
- emac gap buffer info(Emacs gap buffer reference)
- Text Editing