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

Tree Container Library

, 22 Aug 2007
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 "basic_tree.h"
#include <set>

/************************************************************************************************
**	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.
*************************************************************************************************/

// forward declaration for deref comparison functor
template<typename stored_type, typename node_compare_type, typename node_order_compare_type >
class unique_tree;

// deref comparison functor, derive from binary function per Scott Meyer
template<typename stored_type, typename node_compare_type, typename node_order_compare_type >
struct unique_tree_deref_less : public std::binary_function<const unique_tree<stored_type, node_compare_type, node_order_compare_type>*, const unique_tree<stored_type, node_compare_type, node_order_compare_type>*, bool>
{
	bool operator () (const unique_tree<stored_type, node_compare_type, node_order_compare_type>* lhs, const unique_tree<stored_type, node_compare_type, node_order_compare_type>* rhs) const
	{
		// call < on actual object
		return (*lhs < *rhs);
	}
};


// instanciates base_tree_type with type of container (set of unique_tree ptrs) to use for node and key comparisons
template<typename stored_type, typename node_compare_type = std::less<stored_type>, typename node_order_compare_type = node_compare_type >
class unique_tree : public basic_tree<stored_type, unique_tree<stored_type, node_compare_type, node_order_compare_type>,  std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > >
{
	public:
	// typedefs
		typedef unique_tree<stored_type, node_compare_type, node_order_compare_type> tree_type;
		typedef basic_tree<stored_type, unique_tree<stored_type, node_compare_type, node_order_compare_type>,  std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > > basic_tree_type;
		typedef std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > container_type;
		friend class basic_tree<stored_type, unique_tree<stored_type, node_compare_type, node_order_compare_type>,  std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > >;
		typedef typename basic_tree_type::iterator base_iterator;
		typedef typename basic_tree_type::const_iterator base_const_iterator;

	// constructors/destructor
		unique_tree() : basic_tree_type(stored_type()), pOrphans(NULL), allowing_orphans(false)  {}
		unique_tree( const stored_type& stored_obj ) : basic_tree_type(stored_obj), pOrphans(NULL) {}
		unique_tree( const tree_type& rhs ); // copy constructor
		~unique_tree();

	// less operator.  since data's stored as a ptr, use a dereference less
		friend bool operator < (const tree_type& lhs, const tree_type& rhs) { return node_compare_type()(*lhs.pData, *rhs.pData); }
	// == operator.
		friend bool operator == (const tree_type& lhs, const tree_type& rhs) 
			{ return (!node_compare_type()(*lhs.pData, *rhs.pData) && !node_compare_type()(*rhs.pData, *lhs.pData)); }

	// deref less for find_deep
		struct deref_key_compare
		{
			bool operator() (const tree_type* lhs, const tree_type* rhs) const { return node_compare_type()(*lhs->pData, *rhs->pData); }
		};
		friend struct deref_key_compare;

	// deref less for ordered children set
		struct deref_ordered_compare
		{
			bool operator() (const tree_type* lhs, const tree_type* rhs) const { return node_order_compare_type() (*lhs->pData, *rhs->pData); }
		};
		friend struct deref_ordered_compare;

		// need to define iterators inline, because VC6 complains if not
		class const_ordered_iterator : public std::iterator<std::bidirectional_iterator_tag, stored_type>
		{
		public:
			// typedefs
			typedef std::multiset<tree_type*, deref_ordered_compare> ordered_container_type;

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

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

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

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

			const tree_type* node() const { return *it; }

			// data
		protected:
			typename ordered_container_type::const_iterator it;
		};
		friend class const_ordered_iterator;

		class ordered_iterator : public const_ordered_iterator
		{
		public:
			using const_ordered_iterator::it;
			// constructors/destructor
			ordered_iterator() {}
			ordered_iterator(typename const_ordered_iterator::ordered_container_type::const_iterator it_) : const_ordered_iterator(it_) {}

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

			// public interface
			tree_type& operator*() { return *it.operator *(); }
			tree_type* operator->() { return *it.operator ->(); }

			base_iterator insert(const stored_type& stored_obj) const { return (*it)->insert(stored_obj); }

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

			tree_type* node() { return *it; }
		};
		friend class ordered_iterator;

	// public interface
	public:
		base_iterator insert(const stored_type& stored_obj);
		base_iterator insert(const tree_type& tree_obj );

		base_iterator insert( const stored_type& parent_obj, const stored_type& stored_obj);
		void set(const stored_type& stored_obj) { basic_tree_type::set(stored_obj); }
		void set(const tree_type& tree_obj);

		base_iterator find_deep(const stored_type& stored_obj);
		base_const_iterator find_deep(const stored_type& stored_obj) const;

		const_ordered_iterator ordered_begin() const { return const_ordered_iterator(ordered_children.begin()); }
		const_ordered_iterator ordered_end() const { return const_ordered_iterator(ordered_children.end()); }
		ordered_iterator ordered_begin() { return ordered_iterator(ordered_children.begin()); }
		ordered_iterator ordered_end() { return ordered_iterator(ordered_children.end()); }
		const_ordered_iterator find_ordered(const stored_type& stored_obj) const;
		bool erase(const stored_type& stored_obj);
		template<typename key_type> bool erase(const key_type& key) { return erase( stored_type(key) ); }
		void clear();
		bool allow_orphans() const { return get_root()->allowing_orphans; }
		void allow_orphans(bool allow) { get_root()->allowing_orphans = allow; }
		const tree_type* get_orphans() const { return get_root()->pOrphans; }
		bool is_orphan() const { const tree_type* root = get_root(); return (!root->empty() && root->ordered_children.empty()); }

	private:
		base_iterator insert(stored_type* pStored_obj);
		void inform_grandparents( tree_type* pNew_child, tree_type* pParent );
		bool check_for_duplicate(const stored_type& stored_obj, const tree_type* pParent) const;
		const tree_type* get_root() const;

	// data
	private:
		mutable std::set<tree_type*, deref_key_compare> descendents;
		std::multiset<tree_type*, deref_ordered_compare> ordered_children;
		mutable tree_type* pOrphans;
		mutable bool allowing_orphans;
};

#include "unique_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.140916.1 | Last Updated 22 Aug 2007
Article Copyright 2006 by Mitchel Haas
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid