Project 2: Text Editor Gap Buffer

Build a gap buffer with explicit invariants so you can edit large text efficiently without constant reallocations.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 1-2 weeks
Main Programming Language C (Alternatives: Rust, Zig)
Alternative Programming Languages Rust, Zig
Coolness Level Level 3 (Genuinely Clever)
Business Potential Level 2 (Editor component)
Prerequisites Arrays, pointers, memmove/memcpy, invariants
Key Topics Gap invariants, memory movement, cursor operations

1. Learning Objectives

By completing this project, you will:

  1. Define and enforce the invariants that make a gap buffer correct.
  2. Implement efficient insert and delete operations around a movable gap.
  3. Use memmove correctly for overlapping memory regions.
  4. Design a small editor-like API with predictable performance.
  5. Write tests that validate buffer contents and gap integrity.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Gap Buffer Representation and Invariants

Fundamentals

A gap buffer stores text in a contiguous array with a “gap” (unused region) around the cursor. The key invariant is that the buffer is split into two contiguous text regions separated by the gap: all text before the gap is the content before the cursor, and all text after the gap is the content after the cursor. The gap itself contains no meaningful data and can be overwritten by insert operations. A valid gap buffer must maintain 0 <= gap_start <= gap_end <= capacity, and the total text length is capacity - gap_size. These rules are not optional; they are the definition of correctness for the structure. If any part of the buffer violates these invariants, insert and delete operations will corrupt the text.

Deep Dive into the Concept

The gap buffer is a classic example of an invariant-driven data structure. At any stable point, the buffer must satisfy three conditions: the gap is contiguous, the text before the gap is stored in indices [0, gap_start), and the text after the gap is stored in indices [gap_end, capacity). These conditions allow you to insert by writing into the gap without moving the rest of the text. When you move the cursor, you move the gap instead of moving the text itself; that means you copy only the characters that move across the gap. This is the key to efficiency: inserts at the cursor become O(k) where k is the inserted size, and cursor movement costs O(distance) rather than O(total size).

The invariants are subtle because they involve multiple indices and implicit text length. The logical length is not stored directly; it is derived from capacity minus gap size. This means any off-by-one error in gap indices corrupts the logical view of the text. For example, if gap_start is incremented without writing a character into the gap, your logical text becomes shorter even though the memory still contains old bytes. Conversely, if gap_end is decremented without inserting data, you may accidentally expose stale bytes as part of the text.

Another important invariant is the mapping between logical cursor position and physical indices. The cursor is conceptually at gap_start, but logical indices after the gap must be translated by adding the gap size. For example, logical index i maps to physical index i if i < gap_start, otherwise to i + gap_size. This mapping must be used consistently for get/set operations. If you forget to translate indices or you use the wrong comparison (<= vs <), you will read from the gap or write into the wrong region.

The gap buffer is also a representation invariant challenge because it stores a “hole” in the middle of text that is not real content. This means your API must be careful about exposing the buffer. If you provide a function to return the raw buffer pointer, a caller might expect the text to be contiguous. You must either provide a function that copies text into a contiguous output buffer or clearly document that the raw buffer contains a gap. This is a contract issue: you are responsible for ensuring that the representation does not leak in ways that confuse callers.

Finally, the invariants must be preserved across resizing. If the gap is too small, you allocate a larger buffer, then copy the pre-gap and post-gap segments into the new buffer with a larger gap in between. This is another moment where invariants are temporarily broken: while you copy, the new buffer does not represent a valid gap buffer until you have copied both segments and set new gap_start and gap_end values. Your implementation must ensure that no validation occurs mid-copy, and that the final state satisfies the invariants exactly. Testing this requires verifying both text correctness and gap placement after resize.

How this fits on projects

Every operation (insert, delete, move_cursor) is an exercise in maintaining gap invariants. The project is a direct application of representation invariants to a real-world problem.

