gap_buffer - PatrickAMoran/misc-c-- GitHub Wiki

The gap buffer is a popular data structure for implementing things such as text-editor buffers. This is because it allows efficient insertions and deletions if they tend to be clustered around a certain point (known as the gap or cursor).

A gap buffer is typically implemented with two containers, one holding all the data of the buffer before the cursor, and another holding all the data of the buffer after the cursor. Moving the cursor is implemented by copying data from the front of the after container onto the end of the before container, or vice versa as appropriate.

The gap_buffer subdirectory contains an implementation of a gap buffer (in gap_buffer.hpp) as an STL container adapter. Since many different types could be chosen for the underlying containers, this is used as the template parameter. So, for example, if you would like your underlying containers to be of type std::deque<char>, then you want a gap_buffer<std::deque<char> >.

This adapter notably implements the concepts of Sequence and Reversible Container. The means you can use it as you would expect to use any other STL container, and things should just work.

However, in addition to this, there are also additional member functions that can be used to take advantage of the properties of the gap buffer.

Iterator Access

iterator here();

const_iterator here() const;

reverse_iterator rhere();

const_reverse_iterator rhere() const;

These four member functions return iterators at the position of the gap (plain, const, reverse and const_reverse, respectively). Specifically, if you dereference these iterators, you will get the first element after the gap.

Gap Operations

size_type position() const;

Returns the position of the gap as an unsigned integer offset from the start of the container.

void advance(difference_type);

Advances the cursor by the given amount. If the amount is positive, the cursor moves forward. If the amount is negative, the cursor moves backward a number of elements equal to the absolute value of the argument.

void erase(difference_type);

Remove elements from the container at the cursor. If the given amount is positive, the elements are removed from after the cursor. If the given amount is negative, a number of elements equal to the absolute value of the argument is removed from immediately before the cursor.

void insert(value_type)

Insert an element at the cursor. This moves the cursor to after the newly-inserted element.

template<class TRange> void insert();

Insert any boost range of elements at the cursor, moving the cursor to after the newly-inserted elements.

Iterator Invalidation

Iterators are invalidated by calls to any overload of insert, erase, advance or resize.

This library requires only C++03. Consequently, it does not provide any C++11 features, such as move constructors, rvalue-references, etc.

This is a header-only library. To make use of this gap_buffer, just include gap_buffer.ipp. You should note that it depends on gap_buffer.ipp and gap_buffer_iterators.ipp, so remember to add them to your source tree when you add the gap_buffer.hpp.

There are provided unit tests in the gap_buffer_tests.cpp file. This has an additional requirement on Boost.Test. Using gcov and lcov indicates that these tests reach 100% line coverage, but only about 82% branch coverage (something I hope to remedy soon).

This code should be very portable. It makes use of only standard C++03, and does not directly use any particularly advanced features thereof, like partial template specialization (or any specialization, for that matter). However, the code does depend on several Boost libraries, namely Boost.Iterators, Boost.EnableIf, Boost.TypeTraits, Boost.ConceptCheck, and Boost.Range. So, in short, if you have a working Boost, you can use this.