CS 70

TreeStringSet Specifications

In previous assignments, we've gradually built up the specifications for our classes over several steps. This time, we're going to provide you with the complete specifications for the TreeStringSet class and its associated const_iterator type all at once. We'll still implement it over several steps, but having the complete specifications up front should help you understand how the pieces fit together.

This page describes the interface and encoding for TreeStringSet and TreeStringSet::const_iterator, and the encodings for their implementations, as the TreeStringSet and TreeStringSet::ConstIter classes.

Your implementation must support all the functionality described on this page, including meeting the specified complexity for each function. You may not change the names of anything in the interfaces, nor may you change the encodings. However, you will find it useful (and necessary!) to write private helper member functions, but those functions are not part of the interface and are not described in this document.

Interface

The TreeStringSet Interface

Your tree class must be named TreeStringSet and must support the following operations:

  • A default constructor

  • A destructor

  • The copy constructor and assignment operator should be disabled.

  • A clear member function that

    • Takes no arguments.
    • Removes all items from the TreeStringSet.
    • Requires \(\Theta(n)\) time.
    • After calling myTreeSet.clear(), any iterators that refer to myTreeSet are no longer valid.

  • A swap member function that

    • Takes a reference to another TreeStringSet.
    • Doesn’t return anything (but swaps the contents of the two trees).
    • Requires \(\Theta(1)\) time.
    • After calling swap, any iterators that refer to either tree are no longer valid.

  • A size member function that

    • Takes no arguments.
    • Returns the number of values in the TreeStringSet, as a size_t.
    • Requires \(\Theta(1)\) time.
    • Can be called on a read-only tree (i.e., const at the end).
  • Bjarne speaking

    When people say “constant reference”, they don't mean that the reference itself can't change, because references can't ever be made to refer to something else. What they really mean is “reference to constant” (i.e., “reference to a read-only object”), but that's too much of a mouthful, so they just say “constant reference”. It's a bit of a misnomer, but it's seen everywhere, so you'll just have to get used to it.

  • An insert member function that

    • Takes takes a std::string by constant reference
    • Doesn’t return anything (but inserts the item into the tree).
      • It is okay to call insert with a string that is already in the tree. In that case the item is not inserted again.
    • Takes \(\mathrm{O}(\mathit{height})\) time.
    • After calling insert, any iterators that refer to the tree are no longer valid.

  • An exists member function that

    • Takes takes a std::string by constant reference.
    • Returns a bool indicating whether the item was found in the tree.
    • Takes \(\mathrm{O}(\mathit{height})\) time.
    • Can be called on a read-only tree (i.e., const at the end).

  • A height member function

    • Takes no arguments.
    • Returns an int representing the height of the tree.
      • An empty tree has height -1 (not 0).
    • Requires \(\Theta(n)\) time.
    • Can be called on read-only trees (i.e., const at the end).

  • An averageDepth member function

    • Takes no arguments.
    • Returns a double representing the average depth of the tree.
      • An empty tree has average depth -1 (not 0.0/0).
    • Requires \(\Theta(n)\) time.
    • Can be called on a read-only tree (i.e., const at the end).

  • == and != member functions for tree equality.

    • Returns a bool with the result of the test
      • Two trees are equal if they contain the same values (no matter what tree shape!).
    • Requires \(\mathrm{O}(n)\) time.
    • Can be called on read-only trees (i.e., const at the end and on the argument).

  • A printToStream member function that

    • Takes a std::ostream&.
    • Prints the tree out to that stream (the required format is descibed later).
    • Returns the same std::ostream& it was passed.
    • Can be called on a read-only tree (i.e., const at the end).

  • A showStatistics member function that

    • Takes a std::ostream&.
    • Prints statistics about the tree to that stream (the required format is descibed later).
    • Returns the same std::ostream& it was passed.
    • Can be called on a read-only tree (i.e., const at the end).

  • A begin member function that

    • Takes no arguments.
    • Returns a const_iterator that is set to the first (least) node of the tree.
    • Requires \(\mathrm{O}(\mathit{height})\) time.
    • Can be called on a read-only tree (i.e., const at the end).

  • An end member function that

    • Takes no arguments.
    • Returns a const_iterator that refers is set “past the end” of the tree (i.e., past the greatest element).
    • Requires \(\Theta(1)\) time.
    • Can be called on a read-only tree (i.e., const at the end).