Definitions & key terms

  • Gap: The unused region of the buffer that represents the cursor position.
  • Gap start/end: Indices marking the bounds of the gap.
  • Logical index: Index in the text without the gap.
  • Physical index: Actual index in the underlying array.

Mental model diagram (ASCII)

Buffer: [TEXT][GAP][TEXT]
Indices: 0     gs   ge   cap

Logical: 0 .......... len
Physical: map logical -> physical with gap size

How it works (step-by-step, with invariants and failure modes)

  1. Validate that gap_start <= gap_end and both are within capacity.
  2. Insert: write into gap_start, increment gap_start.
  3. Delete: decrement gap_start or increment gap_end based on delete direction.
  4. Move cursor: copy bytes across the gap and update gap_start/gap_end.
  5. After each operation, verify invariants.

Failure modes: gap becomes non-contiguous, text segments overlap, or logical index mapping fails leading to corrupted output.

Minimal concrete example

assert(buf->gap_start <= buf->gap_end);
assert(buf->gap_end <= buf->capacity);

Common misconceptions

  • “The gap holds empty bytes that must be zeroed.” (It can contain garbage; it is ignored.)
  • “Moving the cursor should move the text.” (You move the gap, not the text as a whole.)
  • “Logical and physical indices are the same.” (They diverge after the gap.)

Check-your-understanding questions

  1. What invariant defines the total logical length of the buffer?
  2. Why is the gap allowed to contain garbage bytes?
  3. How do you map a logical index to a physical index?

Check-your-understanding answers

  1. length = capacity - (gap_end - gap_start).
  2. The gap is not part of the logical text, so its contents are irrelevant.
  3. If i < gap_start, physical index is i, else i + gap_size.

Real-world applications

  • Emacs uses a gap buffer for text editing.
  • Some IDEs use gap buffers for efficient cursor edits.

Where you will apply it

  • This project: See §3.2 Functional Requirements and §4.4 Algorithm Overview.
  • Also used in: P01 Safe Dynamic Array for invariant design.

References

  • GNU Emacs manual: gap buffer design.
  • “C Interfaces and Implementations” by David Hanson, data structure invariants.

Key insights

The gap is an explicit invariant that trades memory for fast edits near the cursor.

Summary

The gap buffer is correct only if its invariants hold; every operation is a controlled transformation that preserves those invariants.

Homework/Exercises to practice the concept

  1. Draw a gap buffer after inserting “abc” at the cursor.
  2. Move the cursor right by 3 and update gap indices.
  3. Write a validator that checks text length from indices.

Solutions to the homework/exercises

  1. Gap shrinks by 3, gap_start increases by 3.
  2. Move 3 characters from after the gap to before it.
  3. Check gap_start <= gap_end <= capacity and length = capacity - gap_size.

2.2 Overlapping Memory Movement and memmove

Fundamentals

When moving the gap, you often copy bytes within the same buffer. These regions can overlap, which makes memcpy unsafe because it assumes non-overlapping memory. memmove is the correct tool because it handles overlap by choosing a safe copy direction. Understanding overlap is critical: if you copy the wrong way, you will overwrite data before it is copied, corrupting text. The correctness of the gap buffer depends on moving text segments safely as the cursor moves. This is a low-level memory correctness concept with immediate real consequences. It also teaches you to think about source and destination ranges explicitly, which is essential for any in-place buffer algorithm in C.

Deep Dive into the Concept

Overlapping memory movement is a classic source of subtle bugs in C. Consider moving a segment of text left by 5 bytes: the source and destination ranges overlap, so copying from left to right would overwrite bytes that have not yet been copied. memmove solves this by detecting overlap and copying in the correct direction internally. However, you still need to supply correct source and destination pointers and lengths. If your length is off by one, you will shift the wrong bytes and corrupt the text.

