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
<html>
<head>
<title>
Tree Container Library: sequential_tree Example Code
</title>
</head>
<body>
<pre>
<code>
  1 //#include "stdafx.h"
  2 #include "sequential_tree.h"
  3 #include &lt;cassert&gt;
  4 #include &lt;string&gt;
  5 #include &lt;iostream&gt;
  6 class CAlpha;
  7 namespace utility
  8 {
  9 	void load_tree(sequential_tree&lt;CAlpha&gt;&amp; alpha_tree );
 10 	template&lt;typename T&gt; void traverse_tree(T&amp; alpha_tree);
 11 
 12 	template&lt;typename T&gt; void print_tree(T&amp; alpha_tree, const int depth)
 13 	{
 14 		std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; std::endl;
 15 
 16 		typename T::const_iterator it = alpha_tree.begin(), it_end = alpha_tree.end();
 17 		for ( ; it != it_end; ++it ) {
 18 			for ( int i = 0; i &lt; depth; ++i ) {
 19 				T* parent = &alpha_tree;
 20 				for ( int j = depth - 1; j &gt; i; --j )
 21 					parent = parent-&gt;parent();
 22 
 23 				std::cout &lt;&lt;  (is_last_child(parent) ? " " : "|");
 24 
 25 				std::cout &lt;&lt; std::string(2, ' ');
 26 			}
 27 			std::cout &lt;&lt; "|" &lt;&lt; std::endl;
 28 			std::cout &lt;&lt; std::string(depth * 3 + 1, ' ') &lt;&lt; "- ";
 29 			print_tree(*it.node(), depth + 1);
 30 		}
 31 	}
 32 
 33 	template&lt;typename T&gt; bool is_last_child(const T* node)
 34 	{
 35 		T* parent = node-&gt;parent();
 36 		typename T::const_iterator it = parent-&gt;end();
 37 		--it;
 38 		return it-&gt;get_text() == node-&gt;get()-&gt;get_text();
 39 	}
 40 }
 41
 42 class CAlpha
 43 {
 44 public:
 45 	CAlpha()  {}
 46 	CAlpha(const std::string&amp; text_ ) : text(text_) {}
 47 	CAlpha(const char* text_ ) : text(text_) {}
 48 	~CAlpha() {}
 49
 50 	friend bool operator &lt; (const CAlpha&amp; lhs, const CAlpha&amp; rhs) 
 51 	{ return lhs.get_text() &lt; rhs.get_text(); }
 52 	std::string get_text() const { return text; }
 53 
 54 private:
 55 	std::string text;
 56 };
 57
 58 bool pred_fcn(const CAlpha&amp; lhs, const CAlpha&amp; rhs)
 59 {
 60 	return lhs.get_text() &gt; rhs.get_text();
 61 }
 62 
 63 struct comp_functor
 64 {
 65 	bool operator() (const CAlpha&amp; lhs, const CAlpha&amp; rhs) const
 66 	{
 67 		return lhs.get_text() &gt; rhs.get_text();
 68 	}
 69 };
 70 
 71 int main(int argc, char* argv[])
 72 {
 73 	// load and print tree&lt;&gt;
 74 	sequential_tree&lt;CAlpha&gt; alpha_tree(CAlpha("sequential_tree&lt;&gt;"));
 75 	
 76 	utility::load_tree( alpha_tree );
 77 	utility::print_tree(alpha_tree, 0);
 78 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 79 
 80 	alpha_tree.sort();
 81 	std::cout &lt;&lt; "Tree root sorted ascending" &lt;&lt; std::endl;
 82 	utility::print_tree(alpha_tree, 0);
 83 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 84 
 85 	alpha_tree.sort_descendants();
 86 	std::cout &lt;&lt; "Whole tree sorted ascending" &lt;&lt; std::endl;
 87 	utility::print_tree(alpha_tree, 0);
 88 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 89 
 90 	alpha_tree.sort(&pred_fcn);
 91 	std::cout &lt;&lt; "Tree root sorted descending" &lt;&lt; std::endl;
 92 	utility::print_tree(alpha_tree, 0);
 93 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 94 
 95 	alpha_tree.sort_descendants(comp_functor());
 96 	std::cout &lt;&lt; "Whole tree sorted descending" &lt;&lt; std::endl;
 97 	utility::print_tree(alpha_tree, 0);
 98 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 99
100 	utility::traverse_tree(alpha_tree);
101 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
102
103 	return 0;
104 }
105
106 void utility::load_tree(sequential_tree&lt;CAlpha&gt;&amp; alpha_tree)
107 {
108 	// create a child iterator
109 	sequential_tree&lt;CAlpha&gt;::iterator it;  
110 
111 	// insert first node, A, and keep an iterator to it's node
112 	it = alpha_tree.insert(CAlpha("A"));
113 	assert(it != alpha_tree.end() &amp;&amp; it-&gt;get_text() == "A" );
114 
115 	// insert D and E under A
116 	it = alpha_tree.begin();
117 	assert(it != alpha_tree.end() &amp;&amp; it-&gt;get_text() == "A");
118 	it.node()-&gt;insert(CAlpha("E"));
119 	it.node()-&gt;insert(CAlpha("D"));
120 
121 	it = it.node()-&gt;begin();
122 	++it;
123 	// insert  J under D
124 	it.node()-&gt;insert(CAlpha("J"));
125 	// insert K under D and remember inserted node
126 	sequential_tree&lt;CAlpha&gt;::iterator child_it = it.node()-&gt;insert(CAlpha("K"));
127 	assert(child_it != it.node()-&gt;end() &amp;&amp; child_it-&gt;get_text() == "K");
128 	// insert R and S under K
129 	child_it.node()-&gt;insert(CAlpha("S"));
130 	child_it.node()-&gt;insert(CAlpha("R"));
131 
132 	// increment it (now at D) to point to E
133 	--it;
134 	// insert L under E
135 	it.node()-&gt;insert(CAlpha("L"));
136
137 	it = alpha_tree.insert(CAlpha("B"));
138 	// insert F under B
139 	child_it = it.node()-&gt;insert(CAlpha("F"));
140 	// insert M under F
141 	it = child_it;
142 	child_it = it.node()-&gt;insert(CAlpha("M"));
143 	// insert T and U under M
144 	child_it.node()-&gt;insert(CAlpha("T"));
145 	child_it.node()-&gt;insert(CAlpha("U"));
146 
147 	// insert N under F  (it still points to F)
148 	child_it = it.node()-&gt;insert(CAlpha("N"));
149 	// insert V under N
150 	child_it.node()-&gt;insert(CAlpha("V"));
151 
152 	it = alpha_tree.begin();
153 	++it;
154 	it = alpha_tree.insert(it, CAlpha("C"));
155 	// insert G and H under C
156 	it.node()-&gt;insert(CAlpha("G"));
157 	child_it = it.node()-&gt;insert(CAlpha("H"));
158 	// insert O under H
159 	it = child_it;
160 	child_it = it.node()-&gt;insert(CAlpha("O"));
161
162 	child_it = it.node()-&gt;begin();
163 	assert(child_it != it.node()-&gt;end() &amp;&amp; child_it-&gt;get_text() == "O");
164 	// insert W under O
165 	child_it.node()-&gt;insert(CAlpha("W"));
166 	// insert P under H
167 	it.node()-&gt;insert(CAlpha("P"));
168
169 	// insert I under C using parent of H (which is C)
170 	child_it = it.node()-&gt;parent()-&gt;insert(CAlpha("I"));
171 	it = child_it;
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 	it = child_it.node()-&gt;insert(CAlpha("Z"));
180 	child_it.node()-&gt;insert(it, CAlpha("Y"));
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.node()-&gt;get()-&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"&gt;&lt;/script>
<noscript>
<p>
	&lt;img style="display: none" src="/stats/static.php" alt='site stats'/>
</p&gt;
</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 | Terms of Use | Mobile
Web03 | 2.8.1411023.1 | Last Updated 22 Aug 2007
Article Copyright 2006 by Mitchel Haas
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid