Project 4: Undo/Redo Engine for a Drawing Application

Implement a command-based undo/redo engine with branching history and state integrity.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 1-2 weeks
Language C
Prerequisites Data structures, serialization basics
Key Topics Command pattern, temporal state, branching history

1. Learning Objectives

By completing this project, you will:

  1. Model edits as commands with do/undo behavior.
  2. Maintain consistent state across undo/redo operations.
  3. Handle branching history when new edits occur after undo.
  4. Persist history safely if desired.

2. Theoretical Foundation

2.1 Core Concepts

  • Command pattern: Each action has an inverse and is replayable.
  • Temporal correctness: History must reflect real execution order.
  • Branching: New commands after undo invalidate the redo chain.

2.2 Why This Matters

Undo/redo engines are the canonical example of temporal state. They show why order and reversibility matter.

2.3 Historical Context / Background

Modern editors use command stacks for undo; many also support non-linear history. The minimal version still teaches most of the state discipline.

2.4 Common Misconceptions

  • “Undo is just popping state”: You must reverse the command logic precisely.
  • “Redo always exists”: Only if history is not branched.

3. Project Specification

3.1 What You Will Build

A command-driven engine for a simple drawing model (shapes on a canvas). Actions like add, move, delete are undoable and redoable.

3.2 Functional Requirements

  1. Command interface: Each command has apply and revert.
  2. Undo stack: Stores executed commands.
  3. Redo stack: Stores undone commands until new edit.
  4. Branching rule: New command clears redo.

3.3 Non-Functional Requirements

  • Reliability: Undo should never corrupt state.
  • Performance: Commands should be small and fast.
  • Usability: Clear APIs for undo/redo availability.

3.4 Example Usage / Output

add circle -> undo stack size 1
move circle -> undo stack size 2
undo -> circle back to old position
redo -> circle moved again

3.5 Real World Outcome

A REPL-style test shows consistent undo/redo behavior:

> add circle x=10 y=10
> move circle x=20 y=10
> undo
> redo

4. Solution Architecture

4.1 High-Level Design

┌──────────────┐     ┌──────────────┐     ┌──────────────┐
│ user action  │────▶│ command obj  │────▶│ canvas state │
└──────────────┘     └──────────────┘     └──────────────┘

4.2 Key Components

Component Responsibility Key Decisions
Command Apply/revert action Store enough info for undo
History Manage stacks Undo/redo stacks
Canvas State to mutate Simple list of shapes

4.3 Data Structures

typedef enum {
    CMD_ADD,
    CMD_MOVE,
    CMD_DELETE
} CommandType;

typedef struct {
    CommandType type;
    int shape_id;
    int x_before, y_before;
    int x_after, y_after;
} Command;

4.4 Algorithm Overview

Key Algorithm: Command history

  1. Apply command and push to undo stack.
  2. On undo, pop undo stack, revert, push to redo.
  3. On new command, clear redo.

Complexity Analysis:

  • Time: O(1) per command.
  • Space: O(H) for history length.

5. Implementation Guide

5.1 Development Environment Setup

gcc --version

5.2 Project Structure

project-root/
├── src/
│   ├── command.c
│   ├── history.c
│   ├── canvas.c
│   └── main.c
└── Makefile

5.3 The Core Question You’re Answering

“How do I move backward and forward in time without breaking state?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Command pattern
    • Actions with inverses
  2. State invariants
    • Canvas must be consistent after every operation
  3. Branching history
    • Redo invalidation rules

5.5 Questions to Guide Your Design

  1. What data must be captured in each command to undo it?
  2. How do you ensure redo is cleared after new actions?
  3. How do you validate that undo/redo is possible?

5.6 Thinking Exercise

If you want unlimited undo, how will you manage memory growth?

5.7 The Interview Questions They’ll Ask

  1. Why use commands instead of snapshots?
  2. What happens to redo after a new command?
  3. How do you guarantee reversibility?

5.8 Hints in Layers

Hint 1: Start with add/delete

  • Move commands later.

Hint 2: Store prior state

  • Keep before/after positions.

Hint 3: Clear redo on new command

  • Always reset redo stack.

5.9 Books That Will Help

Topic Book Chapter
State patterns “Design Patterns” Command pattern
Data structures “Algorithms” Stack usage

5.10 Implementation Phases

Phase 1: Foundation (3-4 days)

Goals:

  • Implement command and history stacks.

Tasks:

  1. Build command struct.
  2. Add undo/redo stacks.

Checkpoint: Add and undo a shape.

Phase 2: Core Functionality (4-5 days)

Goals:

  • Add move and delete commands.

Tasks:

  1. Implement move with before/after.
  2. Implement delete with restore.

Checkpoint: Undo/redo works for all actions.

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

Goals:

  • Robust history behavior.

Tasks:

  1. Clear redo on new action.
  2. Handle empty undo/redo.

Checkpoint: No crashes on repeated undo/redo.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
History model stacks vs snapshots stacks Efficiency
Command storage by value vs heap by value Simpler management

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Undo correctness State restored Move then undo
Redo correctness State reapplied Undo then redo
Branching Redo cleared Undo then new add

6.2 Critical Test Cases

  1. Undo after add removes shape.
  2. Undo after move restores original position.
  3. Redo cleared on new command.

6.3 Test Data

Add circle, move, delete

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Missing state Undo incomplete Store before/after
Redo not cleared Incorrect history Clear on new command
Double delete Crash Guard against invalid ids

7.2 Debugging Strategies

  • Log history stack sizes.
  • Add assertions on command invariants.

7.3 Performance Traps

Long histories consume memory; consider pruning or compression.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add redo count command.

8.2 Intermediate Extensions

  • Implement grouped commands (macro actions).

8.3 Advanced Extensions

  • Add branching history with multiple redo paths.

9. Real-World Connections

9.1 Industry Applications

  • Editors: Undo/redo is mandatory UX.
  • CAD tools: Command history is critical.
  • Krita: Complex undo/redo stack.
  • Blender: Command-based history.

9.3 Interview Relevance

  • Demonstrates temporal state management.

10. Resources

10.1 Essential Reading

  • Design Patterns - Command pattern.

10.2 Video Resources

  • Search: “undo redo command pattern”.

10.3 Tools & Documentation

  • None required beyond C tooling.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain why undo is command-based.
  • I can define the branching rule.

11.2 Implementation

  • Undo/redo are consistent across commands.
  • Redo is cleared after new actions.

11.3 Growth

  • I can apply this to any mutable state system.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Undo/redo for add and move.

Full Completion:

  • All command types with consistent history.

Excellence (Going Above & Beyond):

  • Branching history and command grouping.

This guide was generated from SPRINT_3_CONTROL_FLOW_STATE_PROJECTS.md. For the complete learning path, see the parent directory README.