Skip to content
Tutorials Center
My learning

Topics

Lesson 214 of 225 ยท Projects

Project: Text Editor Buffer with Undo

Build the core of a text editor in stages. Compare string slicing with a gap buffer, add undo and redo stacks with commands, then test it against a simple model.

Every text editor, from a tiny notepad to a full code editor, rests on two data structure decisions. First: how do you store the text so that typing in the middle of a large file is fast? Second: how do you let the user press Ctrl + Z and get back to an earlier state, and then Ctrl + Y to come forward again?

In this project you will answer both. You will start with the obvious approach (a Python string), measure why it struggles, replace it with a gap buffer, and then build undo and redo with two stacks of command objects. Finally you will merge consecutive keystrokes into one undo step, as real editors do, and verify the whole thing by comparing it with a trivially simple model.

What the editor must do

Our editor has a cursor between characters and supports:

  • type(text): insert text at the cursor.
  • backspace(n): delete the n characters before the cursor.
  • move_to(position): put the cursor somewhere else.
  • undo() and redo(): step backward and forward through the history of edits.
  • text(): return the whole document.

Cursor movement is not an edit, so it is not undoable, which matches most editors.

Stage 1: a string and why it hurts

Python strings are immutable. Inserting in the middle builds a new string by copying the part before the cursor, the new text and the part after it. That is O(n) per keystroke for a document of n characters. Let us count the characters copied while typing:

Python Stage 1: a plain string buffer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Typing 2,000 characters copies 1 + 2 + ... + 2000 = 2,001,000 characters in total: quadratic. CPython has some tricks that can make appending to a string cheaper, but they do not help inserts in the middle, and a one-megabyte file would make every keystroke copy a megabyte. We need a representation that makes inserting at the cursor cheap.

Stage 2: the gap buffer

Look at how editing really happens: the user types in one place for a while, then jumps elsewhere. A gap buffer exploits that locality. It stores the text in one array with an empty gap exactly at the cursor:

TEXT
text "Hello world", cursor after "Hello":

  H e l l o _ _ _ _ _   w o r l d
  0 1 2 3 4 ^gap_start  ^gap_end  ...
            (gap of 5 empty slots)

type "!"  ->  H e l l o ! _ _ _ _   w o r l d      (write into the gap: O(1))
move cursor left by 2:   H e l _ _ _ _ _ l o ! ...  (shift two chars across the gap)

Inserting writes into the gap and advances gap_start: constant time as long as the gap has room. Deleting before the cursor just moves gap_start back: the characters are now "in the gap" and will be overwritten. Moving the cursor means sliding the gap by shifting characters across it, which costs time proportional to the distance moved, not the document size. When the gap fills up, we allocate a larger array (doubling, so growth is amortized constant).

Python Stage 2: a gap buffer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Typing 2,000 characters moves nothing (compare that with two million copies for the string), and typing 100 more at the start costs nothing extra once the gap is there. The only expense is the one-off jump of the cursor across 2,000 characters. That is exactly the right trade for editing.

Alternative designs. The two-stacks approach stores the text before the cursor on one stack and the text after it (reversed) on another; moving the cursor pops from one and pushes onto the other. It is simple and has the same costs. Very large editors use a rope or a piece table, which handle edits far from the cursor and cheap undo too.

Stage 3: commands, undo and redo

Undo needs to reverse the most recent edit first. That is last-in, first-out: a stack. Redo needs the edits you just undid, in reverse order: a second stack. The elegant way to organize this is the command pattern: every edit becomes an object that knows how to apply itself and how to undo itself.

TEXT
type "ab"   ->  undo stack: [Insert(0,"ab")]                 redo stack: []
backspace 1 ->  undo stack: [Insert(0,"ab"), Delete(1,"b")]  redo stack: []
undo        ->  undo stack: [Insert(0,"ab")]                 redo stack: [Delete(1,"b")]
undo        ->  undo stack: []                               redo stack: [Delete(1,"b"), Insert(0,"ab")]
type "z"    ->  new edit! the redo stack is cleared.

