Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Tree Container Library

, 22 Aug 2007 Zlib
A generic template class library for storing data in a tree-like structure.
tcldoc_40802.zip
TCL.chm
tcldoc_4_07_01.zip
TCL.chm
tcl_3_55.zip
basic_tree.inl
associative_tree.inl
descendant_iterator.inl
ordered_iterator.inl
multitree.inl
tree.inl
child_iterator.inl
unique_tree.inl
sequential_tree.inl
tcl_4_07.zip
sequential_tree.inl
tree.inl
unique_tree.inl
associative_tree.inl
basic_tree.inl
descendant_iterator.inl
descendant_node_iterator.inl
multitree.inl
tcl_4_08.zip
associative_tree.inl
basic_tree.inl
descendant_iterator.inl
descendant_node_iterator.inl
multitree.inl
sequential_tree.inl
tree.inl
unique_tree.inl
TCL.chm
tcl_test_suite_081606.zip
descendant_iterator_tester.inl
modifying_algorithm_tester.inl
nonmodifying_algorithm_tester.inl
ordered_iterator_checker.inl
sequential_tree_tester.inl
stl_algorithm_tester.inl
unique_tree_tester.inl
associative_tree_tester.inl
basic_tree_tester.inl
child_iterator_tester.inl
child_sequential_iterator_tester.inl
tree_container_library_demo.zip
polymorphic_example_results.jpg
sequential_tree_example_diagram.jpg
sequential_tree_example_explanation.rtf
sequential_tree_example_results.jpg
unique_tree_example_diagram.jpg
unique_tree_example_explation.rtf
unique_tree_example_results.jpg
generic_example_diagram.jpg
generic_example_explanation.rtf
generic_example_results.jpg
polymorphic_example_diagram.jpg
polymorphic_example_explanation.rtf
tree_container_library_demos.zip
generic_example_diagram.jpg
generic_example_results.jpg
polymorphic_example_diagram.jpg
polymorphic_example_results.jpg
sequential_tree_example_diagram.jpg
sequential_tree_example_results.jpg
unique_tree_example_diagram.jpg
unique_tree_example_results.jpg
tree_container_library_src.zip
multitree.inl
basic_tree.inl
Tree.inl
unique_tree.inl
tree_container_lib_src.zip
basic_tree.inl
associative_tree.inl
unique_tree.inl
Tree.inl
sequential_tree.inl
multitree.inl
#pragma once
#include <set>
#include <stack>
#include <deque>
#include <algorithm>

/************************************************************************************************
**	This library was designed and developed by Mitchel Haas
**	This software library is provided �as is� and any express or implied warranties, including, 
**	but not limited to, the implied warranties of merchantability and fitness for a particular 
**	purpose are disclaimed.  The use of this software library is at the user's own risk.  
**	In no event shall the software designer/developer be liable for any direct, indirect, 
**	incidental, special, exemplary, or consequential damages (including, but not limited to, 
**	procurement of substitute goods or services; loss of use, data, or profits; 
**	or business interruption) however caused and on any theory of liability, 
**	whether in contract, strict liability (including negligence or otherwise) 
**	arising in any way out of the use of this software library.
**
**	This library may be used freely, and redistributed, 
**	provided it is kept and distributed in it's entirety,
**	and that all of it's contained files remain unmodified, 
**	in their original state, including this notice and the authors name.
*************************************************************************************************/
 

// stored_type:				type stored in container
// tree_type:				one of three tree types derived from this base
// set_container_type:		type of contain to hold children (can be set or multiset)

template< typename stored_type, typename tree_type,  typename set_container_type >
class basic_tree 
{
	public:
	// typedefs
		typedef basic_tree<stored_type, tree_type, set_container_type> basic_tree_type;
		typedef stored_type* (*tClone_fcn) (const stored_type&);
	private:
	// forward declarations
		struct pre_order_iterator_impl;
		struct post_order_iterator_impl;
		struct level_order_iterator_impl;

	public:
	// constructors/destructor
		basic_tree() : pParent_node(NULL), pData(NULL) {}
		basic_tree(const stored_type& stored_obj);
		virtual ~basic_tree();

	public:
	// child iterator definitions
		class const_iterator : public std::iterator<std::bidirectional_iterator_tag, stored_type>
		{
			public:
			// typedefs
				typedef class basic_tree<stored_type, tree_type, set_container_type> basic_tree_type;

			// constructors/destructor
				const_iterator() {}
				const_iterator(typename set_container_type::const_iterator it_) : it(it_) {}
				virtual ~const_iterator() {}

