The Tree Container Library

This bit of code (click on the code link to the right) shows the polymorphic behavior that the TCL is capable of. This particular example uses the unique_tree to demonstrate the polymorphic behavior, but all three tree containers exhibit this functionality. The code illustrates how the TCL's clone() operation enables the containers to allow the storage of derived objects without slicing.
A source file of this example can be downloaded here.
This example is compatible with versions 3.50 and higher of the TCL. The latest version of the TCL can be downloaded from the TCL download page.

This polymorphic example, as well as the library, is now compatible with Visual C++ 6.0. For this compiler, users need to un-check the Enable minimal rebuild option for successful compilation. Also for VC 6.0 users, the normal #pragma warning (disable : xxxx) directive is necessary to avoid the compiler warnings.

In this example, I use a class hierarchy which might be used in the property rental management business. A tree structure is to contain nodes corresponding to different rental types, such as properties, buildings, units (apartments, suites, rooms), parking lots, parking spots, etc. We will be building a tree structure like the one shown in a link to the right. Since we will be creating classes for these different types, we will derive them from a common base type, CRental, which will be the type we will store in our tree container. The example will show that no slicing will occur when inserting nodes of the derived types.
A sample of the results to the console is also given to the right.

Line 1 is used for Visual Studio compilers. Those using MS compilers can un-comment this line.
Lines 2 - 4 include needed headers from the STL. Line 5 includes the unique_tree header file. A forward declaration of our base class, which will be our stored_type, is given in line 8. A namespace is declared in lines 10 - 15, which declare some needed functions.

Line 17 begins the definition of our base class, CRental. Line 20 defines a default constructor for the base class. Like the STL, a default constructor must be provided for types stored in the tree containers. The constructor in line 21 is mainly for convenience, and also to provide an implicit conversion of an integer to a CRental Object, for the insertion operations, covered below. Lines 22 and 23 define the constructor which the derived classes will call to set the base data members. Since this is a base class, we need to remember to make the destructor virtual, as in line 24. Line 26 defines a virtual function which is used to return a string indicating the object type. This will be the function we will be watching closely, which will indicate if the tree container is indeed polymorphic. Line 27 defines our virtual clone function, also known as a virtual constructor. This will get used indirectly by the tree container to provide a new object of the correct type. The use of clone functions, or virtual constructors, has become somewhat of a C++ idiom or pattern, and you can find information on this subject in many popular C++ books. Line 29 defines the less-than operator, which will be used to determine the node order in our unique_tree. It compares the rental_no of the CRental objects, and since we are using a unique_tree, we will need to insure that this number is unique in every object we insert in the tree. Lines 30 - 37 provide more public interface operations we will need for this example. Notice that we are making all operations, including the virtual operations, const. This will allow us to access these functions with const_iterators. Lines 40 - 41 declare two base class data members.

Lines 44 - 100 define the derived classes for our tree structure. The definition of CProperty begins on line 44. It's constructor in lines 48 - 54 is used to create property objects, and it initializes it's base class with the first two parameter, while setting it's own data members with the last two parameters. Line 57 overrides the virtual function which will show us if the tree is polymorphic. Line 58 overrides the virtual clone operation, and returns a new object of it's own type.

Lines 65 - 100 define CBuilding and CUnit, and are very similar to the definitions of CProperty, but with different data members, so I will not discuss them in detail.

Line 102 defines a function which will be passed to the tree's set_clone() operation. The function signature of this operation is

• stored_type* clone_fcn(const stored_type&)

The function simply calls the clone() operation on the passed object, and returns it's result. If the tree container has this function supplied, it will use this function to create new objects of stored_type, and avoid object slicing.

Line 107 starts the main function. Line 109 declares the unique_tree we will be using in our example, and sets it's root node. Lines 112 - 116 populate and print the unique_tree without first supplying a clone operation to unique_tree. In the display for this first output, you'll notice that all nodes are of type unknown indicating that all node objects were sliced.

Lines 118 - 124 clear, load, and print the unique_tree again, but supply a clone operation first. The display for the second tree structure shows the inserted objects did not get sliced, as they show their correct types. Stepping through the code will also show what is going on during the insertions, and that the derived clone() operations are being used to make copies of the inserted objects.

The function starting on line 129 populates the unique_tree. All insert operations use the insert(parent, child) operation, which is available only to unique_tree. Lines 131 - 134 insert the property objects. Lines 136 - 144 insert the building objects. Lines 147 - 173 insert the unit objects. Since we did not allow orphans for this unique_tree, we need to insure we insert the parents before their children and descendants. If we were to allow orphans, with the allow_orphan() operation, it would not matter what order we perform the insertions in. (You can try this out as an exercise).

Notice in line 132, that the first passed argument makes use of the single parameter constructor for CRental. Objects of the base class, CRental can be used for the first argument, because this parameter is used only to find the parent in which to insert the child. Also notice on all remaining insert operations in this function, that it's not necessary to explicitly use the CRental constructor. That constructor will conveniently convert an integer which is passed as the first argument to a CRental object.

The last two functions, print_tree() and is_last_child() are covered in detail in the generic example.