Requirements & System Scope
Functional Scope (In-Scope)
- Dynamic Formula Resolution: Evaluating raw strings starting with
=supporting coordinate addition and functions (e.g.SUM). - Cell Reference Ranges: Expanding rectangular grid bounding coordinates like
A1:B3to discrete coordinate sequences during dependency evaluation. - Strict Circular Reference Blocking: Intercepting circular loops via DFS checking before allowing any formula insertion.
- Sub-Graph Incremental Recalculation: Minimizing overhead by only re-evaluating cells downstream from modified dependencies.
- Error Cascade Propagation: Instantly bubbling standard spreadsheet error conditions like
#CIRC!or#REF!to all dependent downstream cell configurations.
Explicit Boundaries (Out-of-Scope)
- Advanced Math Functions: Parsing external trigonometry modules, complex statistics formulas, or multi-argument logical operators (e.g. IF/VLOOKUP).
- Physical Rendering Graphics: Canvas/WebGl layouts, cell border rendering, custom fonts, or CSV/XLSX file format encoders.
Class Diagram & Entity Relationships
Spreadsheet internal DAG relationships mapping Cell references:
Loading...
- Cell: Represents a coordinate container holding raw input inputs, resolved computed double or error string, and topological graph vectors.
- Spreadsheet: Map container managing active coordinates, building topological orderings, and orchestrating evaluations.
Design Patterns & SOLID Principles
- Interpreter Pattern: Resolves, evaluates, and parses standard cell coordinate expressions or arithmetic configurations dynamically.
- Observer Pattern: Cells act as publishers notifying their dependents whenever their local computed state resolves to a new value.
- Single Responsibility Principle (SRP): Decouples topological order computation from individual cell parser and math expression evaluators.
Core Execution Workflows
Topological Cell Dependency Recalculation
- A user assigns a value or formula string to cell
X. - The formula is inspected to identify references.
- A cycle-detection traversal (DFS) verifies whether adding
X → Ycreates a graph loop. - If clean, old dependency references are unlinked, new references are saved, and
X's raw input is written. - An incremental sub-graph topological sort (pre-order DFS) is calculated containing
Xand all recursive dependents. - The evaluator executes each node in dependency-sorted order, propagating calculations and cascading errors downstream.
Concurrency & Thread Safety Strategy
Ensuring correctness under concurrent multi-user cell inputs:
- Read-Write Lock Separation: Read-write locks ensure thread safety by allowing multiple threads to query cell values concurrently while serializing write operations during formula adjustments.
- Sub-Graph Thread Locking: For very large sheets, locks can be acquired dynamically per topological path rather than blocking the entire spreadsheet map.
Complete Clean Code Blueprint
Clean reference designs demonstrating pre-order topological evaluation and cycle blocking in Java and Python:
// ─── JAVA BLUEPRINT ──────────────────────────────────────────────────────────
import java.util.*;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.regex.*;
class Cell {
private final String name;
private String rawInput;
// Either Double OR String error code
private Object computedValue;
// Cells THIS cell depends on
private final Set<String> dependencies = new HashSet<>();
// Cells depending on THIS cell
private final Set<String> dependents = new HashSet<>();
public Cell(String name) {
this.name = name;
this.rawInput = "";
this.computedValue = 0.0;
}
public String getName() {
return name;
}
public String getRawInput() {
return rawInput;
}
public void setRawInput(String rawInput) {
this.rawInput = rawInput;
}
public Object getComputedValue() {
return computedValue;
}
public void setComputedValue(Object computedValue) {
this.computedValue = computedValue;
}
public Set<String> getDependencies() {
return dependencies;
}
public Set<String> getDependents() {
return dependents;
}
}
class Spreadsheet {
private final Map<String, Cell> cells = new HashMap<>();
private final ReentrantReadWriteLock rwLock =
new ReentrantReadWriteLock();
public Cell getOrCreateCell(String name) {
return cells.computeIfAbsent(name, Cell::new);
}
public void setCell(String name, String input) throws Exception {
rwLock.writeLock().lock();
try {
Cell cell = getOrCreateCell(name);
Set<String> oldDeps =
new HashSet<>(cell.getDependencies());
Set<String> newDeps =
parseDependencies(input);
// TEMPORARILY update deps for cycle check
cell.getDependencies().clear();
cell.getDependencies().addAll(newDeps);
if (hasCycle(name)) {
// revert
cell.getDependencies().clear();
cell.getDependencies().addAll(oldDeps);
throw new IllegalArgumentException(
"Circular dependency detected for cell: " + name
);
}
// cleanup old relationships
for (String oldDep : oldDeps) {
if (!newDeps.contains(oldDep)) {
Cell depCell = cells.get(oldDep);
if (depCell != null) {
depCell.getDependents().remove(name);
}
}
}
// add new relationships
for (String newDep : newDeps) {
if (!oldDeps.contains(newDep)) {
getOrCreateCell(newDep)
.getDependents()
.add(name);
}
}
cell.setRawInput(input);
recalculate(name);
} finally {
rwLock.writeLock().unlock();
}
}
public Object getCellValue(String name) {
rwLock.readLock().lock();
try {
Cell cell = cells.get(name);
if (cell == null) {
return 0.0;
}
return cell.getComputedValue();
} finally {
rwLock.readLock().unlock();
}
}
// ─────────────────────────────────────────────────────────────
private Set<String> parseDependencies(String input) {
Set<String> deps = new HashSet<>();
if (input == null || !input.startsWith("=")) {
return deps;
}
Pattern rangePattern =
Pattern.compile("([A-Z]+[0-9]+):([A-Z]+[0-9]+)");
Matcher rangeMatcher =
rangePattern.matcher(input);
while (rangeMatcher.find()) {
deps.addAll(
expandRange(
rangeMatcher.group(1),
rangeMatcher.group(2)
)
);
}
Pattern cellPattern =
Pattern.compile("\\b([A-Z]+[0-9]+)\\b");
Matcher cellMatcher =
cellPattern.matcher(
input.replaceAll(
"([A-Z]+[0-9]+):([A-Z]+[0-9]+)",
""
)
);
while (cellMatcher.find()) {
deps.add(cellMatcher.group(1));
}
return deps;
}
private List<String> expandRange(String start, String end) {
List<String> list = new ArrayList<>();
String startColStr =
start.replaceAll("[0-9]", "");
String endColStr =
end.replaceAll("[0-9]", "");
int startRow =
Integer.parseInt(
start.replaceAll("[A-Z]", "")
);
int endRow =
Integer.parseInt(
end.replaceAll("[A-Z]", "")
);
int startCol =
columnToNumber(startColStr);
int endCol =
columnToNumber(endColStr);
int minCol = Math.min(startCol, endCol);
int maxCol = Math.max(startCol, endCol);
int minRow = Math.min(startRow, endRow);
int maxRow = Math.max(startRow, endRow);
for (int col = minCol; col <= maxCol; col++) {
String colName = numberToColumn(col);
for (int row = minRow; row <= maxRow; row++) {
list.add(colName + row);
}
}
return list;
}
private int columnToNumber(String col) {
int result = 0;
for (int i = 0; i < col.length(); i++) {
result =
result * 26 +
(col.charAt(i) - 'A' + 1);
}
return result;
}
private String numberToColumn(int num) {
StringBuilder sb = new StringBuilder();
while (num > 0) {
num--;
sb.append(
(char) ('A' + (num % 26))
);
num /= 26;
}
return sb.reverse().toString();
}
// ─────────────────────────────────────────────────────────────
private boolean hasCycle(String startCell) {
Set<String> visited = new HashSet<>();
Set<String> stack = new HashSet<>();
return dfsCheck(startCell, visited, stack);
}
private boolean dfsCheck(
String curr,
Set<String> visited,
Set<String> stack
) {
if (stack.contains(curr)) {
return true;
}
if (visited.contains(curr)) {
return false;
}
visited.add(curr);
stack.add(curr);
Cell cell = cells.get(curr);
if (cell != null) {
for (String dep : cell.getDependencies()) {
if (dfsCheck(dep, visited, stack)) {
return true;
}
}
}
stack.remove(curr);
return false;
}
// ─────────────────────────────────────────────────────────────
private void recalculate(String startCell) {
List<String> order =
getTopologicalOrder(startCell);
for (String cellName : order) {
evaluateCell(cells.get(cellName));
}
}
private List<String> getTopologicalOrder(String start) {
List<String> order = new ArrayList<>();
Set<String> visited = new HashSet<>();
dfsTopologicalSort(start, visited, order);
return order;
}
private void dfsTopologicalSort(
String curr,
Set<String> visited,
List<String> order
) {
visited.add(curr);
order.add(curr); // pre-order: add BEFORE visiting dependents
Cell cell = cells.get(curr);
if (cell != null) {
for (String dep : cell.getDependents()) {
if (!visited.contains(dep)) {
dfsTopologicalSort(
dep,
visited,
order
);
}
}
}
}
// ─────────────────────────────────────────────────────────────
private void evaluateCell(Cell cell) {
String input = cell.getRawInput();
if (input == null || input.isEmpty()) {
cell.setComputedValue(0.0);
return;
}
// RAW VALUE
if (!input.startsWith("=")) {
try {
cell.setComputedValue(
Double.parseDouble(input)
);
} catch (NumberFormatException e) {
cell.setComputedValue("#VAL!");
}
return;
}
// FORMULA
String formula =
input.substring(1).trim();
try {
// SUM(A1:C5)
if (formula.startsWith("SUM(")) {
String range =
formula.substring(
4,
formula.length() - 1
);
String[] parts =
range.split(":");
List<String> rangeCells =
expandRange(parts[0], parts[1]);
double sum = 0;
for (String rc : rangeCells) {
Object val = getCellValue(rc);
if (val instanceof String) {
cell.setComputedValue(val);
return;
}
sum += (Double) val;
}
cell.setComputedValue(sum);
} else {
// A1+B1+10
String[] parts =
formula.split("\\+");
double sum = 0;
for (String part : parts) {
part = part.trim();
if (
part.matches("[A-Z]+[0-9]+")
) {
Object val =
getCellValue(part);
if (val instanceof String) {
cell.setComputedValue(val);
return;
}
sum += (Double) val;
} else {
sum += Double.parseDouble(part);
}
}
cell.setComputedValue(sum);
}
} catch (Exception e) {
cell.setComputedValue("#REF!");
}
}
}
// ─────────────────────────────────────────────────────────────
public class Main {
public static void main(String[] args)
throws Exception {
System.out.println(
"=== STARTING SPREADSHEET ENGINE DEMO ==="
);
Spreadsheet sheet =
new Spreadsheet();
// ─────────────────────────────────────────
// BASIC VALUES
// ─────────────────────────────────────────
sheet.setCell("A1", "10");
sheet.setCell("B1", "20");
System.out.println(
"A1: " + sheet.getCellValue("A1") +
", B1: " + sheet.getCellValue("B1")
);
// ─────────────────────────────────────────
// SIMPLE FORMULA
// ─────────────────────────────────────────
sheet.setCell("C1", "=A1+B1");
System.out.println(
"Formula C1 (=A1+B1) resolved to: " +
sheet.getCellValue("C1")
);
// ─────────────────────────────────────────
// RANGE SUM
// ─────────────────────────────────────────
sheet.setCell("D1", "=SUM(A1:C1)");
System.out.println(
"Formula D1 (=SUM(A1:C1)) resolved to: " +
sheet.getCellValue("D1")
);
// ─────────────────────────────────────────
// CASCADE UPDATE
// ─────────────────────────────────────────
System.out.println(
"\n--- Changing cell A1 to 150 ---"
);
sheet.setCell("A1", "150");
System.out.println(
"C1 (expected 170): " +
sheet.getCellValue("C1")
);
System.out.println(
"D1 (expected 200): " +
sheet.getCellValue("D1")
);
// ─────────────────────────────────────────
// MULTI LETTER COLUMN TEST
// ─────────────────────────────────────────
sheet.setCell("AA1", "5");
sheet.setCell("AB1", "15");
sheet.setCell("AC1", "=AA1+AB1");
System.out.println(
"\nAC1 (expected 20): " +
sheet.getCellValue("AC1")
);
sheet.setCell("AD1", "=SUM(AA1:AC1)");
System.out.println(
"AD1 (expected 40): " +
sheet.getCellValue("AD1")
);
// ─────────────────────────────────────────
// CIRCULAR DEPENDENCY TEST
// ─────────────────────────────────────────
System.out.println(
"\n--- Attempting Circular Dependency ---"
);
try {
sheet.setCell("C1", "=D1+10");
} catch (IllegalArgumentException e) {
System.out.println(
"[REJECTED SUCCESSFULLY] " +
e.getMessage()
);
}
System.out.println(
"C1 state after rejection: " +
sheet.getCellValue("C1")
);
System.out.println(
"\n=== SIMULATION COMPLETE ==="
);
}
}
Review
Help Us Improve
How helpful was this walkthrough?
Click a star to rate. We actively use this feedback to refine and update our system design content.
Placeholder
Discussion
Share your thoughts, ask questions, or help others.
Loading comments...