Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

Tree Container Library

, 22 Aug 2007
A generic template class library for storing data in a tree-like structure.
tcldoc_40802.zip
TCL.chm
tcldoc_4_07_01.zip
TCL.chm
tcl_3_55.zip
basic_tree.inl
associative_tree.inl
descendant_iterator.inl
ordered_iterator.inl
multitree.inl
tree.inl
child_iterator.inl
unique_tree.inl
sequential_tree.inl
tcl_4_07.zip
sequential_tree.inl
tree.inl
unique_tree.inl
associative_tree.inl
basic_tree.inl
descendant_iterator.inl
descendant_node_iterator.inl
multitree.inl
tcl_4_08.zip
associative_tree.inl
basic_tree.inl
descendant_iterator.inl
descendant_node_iterator.inl
multitree.inl
sequential_tree.inl
tree.inl
unique_tree.inl
TCL.chm
tcl_test_suite_081606.zip
descendant_iterator_tester.inl
modifying_algorithm_tester.inl
nonmodifying_algorithm_tester.inl
ordered_iterator_checker.inl
sequential_tree_tester.inl
stl_algorithm_tester.inl
unique_tree_tester.inl
associative_tree_tester.inl
basic_tree_tester.inl
child_iterator_tester.inl
child_sequential_iterator_tester.inl
tree_container_library_demo.zip
polymorphic_example_results.jpg
sequential_tree_example_diagram.jpg
sequential_tree_example_explanation.rtf
sequential_tree_example_results.jpg
unique_tree_example_diagram.jpg
unique_tree_example_explation.rtf
unique_tree_example_results.jpg
generic_example_diagram.jpg
generic_example_explanation.rtf
generic_example_results.jpg
polymorphic_example_diagram.jpg
polymorphic_example_explanation.rtf
tree_container_library_demos.zip
generic_example_diagram.jpg
generic_example_results.jpg
polymorphic_example_diagram.jpg
polymorphic_example_results.jpg
sequential_tree_example_diagram.jpg
sequential_tree_example_results.jpg
unique_tree_example_diagram.jpg
unique_tree_example_results.jpg
tree_container_library_src.zip
multitree.inl
basic_tree.inl
Tree.inl
unique_tree.inl
tree_container_lib_src.zip
basic_tree.inl
associative_tree.inl
unique_tree.inl
Tree.inl
sequential_tree.inl
multitree.inl
<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&lt;CFamilyMember&gt; 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&lt;CFamilyMember&gt;.  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>


By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The zlib/libpng License

Share

About the Author

Mitchel Haas
Software Developer Datasoft Solutions
United States United States
I'm a c++ programmer in the midwest, now using VC7 at work and at home. I enjoy creating generic libraries, and template based programming.
 
I also enjoy web development (xhtml, css, javascript, php).

| Advertise | Privacy | Mobile
Web04 | 2.8.140905.1 | Last Updated 22 Aug 2007
Article Copyright 2006 by Mitchel Haas
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid