# Is there a less than $O(n)$ algorithm for converting UTF-8 character offsets to byte offsets, in a gap buffer?

A Gap Buffer is a variation on a dynamically-sized array, but with a gap inside it. The gap makes editing operations around the gap more efficient. Deletion before the gap can be implemented by simply making the gap larger for example.

UTF-8 is a variable width encoding for text. The first bits of the first byte of a character describes how many bytes are in the character, to a maximum of four.

When describing a cursor position in a string, (specifically a position between characters), we can use a pair consisting of the line number, (let's say we start at zero), and the horizontal character offset (how many characters to the right the cursor is from the position to the left of the first character on the line). It is useful to use this representation to position a cursor.

However, in order to move the byte offsets that determine where the buffer's gap is we need to convert the line number and character offset to a byte index.

The best way I currently know how to do this is the following $$O(n)$$ algorithm:

Call the line number and character offset we are looking for the byte offset of,
"the target".

Keep track of the current line number and character offset as we go, starting each at 0.

for (the characters before the gap) {
if the current line number and character offset matches the target,
return the byte offset.
}

if the space right after the last character before the gap matches the target,
return the byte offset of the start of the gap.

for (the characters after the gap) {
if the current line number and character offset matches the target,
return the byte offset.
}

if the space right after the last character after the gap matches the target,
return the byte offset of the end of the buffer.

Otherwise, the cursor is out of bounds.


This is all under the assumption that the buffer is well-formed. That is, the gap starts immediately after a UTF-8 character, and the gap ends just before another one, or the end of the entire buffer.

Is there a way to do this with a lower computational complexity than $$O(n)$$? If I try to imagine one, the closest I can get is to try something like binary search, but that seems like finding a pivot point (past maybe the first one which we could cache,) would involve iterating over the buffer anyway, so it wouldn't actually be $$O(\log n)$$.

• Just work with byte offsets all the time. Don’t count characters. Apr 17 '19 at 6:27
• How do you propose I would position a cursor between multi-byte characters? Apr 17 '19 at 6:34
• If you have a three byte character followed by a four byte, the legal offsets are 0, 3 and 7. Apr 17 '19 at 13:59
• If it wasn’t clear, I am trying to implement a text editor. Say I have a multi-line text and the cursor is positioned before the third character on the fifth line. If the user presses up, they expect the cursor to move to before the third character on the fourth line. If the cursor is in character offset form, then calculating the new position is trivial: decrement the line number. Then I have to calculate the byte offset to move the gap. If I use byte offsets, then it seems like I need to iterate over the text to find the line number and character offset to do the movement math anyway. Apr 17 '19 at 14:29
• @gnasher729 I feel like I should respond more directly to your offset comment. I understand that. If I had a one byte character followed a two, then three then four byte character, the legal offsets would be 0, 1,3,6, and 10. But I won't know what the data will be ahead of time, so my current implementation counts characters. Apr 18 '19 at 5:15