Roadmap¶
Every chapter ends with a program that builds and runs. Chapters are written when the previous one is finished, so this page is the plan, not an archive: the Status column tells you what exists today.
Chapters¶
| # | Chapter | You build | Status |
|---|---|---|---|
| Part I — Foundations | |||
| 1 | The Workbench | The library, CLI, feature matrix, DOT writer, tests, benchmark harness | Ready |
| 2 | Counting Steps | Instrumented counters, growth experiments, amortized-cost measurements | Planned |
| 3 | Four Orders, Three Mechanisms | Expression compiler; threaded tree and Morris traversal; lazy in-order range | Planned |
| 4 | Nodes, Ownership, Layout | A scene graph in pointer, arena, and implicit representations | Planned |
| 5 | The Search-Tree Contract | An order book on a BST, with std::map and std::flat_map baselines |
Planned |
| Part II — Balanced search trees | |||
| 6 | AVL: Height, Rotations, and the Cost of Balance | An exchange matching index with rotation snapshots | Planned |
| 7 | Red-Black: Color, Black Height, and the Tree Inside std::map |
A real-time scheduler with an RB tree; a tour of libc++'s __tree |
Planned |
| 8 | Augmented Trees: Rank, Intervals, and Repair | A leaderboard with rank/percentile queries; an interval calendar | Planned |
| 9 | Splay: Amortized Balance and the Potential Method | A self-organizing cache compared with LRU | Planned |
| 10 | Randomization: Treaps, Skip Lists, and the Balance Zoo | A text-editor rope and a symbol-table skip list | Planned |
| Part III — Trees as machines | |||
| 11 | Heaps and Priority Queues: The Engine of Greed | A launch-event simulator; an indexed heap; mergeable heaps | Planned |
| 12 | Huffman: Optimal Codes and the Exchange Argument | A probe-telemetry compressor with canonical codes | Planned |
| 13 | Tries and Radix Trees: Prefixes at Speed | An autocomplete engine and an IP longest-prefix matcher | Planned |
| 14 | B-Trees: The Disk Is the Enemy | A page-based index with simulated disk I/O counters | Planned |
| 15 | B+ Trees in Anger: Range Scans and a Tiny Database | A mini database index with range scans and a page cache | Planned |
| 16 | Segment and Fenwick Trees: Answers About Ranges | Market analytics with range updates and prefix aggregates | Planned |
| 17 | Suffix Arrays and Suffix Trees: Searching Inside Strings | A genome pattern finder with a suffix array, LCP, and search | Planned |
| 18 | Spatial Trees: KD-Trees, Quadtrees, and Nearest Neighbors | Point-cloud k-NN and a quadtree collision broadphase | Planned |
| Part IV — Graphs: structure | |||
| 19 | Graphs and Their Representations: The Cost of a Choice | A network loader and an adjacency-list/matrix/CSR benchmark | Planned |
| 20 | BFS and DFS: Two Ways to Explore | Maze/Pac-Man AI, compiler CFG reachability, and an Euler tour | Planned |
| 21 | Disjoint Sets: Connectivity for Almost Free | A connectivity service and image segmentation | Planned |
| 22 | Topological Order: DAGs, Builds, and Critical Paths | A mini build system with cycle diagnostics | Planned |
| Part V — Graphs: optimization | |||
| 23 | Minimum Spanning Trees: Connecting Everything for Less | A Mars habitat network planner with Kruskal, Prim, and Boruvka | Planned |
| 24 | Dijkstra and A*: Shortest Paths with a Priority Queue | Rover and campus navigation with bidirectional search | Planned |
| 25 | Bellman-Ford, Floyd-Warshall, and Arbitrage | An FX triangular-arbitrage detector | Planned |
| 26 | Strongly Connected Components and 2-SAT | A package dependency analyzer with condensation and 2-SAT | Planned |
| 27 | Network Flow and Matching: Cuts, Assignments, Auctions | A bandwidth broker and an ad auction with Dinic and matching | Planned |
| Part VI — Advanced structures | |||
| 28 | Trees as Graphs: LCA, Tree DP, and Decompositions | A filesystem/org-chart query engine with HLD and centroid decomposition | Planned |
| 29 | Dynamic Graphs: Connectivity Under Change (deep) | A datacenter topology simulator with rollback DSU and link-cut trees | Planned |
| 30 | Persistent Trees: Time Travel for Data Structures (deep) | A versioned ledger with snapshots and time-travel queries | Planned |
| 31 | Succinct Trees: Wavelet Trees and Compressed Indexes (bonus) | A wavelet tree and an FM-index | Planned |
| Part VII — Craft and capstone | |||
| 32 | Proving and Testing Structures | Property tests, differential tests, a fuzzer, and sanitizer runs | Planned |
| 33 | Performance: Cache, Allocators, Concurrency | Cache-conscious layouts, pmr, and a parallel BFS |
Planned |
| 34 | Visualizing Structures | A tree-layout SVG renderer and a step-through viewer | Planned |
| 35 | Hard Graphs: Coloring, TSP, and Approximation (bonus) | Map coloring and delivery routing with approximations | Planned |
| 36 | Capstone: Choose Your Hard Problem | One of five integration projects, with a spec and a rubric | Planned |
Studios¶
The studios are optional set pieces that link atlas_core and combine two to
four chapters. They are not chapters; they are where the library becomes a
product.
| Studio | After | Combines | What you build | Status |
|---|---|---|---|---|
| Calc | Part I | 3, 4, 5 | An expression language with an AST, a constant folder, and an SVG view | Planned |
| Exchange | Part II | 5–8 | A limit order book with matching, rank queries, and a depth chart | Planned |
| Pack & Find | Part III | 12–15 | A Huffman-compressed dictionary, trie autocomplete, and a B+tree index | Planned |
| World | Part IV | 16, 18, 20, 21 | A 512×512 game world with lazy quadtree terrain, 10,000 units, and union-find regions | Planned |
| Mission | Part V | 23, 24, 27 | A space network planner with MST, A*, and max-flow | Planned |
| Time | Part VI | 28, 30 | A versioned filesystem with persistent snapshots and LCA path queries | Planned |
| See | Part VII | 34 | An interactive step-through visualizer for every structure | Planned |
Recommended first three: World, Exchange, See. A mini build system is the Chapter 22 checkpoint and one of the capstone options, so it is not a separate studio.
Side quests¶
Small, optional detours, 30–60 minutes each:
- Chapter 4: a scene graph with dirty flags; move a parent and propagate the transforms to the subtree.
- Chapter 18: an asteroid dodger that uses the quadtree for collision.
- Chapter 20: Pac-Man ghost AI on a maze graph.
- Chapter 25: an FX arbitrage detector on synthetic exchange rates.
- Chapter 34: a rotation animator with pause, step, and replay.