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 "unique_tree.h"
  3 #include &lt;string&gt;
  4 #include &lt;sstream&gt;
  5 #include &lt;vector&gt;
  6 #include &lt;cassert&gt;
  7 #include &lt;iostream&gt;
  8
  9 class CFamilyMember
 10 {
 11 public:
 12 	CFamilyMember() : ssn(0), age(0) {}
 13 	CFamilyMember(int ssn_) : ssn(ssn_), age(0) {}
 14 	CFamilyMember(int ssn_, const std::string& name_, int age_) 
 15 		: ssn(ssn_), age(age_), name(name_)  {}
 16 
 17 	friend bool operator &lt;(const CFamilyMember& lhs, const CFamilyMember& rhs)
 18 	{
 19 		return lhs.ssn &lt; rhs.ssn;
 20 	}
 21 
 22 	int get_ssn() const { return ssn; }
 23 	int get_age() const { return age; }
 24 	std::string get_name_and_age() const
 25 	{
 26 		std::ostringstream ostr;
 27 		ostr &lt;&lt; name &lt;&lt; ",  age: " &lt;&lt; age;
 28 		return ostr.str();
 29 	}
 30 
 31 // data
 32 private:
 33 	int ssn;
 34 	int age;
 35 	std::string name;
 36 };
 37
 38 struct CAgeCompare
 39 {
 40 	bool operator()(const CFamilyMember& lhs, const CFamilyMember& rhs)
 41 	{
 42 		return lhs.get_age() &lt; rhs.get_age();
 43 	}
 44 };
 45 
 46 typedef unique_tree&lt;CFamilyMember, std::less&lt;CFamilyMember&gt;, CAgeCompare&gt; unique_tree_type;
 47
 48 namespace utility
 49 {
 50 	template&lt;typename iterator_type&gt; bool is_last_child(const unique_tree_type* node)
 51 	{
 52 		unique_tree_type* parent = node-&gt;parent();
 53
 54 		iterator_type it, it_end;
 55 		get_begin_end_iterators(*parent, it, it_end);
 56 
 57 		--it_end;
 58 		return it_end-&gt;get_ssn() == node-&gt;get()-&gt;get_ssn();
 59
 60 	}
 61	
 62 	template&lt;typename iterator_type&gt; void print_tree(const unique_tree_type& Tree, const int depth)
 63 	{
 64 		std::cout &lt;&lt; Tree.get()-&gt;get_name_and_age() &lt;&lt; std::endl;
 65
 66 		iterator_type it, it_end;
 67 		get_begin_end_iterators(Tree, it, it_end);
 68 		for ( ; it != it_end; ++it ) {
 69 			for ( int i = 0; i &lt; depth; ++i ) {
 70 				const unique_tree_type* parent = &Tree;
 71 				for ( int j = depth - 1; j &gt; i; --j )
 72 					parent = parent-&gt;parent();
 73 
 74 				std::cout &lt;&lt;  (is_last_child&lt;iterator_type&gt;(parent) ? " " : "|");
 75 
 76 				std::cout &lt;&lt; std::string(2, ' ');
 77 			}
 78 			std::cout &lt;&lt; "|" &lt;&lt; std::endl;
 79 			std::cout &lt;&lt; std::string(depth * 3 + 1, ' ') &lt;&lt; "- ";
 80 			print_tree&lt;iterator_type&gt;(*it.node(), depth + 1);
 81 		}
 82 	}
 83
 84 	void populate_tree(unique_tree_type& Tree);
 85 	void test_multiple_inserts(unique_tree_type& Tree);
 86 	void get_begin_end_iterators(	const unique_tree_type& Tree, 
 87 									unique_tree_type::const_iterator& begin, 
 88 									unique_tree_type::const_iterator& end);
 89 	void get_begin_end_iterators(	const unique_tree_type& Tree, 
 90 									unique_tree_type::const_ordered_iterator& begin, 
 91 									unique_tree_type::const_ordered_iterator& end);
 92
 93 	std::pair&lt;int, CFamilyMember&gt; Family[] =
 94 	{
 95 		std::make_pair(555, CFamilyMember(562, "Jim McAvoy", 59)),
 96 		std::make_pair(562, CFamilyMember(694, "Carmen Palmer", 40)),
 97 		std::make_pair(741, CFamilyMember(814, "Connie Delay", 3)),
 98 		std::make_pair(694, CFamilyMember(749, "Nick Palmer", 17)),
 99 		std::make_pair(694, CFamilyMember(738, "Patty Palmer", 13)),
100 		std::make_pair(694, CFamilyMember(741, "Terri Delay", 20)),
101 		std::make_pair(555, CFamilyMember(573, "Sally Turner", 56)),
102 		std::make_pair(618, CFamilyMember(798, "Mark Arnold", 11)),
103 		std::make_pair(573, CFamilyMember(618, "Kim Arnold", 34)),
104 		std::make_pair(637, CFamilyMember(799, "Steve Lewis", 4)),
105 		std::make_pair(573, CFamilyMember(637, "Joan Lewis", 32)),
106 		std::make_pair(573, CFamilyMember(648, "Lee Turner", 36)),
107 		std::make_pair(637, CFamilyMember(722, "Tammi Lewis", 6)),
108 		std::make_pair(637, CFamilyMember(751, "Stan Lewis", 8)),
109 		std::make_pair(783, CFamilyMember(835, "Phil Turner", 2)),
110 		std::make_pair(644, CFamilyMember(783, "Pam Turner", 20)),
111 		std::make_pair(573, CFamilyMember(644, "Darryl Turner", 38)),
112 		std::make_pair(729, CFamilyMember(872, "Tammy Stewart", 3)),
113 		std::make_pair(729, CFamilyMember(893, "Lee Stewert", 6)),
114 		std::make_pair(768, CFamilyMember(827, "Lenny Kinney", 2)),
115 		std::make_pair(633, CFamilyMember(775, "Frank McAvoy", 23)),
116 		std::make_pair(633, CFamilyMember(729, "Barb Stewart", 25)),
117 		std::make_pair(672, CFamilyMember(768, "Dan Kinney", 20)),
118 		std::make_pair(568, CFamilyMember(633, "Bill McAvoy", 43)),
119 		std::make_pair(568, CFamilyMember(672, "Sue Kinney", 45 )),
120 		std::make_pair(555, CFamilyMember(568, "Pete McAvoy", 63))
121 	};
122 }
123
124 int main(int argc, char* argv[])
125 {
126 	unique_tree_type myFamilyTree(CFamilyMember(555, "John McAvoy", 87));  // declare tree
127
128 	// populate and print tree with allow orphans OFF
129 	std::cout &lt;&lt; "allow orphans OFF" &lt;&lt; std::endl &lt;&lt; std::endl;
130 	utility::populate_tree(myFamilyTree);
131 	utility::print_tree&lt;unique_tree_type::const_iterator&gt;(myFamilyTree, 0);
132 	myFamilyTree.clear();
133 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
134
135 	// populate and print tree with allow orphans ON
136 	myFamilyTree.allow_orphans(true);
137 	std::cout &lt;&lt; "allow orphans ON" &lt;&lt; std::endl &lt;&lt; std::endl;
138 	utility::populate_tree(myFamilyTree);
139 	std::cout &lt;&lt; std::endl;
140 	utility::print_tree&lt;unique_tree_type::const_iterator&gt;(myFamilyTree, 0);
141 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
142
143 	// print tree using ordered_iterators
144 	std::cout &lt;&lt; "using ordered_iterator" &lt;&lt; std::endl &lt;&lt; std::endl;
145 	utility::print_tree&lt;unique_tree_type::const_ordered_iterator&gt;(myFamilyTree, 0);
146 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
147
148 	utility::test_multiple_inserts(myFamilyTree);
149
150 	return 0;
151 }
152
153 void utility::populate_tree(unique_tree_type& Tree)
154 {
155 	// populate unique_tree
156 
157 	for (int i = 0; i &lt; 26; ++i) {
158 		CFamilyMember fmember = utility::Family[i].second;
159
160 		unique_tree_type::const_iterator it = Tree.insert(utility::Family[i].first, fmember);
161 		if ( it != Tree.end() && it.node()-&gt;is_orphan() )
162 			std::cout &lt;&lt; "Node " &lt;&lt; it-&gt;get_name_and_age() &lt;&lt; " inserted as orphan." &lt;&lt; std::endl;
163 	}
164 }
165
166 void utility::get_begin_end_iterators(	const unique_tree_type& Tree, 
167 										unique_tree_type::const_iterator& begin, 
168 										unique_tree_type::const_iterator& end)
169 {
170 	begin = Tree.begin();
171 	end = Tree.end();
172 }
173
174 void utility::get_begin_end_iterators(	const unique_tree_type& Tree, 
175 										unique_tree_type::const_ordered_iterator& begin, 
176 										unique_tree_type::const_ordered_iterator& end)
177 {
178 	begin = Tree.ordered_begin();
179 	end = Tree.ordered_end();
180 }
181
182 void utility::test_multiple_inserts(unique_tree_type& Tree)
183 {
184 	std::cout &lt;&lt; "Testing for multiple inserts." &lt;&lt; std::endl &lt;&lt; std::endl;
185 	unique_tree_type::iterator it;
186
187 	// try inserting duplicate node for Barb Stewart using standard insert in root
188 	it = Tree.insert(CFamilyMember(729, "Duplicate", 0));
189 	if (it == Tree.end())
190 		std::cout &lt;&lt; "Couldn't insert duplicate SSN 729 into root" &lt;&lt; std::endl;
191 
192 	// try inserting node for Connie Delay using standard insert in root
193 	it = Tree.insert(CFamilyMember(814, "Dup", 0));
194 	if (it == Tree.end())
195 		std::cout &lt;&lt; "Couldn't insert duplicate SSN 814 into root" &lt;&lt; std::endl;
196
197 	// try inserting node for Lenny Kinney in Connie Delay using standard insert
198 	unique_tree_type::iterator it_ins_from = Tree.find_deep(CFamilyMember(814));
199 	assert (it_ins_from != Tree.end());
200 	it = it_ins_from.node()-&gt;insert(CFamilyMember(827, "Duplicate", 0));
201 	if (it == it_ins_from.node()-&gt;end())
202 		std::cout &lt;&lt; "Couldn't insert duplicate SSN 827 in other branch." &lt;&lt; std::endl;
203
204 	// try to insert node for John McAvoy in node Phil Turner using standard insert
205 	it_ins_from = Tree.find_deep(835);  // note use of implicit construction of CFamilyMember
206 	assert(it_ins_from != Tree.end());
207 	it = it_ins_from.node()-&gt;insert(CFamilyMember(555, "Duplicate", 0));
208 	if (it == it_ins_from.node()-&gt;end())
209 		std::cout &lt;&lt; "Couldn't insert duplicate SSN 555 in branch" &lt;&lt; std::endl;
210 
211 	// try to insert node Pam Turner in node Patty Palmer using insert(parent, child)
212 	it = Tree.insert(738, CFamilyMember(783, "Duplicate", 0));
213 	if (it == Tree.end())
214 		std::cout &lt;&lt; "Couldn't insert duplicate SSN 783 in node 736 using insert(parent, child)" &lt;&lt; std::endl;
215 }

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