In a gap buffer, moving the gap right requires moving the text after the gap left into the gap. Moving the gap left requires moving text before the gap right into the gap. Both are overlapping moves because the destination (the gap) is inside the same buffer. This is exactly the scenario memmove was designed for. But the operation is more than just a memmove call. You must compute how many bytes to move (distance between cursor positions), and you must update gap_start and gap_end accordingly. If you move too many bytes, you will pull in characters that should stay on the other side; if you move too few, the cursor will not end up at the requested position.

It is also critical to understand that memmove does not interpret data; it moves raw bytes. If your text is UTF-8, you may move a byte range that splits a multi-byte character if you calculate lengths in characters rather than bytes. For this project, assume ASCII or UTF-8 with byte-based cursor movement. If you ever extend to character-aware movement, you must compute byte offsets from logical characters. This is an example of how low-level memory movement relates to higher-level text semantics.

Another subtlety is that you must avoid using memmove on uninitialized regions as source data. When you expand the gap, the new gap region is uninitialized; you should not attempt to move it as text. Similarly, you should avoid reading from the gap when moving it. That means your memmove regions must always be selected from the text segments, not from the gap. A safe pattern is to compute move_len from the cursor delta and then use memmove with the correct segment boundaries.

It is also worth understanding that memmove does not validate sizes or boundaries. If you pass a length that extends beyond the valid text region, memmove will happily copy garbage bytes or read out of bounds. This is why you must treat memmove as a raw byte primitive and wrap it with invariant checks. In practice, you should assert that the source and destination ranges are within [0, capacity), and that move_len does not exceed the size of the segment being moved. This extra discipline turns a fragile operation into a predictable one.

Finally, memmove is not a license to ignore performance. Moving large portions of text is O(n) in the distance moved. The gap buffer is efficient because it keeps most edits near the cursor, so movement cost is low. If you move the cursor far across a large buffer, you will still pay O(n). That is a real cost and should be documented. It is part of your API contract: moving the cursor is proportional to the distance moved.

How this fits on projects

This concept is the heart of gap_move_cursor and gap_insert when the gap is not at the cursor. Every cursor move uses memmove to shift text segments safely.

Definitions & key terms

  • Overlap: When source and destination ranges intersect.
  • memmove: Copy function that handles overlapping memory safely.
  • Cursor delta: Number of bytes the cursor moves.

Mental model diagram (ASCII)

Move gap right by 3:

Before: [abc|____|def]
Move:         ^^^
After:  [abcdef|____]

How it works (step-by-step, with invariants and failure modes)

  1. Compute delta = new_cursor - gap_start.
  2. If delta > 0, move delta bytes from after the gap into the gap.
  3. Use memmove(dst=gap_start, src=gap_end, len=delta).
  4. Update gap_start += delta, gap_end += delta.

Failure modes: using memcpy, miscomputing delta, or moving bytes from the gap instead of text.

Minimal concrete example

memmove(buf->data + buf->gap_start,
        buf->data + buf->gap_end,
        delta);

Common misconceptions

  • “memcpy is always faster, so use it.” (Incorrect for overlapping ranges.)
  • “memmove copies left-to-right.” (It chooses direction based on overlap.)
  • “Moving the cursor is constant time.” (It is proportional to distance.)

Check-your-understanding questions

  1. Why is memcpy unsafe for gap movement?
  2. What happens if you move more bytes than the delta?
  3. How does overlap affect copy direction?

Check-your-understanding answers

  1. The source and destination ranges overlap; memcpy can overwrite source data.
  2. You will corrupt text by moving the wrong bytes.
  3. memmove copies in a direction that avoids overwriting unread data.

Real-world applications

  • Text editors and terminals.
  • Network buffers that shift data after consuming headers.

Where you will apply it

  • This project: See §4.4 Algorithm Overview and §5.10 Phase 2.
  • Also used in: P04 JSON Parser for buffer shifts.

References

  • C standard library documentation for memmove.
  • “Expert C Programming” by Peter van der Linden, memory operations.

