Tree Container Library

//#include "stdafx.h"
#include "sequential_tree.h"
#include <cassert>
#include <string>
#include <iostream>
class CAlpha;
namespace utility
{
	void load_tree(sequential_tree<CAlpha>& alpha_tree );
	template<typename T> void traverse_tree(T& alpha_tree);

	template<typename T> void print_tree(T& alpha_tree, const int depth)
	{
		std::cout << alpha_tree.get()->get_text() << std::endl;

		typename T::const_iterator it = alpha_tree.begin(), it_end = alpha_tree.end();
		for ( ; it != it_end; ++it ) {
			for ( int i = 0; i < depth; ++i ) {
				T* parent = &alpha_tree;
				for ( int j = depth - 1; j > i; --j )
					parent = parent->parent();

				std::cout <<  (is_last_child(parent) ? " " : "|");

				std::cout << std::string(2, ' ');
			}
			std::cout << "|" << std::endl;
			std::cout << std::string(depth * 3 + 1, ' ') << "- ";
			print_tree(*it, depth + 1);
		}
	}

	template<typename T> bool is_last_child(const T* node)
	{
		T* parent = node->parent();
		typename T::const_iterator it = parent->end();
		--it;
		return it->get()->get_text() == node->get()->get_text();
	}
}

class CAlpha
{
public:
	CAlpha()  {}
	CAlpha(const std::string& text_ ) : text(text_) {}
	CAlpha(const char* text_ ) : text(text_) {}
	~CAlpha() {}

	friend bool operator < (const CAlpha& lhs, const CAlpha& rhs) 
	{ return lhs.get_text() < rhs.get_text(); }
	std::string get_text() const { return text; }

private:
	std::string text;
};

bool pred_fcn(const CAlpha& lhs, const CAlpha& rhs)
{
	return lhs.get_text() > rhs.get_text();
}

struct comp_functor
{
	bool operator() (const CAlpha& lhs, const CAlpha& rhs) const
	{
		return lhs.get_text() > rhs.get_text();
	}
};

int main(int argc, char* argv[])
{
	// load and print tree<>
	sequential_tree<CAlpha> alpha_tree;
	alpha_tree.set(CAlpha("sequential_tree<>"));
	utility::load_tree( alpha_tree );
	utility::print_tree(alpha_tree, 0);
	std::cout << std::endl << std::endl << std::endl;

	alpha_tree.sort();
	std::cout << "Tree root sorted ascending" << std::endl;
	utility::print_tree(alpha_tree, 0);
	std::cout << std::endl << std::endl << std::endl;

	alpha_tree.sort_descendants();
	std::cout << "Whole tree sorted ascending" << std::endl;
	utility::print_tree(alpha_tree, 0);
	std::cout << std::endl << std::endl << std::endl;

	alpha_tree.sort(&pred_fcn);
	std::cout << "Tree root sorted descending" << std::endl;
	utility::print_tree(alpha_tree, 0);
	std::cout << std::endl << std::endl << std::endl;

	alpha_tree.sort_descendants(comp_functor());
	std::cout << "Whole tree sorted descending" << std::endl;
	utility::print_tree(alpha_tree, 0);
	std::cout << std::endl << std::endl << std::endl;

	utility::traverse_tree(alpha_tree);
	std::cout << std::endl << std::endl << std::endl;

	return 0;
}

void utility::load_tree(sequential_tree<CAlpha>& alpha_tree)
{
	// create a child iterator
	sequential_tree<CAlpha>::iterator it;  

	// insert first node, A, and keep an iterator to it's node
	it = alpha_tree.insert(CAlpha("A"));
	assert(it != alpha_tree.end() && it->get()->get_text() == "A" );

	// insert D and E under A
	it = alpha_tree.begin();
	assert(it != alpha_tree.end() && it->get()->get_text() == "A");
	it->insert(CAlpha("E"));
	it->insert(CAlpha("D"));

	it = it->begin();
	++it;
	// insert  J under D
	it->insert(CAlpha("J"));
	// insert K under D and remember inserted node
	sequential_tree<CAlpha>::iterator child_it = it->insert(CAlpha("K"));
	assert(child_it != it->end() && child_it->get()->get_text() == "K");
	// insert R and S under K
	child_it->insert(CAlpha("S"));
	child_it->insert(CAlpha("R"));

	// increment it (now at D) to point to E
	--it;
	// insert L under E
	it->insert(CAlpha("L"));

	it = alpha_tree.insert(CAlpha("B"));
	// insert F under B
	child_it = it->insert(CAlpha("F"));
	// insert M under F
	it = child_it;
	child_it = it->insert(CAlpha("M"));
	// insert T and U under M
	child_it->insert(CAlpha("T"));
	child_it->insert(CAlpha("U"));

	// insert N under F  (it still points to F)
	child_it = it->insert(CAlpha("N"));
	// insert V under N
	child_it->insert(CAlpha("V"));

	it = alpha_tree.begin();
	++it;
	it = alpha_tree.insert(it, CAlpha("C"));
	// insert G and H under C
	it->insert(CAlpha("G"));
	child_it = it->insert(CAlpha("H"));
	// insert O under H
	it = child_it;
	child_it = it->insert(CAlpha("O"));

	child_it = it->begin();
	assert(child_it != it->end() && child_it->get()->get_text() == "O");
	// insert W under O
	child_it->insert(CAlpha("W"));
	// insert P under H
	it->insert(CAlpha("P"));

	// insert I under C using parent of H (which is C)
	child_it = it->parent()->insert(CAlpha("I"));
	it = child_it;

	// insert Q under original I
	child_it = it->insert(CAlpha("Q"));
	// insert X under Q
	it = child_it;
	child_it = it->insert(CAlpha("X"));
	// insert Y and Z under X
	it = child_it->insert(CAlpha("Z"));
	child_it->insert(it, CAlpha("Y"));

	std::cout << std::endl << std::endl;
}

template<typename T> void utility::traverse_tree(T& alpha_tree)
{
	std::cout << std::endl;

	std::cout << alpha_tree.get()->get_text() << "::pre_order_iterator" << std::endl;
	typename T::pre_order_iterator pre_it = alpha_tree.pre_order_begin();
	for ( ; pre_it != alpha_tree.pre_order_end(); ++pre_it ) {
		std::cout << pre_it->get()->get_text() << " ";	
	}
	std::cout << std::endl << std::endl;

	std::cout << alpha_tree.get()->get_text() << "::post_order_iterator" << std::endl;
	typename T::const_post_order_iterator post_it = alpha_tree.post_order_begin();
	for ( ; post_it != alpha_tree.post_order_end(); ++post_it ) {
		std::cout << post_it.node()->get()->get_text() << " ";	
	}
	std::cout << std::endl << std::endl;

	std::cout << alpha_tree.get()->get_text() << "::level_order_iterator" << std::endl;
	typename T::const_level_order_iterator level_it = alpha_tree.level_order_begin();
	for ( ; level_it != alpha_tree.level_order_end(); ++level_it ) {
		std::cout << level_it->get()->get_text() << " ";	
	}

	std::cout << std::endl;
}