//#include "stdafx.h"
#include "unique_tree.h"
#include <string>
#include <sstream>
#include <vector>
#include <cassert>
#include <iostream>
class CFamilyMember
{
public:
CFamilyMember() : ssn(0), age(0) {}
CFamilyMember(int ssn_) : ssn(ssn_), age(0) {}
CFamilyMember(int ssn_, const std::string& name_, int age_)
: ssn(ssn_), age(age_), name(name_) {}
friend bool operator <(const CFamilyMember& lhs, const CFamilyMember& rhs)
{
return lhs.ssn < rhs.ssn;
}
int get_ssn() const { return ssn; }
int get_age() const { return age; }
std::string get_name_and_age() const
{
std::ostringstream ostr;
ostr << name << ", age: " << age;
return ostr.str();
}
// data
private:
int ssn;
int age;
std::string name;
};
struct CAgeCompare
{
bool operator()(const CFamilyMember& lhs, const CFamilyMember& rhs)
{
return lhs.get_age() < rhs.get_age();
}
};
typedef unique_tree<CFamilyMember, std::less<CFamilyMember>, CAgeCompare> unique_tree_type;
namespace utility
{
template<typename iterator_type> bool is_last_child(const unique_tree_type* node)
{
unique_tree_type* parent = node->parent();
iterator_type it, it_end;
get_begin_end_iterators(*parent, it, it_end);
--it_end;
return it_end->get_ssn() == node->get()->get_ssn();
}
template<typename iterator_type> void print_tree(const unique_tree_type& Tree, const int depth)
{
std::cout << Tree.get()->get_name_and_age() << std::endl;
iterator_type it, it_end;
get_begin_end_iterators(Tree, it, it_end);
for ( ; it != it_end; ++it ) {
for ( int i = 0; i < depth; ++i ) {
const unique_tree_type* parent = &Tree;
for ( int j = depth - 1; j > i; --j )
parent = parent->parent();
std::cout << (is_last_child<iterator_type>(parent) ? " " : "|");
std::cout << std::string(2, ' ');
}
std::cout << "|" << std::endl;
std::cout << std::string(depth * 3 + 1, ' ') << "- ";
print_tree<iterator_type>(*it.node(), depth + 1);
}
}
void populate_tree(unique_tree_type& Tree);
void test_multiple_inserts(unique_tree_type& Tree);
void get_begin_end_iterators( const unique_tree_type& Tree,
unique_tree_type::const_iterator& begin,
unique_tree_type::const_iterator& end);
void get_begin_end_iterators( const unique_tree_type& Tree,
unique_tree_type::const_ordered_iterator& begin,
unique_tree_type::const_ordered_iterator& end);
std::pair<int, CFamilyMember> Family[] =
{
std::make_pair(555, CFamilyMember(562, "Jim McAvoy", 59)),
std::make_pair(562, CFamilyMember(694, "Carmen Palmer", 40)),
std::make_pair(741, CFamilyMember(814, "Connie Delay", 3)),
std::make_pair(694, CFamilyMember(749, "Nick Palmer", 17)),
std::make_pair(694, CFamilyMember(738, "Patty Palmer", 13)),
std::make_pair(694, CFamilyMember(741, "Terri Delay", 20)),
std::make_pair(555, CFamilyMember(573, "Sally Turner", 56)),
std::make_pair(618, CFamilyMember(798, "Mark Arnold", 11)),
std::make_pair(573, CFamilyMember(618, "Kim Arnold", 34)),
std::make_pair(637, CFamilyMember(799, "Steve Lewis", 4)),
std::make_pair(573, CFamilyMember(637, "Joan Lewis", 32)),
std::make_pair(573, CFamilyMember(648, "Lee Turner", 36)),
std::make_pair(637, CFamilyMember(722, "Tammi Lewis", 6)),
std::make_pair(637, CFamilyMember(751, "Stan Lewis", 8)),
std::make_pair(783, CFamilyMember(835, "Phil Turner", 2)),
std::make_pair(644, CFamilyMember(783, "Pam Turner", 20)),
std::make_pair(573, CFamilyMember(644, "Darryl Turner", 38)),
std::make_pair(729, CFamilyMember(872, "Tammy Stewart", 3)),
std::make_pair(729, CFamilyMember(893, "Lee Stewert", 6)),
std::make_pair(768, CFamilyMember(827, "Lenny Kinney", 2)),
std::make_pair(633, CFamilyMember(775, "Frank McAvoy", 23)),
std::make_pair(633, CFamilyMember(729, "Barb Stewart", 25)),
std::make_pair(672, CFamilyMember(768, "Dan Kinney", 20)),
std::make_pair(568, CFamilyMember(633, "Bill McAvoy", 43)),
std::make_pair(568, CFamilyMember(672, "Sue Kinney", 45 )),
std::make_pair(555, CFamilyMember(568, "Pete McAvoy", 63))
};
}
int main(int argc, char* argv[])
{
unique_tree_type myFamilyTree(CFamilyMember(555, "John McAvoy", 87)); // declare tree
// populate and print tree with allow orphans OFF
std::cout << "allow orphans OFF" << std::endl << std::endl;
utility::populate_tree(myFamilyTree);
utility::print_tree<unique_tree_type::const_iterator>(myFamilyTree, 0);
myFamilyTree.clear();
std::cout << std::endl << std::endl << std::endl << std::endl;
// populate and print tree with allow orphans ON
myFamilyTree.allow_orphans(true);
std::cout << "allow orphans ON" << std::endl << std::endl;
utility::populate_tree(myFamilyTree);
std::cout << std::endl;
utility::print_tree<unique_tree_type::const_iterator>(myFamilyTree, 0);
std::cout << std::endl << std::endl << std::endl << std::endl;
// print tree using ordered_iterators
std::cout << "using ordered_iterator" << std::endl << std::endl;
utility::print_tree<unique_tree_type::const_ordered_iterator>(myFamilyTree, 0);
std::cout << std::endl << std::endl << std::endl << std::endl;
utility::test_multiple_inserts(myFamilyTree);
return 0;
}
void utility::populate_tree(unique_tree_type& Tree)
{
// populate unique tree
for (int i = 0; i < 26; ++i) {
CFamilyMember fmember = utility::Family[i].second;
unique_tree_type::const_iterator it = Tree.insert(utility::Family[i].first, fmember);
if ( it != Tree.end() && it.node()->is_orphan() )
std::cout << "Node " << it->get_name_and_age() << " inserted as orphan." << std::endl;
}
}
void utility::get_begin_end_iterators( const unique_tree_type& Tree,
unique_tree_type::const_iterator& begin,
unique_tree_type::const_iterator& end)
{
begin = Tree.begin();
end = Tree.end();
}
void utility::get_begin_end_iterators( const unique_tree_type& Tree,
unique_tree_type::const_ordered_iterator& begin,
unique_tree_type::const_ordered_iterator& end)
{
begin = Tree.ordered_begin();
end = Tree.ordered_end();
}
void utility::test_multiple_inserts(unique_tree_type& Tree)
{
std::cout << "Testing for multiple inserts." << std::endl << std::endl;
unique_tree_type::iterator it;
// try inserting duplicate node for Barb Stewart using standard insert in root
it = Tree.insert(CFamilyMember(729, "Duplicate", 0));
if (it == Tree.end())
std::cout << "Couldn't insert duplicate SSN 729 into root" << std::endl;
// try inserting node for Connie Delay using standard insert in root
it = Tree.insert(CFamilyMember(814, "Dup", 0));
if (it == Tree.end())
std::cout << "Couldn't insert duplicate SSN 814 into root" << std::endl;
// try inserting node for Lenny Kinney in Connie Delay using standard insert
unique_tree_type::iterator it_ins_from = Tree.find_deep(CFamilyMember(814));
assert (it_ins_from != Tree.end());
it = it_ins_from.node()->insert(CFamilyMember(827, "Duplicate", 0));
if (it == it_ins_from.node()->end())
std::cout << "Couldn't insert duplicate SSN 827 in other branch." << std::endl;
// try to insert node for John McAvoy in node Phil Turner using standard insert
it_ins_from = Tree.find_deep(835); // note use of implicit construction of CFamilyMember
assert(it_ins_from != Tree.end());
it = it_ins_from.node()->insert(CFamilyMember(555, "Duplicate", 0));
if (it == it_ins_from.node()->end())
std::cout << "Couldn't insert duplicate SSN 555 in branch" << std::endl;
// try to insert node Pam Turner in node Patty Palmer using insert(parent, child)
it = Tree.insert(738, CFamilyMember(783, "Duplicate", 0));
if (it == Tree.end())
std::cout << "Couldn't insert duplicate SSN 783 in node 736 using insert(parent, child)" << std::endl;
}