●   You do not have to produce any code/result for various other things that are

illustrated in, or related to, this lab, such as the AST and ASD classes, or performance tests, etc.

Overview/Concepts

In this lab, you will create a C++ class that can be used to record, and then look up, name/value pairs. Python programmers will know this as a "dictionary"; Java programmers as a "hash map"; the C++ standard library calls it a "map"; some languages call it an "association". But, instead of doing the obvious approach of just using std::map, you will create your own implementation,

using smart pointers to manage memory, so that your project should be roughly as easy to program as a 100-level lab about, for example, hash tables or binary search trees; you just need to use C++ notation and select the appropriate kind of smart pointer.

Our tests include cases in which we want to put a set of things into the dictionary and then, later, revert to what we had before. This is similar to allowing an "undo" feature in a user-facing application or processing variable names in a programming language. (Programming languages use the dictionary data structure to implement a "symbol table", which associates variable names ("symbols") with other information, such as the variable's value, memory location, type, or several of those; then, as the system processes, e.g., a function, it records all the local symbols in that function, processes the function and then gets rid of all those local variables, all at once).

We do not require any other "remove" operation for our dictionary class. This is a good thing,  because "remove" is generally thought to be harder (or, a lot harder) than other operations for most dictionary data structures.

Fortunately, reverting to an earlier value turns out to be trivially easy in the pure-functional paradigm, since the central point of that paradigm is that we don 't change object values, or the   relationship of variables to objects. So, we just go back to using a previous variable, and we'll automatically have the old value, without needing a "revert" or "checkpoint" method in the class.

Checkpoint and revert are a bit more challenging in the imperative paradigm, but note that you don't have to worry about the efficiency of checkpoint/revert in this lab. Thus, you can implement these by just doing a hopefully familiar (though resource-intensive) deep-copy operation to make the checkpoint data, and, possibly, a deep-copy again to revert. But, you need to do this in a framework that would allow a later update with a more efficient approach: The user of the class dictionary will call methods "checkpoint" and "revert", rather than calling deep-copy   directly, so that we could change the implementation later so that revert that just efficiently removes the few things that have been added since the last checkpoint, rather than a full   deep-copy.

This lab will use the starter files in the Dictionary project.

Choices (record in README-info.txt)

You may choose the data structure you want to implement, and the paradigm you want to use, form the following list:

1. binary search tree, using the imperative paradigm (in which d.insert(name, number) changes the dictionary object d, so that name is now associated with the number when we do a lookup)

2. binary search tree, using the pure functional paradigm (in which d.add(name,

number), and all other operations on binary search trees, does not change the dictionary d; instead, it returns a new dictionary that is just like d, but has "name" associated with    "number"

3. a hash table, using the imperative paradigm (d.insert functions as described under the above "imperative BST" option), but, to demonstrate smart pointers, each "bucket" in

your hash table should have a linked list that you construct, i.e. use the approach that Wikipedia calls "separate chaining", and sometimes called "external chaining" or sometimes "closed addressing").

4.  A skip-list, using the imperative paradigm.

5.  A skip-list, using the pure functional paradigm.

6.   if you want to do something else, talk to your professor about it; we could discuss a

simpler structure, for partial credit if you're worried about BST's and externally chained hash tables; or, you could consider trying something more ambitious, such as a red-black tree, AVL tree, 2-3 or 2-3-4 tree, etc., if you don't have much work in other   courses in the coming week. But, you can only attempt a different structure if you get permission first (we had imagined this would only be relevant in future offerings of the course, but list it here just in case). Note that you can always take on some of those "not required" elements if you finish early.

Though the degree of difficulty will depend a lot on what techniques and data structures you're familiar with; for a programmer who is comfortable with both approaches, probably the pure-functional BST is the easiest, though the imperative BST isn't far behind, if you find it easy to write "deep copy" algorithms and don't care about performance of the checkpoint/revert operations.

Once you've chosen a data structure and paradigm, choose the appropriate kind of smart pointer; as we saw with the lecture AST and ASD examples, each of the options only works out well with the right kind of smart pointer; if you're not sure, talk to your instructor or T.A. or post to Piazza … we'd be happy to have a general discussion of this.

You should also choose whatever non-C++ references you want for understanding/reviewing your data type, e.g., you can use a Java or Python book that has runnable code for, e.g., a Binary Search Tree. You can even copy-paste that code, as long as you're not starting with C++ (or C). But, you must record any references you use, as noted below. You can update this list  as you work, though, you don't have to pick them all in advance.

○   You won't need an explicit way to checkpoint/revert, since that's only needed if objects can change.

●   You are encouraged to write your own tests, and test each function as you write it; you   can start with our sample program, temporarily commenting out parts you've not run yet (e.g., comment out all the "checkpoint and revert" lines until you get that part written).

● Your dictionary class must appropriately use C++ smart pointers to allow some sort of

variable-size linked structure (as noted under "options"), without any memory errors such as following an uninitialized or dangling pointer, or producing garbage, for both your tests, our starter file tests, and the actual tests we'll use for grading.

Copy Constructors, "box and arrow" diagrams and deep-copy

In the imperative paradigm, we generally need to write a "copy constructor", e.g. something to handle a line like

Dictionary d2 = d1;

which would use a "copy constructor", e.g., Dictionary::Dictionary(const Dictionary &). In the imperative paradigm (e.g.,, if you have an "insert" method that changes a node in a BST), this would be a "deep-copy", which you may recall from CMSC 106/151/107 (ask a T.A. or professor  for help, if not). If you're using the pure-functional paradigm, you don 't need to write a deep-copy operation; in this case, the default mechanisms of C++ will typically work fine without you writing a copy-constructor at all.

Optionally, read the details below, if you want to know why.

In C++, the meaning of that "Dictionary d2 = d1;" line is that d2 should be a "separate object" from d1, so that changes to d1 don't affect d2, and vice-versa. We normally diagram this by drawing d1 and d2 as completely separate objects, each next to the corresponding name, i.e., without sharing any parts.

But, note that our data structure is allowed to implement this behavior in any of a variety of ways, as long as the program always produces the result we would get if d1 and d2 didn 't share any parts. So, for example, if d1 and d2 are implemented as BST's, this should happen automatically if we put in a new element using the pure-functional equivalent of "insert", which we're calling "add":

Dictionary d1_with a cat = d1.add("cat", "10000");

If this follows the rules of the pure-functional approach, d1 won't change at all. So, if d1 and d2 both have pointers to the same root node, or each has a root node but the two root have pointers to the same left subtree, and both have pointers to the same right subtree, everything is o.k. … d1_with a cat will need to have a separate root node, and a separate left subtree

(assuming "cat" goes on the left), but d2, d1, and d1_with a cat can all share the same right subtree object, since they'll all have the same results if we look for "wombat" (as an example of something that would hopefully be in the right subtree somewhere).

Other C++ details/issues

Note: DO NOT cast pointers in C++!

There are many times a C programmer will need to convert one kind of pointer into another, e.g.,

int *p = (int *) malloc(12*sizeof(int));  // malloc gives "void *", but we now we have space for "int"

BUT, you should not have to do this in your C++ code. If you do, you'll be stepping outside of the rules of shared pointers, and your code won't work (maybe crash, maybe fail valgrind,

maybe fail only on our extended tests but not the basic examples from the starter files). So, don't.

Returning "this" as a shared_ptr

If you are using shared_ptr to point to, say, a tree node, and happen to want a function that

returns "this", you'll probably get an error that says something along the lines of "no viable

conversion from AST_Node* to shared_ptr". This problem occurs because "this" is a regular pointer, not a shared_ptr.

Probably the easiest way to deal with this is not to have a member function that returns "this", but instead to just write a regular function with a shared_ptr parameter, and then use that. If you really really want to know how to return "this" as a shared pointer, ask J.D. or Dave to help you   work through this description.

Traversing a tree that's linked together via unique pointers

If we were using regular pointers, we would be free to traverse from the root of a tree to any leaf in a variety of ways. Consider the example from the Example PDF, and assume we also choose to have a class "Tree" as well as that "AST_Node" class. We would be free to either

a.   Write a loop in a method of class Tree, like the following (assuming we let it get to the "left" and "right" children of the node):

void Tree::print_left_children ( ) {  // just an example, code not tested

AST_Node *where = this->root;