Editing Gap buffer (section)

{{Short description|Data structure used in text editors}}
{{refimprove|date=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 editor]]s, where most changes to the text occur at or near the current location of the [[cursor (computers)|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 [[string (computer science)|strings]], which take very little extra space and which can be searched and displayed very quickly, compared to more sophisticated [[data structure]]s such as [[linked list]]s. 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 analysis|amortized]] over the more common cheap operations. This makes the gap buffer a simpler alternative to the [[rope (data structure)|rope]] for use in text editors<ref name="chucarroll">Mark C. Chu-Carroll. "[http://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-why-bother-with-1/ Gap Buffers, or, Don’t Get Tied Up With Ropes?]" ''ScienceBlogs'', 2009-02-18. Accessed 2013-01-30.</ref> such as [[Emacs]].<ref name="elisp">[https://www.gnu.org/software/emacs/manual/html_node/elisp/Buffer-Gap.html emacs gap buffer info] Accessed 2013-01-30.</ref>