A policy based reference counting implementation for compound objects

/////////////////////////////////
// compounds.hpp
//	generic compound objects
//

#pragma once
#include "smart.hpp"
#pragma message ("Compiling " __FILE__)


namespace GE_{ namespace stdx{


	//////////////////
	//	traits classes definig types and type related helper functions

    struct comp_dumb_traits
	{
		template<class Derived>
		class types
		{
		public:
			typedef Derived value;
			typedef Derived* ptr;	//forward pointers
			typedef Derived* wptr;	//backward pointers
		};

		template<class P> //a pointer
		static void clear_ptr(P& p) { p=0; } 

		class base //will hinerit this class
		{
		};

	};

	struct comp_smart_traits
	{
		template<class Derived>
		class types
		{
		public:
			typedef Derived value;
			typedef typename stdx::ptr<Derived>::strong ptr;
			typedef typename stdx::ptr<Derived>::weak wptr;
		};

		template<class P>
		static void clear_ptr(P& p) { p=P(); }

		class base:
			public virtual refcountable
		{
		};
	};

	
	/////////////////////////////// 
	//	an iterator class
	//

	//traits for linear visit iterator
	struct iter_traits_chain
	{
		template<class D>
			struct types
		{
			typedef D* access_t;
			typedef D& reference_t;
		};

		template<class P>
			static P access(const P& p) { return p; }
		template<class D>
			static D& dereference(D* p) { return *p; }

		template<class P>
			static void increment(P& p, int i=1) 
		{ 
			while(p && i>0) p=p->get_next(), i--; 
			while(p && i<0) p=p->get_prev(), i++; 
		}
		
		template<class P>
			static void decrement(P& p, int i=1) 
		{
			while(p && i>0) p=p->get_prev(), i--; 
			while(p && i<0) p=p->get_next(), i++; 
		}

	};

	//traits for deep tree visit iterator
	struct iter_traits_deep:
		public iter_traits_chain
	{
		template<class P>
			static void increment(P& p, int i=1) 
		{ 
			while(p && i>0) p=p->get_deepfirst_next(), i--; 
			while(p && i<0) p=p->get_deepfirst_prev(), i++; 
		}
		
		template<class P>
			static void decrement(P& p, int i=1) 
		{
			while(p && i>0) p=p->get_deepfirst_prev(), i--; 
			while(p && i<0) p=p->get_deepfirst_next(), i++; 
		}
	};

	//the iterator class 
	template<class Compound, 
			class iter_trs = iter_traits_chain,
			class traits = Compound::traits_t >
	class iterator
	{
		friend class iterator;
	private:
		typename traits::types<Compound>::wptr p;
	public:
		typedef traits traits_t;
		typedef iter_trs iter_traits_t;
		typedef Compound value_type;
		typedef typename iter_trs::types<Compound>::access_t pointer;
		typedef typename iter_trs::types<Compound>::reference_t reference;

		iterator() { traits::clear_ptr(p); }
		iterator(const iterator& i) { p = i.p; }
		template<class traits2, class trs2>
			iterator(const iterator<Compound,traits2,trs2>& i) { p = i.p; }
		iterator(const typename traits::types<Compound>::wptr& pD) :p(pD) {}
		iterator& operator=(const iterator& i) { p = i.p; return *this; }

		pointer operator->() const { return iter_trs::access(p); }
		reference operator*() const { return iter_trs::dereference(&*p); }
		iterator& operator++() {  iter_trs::increment(p); return *this; }
		iterator& operator--() {  iter_trs::decrement(p); return *this; }
		iterator operator++(int) { iterator i(*this); ++(*this); return i; }
		iterator operator--(int) { iterator i(*this); --(*this); return i; }
		iterator& operator+=(int i)	{ iter_trs::increment(p,i); return *this; }
		iterator& operator-=(int i) { iter_trs::decrement(p,i); return *this; }
		Compound& operator[](int i) const
		{	iterator it(*this) it+=i; return *it;	}

		bool operator==(const iterator& i) { return p==i.p; }
		bool operator!=(const iterator& i) { return p!=i.p; }
		bool operator<(const iterator& i) { return p<i.p; }
		bool operator!() const { return !p; }
	};
    



	////////////////////////////
	//	collection nodes:
	//	derive from here for self collecting object
	//

	// chain class: link nodes in a bidirectional list
	template<class Derived, class traits = comp_dumb_traits>
	class chain_node:
		public traits::base
	{
	public:
		typedef typename traits::types<Derived>::ptr ptr;
		typedef typename traits::types<Derived>::wptr wptr;
		typedef stdx::iterator<Derived,iter_traits_chain, traits> iterator;

		typedef Derived chain_t;
		typedef traits traits_t;

		ptr get_next() const {return pNext;} 
		wptr get_prev() const {return pPrev;} 
		wptr get_first() { wptr p(pThis()), q; while(!!p) { q=p; p=p->get_prev(); } return q; }
		ptr get_last() { ptr p(pThis()), q; while(!!p) { q=p; p=p->get_next(); } return q; }
		void leave_chain()
		{
			if(!!pNext) P(pNext)->pPrev = pPrev;
			if(!!pPrev) P(pPrev)->pNext = pNext;
			traits::clear_ptr(pNext); traits::clear_ptr(pPrev);
		}

		void set_next(ptr pNewNext)
		{
			if(!pNewNext) return;
			pNewNext->leave_chain();
			if(!!pNext) 
				P(pNext)->pPrev = pNewNext;
			P(pNewNext)->pNext = pNext;
			P(pNewNext)->pPrev= pThis();
			pNext = pNewNext;
		}

		void set_prev(ptr pNewPrev)
		{
			if(!pNewPrev) return;
			pNewPrev->leave_chain();
			if(!!pPrev) 
				P(pPrev)->pNext = pNewPrev;
			P(pNewPrev)->pPrev = pPrev;
			P(pNewPrev)->pNext= pThis();
			pPrev = pNewPrev;
		}

		chain_node()
		{
			traits::clear_ptr(pNext); traits::clear_ptr(pPrev);
		}

		~chain_node() { leave_chain(); }

	private:
		friend class chain_node<Derived>;
		ptr pThis() const { return static_cast<Derived*>(const_cast<chain_node*>(this)); }
		chain_node* P(Derived* p) const { return static_cast<chain_node*>(p); }
		ptr pNext;
		wptr pPrev;

	};

	//hierarchy class: link nodes inside a tree
	template<class Derived, class traits = comp_smart_traits> //type derives from hierarchy_node
	class hierarchy_node:
		public traits::base
	{
	public:
		typedef typename traits::types<Derived>::ptr ptr;
		typedef typename traits::types<Derived>::wptr wptr;

		typedef Derived chain_t;
		typedef traits traits_t;

		typedef stdx::iterator<Derived, iter_traits_chain, traits> shallowiterator;
		typedef stdx::iterator<Derived, iter_traits_deep, traits> deepiterator;

		wptr get_parent() const { return pParent; };
		wptr get_root() { return (!pParent)? pThis(): get_parent()->get_root(); }
		ptr get_first() const { return pFirst; }
		ptr get_next() const { return pNext; }
		ptr get_last() const { return pLast; }
		wptr get_prev() const { return pPrev; }
		unsigned get_childrencount() const { return count; }

		ptr get_deepfirst_next() const
		{
			if(pFirst) return pFirst;
			if(pNext) return pNext;
			wptr p(get_parent());
			while(!!p)
			{
				ptr r(p->get_next());
				if(!!r) return r;
				p = p->get_parent();
			}
			return 0;
		}

		ptr get_deepfirst_last() const
		{
			ptr p(pThis()), q;
			while(!!p)
			{	q = p;	p = p->get_last();	}
			return q;
		}

		ptr get_deepfirst_prev() const
		{
			if(!!pPrev)
				return pPrev->get_deepfirst_last();
			return get_parent();
		}
		
		ptr get_deeplast_next() const
		{
			if(pLast) return pLast;
			if(pPrev) return pPrev;
			wptr p(get_parent());
			while(!!p)
			{
				ptr r(p->get_prev());
				if(!!r) return r;
				p = p->get_parent();
			}
			return 0;
		}

		ptr get_deeplast_last() const
		{
			ptr p(pThis()), q;
			while(!!p)
			{	q = p;	p = p->get_first();	}
			return q;
		}

		ptr get_deeplast_prev() const
		{
			if(!!pNext)
				return pNext->get_deeplast_last();
			return get_parent();
		}

		
		ptr get_child(int idx) const
		{  
			idx%=count; if(idx<0) idx+=count;
			ptr p(get_first()); 
			while(idx--) p = p->get_next(); 
			return p; 
		}

		int get_index()
		{
			if(!pParent) return 0;
			ptr p = get_parent()->get_first();
			ptr th = pThis();
			int idx=0;
			while(p != th) p = p->get_next(), idx++;
			return idx;
		}
		
		void leave_parent()
		{
			ptr keep(pThis());
			if(!pParent) return;
			if(!!pNext) pNext->pPrev = pPrev;
			else pParent->pLast = pPrev;
			if(!!pPrev) pPrev->pNext = pNext;
			else pParent->pFirst = pNext;
			pParent->count--;
			traits::clear_ptr(pParent);
			traits::clear_ptr(pPrev);
			traits::clear_ptr(pNext);
		}

		void set_first(ptr pNewFirst)
		{
			if(!pNewFirst) return;
			pNewFirst->leave_parent();
			if(pFirst)
			{
				pNewFirst->pNext = pFirst;
				pFirst->pPrev = pNewFirst;
			}
			else 
				pLast = pNewFirst;
			pFirst = pNewFirst;
			pNewFirst->pParent = pThis();
			count++;
			return;
		}

		void set_next(ptr pNewNext)
		{
			if(!pNewNext) return pThis;
			ptr keep(pThis());
			pNewNext->leave_parent();
			if(!!pNext)
			{
				pNext->pPrev = pNewNext;
				pNewNext->pNext = pNext;
				pNewNext->pPrev = pThis();
				pNext = pNewNext;
			}
			else
			{
				pNext = pNewNext;
				pNewNext->pPrev = pThis();
				if(!!pParent) pParent->pLast = pNewNext;
			}
			pNewNext->pParent = pParent;
			pParent->count++;
			return;
		}

		void set_last(ptr pNewLast)
		{
			if(!pNewLast) return;
			pNewLast->leave_parent();
			if(pLast)
			{
				pNewLast->pPrev = pLast;
				pLast->pNext = pNewLast;
			}
			else 
				pFirst = pNewLast;
			pLast = pNewLast;
			pNewLast->pParent = pThis();
			count++;
			return;
		}

		void set_prev(ptr pNewPrev)
		{
			if(!pNewPrev) return;
			ptr keep(pThis());
			pNewPrev->leave_parent();
			if(!!pPrev)
			{
				pPrev->pNext = pNewPrev;
				pNewPrev->pPrev = pPrev;
				pNewPrev->pNext = pThis();
				pPrev = pNewPrev;
			}
			else
			{
				pPrev = pNewPrev;
				pNewPrev->pNext = pThis();
				if(!!pParent) pParent->pFirst = pNewPrev;
			}
			pNewPrev->pParent = pParent;
			pParent->count++;
			return;
		}

		void set_at(int idx, ptr pNew)
		{
			if(!count) 
			{
				set_first(pNew);
				return;
			}
            
			if(idx<0)
			{
				idx++; idx%=count; //-1 remains the last
				ptr p(get_last());
				while(idx++) 
					p=p->get_prev();
				p->set_next(pNew);
			}
			else
			{
				idx%=count; //0 remains the first
				ptr p(get_first());
				while(idx--) 
					p=p->get_next();
				p->set_prev(pNew);
			}
			return;
		}

		hierarchy_node() 
		{ 
			count =0 ; 
			traits::clear_ptr(pFirst);
			traits::clear_ptr(pLast);
			traits::clear_ptr(pParent);
			traits::clear_ptr(pPrev);
			traits::clear_ptr(pNext);
		}

	protected:

		//virtual and automatically called with smart nodes
		// call it in the Derived destructor elsewhere
		void on_lastrelease() 
		{
			while(count)
				get_last()->leave_parent();
			leave_parent();
		}

	private:
		friend class hierarchy_node<Derived,traits>;
		Derived* pThis() const { return static_cast<Derived*>(const_cast<hierarchy_node*>(this)); }

		ptr pFirst, pLast, pNext;
		wptr pPrev, pParent;
		unsigned count;
	};
	

	//hierachy of pointers (dual indirection)
	template<class Ptr, class traits=comp_smart_traits> //Ptr is a smart pointer
	class hierarchy_refnode:
		public hierarchy_node<hierarchy_refnode, traits>
	{
	protected:
		Ptr pVal;

		template<class iter_traits>
		struct iter_deref:
			public iter_traits
		{
			template<class D> //D is hierarchy_refnode
				struct types
			{
				typedef typename Ptr::value_type* access_t;
				typedef typename Ptr::value_type& reference_t;
			};

			template<class P> //p is hierarchy_refnode*
				static Ptr::value_type* access(const P& p) { return p->pVal; }
			template<class D>
				static Ptr::value_type& dereference(D* p) { return *p->pVal; }

		};

		friend struct iter_deref;
	public:

		typedef stdx::iterator<hierarchy_refnode, iter_deref<iter_traits_chain>, traits > shallowiterator;
		typedef stdx::iterator<hierarchy_refnode, iter_deref<iter_traits_deep>, traits > deepiterator;

		hierarchy_refnode(const Ptr& p) { pVal = p; }
	};

	//hierachy of values (auto dereferece)
	template<class Type, class traits=comp_smart_traits> //Type is a value
	class hierarchy_valnode:
		public hierarchy_node<hierarchy_valnode, traits>
	{
	protected:
		Type val;

		template<class iter_traits>
		struct iter_deref:
			public iter_traits
		{
			template<class D> //D is hierarchy_valnode
				struct types
			{
				typedef Type* access_t;
				typedef Type& reference_t;
			};

			template<class P> //p is hierarchy_valnode*
				static Type* access(const P& p) { return &p->val; }
			template<class D>
				static Type& dereference(D* p) { return p->val; }

		};

		friend struct iter_deref;

	public:

		typedef stdx::iterator<hierarchy_valnode, iter_deref<iter_traits_chain>, traits > shallowiterator;
		typedef stdx::iterator<hierarchy_valnode, iter_deref<iter_traits_deep>, traits > deepiterator;

		hierarchy_valnode(const Type& v) { val = v; }
	};


}}