CS 70

TreeStringSet Constructors

The TreeStringSet class and its iterator are highly connected to each other, and over the course of this assignment you’ll be implementing pieces of each in tandem.

In this phase of development, you'll get to a point where you can make trivial trees (empty ones!) and test them.

Development Process

We'll follow the same kind of development process we used in the previous assignment. Specifically, we've broken the task up into phases, and for each phase that you implement, you will use the same four steps as last week:

1. Plan

By drawing pictures and making notes, you will sketch out what you want to do. Your notes/picture should take into account any edge cases that you will need to consider.

You will submit your planning to us by uploading a picture, which we will check for completeness. We will not grade the correctness of your planning.

You should complete this step in the way that is most beneficial to you for understanding what you’re being asked to implement.

2. Write Tests

After you plan, but before you start writing any code, you will add new test code to the appropriate section of the treestringset-test.cpp file.

Your tests should be designed to investigate whether the implementation is working properly by checking your actual results against expected results. You should specifically test any edge cases that you identified in planning.

We will run your tests against both working and broken implementations of TreeStringSet, and you will be graded for both completeness (your coverage of cases) and for correctness (do your tests check the things that they say they’re checking?).

Because other people need to be able to read your tests and understand what they are doing, make sure you write clear code and also provide suitable comments.

3. Implement

Once you’re satisfied with your planning and test writing, you will implement the function(s) for the step you’re on.

As for all coding parts in CS 70, we will grade your implementation for completeness, correctness, style, elegance, and clarity.

4. Test & Fix

After your implementation is written, you should run your tests to see if your code has any bugs. If your implementation doesn’t pass your tests, you should ask yourself whether the problem is with your implementation (i.e., is your TreeStringSet not doing what it’s supposed to be doing) or with your tests (e.g., do your tests make incorrect assumptions or break the rules?)

Fixing problems may require changes to more than one of these steps—your planning, your tests, and/or your implementation. You don’t need to upload revised versions of your planning document, but you should correct your tests and implementation as needed.

We won’t directly grade your verification work, but this step will help you make sure that your “writing tests” and “implementation” submissions are of high quality.

There's also one more “unofficial” step…

Consider Adding More Tests

Now that you've written and tested your code, do you have more ideas for ways it could have gone wrong or conditions that should be verified? Did you cause and catch bugs along the way that your tests wouldn't have caught? Can you add a test to your test suite that would reveal this bug?

Improving the quality of your tests might even catch more bugs in your implementation!

Let's Go!

  • RHS Cow speaking

    Don't forget to look over the Helpful Hints before you get started!

Your Task, Part 1: Planning

At this point, you need to think about the private data for your TreeStringSet class. Specifically, make sure you understand:

  • What private data members the TreeStringSet class will need to have in order to implement the required functionality.
  • What data members the Node struct will need to have in order to represent a node in the binary search tree.

These details are all covered in the TreeStringSet Specification. Remember that an empty tree has no nodes at all; the pointer to the root node should be nullptr in that case.

Your implementation of clear() will need to use a helper function to recursively destroy and deallocate a tree. An algorithm for destroying and deallocating a subtree is:

DELETE-SUBTREE(subtree):
    if subtree is empty:
        just return — because there is no node to delete
    else:
        DELETE-SUBTREE(subtree→lhs)
        DELETE-SUBTREE(subtree→rhs)
        delete the subtree node itself
  • Cat speaking

    Seems like you've done most of the planning for us for this part!

  • LHS Cow speaking

    Perhaps, but you still (1) need to make sure you understand how the tree is encoded using the Node struct and the private data members of the TreeStringSet class, and (2) need to submit a planning image.

Your Task, Part 2: Writing Tests

At this point, there isn't a lot you can test, since completing this part will only let you create empty trees. However, you should still write test cases to check the following:

  • The default constructor creates an empty tree.
  • The size() function returns 0 for an empty tree.
  • The clear() function works on empty trees (i.e., it leaves them empty and does not crash).
  • The swap() function works on empty trees (i.e., swapping two empty trees leaves them both empty and does not crash).

Because your destructor will just call clear(), you don't need to write any tests specifically for the destructor (in some sense it will be tested implicitly whenever a TreeStringSet object goes out of scope).

Your Task, Part 3: Implementing the Functions

For this phase, you will plan, implement, and test the following member functions from the TreeStringSet class:

  • The constructors.
  • The clear() member function,
  • The destructor (which just trivially calls clear()).
  • The swap() member function.
  • The size() member function.

These functions are described in the TreeStringSet Specification.

Required Implementation Approach for clear()

Your clear() function must call a private, recursive, helper function. This helper function must take a single Node* as its parameter, indicating the root of a subtree to destroy and deallocate, and must be declared as static.

The algorithm for this helper function is given in the planning section above.

After you've deleted all the tree nodes, make sure you set your root pointer to nullptr and your size to 0.

  • Duck speaking

    Couldn't I make Node a class instead and add a destructor to it?

  • LHS Cow speaking

    In our design, Nodes are “just data”, they don't have any member functions. Although it's technically possible to adopt an approach where Node is a class, that approach has a number of subtleties, with more opportunities for bugs.

  • Hedgehog speaking

    Can someone explain to me what a “static member function” is, where I put static, and why?

  • LHS Cow speaking

    A static member function is one that doesn't have a this object it can access. In the algorithm above, we're working solely on Node pointers; the recursive code doesn't need to do anything with the outer tree object that owns all the nodes, so it can (and should) be static. We put the static keyword at the very front, but (strangely perhaps) we only need to say it in the header file.

  • Cat speaking

    I think we actually covered this topic in one of the lessons.

Required Implementation Approach for the Other Functions

The default constructor, destructor, and swap() function should be straightforward to implement based on their specifications. You can look back your code for Homework 5 to see how you implemented similar functions for IntList.

Your Task, Part 4: Testing & Fixing

Build your code by running

cs70-make -H treestringset-test

Then run your tests with

./treestringset-test

You should also run your tests with Valgrind to check for memory errors:

valgrind --leak-check=full ./treestringset-test

When all your tests pass and Valgrind reports no memory errors, you're done with this part of the assignment!

Helpful Hints

Plan Before You Code, Add Your Planning Image

Remember to git add your new image file to your repository so that we can see it!

Structure of Your Testing Code

There are two useful help pages for writing tests:

One piece of overall advice is that your test_XXXX() functions should each test a particular area of functionality. You probably can't just test one TreeStringSet function at a time, because many functions depend on others, but if a test group becomes a sprawling mess, you should probably break it up into smaller test functions.

You Can't Explicitly Test the Destructor

Remember that we never call a class’s destructor directly, so you shouldn’t write tests for it. But you can test clear(), and you can use Valgrind to check for memory leaks when your TreeStringSet objects go out of scope.

Always Run with Valgrind

We gave you explicit advice to run your tests with Valgrind in the main instructions above, but it's worth repeating here: You should always run your tests with Valgrind to check for memory errors! Using Valgrind is especially important when you're writing code that manages memory directly, as you are here. We won't always explicitly tell you to use Valgrind in future parts of the assignment, but doing so should be part of your regular workflow.

To Complete This Part of the Assignment…

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)