Tree Container Library

#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"