Introduction
This article provides a generic templatized implementation of the composite, including iterators for deep and shallow iteration. It then integrates this composite with a Loki Visitor (see Andrei Alexandrescu's work on the Loki library), detailing different visitation strategies.
Background
The composite is one of my favorite design patterns. It provides a simple implementation of a tree hierarchy. Potential uses include: the scene hierarchy in a graphics system; or the implementation of expression trees. Whilst the composite is a very powerful design pattern and is used in a huge variety of applications, I have not seen any good generic implementations. In approaching this problem, I wanted to deal with many of the key issues with building composites. These issues include memory management, the provision of iterators (both to iterate at a single level in the tree and to iterate over the whole tree), and providing a simple API. In order to achieve these goals, I used the curiously recurring template pattern to provide the programmer with a base class whose interface is easily usable by the inherited class. I have tried to keep dynamic casts to a minimum in the implementation, but have been forced to allow a few in. The deep iterators require 2 dynamic casts, and navigating up the tree requires a dynamic cast.
The implementation of deep and shallow iterators on the composite follows the normal techniques for creating iterators that are compatible with STL containers. The shallow iterator is a bi-directional iterator; whereas the deep iterator is unidirectional. They are not fully STL compliant, because I have not inherited off the STL iterator class, which means that they do not implement iterator traits; however, this addition should be relatively easy if a particular application requires it. The only other area where considerable improvements could be made is that I have implemented the deep iterator to be small, rather than efficient. The deep iterator starts at a particular node, it then moves through all the children, before moving onto siblings. The process of iterating to the next sibling involves searching the entire child list of the parent to get the current position. This could be improved by storing an STL list iterator in the deep iterator class and using it to move to the next sibling. This optimization is left as an exercise, although I will implement it if there is sufficient interest.
The visitor that I have used is the Loki visitor implemented by Alexandrescu. He has created by far the most impressive templatized visitor I have ever come across. At the cost of a single dynamic cast to accept the visitor, he completely decouples the visitor and visitable classes. In doing so, the implementation neatly sidesteps the only really major issue with the visitor pattern as described by Gamma et al. I have expanded on his work in 2 very simple ways. The first point is that if you have a hierarchy of classes, the Loki Visitor will only visit the level at which you specify visitation should occur. By placing some simple code in the base class visitor, you can make the system repeatedly try to visit base classes until it finds one that has been implemented. The second point concerns the integration of the visitor with a composite. Generally, when discussing the visitor pattern, no mention is made of how to visit an entire hierarchy of objects, such as that defined by a composite. By implementing the order of visitation in a number of interface classes, the order of visitation can be easily mixed into each visitor as required. This leaves a remarkably clean interface where a visitor can visit an entire composite hierarchy using the trivial line of code:
visitor( composite );
Using the Code
To implement a generic composite, derive from the CGenericTree class like this:
class CNodeBase : public Types::CGenericTree<CNodeBase>
{
virtual CNodeBase *Clone() { return new CNodeBase( *this ); }
};
In order to make the composite visitable with the Loki visitor, use:
class CNodeBase : public Loki::BaseVisitable<>,
public Types::CGenericTree<CNodeBase>
{
DEFINE_VISITABLE()
virtual CNodeBase *Clone() { return new CNodeBase( *this ); }
};
Examples of the use of the CGenericTree usage can be seen in the NodeBase.h source file. Here, I have created a simple hierarchy of a base class and 2 derived classes, all of them visitable. Note that the implementation of the Clone function is necessary to enable the composite tree copy and equals operators to work properly.
To implement a generic visitor is slightly more complicated. The basic Loki visitor is implemented as follows:
class CVisitorBase : public Loki::BaseVisitor,
public Loki::Visitor<CNodeBase>
{
virtual void Visit( CNodeBase &node ) {}
};
If you look in VisitorBase.h, you will see the base class defined in CVisitorBase. Here, you can see the additional (simple) code necessary to make sure that if we have a type for which the visit function is not implemented in the derived class, a generic base class Visit function can be used. This is demonstrated in CVisitorDerived1. CVisitorDerived2 shows a completely defined visitor.
Now, for the clever part. By mixing in the curiously recurring template from GenericVisitor.h, you can turn your plain vanilla visitor into functors that visit tree hierarchies in a given order. For example:
class CVisitorDerived2TopToBottom :
public CVisitorDerived2,
public Types::CVisitorTopToBottom<CVisitorDerived2TopToBottom,CNodeBase>
{
};
Note that you do not need to implement any code into this final derived version of the visitor, it is only necessary to mix together the 2 base classes to generate a fully working visitor. The usage of the visitor could not then be easier:
CVisitorDerived2TopToBottom visitor;
CNodeBase *head = ;
visitor( head );
The Code
For completeness, I have included the code for the composite base class CGenericTree and the 3 mix-in classes for the visitor. I have removed the const functions and iterators, and reformatted the code slightly to make it a little easier for browsing.
#pragma once
#include <list>
#include <algorithm>
namespace Types {
template <typename T>
class CGenericTree
{
public:
class shallow_iterator;
class deep_iterator;
friend class shallow_iterator;
friend class deep_iterator;
private:
typedef typename T* _tptr;
typedef typename std::list<T*>::iterator container_iterator;
typedef typename std::list<T*>::const_iterator const_container_iterator;
public:
class shallow_iterator
{
friend class CGenericTree<T>;
public:
shallow_iterator() :
m_iterator() {}
shallow_iterator( const shallow_iterator &src ) :
m_iterator( src.m_iterator ) {}
shallow_iterator &operator=( const shallow_iterator &rhs )
{
if ( this != &rhs )
{
m_iterator = rhs.m_iterator;
}
return *this;
}
~shallow_iterator() {}
bool operator==( const shallow_iterator &rhs ) const
{
return m_iterator == rhs.m_iterator;
}
bool operator!=( const shallow_iterator &rhs ) const
{
return m_iterator != rhs.m_iterator;
}
_tptr& operator*()
{
return *m_iterator;
}
_tptr* operator->()
{
return m_iterator.operator->();
}
shallow_iterator& operator++()
{
++m_iterator;
return *this;
}
shallow_iterator operator++(int)
{
shallow_iterator tmp = *this;
++*this;
return tmp;
}
shallow_iterator& operator--()
{
--m_iterator;
return *this;
}
shallow_iterator operator--(int)
{
shallow_iterator tmp = *this;
--*this;
return tmp;
}
private:
explicit shallow_iterator( const container_iterator &iter ) :
m_iterator( iter ) {}
container_iterator GetIterator()
{
return m_iterator;
}
container_iterator m_iterator;
};
class deep_iterator
{
friend class CGenericTree<T>;
public:
deep_iterator() :
m_iterator( NULL ) {}
deep_iterator( const deep_iterator &src ) :
m_iterator( src.m_iterator ) {}
deep_iterator &operator=( const deep_iterator &rhs )
{
if ( this != &rhs )
{
m_iterator = rhs.m_iterator;
}
return *this;
}
~deep_iterator()
{
m_iterator = NULL;
}
bool operator==( const deep_iterator &rhs ) const
{
return m_iterator == rhs.m_iterator;
}
bool operator!=( const deep_iterator &rhs ) const
{
return m_iterator != rhs.m_iterator;
}
_tptr& operator*()
{
return m_iterator;
}
_tptr* operator->()
{
return &**this;
}
deep_iterator& operator++()
{
if ( m_iterator ) m_iterator = m_iterator->GetNext();
return *this;
}
deep_iterator operator++(int)
{
deep_iterator tmp = *this;
++*this;
return tmp;
}
private:
explicit deep_iterator( CGenericTree<T> *src ) :
m_iterator( dynamic_cast<T*> ( src ) ) {}
T* m_iterator;
};
private:
T* GetNext();
T* GetNext( CGenericTree<T> *src );
public:
CGenericTree() : m_parent( NULL ) {}
CGenericTree( const CGenericTree &src );
CGenericTree &operator=( const CGenericTree &rhs );
~CGenericTree() { DeleteAllChildren(); }
virtual T* Clone() = 0;
private:
void CopyAllChildren( const CGenericTree &src );
void DeleteAllChildren();
public:
shallow_iterator begin_shallow()
{
return shallow_iterator( m_children.begin() );
}
shallow_iterator end_shallow()
{
return shallow_iterator( m_children.end() );
}
deep_iterator begin_deep()
{
return deep_iterator( this );
}
deep_iterator end_deep()
{
if ( m_parent )
return deep_iterator( m_parent->GetNext( this ) );
else
return deep_iterator( NULL );
}
T* GetParent();
unsigned int size() const
{
return (unsigned int) m_children.size();
}
bool empty() const
{
return m_children.empty();
}
void DeleteFromTree();
void push_back( T* entry );
T* remove( T* entry );
T* remove( shallow_iterator iter );
T* remove( deep_iterator iter );
private:
std::list<T*> m_children;
CGenericTree<T>* m_parent;
};
template <typename T>
T*
CGenericTree<T>::GetNext()
{
if ( m_children.empty() )
{
if ( m_parent )
return m_parent->GetNext( this );
else
return NULL;
}
return m_children.front();
}
template <typename T>
T*
CGenericTree<T>::GetNext( CGenericTree<T> *src )
{
T* entry = dynamic_cast<T*> ( src );
container_iterator iter = ++( find( m_children.begin(),
m_children.end(), entry ) );
if ( iter != m_children.end() )
return *iter;
if ( m_parent )
return m_parent->GetNext( this );
return NULL;
}
template <typename T>
CGenericTree<T>::CGenericTree( const CGenericTree<T> &src ) : m_parent( NULL )
{
CopyAllChildren( src );
}
template <typename T>
CGenericTree<T> &
CGenericTree<T>::operator=( const CGenericTree<T> &rhs )
{
if ( this != &rhs )
{
DeleteAllChildren();
m_parent = NULL;
CopyAllChildren( rhs );
}
return *this;
}
template <typename T>
void
CGenericTree<T>::CopyAllChildren( const CGenericTree<T> &src )
{
const_container_iterator iter = src.m_children.begin();
for ( ; iter != src.m_children.end(); ++iter )
push_back( (*iter)->Clone() );
}
template <typename T>
void
CGenericTree<T>::DeleteAllChildren()
{
container_iterator iter = m_children.begin();
for ( ; iter != m_children.end(); ++iter )
delete (*iter);
m_children.clear();
}
template <typename T>
void
CGenericTree<T>::DeleteFromTree()
{
if ( m_parent )
m_parent->remove( (T*) this );
delete this;
}
template <typename T>
T*
CGenericTree<T>::GetParent()
{
return dynamic_cast<T*> (m_parent);
}
template <typename T>
void
CGenericTree<T>::push_back( T* entry )
{
m_children.push_back( entry );
entry->m_parent = this;
}
template <typename T>
T*
CGenericTree<T>::remove( T* entry )
{
container_iterator iter = find( m_children.begin(), m_children.end(),
entry );
if ( iter != m_children.end() )
m_children.erase( iter );
entry->m_parent = NULL;
return entry;
}
template <typename T>
T*
CGenericTree<T>::remove( shallow_iterator iter )
{
if ( iter != end_shallow() )
m_children.erase( iter.GetIterator() );
(*iter)->m_parent = NULL;
return *iter;
}
template <typename T>
T*
CGenericTree<T>::remove( deep_iterator iter )
{
if ( (*iter)->m_parent )
(*iter)->m_parent->remove( (*iter) );
return *iter;
}
}
#pragma once
#include <Visitor.h>
namespace Types {
template <typename Visitor, typename BaseVisitable>
class CVisitorTopToBottom
{
public:
virtual ~CVisitorTopToBottom() {}
void operator()( BaseVisitable * );
};
template <typename Visitor, typename BaseVisitable>
class CVisitorBottomToTop
{
public:
virtual ~CVisitorBottomToTop() {}
void operator()( BaseVisitable * );
};
template <typename Visitor, typename BaseVisitable>
class CVisitorLeftToRight
{
public:
virtual ~CVisitorLeftToRight() {}
void operator()( BaseVisitable * );
};
template <typename Visitor, typename BaseVisitable>
void
CVisitorTopToBottom<Visitor, BaseVisitable>::operator()(
BaseVisitable *visitable )
{
visitable->Accept( *dynamic_cast<Visitor*>( this ) );
if ( visitable->empty() )
return;
BaseVisitable::shallow_iterator iter = visitable->begin_shallow();
for ( ; iter != visitable->end_shallow(); ++iter )
(*this)(*iter);
}
template <typename Visitor, typename BaseVisitable>
void
CVisitorBottomToTop<Visitor, BaseVisitable>::operator()(
BaseVisitable *visitable )
{
if ( !visitable->empty() )
{
BaseVisitable::shallow_iterator iter = visitable->begin_shallow();
for ( ; iter != visitable->end_shallow(); ++iter )
(*this)(*iter);
}
visitable->Accept( *dynamic_cast<Visitor*>( this ) );
}
template <typename Visitor, typename BaseVisitable>
void
CVisitorLeftToRight<Visitor, BaseVisitable>::operator()(
BaseVisitable *visitable )
{
if ( !visitable->empty() )
(*this)(*visitable->begin_shallow());
visitable->Accept( *dynamic_cast<Visitor*>( this ) );
if ( visitable->size() > 1 )
{
BaseVisitable::shallow_iterator iter = ++visitable->begin_shallow();
for ( ; iter != visitable->end_shallow(); ++iter )
(*this)(*iter);
}
}
}
Points of Interest
There are a several points of interest in this article, I'll pick out a few that I think are quite neat.
The curiously recurring template pattern allows you to give information about derived classes to a generic base class. This can be used in very simple ways, such as implementing a generic reference counting mechanism (the usual book example). I've used the pattern twice. The first time allowed me to make the interface of CGenericTree into something usable by the base class, without the programmer constantly worrying about dynamic casts. The second time was used to implement the dispatch from the mix-in strategy for the visitor, allowing me to dispatch the visitable objects to the visitor without knowing anything about the final implementation of the visitor.
Implementing STL style iterators is easy and incredibly useful. The 2 iterators used in CGenericTree can be fed into STL algorithms (e.g., find) without thinking about it. The main reason that I believe people don't implement iterators regularly is the occasionally difficult syntax. My advice is that if you are stuck, look at someone else's implementation. I regularly browse the Microsoft list implementation for inspiration. An example of tricky syntax which takes a bit of getting used to is:
const _ctptr* operator->() const { return &**this; }
Loki is an excellent library. There are other articles on CodeProject concerning, for example, Singletons, Factories, or Multiple Dispatch. My advice on all of these is to buy Alexandrescu's book and use the Loki library.
The generic tree was implemented using normal C++ pointers, another implementation is possible using Boost smart pointers. I've done this once before, and it works really well, just note that there are some implementation issues. For example, the parent pointer must be a weak_ptr, whereas the storage must use a shared_ptr. Also, a weak_ptr cannot be created during construction, so if you want composite nodes to add themselves into a tree automatically, you have to use some sort of factory.
Multiple inheritance can be your friend, just be careful how you use it. I learnt about how good multiple inheritance can be by using the Loki visitor. The only thing that I would recommend steering well clear of in multiple inheritance is the diamond. Generally, I use multiple inheritance to mix-in a new feature into a class, or as an interface. In either case, it is a very powerful tool and not something to be scared of. In this article, multiple inheritance has been used in a wide variety of places. It is used to make an object both a member of a composite tree, and to be visitable by a Loki visitor. It is a critical feature of the Loki Visitor, using a small base class for each visitable type. Finally, it allows a Loki visitor to implement a variety of different strategies for visiting a composite tree.
Finally, I recommend having a look at the ++ operator in the deep iterator along with the GetNext() functions. These functions implement the best way to get across all tree elements (in my opinion), without storing any state other than where you are at present. GetNext() is used to do one of two things. If we have any children, then go down to the first child in the list. Otherwise, recursively go to the parent's next sibling using GetNext(this). This function looks for this in the child list, when it is found it returns the next child; if it is the last child, it goes up to the next parent to do a GetNext(this). When we have run out of parents, we use NULL to signify end(). Note that the implementation of the end_deep() function is not quite as trivial as returning NULL, since we allow deep iterations to start and end at a node other than the root node. The end_deep() function is therefore implemented to return what the value of an increment would be if we were doing a full tree iteration. This can either be NULL or the first node outside the desired iteration range.
Post Script
I have never quite understood the paranoia amongst many C++ programmers about using RTTI. The overhead it adds to an application is tiny, and its uses are almost endless; nevertheless, it seems that there are still people out there who don't like the idea of a few tens of KB of extra memory footprint. As such, I've written a version of the CGenericTree class that static casts up the inheritance hierarchy rather than dynamic casts down. Even though this version is likely to be slightly faster, and doesn't require RTTI, I would recommend using the first version included in the main project. The reason for this is that a maintenance programmer years down tracking could make the mistake of not inheriting from the CGenericTree and try to use it as a normal container. In those circumstances, the static casts will fail catastrophically, whereas the dynamic casts would only return NULL. It's marginal, but I would argue that the latter is easier to debug.
History
- 8th August, 2004 - Initial release
- 10th August, 2004 - Additional file added for no dynamic casts generic tree
- 10th October, 2004 - Amended templates to resolve crash in remove functions
License
This article has no explicit license attached to it, but may contain usage terms in the article text or the download files themselves. If in doubt, please contact the author via the discussion board below.
A list of licenses authors might use can be found here.