Key insights

The correctness of a gap buffer depends on safe overlapping memory movement; memmove is non-negotiable.

Summary

When you move the gap, you are moving bytes within the same buffer. Overlap makes memmove mandatory and careful length calculations essential.

Homework/Exercises to practice the concept

  1. Implement a small array shift using memmove and verify with tests.
  2. Create a failing example using memcpy on overlapping ranges.
  3. Measure time to move the gap by 1 vs 1,000 bytes.

Solutions to the homework/exercises

  1. Shift [1,2,3,4] right by 1 and verify output [1,1,2,3] when you copy correct range.
  2. Use memcpy in an overlapping copy and observe corruption.
  3. The time grows roughly linearly with distance moved.

2.3 Cursor Movement Complexity and Edit Semantics

Fundamentals

In a gap buffer, insert and delete operations are fast near the cursor because the gap provides immediate free space. Moving the cursor is the operation that can be expensive because it requires moving bytes across the gap. The key semantic invariant is that logical cursor position equals gap_start. When you move the cursor, you must update the gap so that this invariant holds. The performance model is therefore simple: edits near the cursor are O(k) for k characters inserted or deleted, and cursor movement is O(d) for d characters moved. Understanding this model allows you to design efficient editing commands and to explain the trade-offs of a gap buffer.

Deep Dive into the Concept

Text editing is fundamentally a sequence of cursor moves and inserts/deletes. The gap buffer is optimized for the common case where edits are local. The cursor movement semantics are tied to the gap invariants: the cursor position is defined as the index immediately before the gap. This is not just a convenience; it is the core of the data structure. When you move the cursor to a new logical position, you must move the gap to the same position so that the invariant cursor == gap_start holds. This can be done by copying bytes from one side of the gap to the other, effectively sliding the gap across the buffer.

The complexity is driven by the distance moved. If you move the cursor by a small amount, the cost is small. If you move the cursor from the start of a file to the end, you move almost all characters, which is O(n). That is acceptable in many editing scenarios because large cursor jumps are less frequent than local edits. This is a design trade-off compared to other text structures like ropes or piece tables, which are optimized for large edits and long-distance cursor moves. In a gap buffer, you accept occasional O(n) moves in exchange for fast local edits and a simple data representation.

To implement cursor movement safely, you must calculate the delta between the current cursor and the new cursor. If the cursor moves right, you copy bytes from after the gap into the gap; if it moves left, you copy bytes from before the gap into the gap. The semantic invariant is that the logical text is preserved. This means that after moving the gap, the concatenation of pre-gap and post-gap text must be identical to the original logical text, and the cursor should now be at the new position. This is a strong invariant that can be tested by reconstructing the text into a temporary buffer and comparing it before and after move.

Another key aspect is how you define editing operations. A typical API includes insert(text), delete(n), move_cursor(pos), and get_text(). Each operation should be specified in terms of logical indices, not physical indices. That way, callers do not need to understand the gap. Your implementation translates logical indices into physical positions using the gap mapping. This is where many bugs occur: if you forget to translate, you might insert into the wrong place or delete the wrong range. Therefore, one recommended approach is to centralize the mapping in helper functions and never allow raw index arithmetic to appear in multiple places.

Cursor movement also interacts with resizing. If the gap is too small for an insertion, you expand the buffer and create a larger gap. This expansion should preserve the logical cursor position. The most reliable approach is to allocate a new buffer, copy the pre-gap text to the same index, and copy the post-gap text to the end, leaving a larger gap in between. This makes the cursor invariant trivial to preserve because gap_start stays the same logical position. When you do this, you must ensure that the new gap size is sufficient for the incoming text so you do not resize repeatedly in a loop.

Finally, edit semantics include deletion direction. A forward delete consumes characters after the cursor (i.e., extends gap_end), while a backspace consumes characters before the cursor (i.e., decreases gap_start). Both operations must ensure that the gap remains contiguous and that you do not delete beyond the available text. This again depends on correct mapping between logical and physical indices and on careful bounds checking.

