Gap buffer
This article will address the topic of Gap buffer, which has generated multiple debates and has aroused the interest of different sectors of society. Gap buffer is a topic of current relevance that has been the subject of study and research in different contexts and disciplines. Over time, Gap buffer has undergone various transformations and has acquired different meanings, which makes it a topic of great complexity and breadth. Therefore, it is essential to analyze in depth the different aspects and dimensions that Gap buffer encompasses, in order to understand its scope and impact in various areas. By exploring its origins, evolution and consequences, it is intended to offer a comprehensive and objective vision of Gap buffer, with the purpose of contributing to the understanding and reflection on this topic.
 | This article needs additional citations for verification. (April 2012) |
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 editors, 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 deletes it.
Text in a gap buffer is represented as two strings, which take very little extra space and which can be searched and displayed very quickly, compared to more sophisticated data structures such as linked lists. However, operations at different locations in the text and ones that fill the gap (requiring a new gap to be created) may require 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 amortized over the more common cheap operations. This makes the gap buffer a simpler alternative to the rope for use in text editors[1] such as Emacs.[2]
Example
Below are some examples of operations with buffer gaps. The gap is represented 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.
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 array, the special case of a gap buffer where the gap is always at the end
- Zipper (data structure), conceptually a generalization of the gap buffer.
- Linked list
- Circular buffer
- Rope (data structure)
- Piece table - data structure used by Bravo and Microsoft Word
References
- ^ Mark C. Chu-Carroll. "Gap Buffers, or, Don’t Get Tied Up With Ropes?" ScienceBlogs, 2009-02-18. Accessed 2013-01-30.
- ^ emacs gap buffer info Accessed 2013-01-30.
External links
- Implementation in C
- Brief overview and sample C++ code
- Use of gap buffer in early editor. (First written somewhere between 1969 and 1971)
- emacs gap buffer info (Emacs gap buffer reference)
- Flexichain: An editable sequence and its gap-buffer implementation
- Text showdown: Gap Buffers vs Ropes