			// overloaded operators
				friend bool operator != ( const const_iterator& lhs, const const_iterator& rhs )  { return lhs.it != rhs.it; }
				friend bool operator == ( const const_iterator& lhs, const const_iterator& rhs )  { return lhs.it == rhs.it; }

				const tree_type& operator*() const { return  *it.operator *(); }
				const tree_type* operator->() const { return *it.operator ->(); }

				const_iterator& operator ++() { ++it; return *this; }
				const_iterator operator ++(int) { const_iterator old(*this); ++*this; return old; }
				const_iterator& operator --() { --it; return *this; }
				const_iterator operator --(int) { const_iterator old(*this); --*this; return old; }

			// public interface
				const tree_type* node() { return *it; }
				friend class post_order_iterator;
				friend class pre_order_iterator;
				friend class level_order_iterator;

			// data
			protected:
				typename set_container_type::const_iterator it;
		};
		friend class const_iterator;

		class iterator : public const_iterator
		{
			public:
				using const_iterator::it;
			// typedefs
				typedef class basic_tree<stored_type, tree_type, set_container_type> basic_tree_type;

			// constructors/destructor
				iterator() {}
				iterator(typename set_container_type::iterator it_) : const_iterator(it_) {}
				~iterator() {}

			// overloaded operators
				friend bool operator != ( const iterator& lhs, const iterator& rhs )  { return lhs.it != rhs.it; }
				friend bool operator == ( const iterator& lhs, const iterator& rhs )  { return lhs.it == rhs.it; }

				tree_type& operator*() { return *it.operator *(); }
				tree_type* operator->() { return *it.operator ->(); }
				iterator& operator ++() { ++it;  return *this; }
				iterator operator ++(int) { iterator old(*this); ++*this; return old; }
				iterator& operator --() { --it; return *this; }
				iterator operator --(int) { iterator old(*this); --*this; return old; }

			// public interface
				tree_type* node() { return *it; }
		};
		friend class iterator;


		// descendent tree iterator definitions

		class const_pre_order_iterator : public std::iterator<std::bidirectional_iterator_tag, stored_type>
		{
		public:
			// constructors/destructor
			const_pre_order_iterator() {}
			const_pre_order_iterator(const basic_tree_type* pTop_node_) { it = pTop_node_->children.begin(); pTop_node = pTop_node_; }
		protected:
			explicit const_pre_order_iterator(const_iterator& it_) : it(it_) {}

		public:
			// overloaded operators
			friend bool operator != ( const const_pre_order_iterator& lhs, const const_pre_order_iterator& rhs ) { return lhs.it != rhs.it; }
			friend bool operator == ( const const_pre_order_iterator& lhs, const const_pre_order_iterator& rhs ) { return lhs.it == rhs.it; }
			const_pre_order_iterator& operator ++() { return impl.incr(this); }
			const_pre_order_iterator operator ++(int) { const_pre_order_iterator old(*this); ++*this; return old; }
			const_pre_order_iterator operator --() { return impl.decr(this); }
			const_pre_order_iterator operator --(int) { const_pre_order_iterator old(*this); --*this; return old; }

			// public interface
			const tree_type& operator*() const { return  it.operator *(); }
			const tree_type* operator->() const { return it.operator ->(); }
			const tree_type* node() { return it.node(); }
			friend struct pre_order_iterator_impl;
			friend class basic_tree<stored_type, tree_type, set_container_type>;

			// data
		protected:
			std::stack<const_iterator> node_stack;   
			const basic_tree_type* pTop_node;
			const_iterator it;
			pre_order_iterator_impl impl;
			typename set_container_type::const_reverse_iterator rit;
		};
		friend class const_pre_order_iterator;
		
		class pre_order_iterator : public const_pre_order_iterator
		{
		public:
			using const_pre_order_iterator::it;
			// constructors/destructor
			pre_order_iterator() {}
			pre_order_iterator( basic_tree_type* pTop_node_) : const_pre_order_iterator(pTop_node_) {}
		protected:
			explicit pre_order_iterator(iterator& it_) : const_pre_order_iterator(it_) {}

