Spreadsheet

main.ts

interface Vertex<T> {
  label: string; // TODO(will): do we really need the label here if it's already the key in the vertex map?
  value: T;
}

interface IDirectedGraph<T> {
  add_vertex(label: string, value: T): Vertex<T>;
  add_edge(from: string, to: string): this;
  get_vertex(label: string): Vertex<T> | null;
  get_neighbors_out(label: string): Array<Vertex<T>>;
  get_neighbors_in(label: string): Array<Vertex<T>>;
}

class DirectedGraph<T> implements IDirectedGraph<T> {
  private readonly edgesOut: {
    [from: string]: Array<string>;
  } = {};

  private readonly edgesIn: {
    [to: string]: Array<string>;
  } = {};
  private readonly vertices: { [label: string]: Vertex<T> } = {};

  // NOTE(will): add or update
  add_vertex(label: string, value: T): Vertex<T> {
    const vertex = this.vertices[label];

    if (!vertex) {
      this.vertices[label] = { label, value };
    } else {
      vertex.value = value;
    }

    return vertex;
  }

  add_edge(from: string, to: string): this {
    const fromVertex = this.get_vertex(from);
    if (!fromVertex) throw new Error(`Vertex ${from} does not exist`);

    const toVertex = this.get_vertex(to);
    if (!toVertex) throw new Error(`Vertex ${to} does not exist`);

    // out edges
    if (!this.edgesOut[fromVertex.label]) {
      this.edgesOut[fromVertex.label] = new Array<string>();
    }
    this.edgesOut[fromVertex.label].push(toVertex.label);

    // in edges
    if (!this.edgesIn[toVertex.label]) {
      this.edgesIn[toVertex.label] = new Array<string>();
    }
    this.edgesIn[toVertex.label].push(fromVertex.label);

    return this;
  }

  get_vertex(label: string): Vertex<T> | null {
    return this.vertices[label] || null;
  }

  get_neighbors_out(label: string): Array<Vertex<T>> {
    const neighborLabels = this.edgesOut[label];
    if (!neighborLabels) return new Array<Vertex<T>>();

    const neighbors = new Array<Vertex<T>>();
    for (const label of neighborLabels) {
      const vertex = this.get_vertex(label);
      if (vertex) neighbors.push(vertex);
    }
    return neighbors;
  }

  get_neighbors_in(label: string): Array<Vertex<T>> {
    const neighborLabels = this.edgesIn[label];
    if (!neighborLabels) return new Array<Vertex<T>>();

    const neighbors = new Array<Vertex<T>>();
    for (const label of neighborLabels) {
      const vertex = this.get_vertex(label);
      if (vertex) neighbors.push(vertex);
    }
    return neighbors;
  }
}

class Sheet {
  public readonly graph: IDirectedGraph<number> = new DirectedGraph<number>();

  constructor() {}

  //  TODO(will): return undefined instead of throwing errors
  get_cell(label: string): number {
    const value = this.graph.get_vertex(label)?.value;
    if (value) {
      return value;
    } else {
      throw new Error("Cell does not exist");
    }
  }

  // for a given vertex, update itself and all downstream vertices
  update_cache(label: string): void {
    // directly downstream vertices
    const downstream = Array.from(this.graph.get_neighbors_out(label));

    for (const vertex of downstream) {
      // get the dependencies of the vertex in question
      const deps = this.graph.get_neighbors_in(vertex.label);

      let sum = 0;
      for (const dep of deps) {
        const vertex = this.graph.get_vertex(dep.label);
        if (!vertex) throw new Error(`Cell ${dep} does not exist`);
        sum += vertex.value;
      }

      // NOTE(will): we're using add_vertex to update, a little ugly but saves us an interface method
      this.graph.add_vertex(vertex.label, sum);

      // we've mutated the vertex, propagate changes downstream
      this.update_cache(vertex.label);
    }
  }

  set_cell(label: string, value: number | string[]): void {
    if (typeof value === "number") {
      // we're a leaf, directly set the value
      this.graph.add_vertex(label, value);
    } else {
      // ...we're a node, add ourselves to the tree

      // NOTE(will) add the veretx to the graph first, then calculate the sum
      this.graph.add_vertex(label, 0);
      let sum = 0;
      for (const dep of value) {
        const vertex = this.graph.get_vertex(dep);
        if (!vertex) throw new Error(`Cell ${dep} does not exist`);
        this.graph.add_edge(dep, label);

        sum += vertex.value;
      }

      // add vertex in question
      // NOTE(will): as long as there aren't cycles, we can use the cached value of our dependencies directly as they don't need to be recalculated
      this.graph.add_vertex(label, sum);
    }

    // we've mutated the vertex, propagate changes downstream
    this.update_cache(label);
  }
}

function assert(something: boolean, message: string): void {
  if (!something) throw new Error(message);
}

const sheet = new Sheet();
sheet.set_cell("A1", 1);
sheet.set_cell("A2", 2);
sheet.set_cell("A3", ["A1", "A2"]);
sheet.set_cell("A1", 3);
assert(sheet.get_cell("A3") === 5, "A3 should be 5");

sheet.set_cell("A4", ["A3", "A1"]);
assert(sheet.get_cell("A4") === 8, "A4 should be 8");

sheet.set_cell("A5", ["A1", "A1"]);
assert(sheet.get_cell("A5") === 6, "A5 should be 6");

sheet.set_cell("A6", ["A5", "A4"]);
assert(sheet.get_cell("A6") === 14, "A6 should be 14");

sheet.set_cell("A1", 1);
assert(sheet.get_cell("A3") === 3, "A3 should be 3");
assert(sheet.get_cell("A4") === 4, "A4 should be 4");
assert(sheet.get_cell("A5") === 2, "A5 should be 2");
assert(sheet.get_cell("A6") === 6, "A6 should be 6");

sheet.set_cell("A7", ["A1", "A1", "A2"]);
assert(sheet.get_cell("A7") === 4, "A7 should be 1 + 1 + 2");
sheet.set_cell("A2", 3);
assert(sheet.get_cell("A7") === 5, "A7 should be 1 + 1 + 3");

console.log("All tests passed 😅");

package.json

{
  "devDependencies": {
    "ts-node": "^10.9.1",
    "typescript": "^5.3.2"
  }
}

SPREADSHEET.md

Fast{er} Spreadsheet

Dependencies

$ npm install -D

Running

$ npx ts-node main.ts
All tests passed!