The Tree Container Library

The descendant iterators are much more complex than child iterators. They are declared and defined in descendant_iterator.h/inl. There are three types of descendant iterators.

• pre_order_descendant_iterator
const_pre_order_descendant_iterator
  The pre order iterators traverse over nodes in a pre-order fashion. These iterators recurringly visit a parent node first, then the nodes children, before going on the parent's sibling node.
• post_order_descendant_iterator
const_post_order_descendant_iterator
  The post order iterators traverse over nodes in a post-order fashion. These iterators recurringly visit a parent's children first, then visit the parent, before going on to the parent's sibling.
• level_order_descendant_iterator
const_level_order_iterator
  The level order iterators traverse over nodes in a level_order fashion. These iterators traverse child nodes, level by level. The first level would be considered the immediate children of a parent node. the second level would be considered the parent's grandchildren. The third level would be considered the parent's great grandchildren, and so on.

These descendant iterators are very similar in their declaration, but vary widely in their implementation of the increment and decrement operations. Since they are so similar in their declarations, I'll discuss them all at once, and comment on any differences. Like the child iterators, the descendant iterators are defined in pairs as mentioned above.
All of the non-const descendant iterators inherit from their const equivalents. In the following discussion, I'll refer to all three descendant iterator types as const_descendant_iterators and descendant_iterators.

All of the descendant iterator classes accept four template parameters. The first three of these are the same as those accepted by the child iterator, associative_tree, and basic_tree. The forth template parameter, tree_category_type is particular to the descendant iterators.

• stored_type
  This is the same first template parameter specified for all the tree container value classes. This type parameter informs the child iterators the stored_type which is stored in the nodes.
• tree_type
  This is the fully specified derived value class type. It can also be considered the node type.
• container_type
  This template parameter is used to specify the storage container used to store children in each node.
• tree_category_type
  Specifies which tree the descendant iterators will be defined in. This parameter will either be the fully specified associative_tree, or the fully specified sequential_tree.

The const_descendant_iterators (pre and post) inherit from std::iterator<std::bidirectional_iterator_tag, stored_type>, putting it in the iterator category of a bidirectional iterator. The level order iterators inherit from std::iterator<std::forward_iterator_tag, stored_type>, putting it in the iterator category of a forward only iterator. Most of the implementation, including all data members, are declared in the const descendant iterators. The non-const descendant iterators are derived from the const equivalents, which allow them to inherit most of the implementation.

Before discussing the descendant iterators operations, I'll first cover their data members. The data member which drives the descendant iterator is a TCL child iterator, named it. This child iterator is positioned on the appropriate child node of the appropriate parent node, to keep track of where the descendant iterator currently resides in the tree hierarchy. This member is defined as
typename tree_category_type::const_iterator it;
Note the use of the forth template parameter, here, tree_category_type, in it's declaration. An equally important data member, is a STL stack (or queue, for the level order iterators) which contains objects of TCL child const iterators, named node_stack (or node_queue for the level order iterator). Since the iterators will be traversing up and down the tree hierarchy, the iterator stack/queue helps maintain the position of the internal TCL child iterator. The third data member which is used in all descendant iterators is a pointer to the top node over which the descendant iterator is traversing, named pTop_node. This data member is essential to determine when the descendant iterator has reached the end of the traversal. The pre and post descendant iterators have a forth data member, which is a reverse iterator. This iterator is used in the implementation of the increment and decrement operations. The level order iterator has a data member, node_depth which is needed to track the depth of the iterator in it's traversal. The level order iterators also offer a depth() operation, which return the value of this member.

The default constructors and destructor's are declared public. The destructor for all the descendant iterators has no need to be virtual, as there is no need for users to derive from these classes. The second constructor for the descendant iterators is declared protected, since it only need to be available to associative_tree or sequential_tree, which are both declared as friends further below. This second constructor is defined as
const_descendant_iterator(typename tree_category_type::const_iterator& it_, const tree_category_type* pTop_node_) : it(it_), pTop_node(pTop_node_) {}
It is needed for associative_tree's and sequential_tree's xxx_order_begin() and/or xxx_order_end() operations. The post order iterator's have a third constructor,
explicit const_post_order_descendant_iterator(const tree_category_type* pTop_node_)

The majority of public interface functions and overloaded operators in the const descendant iterators simply delegate the appropriate action to the const_iterator member, it. The increment and decrement operations are much more complex. Those operations call the member functions incr() and decr(), which are commented in the code. As mentioned previously, a stack is used to save the states of parent iterators during the iterations.

The non-const descendant iterators inherit from their non-const equivalents. They override some of the overloaded operator functions for const/non-const correctness. Some of the operations call the base class (const descendant iterator) operation using a necessary cast.

The increment and decrement operations for the descendant iterators are the most complex of all of their operations. They are implemented and commented in the inl file.