		public:
			// overloaded operators
			friend bool operator != ( const pre_order_iterator& lhs, const pre_order_iterator& rhs ) { return lhs.it != rhs.it; }
			friend bool operator == ( const pre_order_iterator& lhs, const pre_order_iterator& rhs ) { return lhs.it == rhs.it; }
			pre_order_iterator& operator ++() { ++(*static_cast<const_pre_order_iterator*>(this)); return *this; }
			pre_order_iterator operator ++(int) { pre_order_iterator old(*this); ++*this; return old; }
			pre_order_iterator operator --() { --(*static_cast<const_pre_order_iterator*>(this)); return *this; }
			pre_order_iterator operator --(int) { pre_order_iterator old(*this); --*this; return old; }

			// public interface
			tree_type& operator*() { return  it.operator *(); }
			tree_type* operator->() { return const_cast<tree_type*>(it.operator ->()); }
			tree_type* node() { return const_cast<tree_type*>(it.node()); }
			friend class basic_tree<stored_type, tree_type, set_container_type>;
		};
		friend class pre_order_iterator;

		class const_post_order_iterator : public std::iterator<std::bidirectional_iterator_tag, stored_type>
		{
		public:
			// constructors/destructor
			const_post_order_iterator() {}
			const_post_order_iterator(const basic_tree_type* pTop_node_) { impl.init(this, pTop_node_); }
		protected:
			explicit const_post_order_iterator(const_iterator& it_) : it(it_) {}

		public:
			// overloaded operators
			friend bool operator != ( const const_post_order_iterator& lhs, const const_post_order_iterator& rhs ) { return lhs.it != rhs.it; }
			friend bool operator == ( const const_post_order_iterator& lhs, const const_post_order_iterator& rhs ) { return lhs.it == rhs.it; }
			const_post_order_iterator& operator ++() { return impl.incr(this); }
			const_post_order_iterator operator ++(int) { const_post_order_iterator old(*this); ++*this; return old; }
			const_post_order_iterator operator --() { return impl.decr(this); }
			const_post_order_iterator operator --(int) { const_post_order_iterator old(*this); --*this; return old; }

			// public interface
			const tree_type& operator*() const { return  it.operator *(); }
			const tree_type* operator->() const { return it.operator ->(); }
			const tree_type* node() { return it.node(); }
			friend struct post_order_iterator_impl;
			friend class basic_tree<stored_type, tree_type, set_container_type>;

			// data
		protected:
			std::stack<const_iterator> node_stack;   
			const basic_tree_type* pTop_node;
			const_iterator it;
			post_order_iterator_impl impl;
			typename set_container_type::const_reverse_iterator rit;
		};
		friend class const_post_order_iterator;


		class post_order_iterator : public const_post_order_iterator
		{
		public:
			using const_post_order_iterator::it;
			// constructors/destructor
			post_order_iterator() {}
			post_order_iterator(basic_tree_type* pTop_node_) : const_post_order_iterator(pTop_node_) { }
		protected:
			explicit post_order_iterator(iterator& it_) : const_post_order_iterator(it_) {}

		public:
			// overloaded operators
			friend bool operator != ( const post_order_iterator& lhs, const post_order_iterator& rhs ) { return lhs.it != rhs.it; }
			friend bool operator == ( const post_order_iterator& lhs, const post_order_iterator& rhs ) { return lhs.it == rhs.it; }
			post_order_iterator& operator ++() { ++(*static_cast<const_post_order_iterator*>(this)); return *this; }
			post_order_iterator operator ++(int) { post_order_iterator old(*this); ++*this; return old; }
			post_order_iterator operator --() { --(*static_cast<const_post_order_iterator*>(this)); return *this; }
			post_order_iterator operator --(int) { post_order_iterator old(*this); --*this; return old; }

			// public interface
			tree_type& operator*() { return  it.operator *(); }
			tree_type* operator->() { return const_cast<tree_type*>(it.operator ->()); }
			tree_type* node() { return const_cast<tree_type*>(it.node()); }
			friend class basic_tree<stored_type, tree_type, set_container_type>;

		};
		friend class post_order_iterator;



		class const_level_order_iterator : public std::iterator<std::forward_iterator_tag, stored_type>
		{
		public:
			// constructors/destructor
			const_level_order_iterator() {}
			const_level_order_iterator(const basic_tree_type* pTop_node_) : pTop_node(pTop_node_), node_depth(0) { it = pTop_node_->children.begin(); }
		protected:
			explicit const_level_order_iterator(const_iterator& it_) : it(it_) {}

