Use a
Spreadsheet class owning a private rectangular Java array of cells. Each immutable internal Cell contains a private tag Kind with values EMPTY, LABEL, NUMBER, FORMULA, and the corresponding payload: a string, a double or a formula reference. The tag determines which payload is meaningful, and the spreadsheet's setters create valid combinations rather than letting callers change fields independently. The cell object need not be public; public methods can expose its kind and label when needed for display.Provide public
setEmpty(r,c), setLabel(r,c,text), setNumber(r,c,x) and setFormula(r,c,f) methods, each checking its target coordinates and invalidating cached results. A public valueAt(r,c) supplies the numerical value, treating out-of-grid, empty and label cells as zero, and a public recalculate() brings all valid formulas up to date. Keep cached numeric results and evaluation-state flags private; they are derived data rather than editable cell content.Define a public
Formula interface with double evaluate(Lookup values, int row, int column). Lookup supplies only valueAt(r,c), so a formula can read dependencies without needing direct access to cells or a mutation API. An immutable AddFormula stores four integer offsets, two row/column pairs. It evaluates the two coordinates relative to the formula's own position and returns their sum. New formula kinds implement the same interface, avoiding changes to the storage representation or a large central switch over all formula operations.The private spreadsheet dependency evaluation mechanism provides the
Lookup implementation, checks cycles and caches evaluated cells. Formula evaluation is required to be side-effect-free with fixed dependencies during a recalculation. This separates encapsulation in object-oriented programming from extension: callers can change a cell through public setters and add new formula implementations, while internal cell invariants and cached values remain protected. Use tagged cell contents, an extensible formula interface and spreadsheet-owned evaluation state.Use recursive dependency evaluation with memoization. After an edit, invalidate all cell states. To evaluate one formula, recursively obtain its dependencies before storing its own result. This is a depth-first search of the dependency graph; a visiting mark identifies a cycle, and a done mark avoids repeated evaluation of a shared dependency. The following single class implements the design, with public nested interfaces for formula extensions:The outer loop's order need not be a topological ordering, since recursion evaluates dependencies first. After an edit, callers can invoke
public final class Spreadsheet {
public enum Kind { EMPTY, LABEL, NUMBER, FORMULA }
public interface Lookup {
double valueAt(int row, int col);
}
public interface Formula {
double evaluate(Lookup values, int row, int col);
}
public static final class AddFormula implements Formula {
private final int dr1, dc1, dr2, dc2;
public AddFormula(int dr1, int dc1, int dr2, int dc2) {
this.dr1 = dr1; this.dc1 = dc1;
this.dr2 = dr2; this.dc2 = dc2;
}
public double evaluate(Lookup values, int r, int c) {
return values.valueAt(r + dr1, c + dc1)
+ values.valueAt(r + dr2, c + dc2);
}
}
private static final class Cell {
private final Kind kind;
private final String label;
private final double number;
private final Formula formula;
private Cell(Kind k, String s, double n, Formula f) {
kind = k; label = s; number = n; formula = f;
}
}
private static final Cell EMPTY =
new Cell(Kind.EMPTY, null, 0.0, null);
private final int rows, cols;
private final Cell[][] cells;
private final double[][] cache;
private final byte[][] state;
private final Lookup view = new Lookup() {
public double valueAt(int r, int c) {
return Spreadsheet.this.valueAt(r, c);
}
};
public Spreadsheet(int rows, int cols) {
if (rows < 0 || cols < 0) throw new IllegalArgumentException();
this.rows = rows; this.cols = cols;
cells = new Cell[rows][cols];
cache = new double[rows][cols];
state = new byte[rows][cols];
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) cells[r][c] = EMPTY;
}
private boolean inside(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
private void check(int r, int c) {
if (!inside(r, c)) throw new IndexOutOfBoundsException();
}
private void invalidate() {
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) state[r][c] = 0;
}
private void put(int r, int c, Cell cell) {
check(r, c); cells[r][c] = cell; invalidate();
}
public void setEmpty(int r, int c) { put(r, c, EMPTY); }
public void setLabel(int r, int c, String text) {
if (text == null) throw new IllegalArgumentException();
put(r, c, new Cell(Kind.LABEL, text, 0.0, null));
}
public void setNumber(int r, int c, double x) {
put(r, c, new Cell(Kind.NUMBER, null, x, null));
}
public void setFormula(int r, int c, Formula f) {
if (f == null) throw new IllegalArgumentException();
put(r, c, new Cell(Kind.FORMULA, null, 0.0, f));
}
public Kind kindAt(int r, int c) {
check(r, c); return cells[r][c].kind;
}
public String labelAt(int r, int c) {
check(r, c); return cells[r][c].label;
}
public double valueAt(int r, int c) {
if (!inside(r, c)) return 0.0;
if (state[r][c] == 2) return cache[r][c];
if (state[r][c] == 1)
throw new IllegalStateException("Cyclic formula dependency");
state[r][c] = 1;
try {
Cell cell = cells[r][c];
double answer;
switch (cell.kind) {
case NUMBER: answer = cell.number; break;
case FORMULA: answer = cell.formula.evaluate(view, r, c); break;
default: answer = 0.0;
}
cache[r][c] = answer;
state[r][c] = 2;
return answer;
} catch (RuntimeException error) {
state[r][c] = 0;
throw error;
}
}
public void recalculate() {
invalidate();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) valueAt(r, c);
}
}recalculate; ordinary valueAt calls also calculate lazily from the invalidated state. Empty and label cells contribute zero without destroying their display content. Relative references are interpreted at the formula's location, and off-grid references contribute zero as required.For an acyclic graph, mathematical induction over a topological ordering proves that each cached value equals the evaluation of current cell contents. Each cell becomes done at most once in a pass, so the time complexity is for cells and dependency references, plus formula arithmetic. The stack depth is at most the longest dependency path. A more elaborate implementation can record reverse dependencies and invalidate only cells affected by an edit.
The PDF gives no policy for circular formulas. Repeated numerical sweeps are not a general solution: a cell defined as itself plus one has no finite value, while a cell defined as itself plus zero has no unique value. The implementation therefore reports a cycle instead of looping or presenting an arbitrary stale value. An acyclic dependency graph is evaluated once per cell; circular dependencies are detected and rejected.
Articles by others on the same topic
There are currently no matching articles.