Homework 6: Implementing a Spreadsheet
Due Tuesday April 28 at 11:59 pm via Turnin. myWPI questionnaire due 45 minutes later (closing at 12:45am). Once you access the questionnaire, you will have only 30 minutes to submit your answers.
This assignment pulls together all of the topics we have done since the midterm. We will weight the testing scores on this assignment heavier in final testing grades, to allow you to make up testing points here.
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.
Implementing a spreadsheet requires a class for spreadsheets and a way to capture the formulas inside of cells. We have given you most of what you need to capture formulas. In this assignment, you will provide the spreadsheet class and make a key modification to the formula classes (described in the rest of this document).
2 Background: Representing Formulas
We capture formulas through a tree-like collection of classes that implement an IFormula interface. The starter file gives you most of the code for capturing formulas. There is a Num class for simple numeric formulas, a Plus class for sums of formulas, and a CellRef class for capturing references to other cells. The following examples create formulas for "5 + 8" and "5 + a10" (where a10 is a reference to another cell):
IFormula f1 = new Plus(new Num(5), new Num(8)); |
IFormula f2 = new Plus(new Num(5), new CellRef("a10")) |
Note that for simplicity, we are using a single string for a cell name, rather than a string for the column name ("a") and a separate number for the row (10). While separating the row from the column would be more realistic, the single string is simpler while still supporting the goals for this assignment.
The IFormula interface also specifies two methods:
valueOf computes the value of a formula. For example, f1.valueOf() would return 13.
noRefs returns a boolean indicating whether the formula contains any cell references. For example, f1.noRefs() is true and f2.noRefs() is false (because of the reference to "a10").
The Examples class in the starter file provides simple examples of creating formulas and using these two methods.
The starter file is incomplete, in that it currently throws an exception when asked to compute the value of a formula that contains a cell reference. As part of your work on this assignment (described in detail below), you will modify valueOf in the CellRef class to correctly compute the value of formulas with cell references.
3 Exercises
3.1 Create a Spreadsheet Class and Compute values on CellRefs
Create a spreadsheet class which satisfies at least the following interface:
interface ISpreadSheet { |
void editContents(String cellname, IFormula expr); |
Integer lookupValue(String forcell); |
} |
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 |
To get these tests to work, you will have to edit valueOf in the CellRef class to extract formulas from cells and compute their values. How you do this depends on how you choose to associate formulas and values with cells. You may modify any aspect of the IFormula starter file to do this (adding fields, changing inputs to methods in the interface, etc). There are a couple of different viable approaches to this problem.
3.2 Handle Cyclic Cell References
A cell has a cyclic cell reference if it needs its own value to compute its own value. The simplest example would be storing the formula CellRef("a10") in cell "a10". Cyclic cell references cannot be evaluated to numeric answers under lookupValue. A naive spreadsheet would let lookupValue go into an infinite loop when asked for the value of 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.
Documentation: in comments on the valueOf method on the CellRef class, provide an argument that ValueOf will terminate in the face of a cyclic cell reference.}
3.3 Testing
Provide a good set of test cases for the methods in the ISpreadsheet interface. In particular, you should test that lookupValue returns the correct answer before and after a cell gets edited. You do not need to include tests solely on methods in the provided IFormula classes. Remove the Examples class from the IFormula starter file, replacing it with your own Examples class for the spreadsheet.
3.4 Optional Challenge
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.
4 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.
5 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 problem.
Whether you accurately detect cyclic cell references.
Whether you understand how to argue for termination.
Whether your code is clean and follows good OO practice.
6 What to Turn In
Submit your .java files (either as separate files or as a single zip), including your modified IFormula.java file.