Pre-order forward iterator class

class iterator_preorder

The constructor for class iterator_preorder sets current to the root. The iterator uses bool at_end to track completion. The Node *successor() method, called by iterator_preorder& operator++() to advance to the next node, is explained below.

 class iterator_preorder {  // This not efficient to copy due to the stack container inside it.

   using node_type = bstree<Key, Value>::node_type;

   node_type *current;
   bool at_end = false;

   bstree<Key, Value>& tree;

   Node *successor();

  public:

   using difference_type  = std::ptrdiff_t;
   using value_type       = bstree<Key, Value>::value_type;
   using reference        = value_type&;
   using pointer          = value_type*;

   using iterator_category = std::bidirectional_iterator_tag;

   explicit iterator_preorder(bstree<Key, Value>& bstree) : tree{bstree}
   {
      current = bstree.root.get();
   }

   iterator_preorder(const iterator_preorder& lhs) : current{lhs.current}, tree{lhs.tree}
   {
   }

   iterator_preorder& operator++() noexcept
   {
      current = successor();
      return *this;
   }

   operator bool() const
   {
      return at_end;
   }

   iterator_preorder operator++(int) noexcept
   {
      iterator_preorder tmp(*this);
      current = successor();
      return tmp;
   }

   reference operator*() const noexcept
   {
       return current->__get_value(); // May want 'Node *' itself
   }

   pointer operator->() const noexcept
   {
      return &(operator*());
   }

   struct sentinel {}; // Use for determining "at the end" in 'bool operator==(const iterator_preorder&) const' below

   bool operator==(const iterator_preorder::sentinel& sent) const noexcept
   {
       return at_end;
   }

   bool operator!=(const iterator_preorder::sentinel& lhs) const noexcept
   {
     return !operator==(lhs);
   }

   friend bool operator==(const iterator_preorder::sentinel& sent, const iterator_preorder& iter) noexcept
   {
       return iter.operator==(sent);
   }

   friend bool operator!=(const iterator_preorder::sentinel& lhs, const iterator_preorder& iter) noexcept
   {
     return iter.operator!=(lhs);
   }
};

Node *iterator_preorder::successor()

Todo

what exactly is current inside the last else below.

It chooses the left child, if exists, before choosing the right child, if it exists. If neither exist, then __y is a leaf node, and so we check if its parent has a right child, and if it does, we make it the pre-order successor; otherwise, if the leaf is a right child or a left child whose parent does not have a right child, we ascend the parent chain until we find a parent whose right child’s is greater than __y’s key: parent->right->key > __y->key().

When parent’s key is > current->key(), then we are high enough in the parent chain to determine if the parent’s right child’s key > current->key(). If it is, this is the preorder successor for the leaf node current. If not, we continue up the parent chain. If we encounter the root, then there is no pre-order successor. We are done iterating.

Node *iterator_preorder::successor()
{
  if (at_end) return current;

  Node *__y = current;

  if (__y->left)            // Prefer left child
      __y = __y->left.get();
  else if (__y->right)   // otherwise, the right
      __y = __y->right.get();
  else if (__y->parent == nullptr) {} // root is a leaf node, do nothing. Loop will exit.
  else  { // If current is a leaf node...

     // ...and it's parent has a right child, make it current
     if (current == current->parent->left.get() && current->parent->right)

            __y = current->parent->right.get();

     else {
       // else the leaf is a right child or a left child whose parent does not have a right child,
       // and we ascend the parent chain until we find a parent whose right child's key > __y->key(), where __y is initially current and then...
       // When parent's key is > current->key(), then we are high enough in the parent chain to determine if the
       // parent's right child's key > current->key(). If it is, this is the preorder successor for the leaf node current.
       // If not, continue up the parent chain....
       for(auto parent = __y->parent; 1; parent = parent->parent) {

          // Note: we combine all three tests--right child of parent exits, parent key is > current's,
          // and parent's right child's key > current's--into one if-test.
          if (parent->right && parent->key() > __y->key() && parent->right->key() > __y->key()) {
               __y = parent->right.get();
               break;
          }
          //...if we ascend to the root, there is no further pre-order successor. We are done.
          if (parent == tree.root.get()) {
              at_end = true;
              break;
          }
       }
     }
  }
  return __y;