The Tree Container Library

This bit of code (click on the code link to the right) shows the unique_tree container at work. It uses functions to perform many of the same operations performed in the generic example. The code illustrates how the unique_tree container is used. The code can be viewed an printed from the icon to the right.
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 generic 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.

The example inserts objects of the class CFamilyMember into a unique_tree, to form a family tree. Nodes are inserted in a linear manner, with no guarantees that the parent will be inserted before any of it's child nodes. Depending on whether orphans are allowed or not, not all of nodes will be inserted successfully. A sample of the results to the console is also given to the right. Please insure that you have downloaded version 1.08 or greater of the TCL for this example.

The #include in line 1 is commented out. Microsoft compilers need this line, so if you're compiling with a microsoft compiler, you can un-comment this line. Line 2 includes the header for unique_tree. Since we will be working with the unique_tree container exclusively, we won't need to include the header for tree and multitree. Lines 3 - 7 include STL needed headers.

Line 9 begins the declaration of the class CFamilyMember, which will be the stored_type used in unique_tree. It will be objects of this class that will be stored in the tree nodes. Just like the STL containers, objects stored in the tree containers need default constructors, which is supplied for CFamilyMember in line 12. The constructor accepting one argument in line 13 is used to create elements with a valid 'key' member. Furthermore, this constructor will be used to implicitely create CFamilyMember objects in unique_tree operations, as explained in unique tree usage.

The constructor in line 14 - 15 is the constructor which is used to create a valid CFamilyMember object to store in the unique_tree container. Lines 17 - 20 define a less-than operator for the class. Since we will be using the default std::less<CFamilyMember> as the second template parameter for the unique_tree declaration, this less-than operator will be used for the node_compare_type. Since the operation compares the ssn class member, the ssn class member is referred to as the 'key' member.

In line 22, get_ssn() is defined to return the ssn number. In this example, the ssn number is a three digit number, to make the example easier to follow. line 23, get_age() is defined for use of the ordered_iterator operations, described further below. Lines 24 - 29 define a function, get_name_and_age(), which returns a string containing the name and age of the person. Lines 33 - 35 declare the class member variables. In this example, ssn will be used as the 'key' member, or 'key' field. The member age will be used for the key field for the node_order_compare_type comparisons, explained immediately below.

Lines 38 - 44 define the comparison function object mentioned above. This function object is used as the third template parameter for our unique_tree, defined on line 46; This comparison operation compares the age members, and is used to set the child node traversal order of the ordered_iterators.

The typedef in line 46 declares the unique_tree type we will be using in this example. Let's examine this declaration closely. The first template parameter defines the stored_type which will be CFamilyMember. The second template parameter defines the node_compare_type. In this case, we explicitly supply the same type as the default, std::less<CFamilyMember>. We need to explicitly provide this if we will be providing the third template parameter. This second template parameter instructs the unique_tree to use the less-than operator of CFamilyMember, which compares the ssn members of the class objects, thus making ssn the 'key' member. The third template parameter specifies a comparison function object (defined below) which specifies the node_order_compare_type. This is used to set the order of the ordered iterators. Since the comparison function object compares the age member of the class, the unique_tree's ordered_iterators will iterate over a nodes children according to the age member of each node.

Line 48 declares a namespace for needed functions and variables. Lines 50 - 91 declare and define functions which will be used to populate and print the unique_tree. The function starting on line 50, is_last_child(), is similar to the one in the generic example. This function is templatized also, to pass in the type of iterators to be used. Refer also the generic example documentation on a description on how this function works.

Line 62 begins the function which prints the unique_tree contents. You will notice right away that this is a template function. What isn't immediately apparent, though, that the template parameter is not used in the function signature. So, when this function is called, the template parameter must be explicitly specified in the function call. This is done in lines 131, 140, and 145. The template parameter specifies the iterator type to use to traverse the child nodes. This function uses the same techniques to print the contents of the unique_tree as the generic example. The only difference is the iterators that are used to traverse the child nodes. In this function, the type of iterators can either be standard child iterators or ordered_iterators. Line 66 declares the iterators using the template parameter. Line 67 calls the appropriate overloaded function, depending on the type of iterator, to set the iterator values. The rest of the function is identical to the function given in the generic example. Refer to the documentation there for a description on how the code works.

