Gap Buffer / Piece Table

Why Gap Buffer / Piece Table Matters

Text editors and IDEs process large documents where users continuously insert and delete characters at arbitrary cursor positions. Storing a document as a standard contiguous array or string requires copying up to $N$ characters for every single keystroke inserted into the middle of a file. For a 50-megabyte file, typing a single character would force the CPU to reallocate and shift tens of megabytes of memory, rendering real-time typing impossibly sluggish.

Gap Buffers and Piece Tables eliminate this linear copy penalty by optimizing for document mutation patterns. A Gap Buffer maintains an unused buffer region (a "gap") directly at the cursor location; typing simply places characters into the gap in $O(1)$ time, moving the gap only when the user navigates to a new line or section. A Piece Table decouples text storage from document representation: the original document and all newly typed text are stored in immutable, append-only buffers, while the document itself is represented as a lightweight sequence of "piece descriptors" pointing to spans within those buffers. Both structures reduce localized typing overhead from $O(N)$ to $O(1)$ amortized time, enabling text editors like Emacs, VS Code, and MS Word to handle massive files smoothly.

Gap Buffers and Piece Tables solve the $O(N)$ array-reallocation problem in text editors. A Gap Buffer keeps a movable empty window at the cursor for $O(1)$ local edits, while a Piece Table represents documents as an ordered list of spans pointing into immutable append-only text buffers, providing $O(1)$ inserts and effortless undo history without copying document text.

Core Concepts and Terminology

Understanding text editor data structures requires separating the physical storage of characters from the logical sequence displayed to the user.

Gap Buffer Architecture

A Gap Buffer consists of a single large array of capacity $C$ split into three sections:

Pre-Gap Text: Characters from index $0$ to $\text{gap\_start} - 1$.
The Gap: Unused memory buffer spanning from $\text{gap\_start}$ to $\text{gap\_end} - 1$.
Post-Gap Text: Characters from $\text{gap\_end}$ to $C - 1$.

When inserting a character at the cursor, it is written at gap_start, and gap_start is incremented by 1. When moving the cursor, characters are shifted across the gap to reposition the empty window.

Piece Table Architecture

A Piece Table maintains two static/append-only character buffers and a list of descriptors:

Original Buffer: The read-only initial file content loaded from disk.
Add Buffer: An append-only buffer containing all newly inserted text.
Piece List: A sequence of descriptors (BufferType, StartIndex, Length), where BufferType indicates whether the span points to ORIGINAL or ADD.

Term	Definition	Role in Algorithm	Example
Gap Buffer	Contiguous array containing pre-gap text, an empty buffer region, and post-gap text.	Provides $O(1)$ insertions and deletions at the current cursor position.	Array `['H','e','l','l','o', _, _, 'W','o','r','l','d']`.
Gap Move	Shifting characters from pre-gap to post-gap (or vice versa) when the cursor relocates.	Re-aligns the empty gap with the new editing location.	Moving cursor left 1 char shifts `'o'` across the gap.
Original Buffer	A read-only character sequence containing the initial file contents loaded from disk.	Never modified during editing, serving as a static reference backing store.	`original = "Hello World"`
Add Buffer	An append-only string where all newly typed text is accumulated sequentially.	Receives all newly inserted character data.	`add = " Beautiful"`
Piece Descriptor	A tuple `(buffer_type, start, length)` denoting a span of characters in a buffer.	Forms the logical sequence of the document when concatenated.	`[ORIGINAL, 0, 5]` represents `"Hello"`.
Piece Splitting	Dividing a piece into two descriptors when inserting text in the middle of its span.	Preserves surrounding text spans while inserting a new piece descriptor.	Splitting `[ORIGINAL, 0, 11]` at offset 5 into `[0, 5]` and `[5, 6]`.

How Gap Buffer / Piece Table Works, Step by Step

Let us examine the operational mechanics for both Gap Buffer character updates and Piece Table text insertions.

1. Gap Buffer Control Flow

Insert Character at Cursor: 1. Check if the gap is empty (gap_start == gap_end). If empty, allocate a larger array and shift post-gap text rightward to expand the gap. 2. Write character at buffer[gap_start]. 3. Increment gap_start by 1.

Move Cursor to Target Offset: 1. If target < gap_start: Shift gap_start - target characters from post-gap to pre-gap (moving pre-gap text to post-gap space). 2. If target > gap_start: Shift target - gap_start characters from post-gap to pre-gap. 3. Set gap_start = target and adjust gap_end accordingly.

2. Piece Table Control Flow

Insert Text (text) at Logical Offset (pos): 1. Append text to the Add buffer. Let add_start be the length of Add prior to append. 2. Create a new descriptor new_piece = (ADD, add_start, len(text)). 3. Iterate through piece_list accumulating character lengths to find the piece $P_i$ containing offset pos. 4. If pos falls exactly at a piece boundary, insert new_piece into piece_list at that index. 5. If pos falls inside $P_i$, split $P_i$ into $P_{i, left}$ and $P_{i, right}$. Replace $P_i$ with the sequence $[P_{i, left}, \text{new\_piece}, P_{i, right}]$.

The control flow diagram below summarizes Piece Table insertion and deletion decision logic:

Gap Buffer / Piece Table control flow

flowchart TD
A[Start: PieceTable.insert offset, text] --> B[Append text to Add Buffer; record add_start]
B --> C[Create new_piece = ADD, add_start, len text]
C --> D[Walk piece_list to locate piece containing offset]
D --> E{Is offset on piece boundary?}
E -- Yes --> F[Insert new_piece directly into piece_list]
E -- No --> G[Split piece into left_piece and right_piece]
G --> H[Replace original piece with left_piece, new_piece, right_piece]
F --> I[Done: Document updated]
H --> I

Worked Example with a Full Trace

Let us trace a sequence of operations on a Piece Table step by step:

Initialize: original = "Hello World", add = "". * Piece 1: [ORIGINAL, start=0, len=11] $\implies$ Document: "Hello World"

Operation 1: insert(5, " Beautiful") add becomes " Beautiful" (length 10). Target offset 5 splits Piece 1 into [ORIGINAL, 0, 5] ("Hello") and [ORIGINAL, 5, 6] (" World"). Piece List: [ORIG, 0, 5], [ADD, 0, 10], [ORIG, 5, 6]. Document: "Hello Beautiful World".

Operation 2: delete(5, 10) (Deletes " Beautiful") Removes the middle piece [ADD, 0, 10]. Piece List: [ORIG, 0, 5], [ORIG, 5, 6]. * Document: "Hello World".

Operation 3: insert(5, " Code") add becomes " Beautiful Code". New addition starts at index 10, length 5. Piece List: [ORIG, 0, 5], [ADD, 10, 5], [ORIG, 5, 6]. * Document: "Hello Code World".

Worked Example

Trace It by Hand

Trace Challenge: Starting from the final state of the worked trace above:

original = "Hello World"
add = " Beautiful Code"
Piece List = [ [ORIG, 0, 5], [ADD, 10, 5], [ORIG, 5, 6] ] (Document: "Hello Code World")

Follow these additional steps:

Execute delete(0, 6) (Deletes "Hello ").
Execute insert(10, "!") (Inserts ! at the end before "World").

Questions:

What is the piece list after Step 1 (delete(0, 6))?
What is the final text rendered after Step 2?
How many bytes of new character data were allocated in add during both operations combined?

Answer:

Step 1 removes [ORIG, 0, 5] ("Hello") and 1 character from [ADD, 10, 5] (" Code" $\to$ "Code"). Piece List becomes: [ [ADD, 11, 4], [ORIG, 5, 6] ].
Final rendered document: "Code World!".
Exactly 1 byte was appended to add ("!"). add becomes " Beautiful Code!".

Implementation in Python, C++, and Java

The code implementations below construct a complete, fully functional Piece Table supporting insert(offset, text), delete(offset, length), and get_text(). All three implementations follow identical logic and produce identical output.

class BufferType:
    ORIGINAL = 0
    ADD = 1


class Piece:
    def __init__(self, buffer_type, start, length):
        self.buffer_type = buffer_type
        self.start = start
        self.length = length