How this fits on projects

This concept shapes the design of the move_cursor, insert, and delete APIs and how you test them. It also justifies the gap buffer as a practical data structure for editors.

Definitions & key terms

  • Cursor position: The logical index where insertion occurs.
  • Delta: The distance moved when repositioning the cursor.
  • Local edit: Insert/delete near current cursor position.

Mental model diagram (ASCII)

Cursor at gap_start

Before move: [abc|____|def]
Move cursor right 2
After move:  [abcde|__|f]

How it works (step-by-step, with invariants and failure modes)

  1. Compute delta = new_pos - gap_start.
  2. If delta > 0, move bytes from after gap into gap.
  3. If delta < 0, move bytes from before gap into gap.
  4. Update gap_start and gap_end so cursor invariant holds.
  5. Validate the full text reconstruction.

Failure modes: gap positioned incorrectly, logical text altered, cursor position off by one.

Minimal concrete example

bool gap_move(GapBuf *b, size_t new_pos) {
    if (new_pos > gap_len(b)) return false;
    // move right or left using memmove
    return true;
}

Common misconceptions

  • “Cursor position is stored separately.” (In gap buffers, it is the gap.)
  • “Deletion is just shrinking length.” (You must adjust gap bounds.)
  • “Large cursor moves are always rare.” (Not always; test them.)

Check-your-understanding questions

  1. Why is moving the cursor proportional to distance?
  2. How do you ensure logical text is preserved after a move?
  3. What invariant links cursor position to gap indices?

Check-your-understanding answers

  1. Because bytes must be moved across the gap.
  2. By copying exactly the moved range and validating the concatenated text.
  3. cursor == gap_start at stable points.

Real-world applications

  • Emacs and some IDE editors.
  • Interactive consoles that insert/delete near a prompt.

Where you will apply it

  • This project: See §3.2 Functional Requirements and §5.10 Phase 2.
  • Also used in: P06 HTTP Server for state machine cursor positions.

References

  • GNU Emacs manual (buffer gap).
  • Data structure texts on text editor buffers.

Key insights

The gap buffer is fast because it localizes cost: edits are cheap where the cursor lives.

Summary

Cursor movement defines performance and correctness. The gap buffer is efficient when the cursor stays local, and it remains correct only when cursor invariants are enforced.

Homework/Exercises to practice the concept

  1. Simulate moving the cursor across a 10-character buffer and track indices.
  2. Write a test that reconstructs text and compares before/after cursor moves.
  3. Implement backspace vs delete and verify difference in gap indices.

Solutions to the homework/exercises

  1. Track gap_start/gap_end updates and verify gap_size constant.
  2. Copy pre-gap and post-gap into a temp buffer and compare strings.
  3. Backspace decrements gap_start; delete increments gap_end.

3. Project Specification

3.1 What You Will Build

A gap buffer library with a small CLI demo that simulates text editing operations. The library will include functions to insert text, delete text, move the cursor, and extract the full text as a contiguous string.

Included:

  • gapbuf.h and gapbuf.c
  • CLI demo: gapedit with scripted commands
  • Debug validation and invariant checks

Excluded:

  • Full editor UI
  • Unicode grapheme-aware cursor movement
  • Concurrent edits

3.2 Functional Requirements

  1. Initialization: Create a gap buffer with a specified initial capacity.
  2. Insert: Insert a string at the cursor, expanding the gap if needed.
  3. Delete: Delete N characters before or after the cursor.
  4. Move Cursor: Move to any valid logical index.
  5. Extract Text: Return a contiguous string of current content.
  6. Validate: Provide a function to validate invariants.

3.3 Non-Functional Requirements

  • Performance: Insert/delete near cursor should be O(k).
  • Reliability: No out-of-bounds or invalid memory access.
  • Usability: API should expose logical indices only.

