|
//#include "stdafx.h"
#include "tree.h"
#include "multitree.h"
#include "unique_tree.h"
#include <cassert>
#include <string>
#include <iostream>
namespace utility
{
template<typename T> void load_tree(T& 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.node(), 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_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;
};
int main(int argc, char* argv[])
{
// load and print tree<>
tree<CAlpha> alpha_tree(CAlpha("tree<>"));
utility::load_tree( alpha_tree );
utility::print_tree(alpha_tree, 0);
utility::traverse_tree(alpha_tree);
std::cout << std::endl << std::endl << std::endl;
// load and print multitree<>
multitree<CAlpha> alpha_multitree(CAlpha("multitree<>"));
utility::load_tree( alpha_multitree );
utility::print_tree( alpha_multitree, 0 );
utility::traverse_tree(alpha_multitree);
std::cout << std::endl << std::endl << std::endl;
// load and print unique_tree<>
unique_tree<CAlpha> alpha_uniquetree(CAlpha("unique_tree<>"));
utility::load_tree( alpha_uniquetree );
utility::print_tree( alpha_uniquetree, 0 );
utility::traverse_tree(alpha_uniquetree);
std::cout << std::endl << std::endl << std::endl;
return 0;
}
template<typename T> void utility::load_tree(T& alpha_tree)
{
// create a child iterator
typename T::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_text() == "A" );
// try to insert another A. Should fail for tree & unique_tree
it = alpha_tree.insert(CAlpha("A"));
if ( it == alpha_tree.end() )
std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second A." << std::endl;
// insert D and E under A
it = alpha_tree.begin();
assert(it != alpha_tree.end() && it->get_text() == "A");
typename T::iterator child_it = it.node()->insert(CAlpha("D"));
it.node()->insert(CAlpha("E"));
assert(child_it != it.node()->end() && child_it->get_text() == "D");
it = child_it;
// insert J under D
it.node()->insert(CAlpha("J"));
// insert K under D and remember inserted node
child_it = it.node()->insert(CAlpha("K"));
assert(child_it != it.node()->end() && child_it->get_text() == "K");
// insert R and S under K
child_it.node()->insert(CAlpha("R"));
child_it.node()->insert(CAlpha("S"));
// increment it (now at D) to point to E
++it;
// insert L under E
it.node()->insert(CAlpha("L"));
it = alpha_tree.insert(CAlpha("B"));
// insert second E and F under B
child_it = it.node()->insert(CAlpha("E")); // should fail for unique_tree
if ( child_it == it.node()->end() )
std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second E." << std::endl;
child_it = it.node()->insert(CAlpha("F"));
// insert M under F
it = child_it;
child_it = it.node()->insert(CAlpha("M"));
// insert T and U under M
child_it.node()->insert(CAlpha("T"));
child_it.node()->insert(CAlpha("U"));
// insert N under F (it still points to F)
child_it = it.node()->insert(CAlpha("N"));
// insert second U and V under N
if ( child_it.node()->insert(CAlpha("U")) == child_it.node()->end() ) // should fail for unique_tree
std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second U." << std::endl;
child_it.node()->insert(CAlpha("V"));
it = alpha_tree.insert(CAlpha("C"));
// insert G and H under C
it.node()->insert(CAlpha("G"));
child_it = it.node()->insert(CAlpha("H"));
// insert O under H
it = child_it;
child_it = it.node()->insert(CAlpha("O"));
// try to insert another O
child_it = it.node()->insert(CAlpha("O")); // should fail for tree/unique_tree
if ( child_it == it.node()->end() )
std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second O." << std::endl;
child_it = it.node()->begin();
assert(child_it != it.node()->end() && child_it->get_text() == "O");
// insert W under O
child_it.node()->insert(CAlpha("W"));
// insert P under H
it.node()->insert(CAlpha("P"));
// insert I under C using parent of H (which is C)
child_it = it.node()->parent()->insert(CAlpha("I"));
assert(child_it != it.node()->parent()->end() && child_it->get_text() == "I");
// insert second I under I
it = child_it;
child_it = it.node()->insert(CAlpha("I")); // should fail for unique tree
if ( child_it == it.node()->end() )
std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second I." << std::endl;
// insert Q under original I
child_it = it.node()->insert(CAlpha("Q"));
// insert X under Q
it = child_it;
child_it = it.node()->insert(CAlpha("X"));
// insert Y and Z under X
child_it.node()->insert(CAlpha("Y"));
child_it.node()->insert(CAlpha("Z"));
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_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->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_text() << " ";
}
std::cout << std::endl;
}
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.