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

Tree Container Library

, 22 Aug 2007 Zlib
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 - Polymorphic Example Explanation
</h1>
<hr />

<p>
	This bit of code shows the polymorphic behavior that the TCL is capable of.   
	This particular example uses the <code>unique_tree</code> 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.<br/>
	A source file of this example is included with this 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 polymorphic 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>
	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 <i>rental types</i>, 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. <br/>
	A sample of the results to the console is also in this download.
</p>
<p>
	Line 1 is used for Visual Studio compilers.  Those using MS compilers can un-comment this line.<br/>
	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 <code>stored_type</code>, is given
	in line 8.  A namespace is declared in lines 10 - 15, which declare some needed functions.
</p>
<p>
	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 <i>virtual constructor</i>. 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 <code>rental_no</code> 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.
</p>
<p>
	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.
</p>
<p>
	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.
</p>
<p>
	Line 102 defines a function which will be passed to the tree's <code>set_clone()</code> operation.
	The function signature of this operation is 
</p>
<ul>
	<li>stored_type* clone_fcn(const stored_type&amp;)</li>
</ul>
<p>
	The function simply calls the <code>clone()</code> 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.
</p>
<p>
	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 <i>unknown</i> indicating that all node objects were sliced.  
</p>
<p>
	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.
</p>
<p>
	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 
	<code>allow_orphan()</code> operation, it would not matter what order we perform the insertions in.
	(You can try this out as an exercise).
</p>
<p>
	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.
</p>
<p>
	The last two functions, <code>print_tree()</code> and <code>is_last_child()</code> are covered in detail
	in the generic example.
</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 | Terms of Use | Mobile
Web03 | 2.8.1411028.1 | Last Updated 22 Aug 2007
Article Copyright 2006 by Mitchel Haas
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid