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 }
