CSCI 362 — Lab 5a

Set: a std::set class (but mostly just a Binary Search Tree)

Due: June 18, 2019 @ 11:59PM

Handout

Grab the handout tarfile from here: http://cs.millersville.edu/~wkillian/2019/summer/files/csci362/lab5a-set.tar

Overview

I've given you a mostly complete implementation of Set. Set is almost like std::set however, we do not handle "balancing" the tree. You are tasked with completing its implementation which relies heavily on Tree.

The assignment is split into three files:

These are not small files -- Just the handout code is over 750 lines. My reference solutions only add about 120 lines total. Like prior labs, it can be easy to get overwhelmed. But, if you work on one file at a time and complete the implementations of the functions in the specified order, you will make progress quickly!

  1. I recommend solving the pieces in the order I have them listed
  2. I am giving you a comprehensive unit test autograder as part of the handout

Required functions

NOTE: solve in the listed order

TreeNode.hpp
template <typename T>
struct TreeNode {
  // [2] constructor
  TreeNode (T const&, TreeNode<T>*, TreeNode<T>*, TreeNode<T>*);
  // [2] value constructor
  TreeNode (T const&);
};

namespace TreeNodeUtils
{
  // [2] is node root
  template <typename T>
  constexpr bool
  isRoot (TreeNode<T>*) noexcept;

  // [2] is node a leaf
  template <typename T>
  constexpr bool
  isLeaf (TreeNode<T>*) noexcept;

  // [2] is node a left child
  template <typename T>
  constexpr bool
  isLeftChild (TreeNode<T>*) noexcept;

  // [2] is node a right child
  template <typename T>
  constexpr bool
  isRightChild (TreeNode<T>*) noexcept;

  // [3] minimum of a tree rooted at node
  template <typename T>
  constexpr TreeNode<T>*
  minimum (TreeNode<T>*) noexcept;

  // [3] maximum of a tree rooted at node
  template <typename T>
  constexpr TreeNode<T>*
  maximum (TreeNode<T>*) noexcept;

  // [3] in-order successor of a node
  template <typename T>
  constexpr TreeNode<T>*
  successor (TreeNode<T>*) noexcept;

  // [3] in-order predecessor of a node
  template <typename T>
  constexpr TreeNode<T>*
  predecessor (TreeNode<T>*) noexcept;

  // [4] copies a tree rooted at a node and updates parent
  template <typename T>
  TreeNode<T>*
  copy (TreeNode<T>*, TreeNode<T>*);

  // [4] clear a tree rooted at a node, then sets node to nullptr
  template <typename T>
  void
  clear (TreeNode<T>*&);
}
Tree.hpp
template <typename T, bool AllowDuplicates = false>
struct Tree
{
  // [4] updates min()/max() as if we would be inserting the passed node into our tree
  void
  fixupExtremeInsert (TreeNode<T>*) noexcept;

  // [5] inserts a value into the tree
  std::pair<TreeNode<T>*, bool>
  insert (T const&);

  // [5] inserts an r-value into the tree
  std::pair<TreeNode<T>*, bool>
  insert (T&&);

  // [4] returns a pointer to the node holding the passed value (or nullptr if not found)
  constexpr TreeNode<T>*
  find (T const &) const;

  // [4] copy constructor
  Tree (Tree const&);

  // [4] copy assignment
  Tree& operator= (Tree const&);

  // [2] removes all nodes, resets min()/max(), size set to zero
  void clear();

  // [12] removes a specified node from our tree; returns the in-order successor
  TreeNode<T>*
  remove (TreeNode<T>*);
};
Set.hpp
template <typename T>
class SetIterator {
public:
  // [2] increments the iterator (goes to in-order successor)
  constexpr SetIterator&
  operator++() noexcept;

  // [2] decrements the iterator (goes to in-order predecessor)
  constexpr SetIterator&
  operator--() noexcept;

  // [2] compares two iterators for equality (do they point to the same node)
  constexpr friend bool
  operator== (SetIterator, SetIterator);
};

template <typename T>
class Set {
public:
  // [1] returns an iterator to the first element in the Set
  constexpr iterator
  begin() noexcept;

  // [1] returns an iterator to the first element in the Set
  constexpr const_iterator
  begin() const noexcept;

  // [1] returns an iterator to one past-the-last element in the Set
  constexpr iterator
  end() noexcept;

  // [1] returns an iterator to one past-the-last element in the Set
  constexpr const_iterator
  end() const noexcept;

  // [4] inserts the range [first, last) into the set as if insert were called
  //     in order for each value in the range
  template <typename InputIt, REQUIRES(concepts::ForwardIterator, InputIt)>
  void
  insert (InputIt, InputIt);

  // [4] removes the range [first, last) from the set. returns an iterator to
  //     "last" (but returns `iterator`, not `const_iterator`)
  void
  erase (const_iterator, const_iterator);
};

Running the autograder

Invoking make should create the autograder.

There can be a lot of output shown from the autograder. Some of it could be overwhelming at times. I recommend adding a couple of arguments to the autograder to help ease the pain.

./autograder -a

Will run the autograder and stop as soon as the first FAILURE is found

./autograder -t

Will list all of the tags for each of the tests. If you want to run a specific subset of tags you can do so by stating the following:

./autograder [access],[iterator]

Will run all tests that have the access and iterator tags

./autograder --failed

Will list all failed tests at the end of the autograder output

./autograder --passed

Will list all passed tests at the end of the autograder output

Style

Use good programming style:

Submission

Since this consists of multiple files, a tarball will be required for submission.

invoking make handin should create handin.tar

Please submit handin.tar to autolab

Grading

This lab is graded out of 100 points.