class PieceTable:
    def __init__(self, original_text=""):
        self.original = original_text
        self.add = ""
        self.pieces = []
        if original_text:
            self.pieces.append(Piece(BufferType.ORIGINAL, 0, len(original_text)))

    def get_text(self):
        result = []
        for piece in self.pieces:
            buf = self.original if piece.buffer_type == BufferType.ORIGINAL else self.add
            result.append(buf[piece.start\:piece.start + piece.length])
        return "".join(result)

    def insert(self, offset, text):
        if not text:
            return

        add_start = len(self.add)
        self.add += text
        new_piece = Piece(BufferType.ADD, add_start, len(text))

        if not self.pieces or offset == 0:
            self.pieces.insert(0, new_piece)
            return

        new_pieces = []
        curr_pos = 0
        inserted = False

        for piece in self.pieces:
            p_end = curr_pos + piece.length

            if not inserted and curr_pos <= offset <= p_end:
                left_len = offset - curr_pos
                right_len = piece.length - left_len

                if left_len > 0:
                    new_pieces.append(Piece(piece.buffer_type, piece.start, left_len))

                new_pieces.append(new_piece)

                if right_len > 0:
                    new_pieces.append(Piece(piece.buffer_type, piece.start + left_len, right_len))

                inserted = True
            else:
                new_pieces.append(piece)

            curr_pos = p_end

        if not inserted:
            new_pieces.append(new_piece)

        self.pieces = new_pieces

    def delete(self, offset, length):
        if length <= 0 or not self.pieces:
            return

        new_pieces = []
        curr_pos = 0
        del_end = offset + length

        for piece in self.pieces:
            p_start = curr_pos
            p_end = curr_pos + piece.length

            # Check overlap between [p_start, p_end] and [offset, del_end]
            if p_end <= offset or p_start >= del_end:
                # Completely outside deletion range
                new_pieces.append(piece)
            else:
                # Left slice
                if offset > p_start:
                    left_len = offset - p_start
                    new_pieces.append(Piece(piece.buffer_type, piece.start, left_len))

                # Right slice
                if del_end < p_end:
                    right_start_offset = del_end - p_start
                    right_len = p_end - del_end
                    new_pieces.append(Piece(piece.buffer_type, piece.start + right_start_offset, right_len))

            curr_pos = p_end

        self.pieces = new_pieces


if __name__ == "__main__":
    pt = PieceTable("Hello World")
    print("Initial:", pt.get_text())

    pt.insert(5, " Beautiful")
    print("After insert(5, \" Beautiful\"):", pt.get_text())

    pt.delete(5, 10)
    print("After delete(5, 10):", pt.get_text())

    pt.insert(5, " Code")
    print("After insert(5, \" Code\"):", pt.get_text())

#include <iostream>
#include <string>
#include <vector>

enum class BufferType { ORIGINAL, ADD };

struct Piece {
    BufferType buffer_type;
    size_t start;
    size_t length;

    Piece(BufferType type, size_t s, size_t l)
        : buffer_type(type), start(s), length(l) {}
};

class PieceTable {
private:
    std::string original;
    std::string add;
    std::vector<Piece> pieces;

public:
    explicit PieceTable(const std::string& original_text) : original(original_text), add("") {
        if (!original.empty()) {
            pieces.emplace_back(BufferType::ORIGINAL, 0, original.length());
        }
    }

    std::string getText() const {
        std::string result = "";
        for (const auto& piece : pieces) {
            const std::string& buf = (piece.buffer_type == BufferType::ORIGINAL) ? original : add;
            result += buf.substr(piece.start, piece.length);
        }
        return result;
    }

    void insert(size_t offset, const std::string& text) {
        if (text.empty()) return;

        size_t add_start = add.length();
        add += text;
        Piece new_piece(BufferType::ADD, add_start, text.length());

        if (pieces.empty() || offset == 0) {
            pieces.insert(pieces.begin(), new_piece);
            return;
        }

        std::vector<Piece> new_pieces;
        size_t curr_pos = 0;
        bool inserted = false;

        for (const auto& piece : pieces) {
            size_t p_end = curr_pos + piece.length;

            if (!inserted && offset >= curr_pos && offset <= p_end) {
                size_t left_len = offset - curr_pos;
                size_t right_len = piece.length - left_len;

                if (left_len > 0) {
                    new_pieces.emplace_back(piece.buffer_type, piece.start, left_len);
                }

                new_pieces.push_back(new_piece);

                if (right_len > 0) {
                    new_pieces.emplace_back(piece.buffer_type, piece.start + left_len, right_len);
                }

                inserted = true;
            } else {
                new_pieces.push_back(piece);
            }

            curr_pos = p_end;
        }

        if (!inserted) {
            new_pieces.push_back(new_piece);
        }

        pieces = std::move(new_pieces);
    }

