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
<html>
<head>
<title>
Tree Container Library: unique_tree Example Code
</title>
</head>
<body>
<pre>
<code>
  1 //#include "stdafx.h"
  2 #include "tree.h"
  3 #include "multitree.h"
  4 #include "unique_tree.h"
  5 #include &lt;cassert&gt;
  6 #include &lt;string&gt;
  7 #include &lt;iostream&gt;
  8
  9 namespace utility
 10 {
 11 	template&lt;typename T&gt; void load_tree(T&amp; alpha_tree );
 12 	template&lt;typename T&gt; void traverse_tree(T&amp; alpha_tree);
 13 
 14 	template&lt;typename T&gt; void print_tree(T&amp; alpha_tree, const int depth)
 15 	{
 16 		std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; std::endl;
 17 
 18 		typename T::const_iterator it = alpha_tree.begin(), it_end = alpha_tree.end();
 19 		for ( ; it != it_end; ++it ) {
 20 			for ( int i = 0; i &lt; depth; ++i ) {
 21 				T* parent = &alpha_tree;
 22 				for ( int j = depth - 1; j &gt; i; --j )
 23 					parent = parent-&gt;parent();
 24 
 25 				std::cout &lt;&lt;  (is_last_child(parent) ? " " : "|");
 26 
 27 				std::cout &lt;&lt; std::string(2, ' ');
 28 			}
 29 			std::cout &lt;&lt; "|" &lt;&lt; std::endl;
 30 			std::cout &lt;&lt; std::string(depth * 3 + 1, ' ') &lt;&lt; "- ";
 31 			print_tree(*it.node(), depth + 1);
 32 		}
 33 	}
 34 
 35 	template&lt;typename T&gt; bool is_last_child(const T* node)
 36 	{
 37 		T* parent = node-&gt;parent();
 38 		typename T::const_iterator it = parent-&gt;end();
 39 		--it;
 40 		return it-&gt;get_text() == node-&gt;get()-&gt;get_text();
 41 	}
 42 }
 43 
 44 class CAlpha
 45 {
 46 public:
 47 	CAlpha()  {}
 48 	CAlpha(const std::string&amp; text_ ) : text(text_) {}
 49 	CAlpha(const char* text_ ) : text(text_) {}
 50 	~CAlpha() {}
 51 
 52 	friend bool operator &lt; (const CAlpha&amp; lhs, const CAlpha&amp; rhs) 
 53 		{ return lhs.get_text() &lt; rhs.get_text(); }
 54 	std::string get_text() const { return text; }
 55 
 56 private:
 57 	std::string text;
 58 };
 59 
 60 int main(int argc, char* argv[])
 61 {
 62 	// load and print tree&lt;&gt;
 63 	tree&lt;CAlpha&gt; alpha_tree(CAlpha("tree&lt;&gt;"));
 64 	
 65 	utility::load_tree( alpha_tree );
 66 	utility::print_tree(alpha_tree, 0);
 67 	utility::traverse_tree(alpha_tree);
 68 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 69 
 70 	// load and print multitree&lt;&gt;
 71 	multitree&lt;CAlpha&gt; alpha_multitree(CAlpha("multitree&lt;&gt;"));
 72 	
 73 	utility::load_tree( alpha_multitree );
 74 	utility::print_tree( alpha_multitree, 0 );
 75 	utility::traverse_tree(alpha_multitree);
 76 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 77 
 78 	// load and print unique_tree&lt;&gt;
 79 	unique_tree&lt;CAlpha&gt; alpha_uniquetree(CAlpha("unique_tree&lt;&gt;"));
 80 	
 81 	utility::load_tree( alpha_uniquetree );
 82 	utility::print_tree( alpha_uniquetree, 0 );
 83 	utility::traverse_tree(alpha_uniquetree);
 84 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 85 
 86 	return 0;
 87 }
 88 
 89 template&lt;typename T&gt; void utility::load_tree(T&amp; alpha_tree)
 90 {
 91 	// create a child iterator
 92 	typename T::iterator it;  
 93 
 94 	// insert first node, A, and keep an iterator to it's node
 95 	it = alpha_tree.insert(CAlpha("A"));
 96 	assert(it != alpha_tree.end() &amp;&amp; it-&gt;get_text() == "A" );
 97 	// try to insert another A.  Should fail for tree &amp; unique_tree
 98 	it = alpha_tree.insert(CAlpha("A"));
 99 	if ( it == alpha_tree.end() )
100 		std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; ": Couldn't insert second A." &lt;&lt; std::endl;
101 
102 	// insert D and E under A
103 	it = alpha_tree.begin();
104 	assert(it != alpha_tree.end() &amp;&amp; it-&gt;get_text() == "A");
105 	typename T::iterator child_it = it.node()-&gt;insert(CAlpha("D"));
106 	it.node()-&gt;insert(CAlpha("E"));
107 	assert(child_it != it.node()-&gt;end() &amp;&amp; child_it-&gt;get_text() == "D");
108 
109 	it = child_it;
110 	// insert  J under D
111 	it.node()-&gt;insert(CAlpha("J"));
112 	// insert K under D and remember inserted node
113 	child_it = it.node()-&gt;insert(CAlpha("K"));
114 	assert(child_it != it.node()-&gt;end() &amp;&amp; child_it-&gt;get_text() == "K");
115 	// insert R and S under K
116 	child_it.node()-&gt;insert(CAlpha("R"));
117 	child_it.node()-&gt;insert(CAlpha("S"));
118
119 	// increment it (now at D) to point to E
120 	++it;
121 	// insert L under E
122 	it.node()-&gt;insert(CAlpha("L"));
123 
124 	it = alpha_tree.insert(CAlpha("B"));
125 	// insert second E and F under B
126 	child_it = it.node()-&gt;insert(CAlpha("E"));  // should fail for unique_tree
127 	if ( child_it == it.node()-&gt;end() )
128 		std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; ": Couldn't insert second E." &lt;&lt; std::endl;
129 	child_it = it.node()-&gt;insert(CAlpha("F"));
130 	// insert M under F
131 	it = child_it;
132 	child_it = it.node()-&gt;insert(CAlpha("M"));
133 	// insert T and U under M
134 	child_it.node()-&gt;insert(CAlpha("T"));
135 	child_it.node()-&gt;insert(CAlpha("U"));
136
137 	// insert N under F  (it still points to F)
138 	child_it = it.node()-&gt;insert(CAlpha("N"));
139 	// insert second U and V under N
140 	if ( child_it.node()-&gt;insert(CAlpha("U")) == child_it.node()-&gt;end() ) // should fail for unique_tree
141 		std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; ": Couldn't insert second U." &lt;&lt; std::endl;
142
143 	child_it.node()-&gt;insert(CAlpha("V"));
144 	
145 	it = alpha_tree.insert(CAlpha("C"));
146 	// insert G and H under C
147 	it.node()-&gt;insert(CAlpha("G"));
148 	child_it = it.node()-&gt;insert(CAlpha("H"));
149 	// insert O under H
150 	it = child_it;
151 	child_it = it.node()-&gt;insert(CAlpha("O"));
152 	// try to insert another O
153 	child_it = it.node()-&gt;insert(CAlpha("O")); // should fail for tree/unique_tree
154 	if ( child_it == it.node()-&gt;end() )
155 		std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; ": Couldn't insert second O." &lt;&lt; std::endl;
156
157 	child_it = it.node()-&gt;begin();
158 	assert(child_it != it.node()-&gt;end() &amp;&amp; child_it-&gt;get_text() == "O");
159 	// insert W under O
160 	child_it.node()-&gt;insert(CAlpha("W"));
161 	// insert P under H
162 	it.node()-&gt;insert(CAlpha("P"));
163 
164 	// insert I under C using parent of H (which is C)
165 	child_it = it.node()-&gt;parent()-&gt;insert(CAlpha("I"));
166 	assert(child_it != it.node()-&gt;parent()-&gt;end() &amp;&amp; child_it-&gt;get_text() == "I");
167 	// insert second I under I
168 	it = child_it;
169 	child_it = it.node()-&gt;insert(CAlpha("I"));  // should fail for unique tree
170 	if ( child_it == it.node()-&gt;end() )
171 		std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; ": Couldn't insert second I." &lt;&lt; std::endl;
172
173 	// insert Q under original I
174 	child_it = it.node()-&gt;insert(CAlpha("Q"));
175 	// insert X under Q
176 	it = child_it;
177 	child_it = it.node()-&gt;insert(CAlpha("X"));
178 	// insert Y and Z under X
179 	child_it.node()-&gt;insert(CAlpha("Y"));
180 	child_it.node()-&gt;insert(CAlpha("Z"));
181
182 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl;
183 }
184
185 template&lt;typename T&gt; void utility::traverse_tree(T&amp; alpha_tree)
186 {
187 	std::cout &lt;&lt; std::endl;
188 	
189 	std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; "::pre_order_iterator" &lt;&lt; std::endl;
190 	typename T::pre_order_iterator pre_it = alpha_tree.pre_order_begin();
191 	for ( ; pre_it != alpha_tree.pre_order_end(); ++pre_it ) {
192 		std::cout &lt;&lt; pre_it-&gt;get_text() &lt;&lt; " ";	
193 	}
194 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl;
195 	
196 	std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; "::post_order_iterator" &lt;&lt; std::endl;
197 	typename T::const_post_order_iterator post_it = alpha_tree.post_order_begin();
198 	for ( ; post_it != alpha_tree.post_order_end(); ++post_it ) {
199 		std::cout &lt;&lt; post_it-&gt;get_text() &lt;&lt; " ";	
200 	}
201 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl;
202 	
203 	std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; "::level_order_iterator" &lt;&lt; std::endl;
204 	typename T::const_level_order_iterator level_it = alpha_tree.level_order_begin();
205 	for ( ; level_it != alpha_tree.level_order_end(); ++level_it ) {
206 		std::cout &lt;&lt; level_it-&gt;get_text() &lt;&lt; " ";	
207 	}
208	
209 	std::cout &lt;&lt; std::endl;
210 }
211
</code>
</pre>

<script type="text/javascript" src="/stats/tracker.js.php"></script>
<noscript>
<p>
	<img style="display: none" src="/stats/static.php" alt='site stats'/>
</p>
</noscript>		


</body>
</html>

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.140926.1 | Last Updated 22 Aug 2007
Article Copyright 2006 by Mitchel Haas
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid