Advanced Project 2 — Spreadsheet Engine¶

Difficulty: Advanced · Estimated effort: 2–3 weeks · Prerequisites: Module 15 — SOLID and Design Patterns, Module 11 — RAII and Smart Pointers, Module 12 — Templates, Module 13 — Exception Handling · Demanded pattern decisions: composite, observer

This is one of the designated integration projects, and one of the projects that requires a design-pattern decision: at least two patterns must be named and justified by a requirement, and one alternative must be considered and declined in writing.

No complete solution is provided. The formula model is the project; a solution would be the design.

1. Scenario¶

A departmental planner keeps a small budget model in a spreadsheet, and wants it in a program because the file gets copied between machines and the formulas diverge. The model has formulas over cells, percentages, sums over ranges, and one circular reference that a former colleague introduced and nobody has found.

The hard requirement is honesty about recalculation: changing one cell must update exactly the cells that depend on it, and a cycle must be reported rather than looping forever.

2. Problem statement¶

Build a spreadsheet engine: cells holding numbers or formulas, formulas parsed into a tree, evaluation with dependency tracking, recalculation of exactly the affected cells, cycle detection with a readable path, and a file format that round-trips a sheet exactly.

3. User requirements¶

[ ] Set a cell to a number, a formula or a label.
[ ] Read any cell's value; a formula cell reports its computed value.
[ ] Change a cell and see the affected cells update — and only those.
[ ] Load a sheet from a file and save it back unchanged.
[ ] Be told, with the path, when a formula refers to itself indirectly.
[ ] See the text of a cell's formula as well as its value.

4. Functional requirements¶

[ ] CellAddress with a column and row, parsed from and printed as B7.
[ ] A Cell holding either a number, a label or a formula.
[ ] A formula tree: at least literals, cell references, binary operators, and one range function (SUM).
[ ] A parser for formula text, producing the tree, with line and column context in errors.
[ ] A Sheet owning cells, with dependency information maintained as cells change.
[ ] Recalculation that touches only cells depending on the changed one — proven by a counter of evaluations.
[ ] Cycle detection reporting the cycle as a path of addresses.
[ ] A documented file format with a version marker.

5. Non-functional requirements¶

[ ] Changing a constant cell's value evaluates each affected cell exactly once — the evaluation counter is part of the deliverable.
[ ] A failed formula change leaves the sheet exactly as it was (strong guarantee).
[ ] No dangling references when a cell is cleared; dependents are updated or invalidated.
[ ] Loading a file with a cycle fails with the path, and produces no sheet.
[ ] Builds warning-free with g++ -std=c++17 -Wall -Wextra -Werror.

6. Suggested features¶

Functions beyond SUM: AVERAGE, MIN, MAX, and a two-argument IF.
Recalculation order reported as a list of addresses, which makes the dependency graph visible.
A "trace precedence" query: what does D4 depend on, directly and indirectly?
Ranges with a start and end address, and a note on how a range's dependencies are recorded.

7. OOP concepts involved¶

Concept	Required	Where it appears
Multiple classes	yes	Addresses, cells, expression nodes, parser, dependency graph, sheet, error types
Relationships	yes	Sheet ◆ cells; expression ──> referenced cells; graph ──> edges between cells
Encapsulation	yes	A cell's value is only recomputed by the engine; the graph is not externally mutable
Inheritance or composition	yes	The expression tree is pure inheritance; the sheet has a graph rather than being one
Polymorphism	yes	`evaluate()` over the expression types; no node-type tags
The STL	yes	`std::map` for cells keyed by address, `std::set` for dependents, `<algorithm>` for ranges
Exception handling	yes	Parse errors, bad references and cycles each throw distinct types with context

8. Suggested design considerations¶

The pattern decision you must make and justify¶

Composite, for the expression tree. A formula is a tree of nodes, and evaluation is uniform over the tree — that is the definition of the composite pattern, and the requirement that earns it is one evaluate path for literals, operations and functions alike. You must still say what the alternative was: an interpreted string with a stack machine, or a switch on a node tag.

Observer, for recalculation. Cells depend on cells. Either dependents register with the cells they depend on and are notified on change (observer), or the sheet keeps a graph and recomputes a topological order on demand. The observer earns its place if a change must update only affected cells; the graph earns its place if you also want a visible order. Use both, or decline one with a reason — declining one of these is the declined-pattern item, and it must be argued, not asserted.

Ideas worth weighing and recording: strategy for the recalculation order (probably earned once you compare two orders), and a visitor for a "print all formulas" pass (almost certainly not earned).

Other design points¶

Evaluate exactly once. The evaluation counter is not a nicety: it is the evidence that your dependency tracking works, and the test that catches a dependency graph that is merely a recursion.

Cycles are a first-class outcome. A cycle is not an error of the program; it is a user mistake the program must describe. Reporting the path of addresses is what makes it fixable.

Clearing a cell is a mutation like any other. The dangling-reference bug appears here, not in setting values, and the checklist targets it.

9. Minimum viable version¶

Cells with numbers and labels, one binary operator and SUM, evaluation by recursion, and a text dump of the sheet. No dependency graph, no cycle detection, but references and errors are typed.

10. Intermediate extension¶

Add the formula tree as a composite, dependents registration and recalculation, plus the evaluation counter. Prove that changing one cell evaluates each dependent exactly once, and that a diamond dependency (A → B, A → C, B → D, C → D) evaluates D once, not twice.

11. Advanced extension¶

Add cycle detection with a path, save/load of sheets including formula text, and two more functions. Then write the design note: the patterns chosen and declined, the evaluation counter evidence, and the decision you would reverse — with its cost.

12. Testing checklist¶

[ ] =1+2*3 evaluates to 7, and =(1+2)*3 to 9
[ ] A formula referencing an empty cell evaluates as documented (zero or an error — pick one)
[ ] SUM(A1:A3) includes both endpoints and ignores labels in the range
[ ] Changing A1 updates every dependent and leaves unrelated cells unevaluated (counter)
[ ] A diamond dependency evaluates the shared descendant exactly once
[ ] A direct self-reference and an indirect cycle are both refused with the full path
[ ] Clearing a cell that others depend on leaves the sheet consistent, with those cells invalidated or recomputed as documented
[ ] An out-of-range address (ZZ99999) is refused rather than allocated
[ ] A malformed formula reports the position of the offending character
[ ] A failed formula change leaves the sheet byte-for-byte unchanged
[ ] Save → load → save produces identical files, formula text included

13. Documentation checklist¶

[ ] The formula grammar, written as a grammar
[ ] The class diagram with the expression tree and the dependency edges
[ ] The recalculation policy, with the evaluation-count evidence pasted from a real run
[ ] The cycle report format, with a real example
[ ] The patterns chosen, the one declined, and the reversed decision with its cost

14. Self-evaluation rubric¶

Criterion	Excellent looks like	Weight
Expression model	Tree evaluated uniformly; parser errors precise	25%
Dependency handling	Exactly-once recalculation, demonstrated by counter, including diamonds	25%
Pattern decisions	Composite and observer justified; the declined alternative argued	20%
Cycle handling	Detected, reported as a path, and load-time cycles rejected	10%
Persistence	Round trip preserving formula text and values	10%
Failure handling	Parse, reference and cycle errors typed and contextual	5%
Documentation	Grammar, evidence and the reversed decision written down	5%