3.4 Example Usage / Output

GapBuf *b = gap_create(32);
gap_insert(b, "Hello");
gap_move(b, 0);
gap_insert(b, "Say ");
char *out = gap_to_string(b);

3.5 Data Formats / Schemas / Protocols

Command script format for CLI demo:

INSERT <text>
MOVE <pos>
DELETE <n>
DUMP

3.6 Edge Cases

  • Insert into empty buffer.
  • Move cursor to 0 and to end.
  • Delete more characters than exist (should clamp or error).
  • Insert large text that forces gap expansion.

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

make
./gapedit demo.txt

3.7.2 Golden Path Demo (Deterministic)

Use a fixed script file to ensure deterministic output.

3.7.3 CLI Terminal Transcript (Exact)

$ ./gapedit demo.txt
[insert] "Hello"
[buffer] "Hello|" gap=10
[move] 0
[insert] "Say "
[buffer] "Say Hello|" gap=6
[delete] 3
[buffer] "Say |lo" gap=9
exit_code=0

3.7.4 Failure Demo (Deterministic)

$ ./gapedit --delete 999
[error] delete out of range
exit_code=4

3.7.5 Exit Codes

  • 0: success
  • 4: invalid argument
  • 5: invariant violation
  • 6: allocation failure

4. Solution Architecture

4.1 High-Level Design

+-------------+     +-----------------+     +-----------------+
| gapbuf API  | --> | core operations | --> | invariant checks|
+-------------+     +-----------------+     +-----------------+
        |                    |
        v                    v
    CLI demo           memmove-based gap moves

4.2 Key Components

| Component | Responsibility | Key Decisions | |———–|—————-|—————| | GapBuf struct | Tracks data and gap indices | Keep indices private | | Cursor ops | Move gap and update indices | Use memmove for overlap | | Validation | Assert gap invariants | Enable in debug/tests |

4.3 Data Structures (No Full Code)

typedef struct {
    char *data;
    size_t capacity;
    size_t gap_start;
    size_t gap_end;
} GapBuf;

4.4 Algorithm Overview

Key Algorithm: Move Cursor

  1. Compute delta between new position and gap_start.
  2. Move bytes across the gap using memmove.
  3. Update gap_start and gap_end.

Complexity Analysis:

  • Insert/delete near cursor: O(k).
  • Cursor move: O(d).

5. Implementation Guide

5.1 Development Environment Setup

cc --version
make --version

5.2 Project Structure

_gapbuf/
├── include/gapbuf.h
├── src/gapbuf.c
├── tests/gapbuf_test.c
├── examples/gapedit.c
└── Makefile

5.3 The Core Question You’re Answering

“How can I edit large text efficiently without reallocating on every insert?”

5.4 Concepts You Must Understand First

  1. Gap invariants and logical vs physical indices.
  2. memmove vs memcpy for overlapping copies.
  3. Cursor movement complexity.

5.5 Questions to Guide Your Design

  1. How will you map logical indices to physical indices?
  2. How will you expand the gap without losing text?
  3. How will you validate that the gap is contiguous?

5.6 Thinking Exercise

Simulate moving the cursor from index 2 to index 7 in a 12-character buffer. Which bytes move and where does the gap end up?

5.7 The Interview Questions They’ll Ask

  1. Why is a gap buffer efficient for text editing?
  2. How do you prevent corruption when moving the gap?
  3. What are the invariants of a gap buffer?

5.8 Hints in Layers

Hint 1: Start with a validator for gap indices. Hint 2: Use memmove for all gap movement. Hint 3: Store logical length as capacity - gap_size.

5.9 Books That Will Help

| Topic | Book | Chapter | |——|——|———| | Data structure invariants | “Code Complete” | Ch. 8 | | Memory operations | “Expert C Programming” | Ch. 3 | | Editor buffers | Emacs manual | Gap Buffer section |

