The Tree Container Library

The design of the TCL is straightforward, but makes heavy use of class templates. It was designed to have a similar interface to the containers found in the STL. As with the STL, the various iterator classes are defined for all trees. The iterators are defined according to type. There are three types of iterators in the TCL. In the following discussion, the terms node and tree are used interchangeably, since both entities share the same operations and properties.

The four trees in the TCL which are available for use are the tree, multitree, unique_tree, and sequential_tree. The first three of these are considered associative trees, since they all use an associative container (set/multiset) in their implementation, and have the properties and operations of associative containers. The forth tree, sequential_tree, is considered a sequential type tree container, since it models the std::vector in design and implementation.

The base class of the four tree containers is basic_tree. basic_tree provides the data members for all the trees, and some of the basic operations which are common to all four trees. basic_tree needs to be supplied with some needed information from the four value classes, which is supplied to it via three template parameters. First and foremost, basic_tree needs to know the stored_type which is the type of element that will be stored in the nodes. Also, basic_tree needs to know the fully specified tree_type, as some of basic_tree's operations accept objects of this type as parameters, and return objects of this type in other operations. Lastly, basic_tree needs to know what kind of container to use to store the children. It uses the last template parameter, container_type for this purpose.

At this point, after basic_tree, the hierarchy splits. Inheriting from basic_tree, is associative_tree, and sequential_tree. While sequential_tree is a usable tree class, associative_tree is an intermediate base class for the other three associative trees. associative_tree is declared with the same three template parameters as basic_tree. It accepts these parameters from the three associative_trees which derive from it, and forwards these template parameters to basic_tree, from which it's derived.

All tree classes and base classes are defined in separate source files, named after the class they define.

A variety of iterators are defined for all four trees. The iterators are defined in separate files, depending on their category. The child iterators are defined in child_iterator.h. The descendant iterators are defined in descendant_iterator.h/inl. The ordered iterators are defined in ordered_iterator.h/inl. The iterators are template classes. They are then declared as typedefs in associative_tree and sequential_tree, to create a containment relationship with those classes. As shown in the class diagram, iterator and const_iterator are typedefed as iterator/const_iterator and contained within associative_tree. sequential_iterator and const_sequential iterator are typedefed as iterator/const_iterator and contained within sequential_tree. All of the descendant iterators are typedefed and contained in both associative_tree and sequential_tree.

The typedefs for the child iterators are shown below. In the typedefs, stored_type is the type of element you are storing in the tree, tree_type is the fully specified tree you are defining, container_type is the type of STL container (set, multiset, or vector) which is used in the implementation to store the nodes. For associative_trees, the typedefs are declared in associative_trees, as shown below.

• typedef const_associative_iterator<stored_type, tree_type, container_type> const_iterator;
• typedef associative_iterator<stored_type, tree_type, container_type> iterator;

Separate child iterators are defined for sequential_tree. This is because these iterators are random orderer iterators, while the child iterators for the associative trees are bidirectional. For sequential_tree, the typedefs for the child iterators are shown below.

typedef const_sequential_iterator<stored_type, tree_type, container_type> const_iterator;
typedef sequential_iterator<stored_type, tree_type, container_type> iterator;

Typedefs are also declared in associative_tree and sequential_tree for the descendant iterators. The same descendant iterator classes are used for both sequential_tree and associative_tree. When typedefed, only the forth template parameter differs in their declarations. The forth formal template parameter for the descendant iterators is tree_category_type, and is used only to specify whether the descendant iterator is being instantiated by associative tree or sequential_tree. The typedefs for the descendant iterators in associative_tree are shown below.

typedef const_pre_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> const_pre_order_iterator;
typedef pre_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> pre_order_iterator;
typedef const_post_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> const_post_order_iterator;
typedef post_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> post_order_iterator;
typedef const_level_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> const_level_order_iterator;
typedef level_order_descendant_iterator<stored_type, tree_type, container_type, associative_tree_type> level_order_iterator;

The typdefs declared in sequential_tree for the descendant iterators are as follows.

typedef const_pre_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> const_pre_order_iterator;
typedef pre_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> pre_order_iterator;
typedef const_post_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> const_post_order_iterator;
typedef post_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type>  post_order_iterator;
typedef const_level_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> const_level_order_iterator;
typedef level_order_descendant_iterator<stored_type, tree_type, container_type, sequential_tree_type> level_order_iterator;

As shown in the class diagram, the three const descendant iterators include a class member of const_iterator. It is this internal iterator member which is used to keep track of the current descendant node position of the descendant iterators. const_ordered_iterator also contains a const_iterator member.

There are a few obvious and necessary differences between the const iterators and non-const iterators. This behavior is also seen in the STL iterator classes.

• With const iterators, node() returns a pointer to const tree_type, and the */-> operations return a reference/pointer to const stored_type.
• const_iterator returns const_iterators for many of it's operations, while iterator returns iterators for those same operations.
• const_iterators can not perform insert operations via it's node() operation, as they preserve their const-ness.

As mentioned above, the three associative tree container classes are all derived from associative_tree, which is derived from basic_tree. Most of the operations common to all four trees are defined in basic_tree, and are available to not only the three associative trees through associative_tree, but also to sequential_tree. associative_tree defines only those operations that are common only to the associative trees. unique_tree differs in other respects from the two other associative trees. Thus, unique_tree offers a larger interface than tree and unique_tree.

The class relationships of the three tree container classes was realized early in the design stage. During the beginning stages of it's development, I realized that there would be a need for more than one type of tree container to accommodate the following needs.

• Tree containers in which every child within a particular parent was unique, but duplicates could exist between nodes with different parents. ( tree )
• Tree containers in which duplicate nodes could exist within the same parent, as well as between nodes with different parents. ( multitree ) I originally thought of this requirement based on the need to hold xml data.
• Tree containers in which there are no duplicate nodes in the tree. Every node in the tree is guaranteed to be unique. ( unique_tree ). This tree container would have the advantage that deep find and other deep operations would be available, because of the uniqueness of the nodes.
• Tree containers in which the nodes were not ordered naturally, but ordered according to the way in which they were inserted. ( sequential_tree ) The node order would also be allowed to be changed dynamically by sorting any or all of the nodes with a user specified predicate.

After some consideration and thought, I came up with the requirements and names for the four types of tree containers. Since all four tree types would share the majority of it's operations and functionality, I decided that a base tree class would be handy to avoid duplication of code. After some time in the development stage, the necessary template parameters of the base class were realized. I also decided to study the design of the STL base classes and iterators, to model the behavior of the iterators for the tree containers.