The rule that surprises beginners: a new edit clears the redo stack. Once you branch off in a new direction, the old future no longer makes sense (editors that keep a tree of histories, such as Vim's undo tree, are the exception).

Python Stage 3: undo and redo with command objects

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each command stores just enough to reverse itself: an insert remembers what and where, a delete remembers the removed text and its position. Memory use is proportional to the amount of text edited, not the document size. Undo, redo and every edit cost O(size of the change) plus the gap-buffer cost of moving the cursor.

Stage 4: merging keystrokes

If every character were its own command, pressing Ctrl + Z after typing a sentence would remove one letter at a time. Real editors coalesce consecutive typing into one undo step. We can do that when a new insert starts exactly where the previous insert ended, and nothing else happened in between (no deletion, undo, or cursor jump).

Implementing that takes four small changes to Editor: remember whether the last action was a typing run, and in type, when the new text is adjacent, extend the previous command instead of pushing a new one. Typing a newline or a space can end a run, so undo is word by word, as in many editors. We implement the "break at whitespace" rule below:

Python Stage 4: coalescing typed characters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Twelve keystrokes (good morning, including the space) become three undo steps: good, the space, and morning. Each keystroke still costs O(1) because merging just appends to the previous command's text.

Stage 5: test against a model

Undo/redo logic is notorious for edge-case bugs: undo after a redo, redo after a new edit, deleting at position 0. We will test it with a model-based test: a deliberately naive model that keeps a full copy of the document after every edit (a stack of snapshots) and a random sequence of operations applied to both. The model is obviously correct because it does not reason about reversing anything. It just remembers old strings.

Python Stage 5: random operations versus a snapshot model

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The commands remember the cursor before and after each edit, so undo and redo put the cursor back where the user expects it (the model gets that for free from its snapshots). The test compares both the text and the cursor after every one of the 4,000 operations. An earlier draft of this editor left the cursor wherever the command ended; the test caught the mismatch immediately, which is exactly what such a test is for.

Complexity

Let n be the document length, d the distance the cursor moves, and c the size of an edit.

Operation String buffer Gap buffer
Insert at cursor O(n) O(c) amortized
Delete before cursor O(n) O(c)
Move cursor by d O(1) O(d)
Undo / redo one edit O(n) O(c + d)
Space O(n) O(n), plus the gap

The undo and redo stacks store each edit once, so their memory is proportional to the total size of edits made (bounded if you cap the history).

Ideas to extend it

  • Limit the history to the last 1,000 steps by using a deque with a maxlen.
  • Multiple cursors and selections. Replace one cursor with a list of ranges.
  • Lines. Keep a separate array of line start offsets (rebuilt lazily) to jump to line numbers.
  • Search. Add substring search with a pattern-matching algorithm.
  • Persistent undo. Use a persistent rope so every document version is cheap to keep.

Common mistakes

  • Not clearing the redo stack on a new edit. Redo then replays edits against a document they no longer fit.
  • Undoing in the wrong order. Commands must be reversed last-in, first-out; reversing out of order corrupts positions.
  • Storing only the new text in a delete command. Undo needs the removed text, so a delete must remember it.
  • Off-by-one in positions. Decide once whether a position is a gap between characters (as here) and stay consistent.
  • Using the gap buffer for random access in loops. Reading buf[i] must skip the gap; use text() or an index helper rather than raw indexes.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is typing at the cursor fast in a gap buffer?

    The gap is positioned at the cursor, so inserting is a single write plus advancing the gap start, with no shifting of the rest of the text.
  2. 2. What costs time in a gap buffer when the user clicks far from the cursor?

    Moving the gap means shifting every character between the old and the new cursor position, so the cost is proportional to the distance, not the document size.
  3. 3. Why does a new edit clear the redo stack?

    Once you edit after an undo, the history has branched. The old future edits assume a document state that no longer exists.
  4. 4. What must a delete command store to be undoable?

    To undo a deletion you must reinsert the exact removed text at the exact position.
  5. 5. In a model-based test, why compare against a snapshot model?

    A model that stores whole copies of the document has nothing subtle to get wrong, which makes it a trustworthy reference for the optimized implementation.

Summary

  • A plain string makes every insert copy the document (O(n)); typing n characters costs O(n^2) in total.
  • A gap buffer keeps the free space at the cursor: inserts and backspaces are O(1) amortized and moving the cursor costs the distance moved.
  • Undo and redo are two stacks of command objects; each command knows how to apply and reverse itself.
  • A new edit clears the redo stack; commands must store whatever is needed to reverse themselves (the removed text for deletes).
  • Coalescing merges consecutive typing into one undo step.
  • A model-based test against a snapshot copy exercises undo/redo edge cases that hand-written tests miss.

Next: Project: Task Scheduler