5.10 Implementation Phases

Phase 1: Foundation (2-3 days)

Goals: Define struct and invariants. Tasks:

  1. Implement create/destroy.
  2. Implement validate.
  3. Add basic insert into gap. Checkpoint: Insert and dump work for small strings.

Phase 2: Core Functionality (4-6 days)

Goals: Cursor moves, delete, resize. Tasks:

  1. Implement gap move left/right.
  2. Implement delete/backspace.
  3. Implement gap expansion. Checkpoint: Cursor moves preserve text.

Phase 3: Polish & Edge Cases (2-3 days)

Goals: CLI, tests, failures. Tasks:

  1. Add CLI script runner.
  2. Add invariant checks after every command.
  3. Add failure demo (invalid delete). Checkpoint: Golden transcript matches.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |———-|———|—————-|———–| | Gap expansion | Double size or fixed | Double | Fewer reallocations | | Index mapping | On-the-fly or cached | On-the-fly | Simpler, less state | | Validation | Debug only or always | Debug + tests | Performance with safety |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |———|———|———-| | Invariant Tests | Validate gap integrity | after every operation | | Functional Tests | Verify edit behavior | insert/delete/move | | Stress Tests | Large moves and inserts | 10k chars |

6.2 Critical Test Cases

  1. Insert large text, then move cursor to 0 and insert again.
  2. Delete more than available and verify error.
  3. Move cursor across entire buffer and verify text unchanged.

6.3 Test Data

Commands:
INSERT Hello
MOVE 0
INSERT Say 
DUMP
Expected: "Say Hello"

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |———|———|———-| | Using memcpy | Corrupted text | Use memmove | | Off-by-one gap indices | Missing or duplicated chars | Add asserts after edits | | Mis-mapped indices | Inserts in wrong place | Centralize mapping helpers |

7.2 Debugging Strategies

  • Print gap indices after each command.
  • Reconstruct full text and compare against expected.

7.3 Performance Traps

Frequent cursor moves over large distances will be O(n); document this and keep gap near edit location.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a replace command.
  • Add load and save functions.

8.2 Intermediate Extensions

  • Add multiple cursors (store multiple gap positions).
  • Add undo/redo using a command stack.

8.3 Advanced Extensions

  • Compare against a rope implementation for large files.
  • Implement a piece table and benchmark.

9. Real-World Connections

9.1 Industry Applications

  • Text editors and IDEs.
  • Code formatters and refactoring tools.
  • GNU Emacs (gap buffer).
  • Micro text editors using gap buffers.

9.3 Interview Relevance

  • Questions about efficient text editing data structures.
  • Memory movement and invariants in C.

10. Resources

10.1 Essential Reading

  • GNU Emacs manual (Gap Buffer section).
  • “Expert C Programming” by Peter van der Linden.

10.2 Video Resources

  • Data structures for text editors (university lectures).

10.3 Tools & Documentation

  • memmove documentation.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain gap buffer invariants without notes.
  • I can justify why memmove is required.
  • I can describe the complexity of cursor movement.

11.2 Implementation

  • All tests pass and invariants hold.
  • CLI output matches golden transcript.
  • Edge cases return correct error codes.

11.3 Growth

  • I can explain this structure in an interview.
  • I can compare gap buffers to ropes.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Insert/delete/move operations work.
  • Invariant validator catches violations.
  • Deterministic demo output is correct.

Full Completion:

  • All edge cases tested.
  • Failure demo returns correct exit code.

Excellence (Going Above & Beyond):

  • Benchmarks against other text structures.
  • Undo/redo support.

13. Additional Content Rules (Hard Requirements)

13.1 Determinism

All demos use fixed scripts and produce deterministic output.

13.2 Outcome Completeness

  • Success demo and failure demo are included.
  • Exit codes are specified in §3.7.5.

13.3 Cross-Linking

13.4 No Placeholder Text

All content is complete and explicit.