Gap buffer

<h2 id="example">Example</h2>
<p>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 <a href="/facts/Pointer_(computer_programming)/fPoNzy9b">pointers</a> 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.
</p><p>Initial state:
</p>
This is the way [                     ]out.

<p>User inserts some new text:
</p>
This is the way the world started [   ]out.

<p>User moves the cursor before "started"; system moves "started " from the first buffer to the second buffer.
</p>
This is the way the world [   ]started out.

<p>User adds text filling the gap; system creates new gap:
</p>
This is the way the world as we know it [                   ]started out.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Dynamic_array/EtocbTWK">Dynamic array</a>, the special case of a gap buffer where the gap is always at the end</li>
<li><a href="/facts/Zipper_(data_structure)/Vjlz5eEe">Zipper (data structure)</a>, conceptually a generalization of the gap buffer.</li>
<li><a href="/facts/Linked_list/Ik4JTgJW">Linked list</a></li>
<li><a href="/facts/Circular_buffer/Xu7vpzmP">Circular buffer</a></li>
<li><a href="/facts/Rope_(computer_science)/VEv4ybP4">Rope (computer science)</a></li>
<li><a href="/facts/Piece_table/JMXSyArk">Piece table</a> - data structure used by Bravo and Microsoft Word</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://github.com/mkohlhaas/Pointers-C-Programming/blob/main/09_Dynamic_Memory_Management/9_7_gapbuf.c">Implementation in C</a></li>
<li><a href="http://www.codeproject.com/KB/recipes/GenericGapBuffer.aspx">Overview and implementation in .NET/C#</a></li>
<li><a href="https://github.com/lazyhacker/gapbuffer">Brief overview and sample C++ code</a></li>
<li><a href="http://www.codeproject.com/KB/recipes/SplitArrayDictionary.aspx">Implementation of a cyclic sorted gap buffer in .NET/C#</a></li>
<li><a href="http://history.dcs.ed.ac.uk/archive/apps/ecce/hmd/e915.imp.html">Use of gap buffer in early editor.</a> (First written somewhere between 1969 and 1971)</li>
<li><a href="https://www.gnu.org/software/emacs/manual/html_node/elisp/Buffer-Gap.html">emacs gap buffer info</a> (Emacs gap buffer reference)</li>
<li><a href="http://www.common-lisp.net/project/flexichain/download/StrandhVilleneuveMoore.pdf">Flexichain: An editable sequence and its gap-buffer implementation</a></li>
<li><a href="https://coredumped.dev/2023/08/09/text-showdown-gap-buffers-vs-ropes/">Text showdown: Gap Buffers vs Ropes</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Mark C. Chu-Carroll. "Gap Buffers, or, Don’t Get Tied Up With Ropes?" ScienceBlogs, 2009-02-18. Accessed 2013-01-30. <a href="http://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-why-bother-with-1/" target="_blank">http://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-why-bother-with-1/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>emacs gap buffer info Accessed 2013-01-30. <a href="https://www.gnu.org/software/emacs/manual/html_node/elisp/Buffer-Gap.html" target="_blank">https://www.gnu.org/software/emacs/manual/html_node/elisp/Buffer-Gap.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Gap buffer open-in-new

Gap buffer