Homework 6: Implementing a Spreadsheet
Due Wednesday December 16 at noon via InstructAssist. Note that we will accept submissions until noon on Wednesday in light of the final exam being on Tuesday.
This assignment pulls together all of the topics we have done since the midterm. It has points available in all four course themes.
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 will give 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).
As in homework 5, this assignment offers both core and full options. We describe them further down (after we explain the problem).
2 Background: Representing Formulas
We capture formulas through a tree-like collection of classes that implement an IFormula interface. The starter files give 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 a Runtime 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. Your final version should remove throwing this exception.
(Side note on Runtime exceptions: we didn’t discuss these in class. You throw them like any exceptions, but you don’t catch them. Throwing them causes your program to stop. They are used for situations that your program isn’t expected to recover from.)
Update 12/11: We updated the following parts of the starter files: ISpreadsheet.java updated to include the throws statement, Examples.java edited to show the exact form of test cases for this assignment, and EmptyCellException.java added. This zip uses a different name from the original, so you can download the new one without affecting any of your existing files.
3 Problems
Formal definitions of the core and full levels follow the problem descriptions. There are aspects of each of these three subsections in each of core and full.
3.1 Create a Spreadsheet Class and Compute values on CellRefs
Create a class called Spreadsheet which satisfies at least the following interface:
interface ISpreadsheet { |
// associates the given cellname with the given formula |
// such that subsequent references to the cell yield the formula |
void editContents(String cellname, IFormula expr); |
|
// compute the current value of the named cell |
Integer lookupValue(String forcell) |
throws CyclicFormulaException, EmptyCellException; |
} |
(IFormula is provided in the starter file). How you associate formulas and values with cells is up to you (put differently, you choose the data structure).
Update 12/11: We added the EmptyCellException for cases in which lookupValue is called on a cellname that does not have an associated IFormula.
Update 12/11: the above interface was revised to include the throws statement.
Your implementation should support the following two test cases (both are in the Examples class in the starter files and serve as your autograding-consistency check):
boolean testSimplePlusCellRefs(Tester t) { |
try { |
ISpreadsheet s = new Spreadsheet(); |
s.editContents("a10", new Num(5)); |
s.editContents("b10", new Num(3)); |
s.editContents("c10", new Plus(new CellRef("a10"), |
new CellRef("b10"))); |
return t.checkExpect(s.lookupValue("c10"), |
8); |
} catch (CyclicFormulaException e) { |
return t.checkExpect(false, true); |
} catch (EmptyCellException e) { |
return t.checkExpect(false, true); |
} |
} |
|
// test that cell refs grab current value of cells |
boolean testUpdateCellRefs(Tester t) { |
try { |
ISpreadsheet s = new Spreadsheet(); |
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)); |
return t.checkExpect(s.lookupValue("c10"), |
12); |
} catch (CyclicFormulaException e) { |
return t.checkExpect(false, true); |
} catch (EmptyCellException e) { |
return t.checkExpect(false, true); |
} |
} |
Update 12/11: the above tests were revised to include the try/catch statements.
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 in part on how you choose to associate formulas and values with cells. You may modify any aspect of the IFormula classes (Num, Plus, and CellRef) in the starter file to do this (adding fields, changing inputs to methods in the interface, etc) EXCEPT changing arguments to the constructors for the IFormula classes.
Update 12/11: You are welcome to change the IFormula interface however you wish, but it must still be called IFormula. You may add methods, change the inputs to methods, change throws statements, etc.
Hint 1: Much of the challenge here lies in getting the CellRef class to have access to your data structure that associates cell with formulas. This question asks you to think about the various ways that a method (such as valueOf) can get access to another object (your data structure). What are all the ways that a method gets access to objects?
Hint 2: You are allowed to have multiple versions of the same method as long as each version’s inputs or input types differ from the others’. You won’t necessarily need this, but some of you may find this useful depending on how you approached the 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.
Update 12/11: We will go with the former (the original handout let you have the exception thrown in either method, but we realized that giving you the choice would vastly complicate how everyone must write tests for autograding): have lookupValue throw a CyclicFormulaException (whose constructor takes the name of a cell with the cyclic reference) if a cell needs its own value to evaluate its results. Since this program lacks a user-interface component, we will simply catch these exceptions within test cases (as shown in the Examples class starter file).
Hint: A reminder that you can modify any aspect of the IFormula classes except the constructors. For example, you may modify the arguments to methods in the IFormula interface.
Update 12/11: Depending on how you approach this, you may want to know about a LinkedList method called clone() that creates a copy of the list. It returns a list of Object. It makes a fresh list with the same contents (but does not make new copies of the objects in the list). If you were to write
myList = new LinkedList<Integer>(); |
newList = myList.clone(); |
newList.add(5); |
then 5 will NOT end up in myList (it will only be in newList).
3.3 Testing
Provide a good set of test cases for the methods in the ISpreadsheet interface. Do not include tests directly on methods in the provided IFormula classes (in case you or we changed the contents of that interface from the starter file); just submit tests on the methods in the ISpreadsheet interface, as shown in the Examples class in the starter file. The Examples class in the starter file shows you the correct setup for handling exceptions.
We will not test for the name of the cell in the exception, in case you have a formula with multiple cyclic references.
Our tests against your code will only call the Spreadsheet constructor and the two methods from the ISpreadsheet interface (editContents and lookupValue). Your tests should do the same. Again, use the test cases in the starter-file Examples class as a model for your own tests–we show you examples of each of tests that expect exceptions and ones that do not.
Update 12/11: The sample tests in the starter file are now using
t.checkExpect(false, true) |
as the action upon catching an unexpected exception. Please use this form, rather than a checkExpect call with only one argument, as the single-argument form interfered with autograding on hwk5.
Update 12/11: The test case format, and these instructions, are now final.
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 Homework Levels: Core and Full
A full assignment requires all aspects of sections 3.1 through 3.3 (section 3.4 is optional for everyone).
A core assignment requires all of section 3.1 (computing values of formulas with cell references) and testing (section 3.3), including tests of formulas with cyclic cell references. A core solution does not, however, have to handle cyclic cell references in your own lookupValue or editContents methods (as in section 3.2).
In other words, if you submit your work as a core assignment, we will run test cases for non-cyclic computations against your code, but we will not run test cases for cyclic computations against your code. We will, however, check that your test cases (that we run against our good/broken solutions) cover cyclic computations. We want to see that you can think of good cyclic scenarios to test, even if you don’t write the code to actually handle them.
As with hwk 5, submitting only a core solution caps your course grade at a B.
5 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 get your tests in order, 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.
6 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 understand how to argue for termination.
Whether your code is clean and follows good OO practice, including use of access modifiers.
(full) Whether you accurately detect cyclic cell references.
7 What to Turn In
Submit a zip containing all .java files for this assignment.