Homework 6: Implementing a Spreadsheet

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

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.

This spreadsheet would have show value 8 in cell c10. Whenever someone changes the value of one cell, the values of cells that reference the edited cell may change. 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).

2 Exercises

1. Create a spreadsheet class which satisfies at least 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 2

   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. Formulas with cyclic cell references cannot result in values under lookupValue. A naive spreadsheet would let lookupValue go into an infinite loop when asked to compute a formula with a cyclic cell reference. A smarter spreadsheet will handle such formulas gracefully.

   Two particular options would be:

   • Have lookupValue throw an exception if asked to compute the value of a cyclic formula.

   • Have editContents throw an exception if someone enters a cyclic formula.

   Choose and implement whichever of these two approaches you deem better. Since this program lacks a user-interface component, you may handle either exception by printing a warning string to the screen and returning null from the corresponding method.

3. 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 previously-computed values in every cell. Don’t overthink the problem.

4. Provide a good set of test cases for your spreadsheet class. You may write your tests in either Tester or JUnit (your preference). You do not need to include tests solely on methods in the provided IFormula classes.

5. In a file questions.txt, provide prose responses to the following:

   1. Justify your choice of approach to handling cyclic cell references (in a sentence or two).

   2. Provide an argument that your ValueOf method will terminate in the face of a cyclic cell reference.

   3. Was there any advantage to our having used a visitor-organization for the ValueOf method on IFormulas?

2.1 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, then handle cyclic references. You will earn more points for code that properly handles only some formulas than for code that has partial but incomplete solutions for all 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 on every cell.

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

3 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 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.

• Whether your code is clean and follows good OO practice.

4 What to Turn In

As usual, turn in all of your .java files as well as your questions.txt file.