    void remove(size_t offset, size_t length) {
        if (length == 0 || pieces.empty()) return;

        std::vector<Piece> new_pieces;
        size_t curr_pos = 0;
        size_t del_end = offset + length;

        for (const auto& piece : pieces) {
            size_t p_start = curr_pos;
            size_t p_end = curr_pos + piece.length;

            if (p_end <= offset || p_start >= del_end) {
                new_pieces.push_back(piece);
            } else {
                if (offset > p_start) {
                    size_t left_len = offset - p_start;
                    new_pieces.emplace_back(piece.buffer_type, piece.start, left_len);
                }
                if (del_end < p_end) {
                    size_t right_start_offset = del_end - p_start;
                    size_t right_len = p_end - del_end;
                    new_pieces.emplace_back(piece.buffer_type, piece.start + right_start_offset, right_len);
                }
            }

            curr_pos = p_end;
        }

        pieces = std::move(new_pieces);
    }
};

int main() {
    PieceTable pt("Hello World");
    std::cout << "Initial: " << pt.getText() << "\n";

    pt.insert(5, " Beautiful");
    std::cout << "After insert(5, \" Beautiful\"): " << pt.getText() << "\n";

    pt.remove(5, 10);
    std::cout << "After delete(5, 10): " << pt.getText() << "\n";

    pt.insert(5, " Code");
    std::cout << "After insert(5, \" Code\"): " << pt.getText() << "\n";

    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {

    enum BufferType {
        ORIGINAL, ADD
    }

    static class Piece {
        BufferType bufferType;
        int start;
        int length;

        Piece(BufferType bufferType, int start, int length) {
            this.bufferType = bufferType;
            this.start = start;
            this.length = length;
        }
    }

    static class PieceTable {
        private final String original;
        private final StringBuilder add;
        private List<Piece> pieces;

        public PieceTable(String originalText) {
            this.original = originalText != null ? originalText : "";
            this.add = new StringBuilder();
            this.pieces = new ArrayList<>();
            if (!this.original.isEmpty()) {
                this.pieces.add(new Piece(BufferType.ORIGINAL, 0, this.original.length()));
            }
        }

        public String getText() {
            StringBuilder sb = new StringBuilder();
            for (Piece piece : pieces) {
                String buf = (piece.bufferType == BufferType.ORIGINAL) ? original : add.toString();
                sb.append(buf, piece.start, piece.start + piece.length);
            }
            return sb.toString();
        }

        public void insert(int offset, String text) {
            if (text == null || text.isEmpty()) return;

            int addStart = add.length();
            add.append(text);
            Piece newPiece = new Piece(BufferType.ADD, addStart, text.length());

            if (pieces.isEmpty() || offset == 0) {
                pieces.add(0, newPiece);
                return;
            }

            List<Piece> newPieces = new ArrayList<>();
            int currPos = 0;
            boolean inserted = false;

            for (Piece piece : pieces) {
                int pEnd = currPos + piece.length;

                if (!inserted && offset >= currPos && offset <= pEnd) {
                    int leftLen = offset - currPos;
                    int rightLen = piece.length - leftLen;

                    if (leftLen > 0) {
                        newPieces.add(new Piece(piece.bufferType, piece.start, leftLen));
                    }

                    newPieces.add(newPiece);

                    if rightLen > 0 {
                        newPieces.add(new Piece(piece.bufferType, piece.start + leftLen, rightLen));
                    }

                    inserted = true;
                } else {
                    newPieces.add(piece);
                }

                currPos = pEnd;
            }

            if (!inserted) {
                newPieces.add(newPiece);
            }

            this.pieces = newPieces;
        }

        public void delete(int offset, int length) {
            if (length <= 0 || pieces.isEmpty()) return;

            List<Piece> newPieces = new ArrayList<>();
            int currPos = 0;
            int delEnd = offset + length;

            for (Piece piece : pieces) {
                int pStart = currPos;
                int pEnd = currPos + piece.length;

                if (pEnd <= offset || pStart >= delEnd) {
                    newPieces.add(piece);
                } else {
                    if (offset > pStart) {
                        int leftLen = offset - pStart;
                        newPieces.add(new Piece(piece.bufferType, piece.start, leftLen));
                    }
                    if (delEnd < pEnd) {
                        int rightStartOffset = delEnd - pStart;
                        int rightLen = pEnd - delEnd;
                        newPieces.add(new Piece(piece.bufferType, piece.start + rightStartOffset, rightLen));
                    }
                }

                currPos = pEnd;
            }

            this.pieces = newPieces;
        }
    }

    public static void main(String[] args) {
        PieceTable pt = new PieceTable("Hello World");
        System.out.println("Initial: " + pt.getText());

        pt.insert(5, " Beautiful");
        System.out.println("After insert(5, \" Beautiful\"): " + pt.getText());

        pt.delete(5, 10);
        System.out.println("After delete(5, 10): " + pt.getText());

        pt.insert(5, " Code");
        System.out.println("After insert(5, \" Code\"): " + pt.getText());
    }
}

Complexity, Correctness, and Invariants

Evaluating text editor performance requires analyzing both operational complexity and spatial efficiency across different editing workloads.

Data Structure	Local Insert / Delete (at Cursor)	Random Insert / Delete (at Offset $K$)	Rendering Entire Document	Memory Overhead
Contiguous Array / String	$O(N)$	$O(N)$	$O(N)$	$O(N)$
Gap Buffer	$O(1)$ amortized (if gap is local)	$O(N)$ (must shift gap across text)	$O(N)$	$O(N + \text{gap\_size})$
Piece Table (Flat List)	$O(P)$ where $P$ is number of pieces	$O(P)$	$O(N)$	$O(N + P)$
Piece Tree (B-Tree / Red-Black)	$O(\log P)$	$O(\log P)$	$O(N)$	$O(N + P)$
Rope (Tree of Strings)	$O(\log N)$	$O(\log N)$	$O(N)$	$O(N \log N)$ (node overhead)

Piece Table Invariant: The logical contents of the document equal the sequential concatenation of text spans referenced by piece_list. Because Original and Add buffers are strictly immutable and append-only, modifying piece descriptors never corrupts or alters previously recorded buffer slices, guaranteeing absolute safety during UNDO and REDO history rollbacks.

Variants, Pitfalls, and Optimizations

Modern Optimizations & Tree Variants

Piece Tree (VS Code Architecture): Flat piece lists degrade to $O(P)$ search time when documents accumulate thousands of pieces. Modern editors wrap piece descriptors inside balanced search trees (such as Red-Black or AVL trees) indexed by character counts and line breaks, reducing insert/delete complexity to $O(\log P)$.
Line Offset Indexing: Storing line break counts (\n) directly inside piece tree nodes enables instant $O(\log P)$ conversions between (line, column) coordinates and raw document offsets.

Top Implementation Pitfalls:

Piece Fragmentation Explosion: Inserting characters individually without checking if the new addition is contiguous with the preceding Add buffer span creates thousands of 1-character piece descriptors, causing linear performance degradation.
Gap Buffer Moving Overhead: Using a Gap Buffer for random multi-cursor editing forces expensive $O(N)$ text shifts whenever editing shifts between distant document lines.
Off-by-One Offset Splitting: Incorrectly mapping logical document offsets to relative piece offsets when splitting descriptors causes character corruption or array index out-of-bounds errors.

Practice Problems and Real-World Use

Gap Buffers and Piece Tables form the core editing engines of industrial software systems:

System / Problem	Architecture Used	Key Benefit / Context
Visual Studio Code	Piece Tree (Piece Table + Red-Black Tree)	Supports gigabyte-sized files with instant open time and low RAM footprint.
GNU Emacs	Gap Buffer	Extremely fast $O(1)$ local cursor editing for single-cursor workflows.
Microsoft Word	Piece Table	Powers undo/redo history and complex document markup tracking.
Neovim / Vim	Undo Tree with Span Descriptors	Branching undo history backed by immutable text buffers.
LeetCode 2296 - Design a Text Editor	Gap Buffer or Doubly Linked List	Solves cursor navigation and text insertion constraints efficiently.
Sublime Text	Custom Piece Tree Variant	High-speed multi-cursor editing across large source files.

Cookie Consent