Assignment 8: CS106XCell

Unit Testing

For both the model and expression classes, we have included a unit testing file containing some starting tests. These files are CS106XCellModelTests.cpp and ExpressionTests.cpp. You can run these unit tests by running the main program and selecting the tests you want to run on the launch popup.

For the expression class, you should add at least 6 additional tests for the functionality that you implement. For the model class, you should add at least 6 additional tests for the functionality that you implement. Make sure that your unit tests test as small, isolated components of your code as possible. Make sure to give each test a detailed name, and comment above it explaining what it is testing.

Also remember to turn in debugging.txt, explaining a bug you encountered, how you identified it, and how you fixed it. You can find this file in the res/ folder of the starter project.

Range Expressions

Your first task is to read through the provided Expression class to understand its behavior, inheritance hierarchy, and implementation. Here is an overview of the public functionality for every Expression:

The expression objects are organized into a binary tree such as the following one for the formula, "=A1/2+7.5*SUM(B3:B7)" . Notice that expressions have operator precedence, so that the + operation is at a higher level in the tree than the * and / operations. However, our provided parser takes care of this.

CompoundExp: operator="+"
|
+-- left=CompoundExp: operator="/"
|         |
|         +-- left=IdentifierExp: name="A1"
|         |
|         +-- right=DoubleExp: value=2.0
|
+-- right=CompoundExp: operator="*"
          |
          +-- left=DoubleExp: value=7.5
          |
          +-- right=RangeExp: function="SUM", range=B3:B7

The expressions are thus represented as an inheritance hierarchy of classes that extend Expression to add various specific behavior for each kind of expression such as compound, text string, and so forth. For instance, the Compound Expression type provides getters for the left and right subexpressions. We won't document all the functions here, but you should familiarize yourself with the different functionality available for each expression type, and how it is implemented. This will come in handy for implementing the new Range Expression type, described below.

Some parts of your code on this assignment will need to use getType to figure out what type of expression you are using so that you can utilize the unique features of that expression:

Expression* exp = ...;   // get a pointer to an expression object
if (exp->getType() == COMPOUND) {
    const Expression* left = ((const CompoundExp *)expr)->getLeft();
    const Expression* right = ((const CompoundExp *)expr)->getRight();
    ...
} else if (exp->getType() == RANGE) {
    CellRange range = ((RangeExp *)expr)->getRange();
    ...
} else {
...

Note that for the left and right subexpressions, getLeft and getRight return const pointers to expressions (so that no-one modifies them). For this reason, you may have to cast using const, as shown above.

Implementing RangeExp

Once you familiarize yourself with the existing Expression hierarchy, you should add a new expression type, called RangeExp, to this existing hierarchy. We don't provide any boilerplate code for this class - you should create and add it to Expression.h/.cpp. This type represents functions applied to a range of cells - for example, "AVERAGE(A1:A5)" specifies that a cell should contain the calculations of the average value of cells A1, A2, A3, A4 and A5. Specifically, a range represents a set of cells between a start and end cell inclusively. Ranges are specified in START:END format indicating the start/end cells, inclusive, such as A1:A6 or B4:H4. A range can span just one row or column or enclose a two-dimensional rectangular block of cells. Thus, ranges like A1:A4, C5:C5, A4:D4, and B2:D6 are valid. One thing to note is that a valid range is required to be non-empty, which means the end cell must be at position greater than or equal to the row and column of the start cell.

Your class will need to provide implementations of existing Expression methods described above, and also add its own unique behavior. Here is the behavior you should implement:

• Constructor: a RangeExp should be able to be created by specifying the name of the function to apply (such as "AVERAGE", "MIN", etc.) as a string, and the range of cells over which to apply this function as a CellRange object. The function name and the cell range should be able to be provided in any case (upper, lower, mixed, etc.).
• a RangeExp is always a formula
• the type of a RangeExp is RANGE (a provided constant)
• a RangeExp's toString() method should return a string representation of the expression in the format "FUNCTION(RANGE)" (e.g. "AVERAGE(B1:B6)").
• it should have a public method getFunction() that returns the value of its function name, in all uppercase.
• it should have a public method getRange() that returns the value of its cell range
• All other behavior should be identical to a regular Expression

We leave the remainder of the class design, such as what private members it will have, up to you.

The CellRange class, which you will need to use in your implementation, contains the following public members:

Finishing Up

Our ExpressionParser class (which you will use in later steps) already contains code to parse out Range Expressions that you can activate when you are done implementing the class behavior above. To do this, in Expression.h, change the line at the top #define RANGE_IMPLEMENTED false to #define RANGE_IMPLEMENTED true. Until you do this, the parser will treat range expressions as unknown expressions and throw an error. Note that you must implement the constructor exactly as specified above, with the first parameter being the function name (string), and the second parameter being the cell range (CellRange). You should not need to modify ExpressionParser.

Once you finish this part of the assignment, try writing tests in ExpressionTests.cpp to test your implementation. You should ensure your implementation is correct before moving on.

Expression Evaluation

Your next task is to implement the eval() method on each of the types of expressions, both the provided ones and your new RangeExp type. This method calculates the numeric value for the expression it is called on, stores it as its value (using setValue()) so that you can retrieve the value later using getValue() without recalculating it, and returns the calculated value. Note that setValue(value) is a private method in Expression (if you're interested, you are able to use it within eval because all Expression subclasses are friends of the base class, though you don't need to worry about this). You need to write the logic to walk the expression binary tree to calculate its resulting value. Note that this is an inherently recursive process, because expressions can contain other sub-expressions as children. In particular, compound expressions represent a binary operation such as "=A2+SUM(B1:B7)". In the case of this example, the left child would be an identifier expression representing A2 and the right child would be a range expression representing SUM(B1:B7).

Because expression evaluation may depend on the value of other cells in the spreadsheet, eval() takes one parameter, which is a map containing cell names (keys) and their calculated values (values) currently in the spreadsheet. The cell names will be in all uppercase, and if a cell is not included in the map it is assumed to have value 0. Note that formulas should be case insensitive. The string "a1" should be equivalent to "A1", and "=sum(a4:BcF17)" should be equivalent to "=SUM(A4:BCF17)".

The default implementation of eval for each included expression just returns 0.0 until you modify the code to properly evaluate the expression. Here is how to evaluate each type of expression:

Once you finish this part of the assignment, try writing tests in ExpressionTests.cpp to test your implementation. Remember to both return the calculated value and store it in the expression itself using setValue. You should ensure your implementation is correct before moving on.

The Model

Next up, we are going to implement CS106XCellModel, the class that stores information for each cell, including its expression and dependencies. It relies on the Expression classes you have implemented already to store the expressions, and graph algorithms to relate them. Note that you must store all cell data in this class using a single instance of the BasicGraph library collection class. You should not declare any other collections as member variables in your class; all spreadsheet/cell data must be stored in the BasicGraph. See further down the page for more information about the graph data structure.

In your graph, each vertex represents a cell that stores a value. (Cells whose values have not yet been set, or whose values are empty, need not be represented in the graph.) An edge from vertex A → B implies that the value of cell B depends on the value of cell A. For example, the following is a diagram of the appropriate graph state to represent the contents of provided input file simple.xcell. Note that the graph is not necessarily connected; vertexes A1 and B3 have no inbound or outbound edges.

	A1 Testing
	A2 10
	A3 =A2+1
	B1 =A3*2
	B2 =A2+A3+B1
	B3 =1+2-3+4*5/6

graph of contents of simple.xcell

Your implementation must have the following public members listed in the table below. Of course you can and should add extra "helper" functions as needed to help you implement the behavior properly and to decompose it into readable chunks of code. Any member functions you add, along with all private member variables, must be declared private, and const as appropriate.

string rawText = "=A1/2+7.5*SUM(B3:B7)";
Expression* exp = ExpressionParser::parseExpression(rawText);
...

One important part of the model is that it must update the rest of the program whenever the contents of a cell change. The way the model can do this is by calling the notifyObservers(cellname) function and passing in as a parameter the (uppercased) name of the cell whose content updated. For example, if the model just updated the contents of cell A2, then you would want to do something like notifyObservers("A2");. This sends out an "alert" in the program that a cell's contents have changed. The controller will be listening for these alerts, and will re-display that cell in the view when it receives one. Make sure to take this extra step when you are clearing cells, updating cells, or updating dependent cells, or else nothing will display in the view.

Graph Data Structure

In this case, unlike with a regular BasicGraph that we have already seen, we also want to store cell data (the Expression object for that cell) inside each vertex of the graph. Associating data with each vertex will be useful when implementing various cell and spreadsheet algorithms. BasicGraph supports this; to store auxiliary data inside each Vertex, you should declare your graph in a different way than what we have seen in class.

// graph with a pointer to an Expression structure stored as data in each vertex
BasicGraphV<Expression*> cellGraph;

If you declare your graph this way, the vertex structure for each vertex in the graph is now called VertexV and will now require a template parameter of Expression* whenever it is used. Similarly, each edge in the graph is now called EdgeV and will also now require a template parameter of Expression* whenever it is used. In return for the bulkier syntax, each vertex structure will contain a useful member variable of type Expression* named data, whose value is initially nullptr until you change it for a given vertex. To access this member, you can write code such as the following:

// accessing a single vertex and its associated expression data
VertexV<Expression*>* v = cellGraph.getVertex("V47");
if (v->data != nullptr) {
    ...
}

Similarly, to access the neighbors of a given vertex, you would write the following:

// accessing all neighbors of a vertex
// (all other vertexes Vi such that there is an edge V47 -> Vi)
for (VertexV<Expression*>* neighbor : cellGraph.getNeighbors("V47")) {
    Expression* exp = neighbor->data;
    ...
}

File Format

The files you must read into your spreadsheet store cell data in the following format. Each line contains the data for a single cell. A line contains a cell name such as "A4", a single space, and then the cell's raw text/formula. For example, the following is the text of input file simple.xcell:

A1 Testing
A2 10
A3 =A2+1
B1 =A3*2
B2 =A2+A3+B1
B3 =1+2-3+4*5/6

If your program loaded this file, the spreadsheet would display the following data:

screenshot of CS106XCell program displaying simple.xcell

Your program should be able to properly load data from files case-insensitively, even if cell names or formulas are not in uppercase.

Note that if you try to open a spreadsheet such as simple.xcell or myspreadsheet.xcell, Qt Creator will display it in a "hex editor" that is meant for editing binary files. This is not an ideal view for looking at our spreadsheet files, which are stored as plain text. To view the file properly, you can either temporarily change the extension to .txt or use another text editing program such as Notepad, TextEdit, or Sublime Text, among others.

Due to various calculations, it may take a few seconds to load a file from disk; this is ok.

Dependencies

One of your greatest challenges is dealing with cell formulas and dependencies. The trickiness comes from the fact that changing a value in one cell may start a chain reaction of updates. A cell that refers to another cell in its formula is said to be dependent on that cell. If the value in a cell is changed, the cells that depend on it also must be updated. Dependencies can either be direct (where a cell has an explicit reference to another in its formula), or indirect (where a cell has a chain of references that eventually lead to that cell). Consider the following spreadsheet data, which comes from provided input file example1.xcell:

A1 42
B1 =A1*2
C1 =B1+5
D1 =C1/B1
E1 =SUM(C1:D1)
F1 =G1+1
G1 7
H1 19

In this data, B1 directly depends on A1, C1 directly depends on B1, D1 directly depends on B1 and C1, and E1 directly depends on C1 and D1, and F1 directly depends on G1. Both C1 and D1 indirectly depend on A1 (through B1), and E1 indirectly depends on A1 and B1. You can visualize the dependencies as a directed graph, as shown below:

graph of dependencies from example1.xcell data

In this graph, the edges trace the direction of outgoing dependencies. The same edges in reverse show the incoming dependencies. For example, when A1 changes, it needs to propagate an update to B1 because the formula for B1 directly references A1. Indirect dependencies are those cells connected through a longer path. D1 indirectly depends on A1, since it relies on B1, which in turn relies on A1. This indirect dependency is represented as a path of edges from A1 to D1.

When the value of a cell is updated, you must update all cells that depend on it, either directly or indirectly. Looking at the outbound edges touching A1, you can see that changing the value in A1 will require four other cells to be updated. Changing F1, on the other hand, requires no changes to any other cells, since it has no cells that depend on it. The cell G1 also has nothing that depends on it, and it is not affected by changes to any other cells.

Traversing the dependent cells sounds suspiciously like depth or breadth-first traversal of the graph. However, a version like this might update some cells multiple times because there is more than one path between them (consider how D1 could be updated twice when traversing from A1). For that reason, you must use topological sort to efficiently order the cell updates so that each dependent cell is updated at most once, only after its dependents have been updated. Even with this topological ordering, however, you should be sure to still only re-calculate cells that need to be updated when a given cell changes.

Before assigning a new formula to a cell, you should ensure it will not create a cycle (also called a circular reference or circular dependency in this context). For example, what if the user tried to set A1 =A1? To calculate the value of A1, you need the value of A1, but you don't know what it is because you're still trying to calculate it! This kind of dependency is called a circular reference, and is bad news in a spreadsheet. Similarly, if the formula for B2 were =SUM(A2:E2), that range contains B2 itself, so this is a circular reference.

You can examine the neighbors (what depends on it) of a given vertex by using the graph's getNeighbors member function. In some situations in this program, you may find that you want to loop over neighbors or edges the opposite way, from a cell A to every other cell B that it depends on. To do so, use the graph's getInverseNeighbors or getInverseEdgeSet member functions, which let you access nodes with an edge to this node, or the edges themselves, respectively. See the library documentation for more information.

Breaking It Down

This is the most difficult part of this assignment, and for this reason we highly encourage you to break it down into steps. One recommended approach could be the following:

• Familiarize yourself with the starter code. Look at the various .h files to understand what functions are available. Hopefully you won't need to look at the provided .cpp files since you generally shouldn't need to know the implementation details if our documentation and comments are detailed enough.
• Build a basic graph. Create your BasicGraph of cell vertex data. When the user sets cell values, parse the raw text into an Expression object and store this in each vertex. Print your graph to the console to see its state. Don't worry about files or dependencies just yet.
• Handle saving and loading of simple files. You don't need to save/load formulas with dependencies yet, but get the basic logic working to read the data from the lines of a file and add it to your graph. We provide an input file named noformulas.xcell that contains cells with just basic text and numbers without any formulas or dependencies; test with that first.
• Handle dependencies in the graph structure. Finish your setCell implementation to handle dependencies between cells and updates to existing cells' values.

Writing unit tests to verify your functionality as you go is a crucial way to ensure your implementation works correctly.

FAQ

Q: What does this error mean when I am trying to evaluate expressions?

'this' argument has type 'const Expression', but function is not marked const

A: This can occur when you are trying to access the left/right members of a Compound expression using the getLeft and getRight member functions, rather than directly by referring to the private member variables lhs and rhs. Try doing the latter.

Q: Does calling removeVertex free the memory for the Expression* that is stored inside the vertex as its 'data'? Is it safe to assume that the destructor for VertexV takes care of all memory inside of it?

A: No, the vertex does not free this memory by itself. You must free it. This is because VertexV<T> can accept any type for T, even non-pointers. So the code for VertexV can't say 'delete' because its data may not really be a pointer.

Q: Does our output file need to match the expected one exactly, including line order? For example, if a column has at least 10 lines, my code outputs the lines for the cells in order A1, A10, A11, A2, etc., because that is what C++ considers to be alphabetical order. Is this acceptable for the output file?

A: Yes; the order of the cells in the file does not have to be strictly alphabetical.

Q: If I set a cell to "=A1+A1000", should I throw an error, because A1000 is not in the spreadsheet? The demo does not throw an error, and appears to treat A1000 as a valid, but uninitialized cell.

A: If a formula refers to a cell that is off the spreadsheet by being too far right/down, such as A1000, you should allow it. The cell will be blank and will have a value of 0.