Homework 6: Implementing a Spreadsheet

This assignment pulls together all of the topics we have done since the midterm.

Thee assignment has two parts: basic functionality and advanced handling. If you are aiming for an A in the course, you must turn in work for both parts. If you want to cap your grade at a B, you may turn in solutions only for part 1. You do not need an A-level grade on this assignment to still get an A in the course. I am merely giving an option to those of you who are struggling to opt into an easier assignment in exchange for a grade cap.

1 Problem Description

This week, we implement a simple spreadsheet. Spreadsheets are made of cells, each of which contains either constant data or a formula that may involve other cells. For example, I could put

The constant 5 in cell a10,
the constant 3 in cell b10, and
the sum of cells a10 and b10 in cell c10.

Whenever someone changes the value of one cell, the values of other cells that reference the edited cell may become invalid. For example, if I edit cell a10 from the above example to contain 9, then cell c10’s new value would be 12.

We looked at spreadsheet formulas when we studied visitors, but we failed to compute values for formulas with cell references. This week, we integrate our previous code for spreadsheet formulas into a spreadsheet class that associates cells with formulas (thus enabling evaluating CellRefs in formulas). Specifically, your spreadsheet class must satisfy the following interface:

interface ISpreadSheet {

void editContents(String cellname, IFormula expr);

Integer lookupValue(String forcell);

}

(where IFormula is provided in the prior code file linked above.) How you associate formulas and values with cells is up to you. Your implementation should, however, satisfy at least the following two test cases (these are not sufficient for the testing component):

  TEST CASE 1
    s.editContents("a10", new Num(5));
    s.editContents("b10", new Num(3));
    s.editContents("c10", new Plus(new CellRef("a10"),
                                   new CellRef("b10")));
    s.lookupValue("c10") should return 8
  -----------------------------------------------
  TEST CASE 1
    s.editContents("a10", new Num(5));
    s.editContents("b10", new Num(3));
    s.editContents("c10", new Plus(new CellRef("a10"),
                                   new CellRef("b10")));
    s.editContents("a10", new Num(9));
    s.lookupValue("c10") should return 12

2 Problems, Part 1

Provide a spreadsheet class that implements ISpreadSheet and satisfies the two test cases given above.
Document your class with Javadoc. You do not need to add Javadocs to the provided IFormula classes.
Provide a good set of tests for your class. You may write your tests in either Tester or JUnit (your preference). You do not need to add tests solely on the provided IFormula classes.

In doing these problems, you may assume that none of the formulas result in cyclic references to the same cell (those doing Part 2 will remove this assumption).

2.1 Grading Criteria

We will be looking for

Whether you correctly compute values of formulas with CellRefs.
Whether your lookupValue function always returns the current value of a cell based on edits to other cells.
Whether you chose reasonable data structures for the problem.
Whether you demonstrate an understanding of how to write test cases for this example.
Whether you provided reasonable documentation

2.2 Hints and Warnings

Do this assignment in stages: first get it working with only Num-style formulas in cells, then go to Plus formulas on Nums, then add CellRefs. You can get more partial credit from having the assignment fully work for at least some formulas.
You could easily make this problem far harder than we are expecting. You do not need to worry about propagating cell edits all over the spreadsheet. You only need to worry about returning the correct answer when someone calls lookupValue. Put differently, if you are imagining a real spreadsheet and its instantaneous updates, assume that all of those updates happened because the GUI called lookupValue.

Don’t overthink this. There are no tricks in this assignment.

3 Problems, Part 2

You must at least attempt these problems to qualify for an A in the course. You may skip them if you want to cap your course grade at a B.

In practice, people do accidentally create cells with cyclic references. They also create cells that end up referencing the same cell multiple times within one formula.

Edit your implementation to
- Throw a RuntimeException if (and only if) asked to lookup the value of a cell that leads to a cyclic reference (as opposed to letting Java crash with a Stack Overflow).
- Evaluate each cell only once as part of looking up the value for any one cell. You do not need to go crazy avoiding duplicate computation across multiple top-level calls to lookupValue. In particular, you do NOT need to optimize your implementation around which cells were edited since the last time a given cell was computed. You may simply assume that an edit to any cell invalidates the values in every cell. Don’t overthink the problem.
Provide a good set of test cases against your handling of cell references.
In a file questions.txt, answer the following questions:
1. Provide an argument that your ValueOf method will terminate in the face of a cyclic cell reference.
2. Was there any advantage to our having used a visitor-organization for the ValueOf method on IFormulas?

3.1 Grading Criteria II

We will be looking for

The criteria from Part 1
Whether you terminate with an exception in the presence of cyclic cell references.
Whether you understand how to argue for termination.
Whether you reuse cell computations within the same top-level call to lookupValue.

4 What to Turn In

As usual, turn in all of your .java files via Turnin.

1	Problem Description
2	Problems, Part 1
3	Problems, Part 2
4	What to Turn In