The Tree Container Library

basic_tree<> serves as the base class for the four tree containers in the TCL, tree, multi_tree, unique_tree, and sequential_tree. Some of the common operations for all four containers are found in basic_tree. Basic_tree serves as an immediate base class only to sequential_tree, and serves as the final base class to the associative trees, described in the TCL design. A class diagram of basic_tree and it's associated derived classes, is shown to the right. In the following discussion, please refer to the actual source files, basic_tree.h and basic_tree.inl.

basic_tree accepts three template parameters, which are passed down from either associative_tree, or sequential_tree, which inherit from it.

• stored_type
  This is the same first template parameter specified for all the tree container value classes. This is the first and only mandatory template parameter that you need supply when declaring your tree container. basic_tree supplies the storage for a copy of an object of that type, in pElement. Thus, each node in the tree will have it's own copy of the stored_type object.
• tree_type
  This is the fully specified derived value class type. It's needed here, because basic_tree would not know otherwise which of the four value classes are deriving from itself. Knowing this type allows basic_tree to provide many operations for the derived classes, which would otherwise have to be implemented in each of those three derived container classes.
• container_type
  This template parameter is used to specify the storage container member (children) that is used by basic_tree to store it's child nodes. It will either be a fully specified std::set<> or std::multiset<> for the associative_trees, or a std::vector<> for sequential_tree.

Figure 1

basic_tree summary class diagram

Derived Tree Class Diagram

These three template parameters give basic_tree all the type info it needs from the derived objects, to perform many of the internal functions, and to provide the needed data members for it's derived classes.

basic_tree first creates a typedef of itself solely for convenience:
typedef basic_tree<stored_type, tree_type, container_type> basic_tree_type;

Then, a typedef is defined for the declaration of the set_clone() operation:
typedef stored_type* (*tClone_fcn) (stored_type*);

Next, some needed typedefs are declared to insure STL comparability.
typedef stored_type value_type;
typedef stored_type& reference;
typedef const stored_type& const_reference;
typedef size_t size_type;
typedef std::allocator<stored_type> allocator_type;


Next, the constructors and destructor are declared. basic_tree defines three constructors, a default constructor, a copy constructor, and a constructor which takes a reference to a stored_type.
The latter constructor simply initializes the node's data store, pElement, with a copy of the passed stored_type. All constructors are given protected access, so that instantiation of this base class will not be possible. The destructor is defined with protected access, and because clients should never have to delete objects of the base class polymorphously, the destructor is non-virtual.

We now come to the public interface section of the class. Almost all the public interface operations are defined inline, and have one or two lines of code, which are self explanatory by studying the operation. After the public interface functions, some protected functions are declared/defined. Most of these functions are delegation functions, called by derived class functions of the same name. These functions couldn't be called directly in basic_tree, because the need for more information. So, the functions are defined in the public interface of the derived trees, and subsequently called in basic_tree, along with a pointer to the derived tree object (this) which is delegating to basic_tree. Also among the protected functions are four functions which are defined to allocate and deallocate memory for stored_type objects and tree_type objects. All memory allocation and deallocation of these objects in both basic_tree, and all derived trees, take place through these protected members. This makes it easier to modify any of the tree container classes to use a different memory allocation model.

At the bottom of the class declaration, the private data members are declared. The data member,
container_type children;
is declared protected, and is the only data member which is used directly by the derived tree classes. The data member,
stored_type* pElement;
declares a pointer to the data which will be stored in the node object. Next, the member,
mutable tree_type* pParent_node;
declares a pointer to the parent node. It's declared as mutable, to make it possible to change the parent node of const objects. The next data member,
is the container for any possible child nodes. The type container_type is the third template parameter for basic_tree, which is defined and passed from either tree, multitree, or unique_tree as a std::set or std::multiset, or from sequential_tree as a std::vector. The data member, static tClone_fcn pClone_fcn; defines a pointer to a clone function which may be set for clone operations for the stored_type. This member is declared as static, because the function should not only be used for the root node, but for every node in the tree structure. The data members, stored_type_allocator and tree_type_allocator are used for the default memory model for the TCL. If you need to use custom allocators for the TCL, you can replace the types of these data members with your own defined type.

There are only a handful of small functions defined in basic_tree.inl. Comments provide the details of the implementation of these operations.