Lines 93 - 122 declare an array of data that will be used to populate the unique_tree. Each array element contains a data pair. The first pair member is the ssn of the parent node in which to insert the second pair member. Looking at the first element in the array, a node is to be created for Jim McAvoy, which is to be inserted in a node which has the ssn equal to 555. Notice that the nodes are in no particular order. Most interesting, you'll notice that some of the children are listed before their parents or other ancestors. This could have a large impact on the success of the insertions. With allow_orphans off, any attempt to insert a child node within a parent node using insert(parent, child) when the parent is not present in the unique_tree, will result in a failed insertion. The insertion will succeed, however, if allow_orphans is enabled. When this happens, a temporary (orphan) node is created for the parent, until the parent node is actually inserted, in which case the orphan will be updated and removed from the orphan state. In this example, we will populate the unique_tree twice. Once with orphans disabled, and once with orphans enabled.

Line 124 starts main(). Line 126 declares the unique_tree we will be using throughout this example, and sets the root node. The root node is set to John McAvoy, with ssn = 555, and age = 87. Lines 128 - 133 load and print the unique_tree with orphans disabled (default case). Loading the tree with orphans disabled will result in many failed insertions, since the order of data does not guarantee that all parent nodes will be inserted before their children are. Lines 135 - 141 re-load and print the unique_tree with orphans enabled. With orphans enabled, all insertions of the form insert(parent, child) are guaranteed to succeed, even when parent does not yet exist in the unique_tree. In this case, the parent (and it's descendants) will remain in an orphan state until that node is actually inserted into the tree, in which case that insertion will bring the orphan out of the orphan state, and put it in it's specified place in the tree. Lines 143 - 146 print the same previously printed tree, but print the tree using ordered_iterators instead of the standard iterators. Using the standard iterators, the child nodes will be printed out in an order dictated by the ssn. Using ordered_iterators, the child nodes will be printed in an order dictated by the age member. Line 148 calls a function which tests the unique_tree, by trying to insert nodes which already exist in the unique_tree.

Line 153 begins the function used to load the unique_tree. When successful, the unique_tree will have the structure shown in figure 2 above. The figure shows the order of insertion in parentheses (), and shows those nodes which are inserted before their ancestors in a different color. These nodes will not be successfully inserted when allow_orphans is disabled. The loop in lines 157 - 163 insert all other nodes in the unique_tree. Line 160 does the actual insertion. All insertions use the insert operation insert(parent, child). This line inserts each element in the Family array, using the first array element pair member in the element as the parent ssn, and the second array element pair member as the child node to be inserted. An iterator is returned from the operation indicating the success of the insert operation. If successful, the iterator will point to the inserted node. If unsuccessful, the iterator will return the end iterator of node which the insertion was performed. Line 161 checks the iterator for success, and if successful, checks to see if the inserted node was inserted as an orphan. If so, line 162 prints a message indicating that the node was inserted as an orphan.

The functions starting on lines 166 and 174 are overloaded functions, which set the beginning and ending iterators for the passed node. Which function is called will depend on the type of iterators passed by the calling function.

Line 182 begins the function which tests the unique_tree for insertions of identical nodes. The unique_tree guarantees that all nodes in the tree will be unique. This function verifies this behavior. Line 185 declares an iterator which will be used to test the success of the insert operations. Line 188 attempt to insert a duplicate node into the root, with a standard insert(child) operation. Even though the node does not exist as a child node of the root, the node does exist in the unique_tree somewhere, so the insertion will fail. Line 193 make the same kind of insertion attempt, but with a different node which already exists somewhere in the unique_tree.

Lines 197 - 202 attempt to insert a node which is already present, into a node other than the root node with a standard insert(child). A node with ssn = 827 is attempted to be inserted in node containing Connie Delay. Looking at figure 2 above, you'll see that these two nodes are not even in the same main branch, but the tree still does not allow the insertion. Notice the find_deep() operation in line 198. This operation makes use of the constructor for CFamilyMember which accepts a single argument. Lines 204 - 209 attempt the same type of insertion, but with different parent and child nodes. Notice the find_deep() operation again in line 205. This line simplifies the operation even more, by using the CFamilyMember constructor implicitely.

Lines 211 - 214 attempt to insert a node which is already present with the insert(parent, child) operation. Notice that line 212 also takes advantage of using the CFamilyMember one-argument constructor implicitly, when passing the parent argument.