1 //#include "stdafx.h"
  2 #include "unique_tree.h"
  3 #include <string>
  4 #include <sstream>
  5 #include <vector>
  6 #include <cassert>
  7 #include <iostream>
  8 using namespace tcl;
  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 <(const CFamilyMember& lhs, const CFamilyMember& rhs)
 18 	{
 19 		return lhs.ssn < 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 << name << ",  age: " << 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() < rhs.get_age();
 43 	}
 44 };
 45 
 46 typedef tcl::unique_tree<CFamilyMember, std::less<CFamilyMember>, CAgeCompare> unique_tree_type;
 47
 48 namespace utility
 49 {
 50 	template<typename iterator_type> bool is_last_child(const unique_tree_type* node)
 51 	{
 52 		const unique_tree_type* parent = node->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->get_ssn() == node->get()->get_ssn();
 59
 60 	}
 61	
 62 	template<typename iterator_type> void print_tree(const unique_tree_type& Tree, const int depth)
 63 	{
 64 		std::cout << Tree.get()->get_name_and_age() << 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 < depth; ++i ) {
 70 				const unique_tree_type* parent = &Tree;
 71 				for ( int j = depth - 1; j > i; --j )
 72 					parent = parent->parent();
 73 
 74 				std::cout <<  (is_last_child<iterator_type>(parent) ? " " : "|");
 75 
 76 				std::cout << std::string(2, ' ');
 77 			}
 78 			std::cout << "|" << std::endl;
 79 			std::cout << std::string(depth * 3 + 1, ' ') << "- ";
 80 			print_tree<iterator_type>(*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<int, CFamilyMember> 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 << "allow orphans OFF" << std::endl << std::endl;
130 	utility::populate_tree(myFamilyTree);
131 	utility::print_tree<unique_tree_type::const_iterator>(myFamilyTree, 0);
132 	myFamilyTree.clear();
133 	std::cout << std::endl << std::endl << std::endl << std::endl;
134
135 	// populate and print tree with allow orphans ON
136 	myFamilyTree.allow_orphans(true);
137 	std::cout << "allow orphans ON" << std::endl << std::endl;
138 	utility::populate_tree(myFamilyTree);
139 	std::cout << std::endl;
140 	utility::print_tree<unique_tree_type::const_iterator>(myFamilyTree, 0);
141 	std::cout << std::endl << std::endl << std::endl << std::endl;
142
143 	// print tree using ordered_iterators
144 	std::cout << "using ordered_iterator" << std::endl << std::endl;
145 	utility::print_tree<unique_tree_type::const_ordered_iterator>(myFamilyTree, 0);
146 	std::cout << std::endl << std::endl << std::endl << 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 < 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()->is_orphan() )
162 			std::cout << "Node " << it->get_name_and_age() << " inserted as orphan." << 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 << "Testing for multiple inserts." << std::endl << 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 << "Couldn't insert duplicate SSN 729 into root" << 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 << "Couldn't insert duplicate SSN 814 into root" << 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()->insert(CFamilyMember(827, "Duplicate", 0));
201 	if (it == it_ins_from.node()->end())
202 		std::cout << "Couldn't insert duplicate SSN 827 in other branch." << 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()->insert(CFamilyMember(555, "Duplicate", 0));
208 	if (it == it_ins_from.node()->end())
209 		std::cout << "Couldn't insert duplicate SSN 555 in branch" << 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 << "Couldn't insert duplicate SSN 783 in node 736 using insert(parent, child)" << std::endl;
215 }