CS11 Advanced C++ Lab 2: Tree-Set Iteration

Now that you have gotten the basic tree-set data structure completed, it's time to implement several of the common features of C++ collection classes: initialization from a list of values, and support for iteration over the contents of the tree-set.

TreeSets and Initializer Lists

Since C++11, the STL collections support initialization from a list of values, like this:

// Initialize a vector of 7 integer values
vector<int> v = {1, 1, 2, 3, 5, 8, 13};

// This syntax also works:
vector<int> v{1, 1, 2, 3, 5, 8, 13};

You can add list-initialization like this to your own classes by using the std::initializer_list<T> type, declared in the <initializer_list> C++ standard header file. Just make a constructor that takes an initializer-list of values of the appropriate type, and you will also be able to initialize your tree-set like this:

TreeSet s1 = {2, 3, 5};
TreeSet s2{2, 3, 5};

TreeSet Iteration

In-order tree traversal is not terribly difficult to implement, but it is made more complicated by the standard C++ iterator abstraction, which allows one to access the current element, or advance to the next element. Your TreeSet class will need to provide functionality similar to the C++ iterator abstraction, like this:

TreeSet s{3, 5, 2, 1};

TreeSet::iterator it = s.begin();
while (it != s.end()) {
    cout << ' ' << *it;
    it++;  // or ++it;
}

This should print out the result "1 2 3 5"; in other words, the values are traversed in increasing order.

To implement this, the TreeSet needs to provide an iterator implementation that can navigate the internal tree structure in order. It's cleanest and easiest to implement this as a separate TreeSetIter class that can access the TreeSet class' private state. Normally this would be disallowed, but the TreeSet class can declare that the TreeSetIter class is a friend class, and then TreeSetIter will be able to access all of the internal details.

The TreeSetIter class needs to hold some internal state that will allow it to remember where it is in traversing the binary search tree. At least one part of that state will be a smart-pointer to the current tree node. You may also need to maintain a std::vector of nodes that the iterator has entered, like a stack, so that it can figure out where to go when the iterator is advanced.

You are encouraged to look at the Wikipedia article on tree traversal for more details of how to implement the iterator logic. The "iterativeInorder(node)" pseudocode will steer you in the right direction.

TreeSetIter Functionality

The TreeSetIter class must provide the following operations:

• Initialization. You do not have to provide copy-initialization or move-initialization; as long as you are not heap-allocating anything (why would you anyway?), the default implementations should suffice.

• TreeSetIter & operator++() (pre-increment operator) - advance the iterator to the next node in the binary search tree. The operator should return a reference to the iterator that was incremented, not a copy.

• TreeSetIter operator++(int) (post-increment operator) - advance the iterator to the next node in the binary search tree. The operator should return a copy of the iterator before it was incremented.

• int operator*() (dereference) - the iterator "points to" the current int value, and dereferencing the iterator should return the int value itself. For this operation the iterator may simply return the value out of the tree node.

• bool operator==(const TreeSetIter &rhs) const - return true if the rhs iterator references the same tree-node that this iterator references. Note that you are not comparing the values in the tree-nodes; you are comparing the pointers to the tree-nodes.

• bool operator!=(const TreeSetIter &rhs) const - inverse of ==

TreeSet Iterator Functionality

The TreeSet class itself must provide the following operations:

• TreeSetIter begin() const - return an iterator to the first value in the tree-set

• TreeSetIter end() const - return an iterator "past the end" of the tree-set. A good approach would be to initialize a TreeSetIter object with an empty node-pointer.

• A public declaration of the TreeSet::iterator type. Like STL collections, this allows the TreeSet to provide a more "standard" name for the iterator type, rather than requiring users to know internal implementation details. This can be done easily with a line like this in your TreeSet class' public section:

  using iterator = TreeSetIter;

Once these features are provided, you should be able to iterate over the contents of a TreeSet in order. Exciting times.

Additional TreeSet Features

Once iteration is complete, many other tree-set features become straightforward to write. Implement these member functions for your TreeSet class, using your iterator implementation:

• bool operator==(const TreeSet &rhs) const - return true if the rhs set contains the same values as this set. Note that the two sets may have different internal tree structures and still compare as equal.

• bool operator!=(const TreeSet &rhs) const - inverse of ==

• TreeSet TreeSet::plus(const TreeSet &s) const - compute the set-union of this set and the provided set s, returning a separate set containing the result.

  Note: This is called plus() and not union() because union is a C++ keyword.

  Note: A more generalized data structure would also provide + and += operators, etc. We are not requiring these operations because it starts to get tedious to implement and test all these operations. However, feel free to provide them if you wish.

• TreeSet TreeSet::intersect(const TreeSet &s) const - compute the set-intersection of this set and the provided set s, returning a separate set containing the result.

• TreeSet TreeSet::minus(const TreeSet &s) const - compute the set-difference of this set and the provided set s, returning a separate set containing the result.

  Note: A more generalized data structure would also provide - and -= operators, etc. We are not requiring these operations because it starts to get tedious to implement and test all these operations. However, feel free to provide them if you wish.

• A stream-output operator << for your TreeSet type, which outputs the contents of the set in this format: "[1,2,3,4]"

  Note that the stream-output operator must not output a "\n" character, or any whitespace.

  An empty set would be output as: "[]"

Testing, Documentation, Build Automation

An updated test suite for your class is provided here. This program includes the testing from last week, as well as additional tests to exercise the new functionality. Make sure to fix any test failures you encounter.

Make sure your Makefile continues to work with your code updates, and with the new tests from this week.

As always, make sure you have written Doxygen-format comments for all updates to your class this week. We expect your comments to be complete and concise. You are not required to provide structural commands for function arguments, return values, etc., unless you really want to.

Submitting Your Work

Once you have completed the above tasks, submit your work through csman. Make sure to submit these files:

• Makefile
• treeset.h
• treeset.cpp (if present)

You do not need to submit the test code; we will test your program with a fresh copy of these files.

Assignment Feedback Survey

Please also complete and submit a feedback survey with your submission, telling us about your experience with this assignment. Doing so will help us to improve CS11 Advanced C++ in the future.

Copyright © 2019 by California Institute of Technology. All rights reserved. Generated from advcpp-lab2.md.