Available as a package on Nuget.

Background

I’ve long been interested in text editors. Not just their use, but their design.

Over the years I’ve knocked up my own little editing tools purely for coding practice, and there are three main aspects that I find tricky/interesting.

• Efficiently handling text buffer storage and editing
• Mapping from screen location to text buffer contents
• Rendering the UI and handling the user input

For the first point probably the best option is a piece table. That said, a Gap Buffer is both simpler and also good enough.

What’s a Gap Buffer?

A normal collection type (eg a List) is a sequence of entries. As items are added or removed some form of shuffling is necessary to make space or compact space accordingly. This has an overhead which grows in direct proportion to the size of the text.

A gap buffer is similar, but it maintains a logical gap at the point of the last edit. The concept is that in the ideal use case a large number of edits happen at roughly the same location. When this occurs, with a gap buffer the text can expand into the gap without the following text needing moving.

For a text editor the majority of user inputs happen around the current cursor position. This makes a gap buffer ideal as that means the gap gets heavy usage.

Implementation of a generic gap buffer

Source

The code is a single file (plus extensive unit and performance tests). I’ve not published it as a package as it is only a beta - it needs more real life testing.

The linked repository includes performance tests. In the ideal use cases it’s between 13 and 1,500 times faster than a List<T>. In the worst case it’s 5 times slower. That use case is however clearly defined and the gap buffer should therefore be avoided.

Example usage

using GapBuffer;

var buffer = new GapBuffer<string>();
buffer.Append("Hello");
buffer.Append("World");
buffer.Insert(1, "Cruel");

for (var i = 0; i < 3; i++)
{
  Console.WriteLine(buffer[i]);
}

// Hello
// Cruel
// World