Updater

1 Introduction

Imagine you have an n-ary tree which you wish to modify. For instance, the tree might represent the HTML of a Web page which you intend to change dynamically.

The simplest way to update the tree would be to copy it, incorporating the change while copying. Copying, however, takes time and space proportional to the size of the tree. If we wish to make several edits that are within close proximity of each other, perhaps we can devise a representation with lower complexity. Furthermore, we might wish to make these edits atomically, i.e., so the client sees only the result of all the edits and not the intermediate stages.

2 The Assignment

We can therefore consider representing trees in terms of a cursor, which reflects the locus around which we wish to modify the tree:

A cursor represents an edge (shown in red) and has two parts: a representation of the (possibly empty) tree below that edge (shown in blue), and the (possibly empty) rest of the tree around that edge (shown in grey). The simplest representation of the part below is the subtree itself, but we have some choices in how we represent the rest of the tree, depending on which operations we wish to support.

We will represent a tree as follows:

data Tree:
| mt
| node(value :: Any, children :: List<Tree>)
end

We wish to support the following operations:

find-cursor(tree :: Tree, pred :: (Any -> Bool)) -> Cursor

This constructs a cursor by finding a point in a tree. The cursor represents the edge above the first node with a value for which the predicate produces true. We will assume that the search proceeds depth-first, so the cursor represents the edge above the leftmost node matching the predicate, and if there are multiple such nodes, it represents the edge above the topmost one. (Also, think about your representation for a Cursor when no node matches the predicate given to find-cursor.)

Given a cursor, we can update the sub-tree at the bottom of the edge that it represents in constant time:

update(c :: Cursor, func :: (Tree -> Tree)) -> Cursor

Note that because we have an explicit representation for an empty node, this operation can be used to insert, change, or delete a subtree. You would be wise to cover these operations in your test cases.

Once we are done performing updates, we can convert a cursor back into a tree:

to-tree(c :: Cursor) -> Tree

In the output from to-tree , mt will only be used to represent a completely empty tree (no nodes), so the tree you return shouldn’t contain any mt nodes, unless the tree is empty. Inside your cursor, however, you may use mt inside your cursor however you’d like: for example, if update is used to delete a subtree.

In addition, we can navigate around a cursor:

left(c :: Cursor) -> Cursor
right(c :: Cursor) -> Cursor
up(c :: Cursor) -> Cursor
down(c :: Cursor, child-index :: Number) -> Cursor

The down function takes a numeric argument to indicate which child to select (with the index starting at 0).

Note that any of these operations might fail dynamically if the cursor is at the appropriate boundary. For instance, left and right should only be able to move between edges that share a common parent. If an invalid move occurs, signal an error. You can use raise to do this [documentation]. To test for error cases, uses raises [documentation].

Critically, we want to make these four “motion” operations efficient: constant time or as close to it as possible. Can you design a data structure that achieves this? What is the complexity of the above operations that result from your representation choice? There’s an open response question about this at the end of the page; make sure you answer it by the deadline along with your program.

2.1 Analysis

Describe the run-time (big-O) complexity of each of the operations in your implementation: namely left, right, up, down, update, and to-tree. Please write your analysis where we give you space to do so in Captain-Teach.

https://www.captain-teach.org/brown-cs019/

3 Template Files

Initial Tests

Implementation Code

Final Tests

Note: Implementation-dependent testing should be in the implementation file. The final tests file should contain your tests for the procedures we had you implement.

4 Handing In

Note that there are additional instructions for handing in your initial tests above.

To submit your implementation, return to the Captain Teach assignments page:

https://www.captain-teach.org/brown-cs019/assignments/

and click “Next Step” again. This time, save and then upload a zip file of both updater-tests.arr and updater-code.arr. You can include as many tests as you want (beyond 10) for this final submission, and you can include tests you saw while reviewing (but copy with care!—and please do attribute the ones you copied to to peer-reviewing, even though you won’t be able to name the author).

After you submit your implementation, you’ll have one further step to complete. We want you to answer a quick two-question survey about what (if any) impact the peer review process had on your final submission. The interface will look similar to the review interface, and once you submit your answers to the two questions there, you’re done. This feedback will have no effect on your grade—we’re interested in hearing about your experience with the review process.