<h1>
Tree Container Library: Examples - unique_tree example explanation
</h1>
<hr />
<p>
This bit of code 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 included file unique_tree_example_explanation.htm. <br/>
A source file of this example is also included in the download. <br/>
This example is compatible with versions 3.50 and higher of the TCL. The latest version of the TCL
can be downloaded from the <a href='/tree_container_library/download.php'>TCL download page</a>.
</p>
<p>
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 <i>Enable minimal rebuild</i> option for successful compilation.
Also for VC 6.0 users, the normal <code>#pragma warning (disable : xxxx)</code> directive
is necessary to avoid the compiler warnings.
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
Line 9 begins the declaration of the class CFamilyMember, which will be the <code>stored_type</code> 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
stored_type objects with a valid 'key' member. Furthermore, this constructor will be used to
implicitely create CFamilyMember objects in unique_tree operations.
</p>
<p>
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.
</p>
<p>
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, <code>ssn</code> will be used as the 'key' member, or 'key' field. The member <code>age</code> will
be used for the key field for the
node_order_compare_type
comparisons, explained immediately below.
</p>
<p>
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.
</p>
<p>
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 <code>stored_type</code> which will be CFamilyMember. The second template parameter defines the <code>node_compare_type</code>.
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 <code>age</code> member of the class, the unique_tree's
ordered_iterators will iterate over a nodes children according to the age member of each node.
</p>
<p>
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.
</p>
<p>
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 <b>not</b> 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.
</p>
<p>
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 <code>allow_orphans</code> 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 <i>orphan state</i>. In this example, we will populate
the unique_tree twice. Once with orphans disabled, and once with orphans enabled.
</p>
<p>
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
<i>orphan state</i> 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.
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
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 <b>does</b> exist in the unique_tree <i>somewhere</i>, 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.
</p>
<p>
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 <code>find_deep()</code> 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 <code>find_deep()</code> operation again in line 205. This line simplifies the operation even
more, by using the CFamilyMember constructor implicitely.
</p>
<p>
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.
</p>
Submit an article or tip