Tree Container Library

//#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;
}