You will likely want to define additional (static) private member functions (e.g., recursive helper functions that work on Node*s), but since those are not part of the interface, they are not included in this specification.

Reminder: Invalid Iterators

When the specification says that “any iterators that refer to the tree are no longer valid,” it does not mean that your code needs to do anything to “invalidate” those iterators. It simply means that users of the TreeStringSet class can no longer expect those iterators to work correctly, and if they attempt to use them (without resetting them to some valid value first), the behavior of the program is undefined.

In your TreeStringSet implementation, your iterators might still actually work if used in some situations where they're technically invalid (perhaps with additional conditions), but that is irrelevant; the specification simply says that after such operations, users of your class cannot rely on those iterators to work correctly, and neither can your test cases.

The TreeStringSet::const_iterator Interface (and ConstIter class)

The TreeStringSet should provide a public const_iterator type that is an alias for a (private) class called ConstIter. This iterator traverses the tree in sorted order.

The ConstIter class should provide at least the following operations:

  • A default constructor (either written or intentionally chosen as the synthesized default constructor).

  • A copy constructor (either written or intentionally chosen as the synthesized copy constructor).

  • An assignment operator (either written or intentionally chosen as the synthesized assignment operator).

  • A destructor (either written or intentionally chosen as the synthesized destructor)

  • A member function called operator* that returns a const string& that doesn't change the iterator itself (i.e., a const member function)

  • A pre-increment operator, operator++, that advances to the next tree item in order (or goes past the end if we were on the last item) and returns a reference to itself (i.e., a ConstIter&).

  • An equality test, operator==, and an inequality test, operator!=, which each return a bool. When comparing two iterators, we will assume that the iterators refer to the same TreeStringSet object. (If they don't, the behavior will be undefined.) We therefore only need to check that the iterators are also at the same point in their traversal of the tree. This test should work on const const_iterators.

Your TreeStringSet will hold std::strings, so your ConstIter should define the following values to interface nicely with iterator-related functions in the C++ standard library:

using value_type        = std::string;
using reference         = const value_type&;
using pointer           = const value_type*;
using difference_type   = ptrdiff_t;
using iterator_category = std::forward_iterator_tag;

You may want to define additional private member functions, but since those are not part of the interface, they are not included in this specification.

Global Functions on TreeStringSets

Using the printToStream member function described above, we could print a TreeStringSet with code like

TreeStringSet tree;
// ... insert some items into tree ...
tree.printToStream(std::cout);
std::cout << std::endl;

which is fine, but a bit cumbersome. In C++, the more idiomatic way to print an object to an output stream is to use the operator<< function, as

TreeStringSet tree;
// ... insert some items into tree ...
std::cout << tree << std::endl;

That code requires us to define a global function (i.e., not a member function, a function defined outside the class at global scope) called operator<< that takes a std::ostream& and a const TreeStringSet& and returns a std::ostream&. This function should simply call the printToStream member function of the TreeStringSet class and return the same std::ostream& that it was passed so that it can be used in chained output operations.

Private Encoding

The lessons discuss the encodings of trees; see, in particular, Encoding a BST in C++. You will need to choose appropriate data member(s) and names, but for consistency we require a specific encoding for tree Nodes.

The Private Node Struct

Inside your TreeStringSet class, you will need to represent the nodes of the tree (a TreeStringSet is not itself a tree node—it is the overarching object that contains tree nodes but also has other information, such as a count of the number of nodes).

Internally, our encoding for trees requires that each tree node stores exactly (and only) the following information:

  • The value stored at that tree node (a std::string).
  • A pointer to the root of the left subtree (i.e., another node) or nullptr if there is no left subtree.
  • A pointer to the root of the right subtree (i.e., another node) or nullptr if there is no right subtree.

(As implied by these requirements, your tree nodes may not have any “parent” pointers going backwards up the tree.)

As in last week's linked-list assignment, Nodes are “just data”. They are manipulated entirely by code in the TreeStringSet class. You may not implement your nodes as a class.

(When logged in, completion status appears here.)