		public:
			// overloaded operators
			friend bool operator != (const const_level_order_iterator& lhs, const const_level_order_iterator& rhs) { return lhs.it != rhs.it; }
			friend bool operator == (const const_level_order_iterator& lhs, const const_level_order_iterator& rhs) { return lhs.it == rhs.it; }
			const_level_order_iterator operator ++() { return impl.incr(this); }
			const_level_order_iterator operator ++(int) { const_level_order_iterator old(*this); ++*this; return old; }
			// declare, but don't define decr operators
			const_level_order_iterator operator --();
			const_level_order_iterator operator --(int);

			// public interface
			const tree_type& operator*() const { return  it.operator *(); }
			const tree_type* operator->() const { return it.operator ->(); }
			int depth() const { return node_depth; }
			const tree_type* node() { return it.node(); }
			friend struct level_order_iterator_impl;
			friend class basic_tree<stored_type, tree_type, set_container_type>;

			// data
		protected:
			const_iterator it;
			std::deque<const_iterator> node_deque;
			const basic_tree_type* pTop_node;
			level_order_iterator_impl impl;
			int node_depth;
		};
		friend class level_order_iterator;

		class level_order_iterator : public const_level_order_iterator
		{
		public:
			using const_level_order_iterator::it;
			// constructors/destructor
			level_order_iterator() {}
			level_order_iterator(basic_tree_type* pTop_node_) : const_level_order_iterator(pTop_node_) { }
		private:
			explicit level_order_iterator(iterator& it_) : const_level_order_iterator(it_) {}
		
		public:
			// overloaded operators
			friend bool operator != (const level_order_iterator& lhs, const level_order_iterator& rhs) { return lhs.it != rhs.it; }
			friend bool operator == (const level_order_iterator& lhs, const level_order_iterator& rhs) { return lhs.it == rhs.it; }
			level_order_iterator& operator ++() { ++(*static_cast<const_level_order_iterator*>(this)); return *this; }
			level_order_iterator operator ++(int) { level_order_iterator old(*this); ++*this; return old; }

			// public interface
			tree_type& operator*() { return  it.operator *(); }
			tree_type* operator->() { return const_cast<tree_type*>(it.operator ->()); }
			tree_type* node() { return const_cast<tree_type*>(it.node()); }
			friend class basic_tree<stored_type, tree_type, set_container_type>;

		};
		friend class level_order_iterator;

	// public interface
		iterator find(const stored_type& stored_obj);
		const_iterator find(const stored_type& stored_obj) const;
		bool is_root() const { return pParent_node == NULL; }
		tree_type* parent() const { return pParent_node; }
		bool empty() const { return children.empty(); }
		int size() const { return static_cast<int>(children.size()); }

		const_iterator begin() const { return const_iterator(children.begin()); }
		const_iterator end() const { return const_iterator(children.end()); }
		iterator begin() { return iterator(children.begin()); }
		iterator end() { return iterator(children.end()); }
		post_order_iterator post_order_begin() { post_order_iterator it(this); return it; }
		post_order_iterator post_order_end() { iterator it = end(); return post_order_iterator(it); }
		const_post_order_iterator post_order_begin() const { const_post_order_iterator it(this); return it; }
		const_post_order_iterator post_order_end() const { return const_post_order_iterator(end()); }
		pre_order_iterator pre_order_begin() { pre_order_iterator it(this); return it; }
		pre_order_iterator pre_order_end() { iterator it = end(); return pre_order_iterator(it); }
		const_pre_order_iterator pre_order_begin() const { const_pre_order_iterator it(this); return it; }
		const_pre_order_iterator pre_order_end() const {  return const_pre_order_iterator(end()); }
		level_order_iterator level_order_begin() { level_order_iterator it(this); return it; }
		level_order_iterator level_order_end() { iterator it = end(); return level_order_iterator(it); }
		const_level_order_iterator level_order_begin() const { const_level_order_iterator it(this); return it; }
		const_level_order_iterator level_order_end() const { return const_level_order_iterator(end()); }
		bool erase(const stored_type& stored_obj);
		stored_type* get() const { return pData; }
		void set(const stored_type& stored_obj);
		void for_each( void (*pFcn)(tree_type*) );
		template<typename T> void for_each( T& func_ob );
		static void set_clone(const tClone_fcn& fcn) { pClone_fcn = fcn; }
	protected:
		iterator insert( const stored_type& stored_obj, tree_type* parent );
		iterator insert(stored_type* pStored_obj, tree_type* parent);
		iterator insert(const tree_type& tree_obj, tree_type* parent);
		void set(const tree_type& tree_obj, tree_type* parent);
		
