CS 70

TreeStringSet Specifications

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.

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

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

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

  • An == 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).

  • A 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.

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.

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

Top-Level Functions

You should also provide a top-level function (i.e., not inside the class definition, but declared after it), operator<<, that defines how to print a TreeStringSet. It takes as arguments a std::ostream& and a const TreeStringSet&; it returns a std::ostream&. That operator will call the public printToStream member function of the TreeStringSet class.

Private Encoding

The lessons discuss encodings of trees; see in particular Encoding a BST in C++. You 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.)