Post-order forward iterator class¶
Class iterator_postorder
iterates the tree in post-order sequence. It begins with the minimun, left-most node and moves the iteration cursor, denoted by current
, each time iterator_postorder& operator++()
is called. Node *successor()
is described below. The enum class position
, like the iterator_preofer
class, implements a finite state machine that consists of three possible positions…
class iterator_postorder { // This not efficient to copy due to the stack container inside it.
using node_type = bstree<Key, Value>::node_type;
node_type *current;
enum class position {at_beg, between, at_end};
position pos;
bstree<Key, Value> *ptree;
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::forward_iterator_tag;
iterator_postorder() : current{nullptr}, ptree{nullptr}, pos{position::at_end}
{
}
explicit iterator_postorder(bstree<Key, Value>& tree) : ptree{&tree}
{
if (ptree->root == nullptr) {
pos = position::at_end;
current = nullptr;
} else {
pos = position::at_beg;
// Set current to node with smallest key.
current = min(ptree->root.get());
}
}
// This constructor is call by bstree::end();
iterator_postorder(bstree<Key, Value>& tree, int dummy) : ptree{&tree}
{
pos = position::at_end;
if (ptree->root == nullptr)
current = nullptr;
else
current = ptree->root.get();// Set current to root
}
iterator_postorder(const iterator_postorder& lhs) : current{lhs.current}, ptree{lhs.ptree}, pos{lhs.pos}
{
}
iterator_postorder& operator++() noexcept
{
switch (pos) {
case position::at_end:
break;
case position::at_beg:
case position::between:
{
auto next = successor();
if (current == next)
pos = position::at_end;
else
current = next;
}
break;
default:
break;
}
return *this;
}
reference operator*() const noexcept { return current->__get_value(); }
pointer operator->() const noexcept { return &(operator*()); }
struct sentinel {};
bool operator==(const iterator_postorder::sentinel& sent) const noexcept
{
return (pos == position::at_end) ? true : false;
}
bool operator!=(const iterator_postorder::sentinel& lhs) const noexcept
{
return !operator==(lhs);
}
friend bool operator==(const iterator_postorder::sentinel& sent, const iterator_postorder& iter) noexcept
{
return iter.operator==(sent);
}
friend bool operator!=(const iterator_postorder::sentinel& sent, const iterator_postorder& iter) noexcept
{
return iter.operator!=(sent);
}
};
Node *successor();
¶
The successor()
method first checks if the given node is the right child of its parent or if the parent’s right child is empty. If either is true, the post-order successor is the parent; otherwise, we search for the left-most
child in the parent’s right substree.
Node *successor();
{
if (current == nullptr || pos == position::at_end) return current;
Node *__y = current;
// If given node is the right child of its parent or parent's right is empty, then the
// parent is postorder successor.
auto parent = __y->parent;
if (!parent->right || __y == parent->right.get())
__y = parent;
else {
// In all other cases, find the left-most child in the right substree of parent.
auto pnode = parent->right.get();
while (pnode->left)
pnode = pnode->left.get();
__y = parent;
}
return __y;
}