	// data
	protected:
		stored_type* pData;   // data accessor
		mutable tree_type* pParent_node;
		set_container_type children;
		static tClone_fcn pClone_fcn;
	private:
		struct pre_order_iterator_impl 
		{
			template<typename T> T& incr(T* self )
			{
				if ( !self->it->empty() ) {
					self->node_stack.push(self->it);
					self->it = self->node()->children.begin();
				} else {
					++self->it;
					while ( !self->node_stack.empty() && self->it == (self->node_stack.top())->end() ) {
						self->it = self->node_stack.top();
						self->node_stack.pop();
						++self->it;
					}
				}
				return *self; 
			}

			template<typename T> T decr(T* self)
			{
				if ( self->it == self->pTop_node->end() ) {
					self->rit = self->pTop_node->children.rbegin();
					if ( self->rit != self->pTop_node->children.rend() ) {
						if ( !(*self->rit)->empty() ) {
							do {
								++self->rit;
								self->it = self->rit.base();
								self->node_stack.push(self->it);
								self->rit = self->node()->children.rbegin();
							} while ( !(*self->rit)->empty() );
							++self->rit;
							self->it = self->rit.base();
						}
					}
				} else {
					if ( self->it != self->node()->parent()->begin() )
					{
						--self->it;
						if (!self->it->empty()) {
							do {
								self->node_stack.push(self->it);
								self->it = self->node()->children.end();
								--self->it;
							} while ( !self->it->empty() );
						}
					} else {
						self->it = self->node_stack.top();
						self->node_stack.pop();
					}
				}
				return *self;
			}
		};

		struct post_order_iterator_impl
		{
			template<typename T> void init(T* self, const basic_tree_type* pTop_node_)
			{
				self->pTop_node = pTop_node_;
				self->it = self->pTop_node->begin();
				if ( !self->it->empty() ) {
					do { 
						self->node_stack.push(self->it);
						self->it = self->node()->begin();
					} while ( !self->it->empty() );
				}

			}

			template<typename T> T& incr(T* self)
			{
				iterator it_end = self->node()->parent()->end();
				++self->it;
				if ( self->it != it_end && !self->it->empty() ) {
					do { 
						self->node_stack.push(self->it);
						self->it = self->node()->children.begin();
					} while ( !self->it->empty() );
				} else {
					while ( !self->node_stack.empty() && self->it == (self->node_stack.top())->end() ) {
						self->it = self->node_stack.top();
						self->node_stack.pop();
					}
				}
				return *self;
			}

			template<typename T> T decr(T* self)
			{
				if ( self->it == self->pTop_node->end() ) {
					typename set_container_type::const_reverse_iterator rit = self->pTop_node->children.rbegin();
					++rit;
					self->it = rit.base();
				} else {
					if ( !self->node()->empty() ) {
						typename set_container_type::const_reverse_iterator rit = self->node()->children.rbegin();
						self->node_stack.push(self->it);
						++rit;
						self->it = rit.base();
					} else {
						if ( self->it != self->node()->parent()->begin() ) {
							--self->it;
						} else {
							while ( !self->node_stack.empty() && self->it == self->node_stack.top()->begin())
							{
								self->it = self->node_stack.top();
								self->node_stack.pop();
							}
							--self->it;
						}
					}
				}
				return *self;
			}
		};

		struct level_order_iterator_impl
		{
			const_level_order_iterator& incr(const_level_order_iterator* self)
			{
				const_iterator it_begin = self->node()->parent()->begin();
				const_iterator it_end = self->node()->parent()->end();
				self->node_deque.push_front(self->it);
				++self->it;

				if ( self->it == it_end ) {
					while ( !self->node_deque.empty() ) {
						self->it = self->node_deque.back();
						self->node_deque.pop_back();
						if ( !self->it->empty() ) {
							self->it = self->node()->children.begin();
							++self->node_depth;
							break;
						} else if ( self->node_deque.empty() ) 	{
							self->it = self->pTop_node->children.end();
							return *self;
						}
					} 
				}

				return *self;

			}
		};

};

#include "basic_tree.inl"

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.

License

This article, along with any associated source code and files, is licensed under The zlib/libpng License

Share

About the Author

Mitchel Haas
Software Developer Datasoft Solutions
United States United States
I'm a c++ programmer in the midwest, now using VC7 at work and at home. I enjoy creating generic libraries, and template based programming.
 
I also enjoy web development (xhtml, css, javascript, php).

| Advertise | Privacy | Mobile
Web04 | 2.8.141022.2 | Last Updated 22 Aug 2007
Article Copyright 2006 by Mitchel Haas
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid