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!

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

  • The constructors
  • The destructor
  • The size() member function

These functions are described in the TreeStringSet Specification.

Required Implementation Approach

Your destructor 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 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 subtree's node
  • 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.

Helpful Hints

Plan Before You Code, Add Your Planning Image

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

Testing

Remember that we never call a class’s destructor directly, so you shouldn’t write tests for it. But you should use Valgrind here (and on every step from here on out!) to make sure that memory is being managed correctly.

Structure of Testing Code

Remember that your tests will have the following structure:

  • Create a TestingLogger object.
  • Set up objects/steps needed for the condition you want to test.
  • Use one or more affirms to check state.
  • Return a summary of the TestingLogger’s state.

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.

Also Run with Valgrind

It is always a good idea to run your tests with Valgrind to see if there are any obvious signs you are using memory improperly. For example, it can detect memory leaks if your destructor isn't working right.

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.)