Gap buffers: pay when the edit cursor crosses text

A gap buffer is one character array with an unused interval between the text before and after the cursor. Its two gap boundaries encode the cursor position; no sentinel character is part of the note. Moving the cursor copies characters across the gap, while insertion consumes spare slots and deletion expands the gap. This implementation always leaves at least one spare slot when an insertion exactly fills the current interval, so a later cursor move still has room to shift a character. When the gap needs more room, it adds spare slots in one allocation. The array contains Python characters, so offsets count Unicode code points rather than user-perceived grapheme clusters. The model has no undo, markers, line index, or concurrent editor state.

Operational case

An incident operator starts with the note Valve offline, inserts the equipment number after Valve, appends a bay location, and finally prepends Alert:. Those edits require a short cursor move, an append, then a move back across nearly the whole note. The output is Alert: Valve-19 offline at bay 6. Typing several characters at one cursor is cheap until the gap grows. Jumping from the end of a large note to its start moves existing characters, so measuring only insertion after the move hides the expensive part of this workload. The text() call materializes a contiguous string for display and also copies the full logical note.

Working Python program

class IncidentGapBuffer:
    def __init__(self, text="", gap_capacity=8):
        if gap_capacity < 1:
            raise ValueError("gap capacity must be positive")
        self.buffer = list(text) + [None] * gap_capacity
        self.gap_left = len(text)
        self.gap_right = len(self.buffer)

    def __len__(self):
        return len(self.buffer) - (self.gap_right - self.gap_left)

    def move_cursor(self, position):
        if not 0 <= position <= len(self):
            raise IndexError("cursor outside note")
        while self.gap_left > position:
            self.gap_left -= 1
            self.gap_right -= 1
            self.buffer[self.gap_right] = self.buffer[self.gap_left]
            self.buffer[self.gap_left] = None
        while self.gap_left < position:
            self.buffer[self.gap_left] = self.buffer[self.gap_right]
            self.buffer[self.gap_right] = None
            self.gap_left += 1
            self.gap_right += 1

    def _grow(self, required):
        spare = max(len(self.buffer), required, 8)
        self.buffer[self.gap_right:self.gap_right] = [None] * spare
        self.gap_right += spare

    def insert(self, text):
        if not text:
            return
        if self.gap_right - self.gap_left <= len(text):
            self._grow(len(text) - (self.gap_right - self.gap_left) + 1)
        for character in text:
            self.buffer[self.gap_left] = character
            self.gap_left += 1

    def delete_forward(self, count):
        if count < 0 or count > len(self.buffer) - self.gap_right:
            raise IndexError("forward deletion outside note")
        for offset in range(count):
            self.buffer[self.gap_right + offset] = None
        self.gap_right += count

    def backspace(self, count):
        if count < 0 or count > self.gap_left:
            raise IndexError("backspace outside note")
        self.gap_left -= count
        for offset in range(count):
            self.buffer[self.gap_left + offset] = None

    def text(self):
        return "".join(self.buffer[:self.gap_left] + self.buffer[self.gap_right:])


note = IncidentGapBuffer("Valve offline", gap_capacity=4)
note.move_cursor(5)
note.insert("-19")
note.move_cursor(len(note))
note.insert(" at bay 6")
note.move_cursor(0)
note.insert("Alert: ")
print("note=", note.text(), " cursor=", note.gap_left, sep="")

Output

note=Alert: Valve-19 offline at bay 6 cursor=7

Time, space, and tradeoff

Moving the cursor by D character positions costs O(D) time and O(1) extra space when the gap has room. Inserting M characters at the current cursor costs O(M) plus an occasional O(N) growth copy; geometric spare growth gives amortized linear cost across local insertions, but does not make distant cursor moves cheap. Forward deletion and backspace cost O(K) here because the code clears K slots; logical deletion could change a boundary without clearing them. Materializing N characters costs O(N) time and space. The allocated array is O(N + G) for note length N and spare gap G. A one-character insertion after a full-buffer cursor jump can still take O(N).

Common Mistakes

Do not display the unused gap as note content.
Do not move a zero-width gap without first making spare space.
Do not claim a distant cursor jump is constant time.
Do not use code-point offsets as grapheme-aware cursor positions.

Connected lessons

Compare its edit and lookup costs with Ropes: share text chunks across immutable revisions, Unrolled lists: link small blocks instead of single items, Segmented arrays: locate blocks through cumulative lengths, then run the sequence audit and contract quiz.