Homework 6: Implementing a Spreadsheet

This assignment pulls together all of the topics we have done since the midterm. It offers a couple of choices in how hard you make the assignment, with harder choices worth more points, as described below.

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 Choose Your Challenge Level

In class, we looked at two versions of spreadsheet formulas: one used visitors and one did not. For this assignment, you will use one of them, your choice. The visitor version earns points towards outcomes related to visitors and passing methods as arguments, but it is conceptually harder.

If you are struggling in the course, you are better off working with the non-visitor version of formulas. The time you would spend understanding the visitors part could be better spent earning solid points on the rest of the assignment.

Starter files: formulas without visitors or formulas with visitors

3 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. Provide a good set of test cases for your spreadsheet class. In particular, you should test that lookupValue returns the correct answer before and after a cell gets edited. 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.

4. Bit challenging (decide whether to complete): Evaluate each cell only once as part of looking up the value for any one cell. For example, given the formula "Plus(c10,c10)", compute the value for c10 only once and reuse the previously-computed value at the second reference.

   Don’t 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.

   While this is a good exercise, it again may be a lot for those of you who are struggling in the course. Finish everything else, and attempt this only if you have time and energy. This will earn skills points towards the low-weight "avoid repeated computation" (only tested here) outcome and some points towards choosing data structures.

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 (or would there have been, if you worked without visitors) any advantage to our having used a visitor-organization for the ValueOf method on IFormulas?

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

4 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 (if you do this part).

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

5 What to Turn In

Assemble your code into a Java package for this assignment. Submit all of your .java files as well as your questions.txt file.