## Introduction

The composite is a very powerful pattern, allowing a polymorphic tree of
objects to know about its structure. In order for this pattern to be successful,
it is usual to implement a variety of iterators over the hierarchy. This article
deals with the problem of typed iteration. Developing work from a previous
article, I have constructed a set of tree iterators that only return children of
a particular type.

## Background

In a previous article on Composites
and Visitors, I dealt with the problem of creating a generic composite tree
and applying different visitation strategies to that tree. In the first of two
articles, I would like to deal with the problem of typed iteration. The second
article will generalize this concept into the use of functors to limit what tree
nodes are returned in an iteration. Typed iteration is particularly useful
because it handles the down-casting of entries into a particular base type.
Also, because the iterators are essentially STL compliant, they can be fed into
STL algorithms as required.

The composite is often used in areas such as expression trees or 3D graphics
applications. In a graphics application, the scene information is often stored
in a composite. A typed iterator would allow you to iterate over the scene
hierarchy picking out only material node, or only geometry nodes. This could be
particularly useful if you are running a triangulation visitor that will
triangulate all geometry nodes.

## Using the code

To understand how to use the composite tree, you should read my previous
article. Essentially, the iterators are quite simple. The only major changes
from a conventional iterator are that in the `begin`

and
`operator++`

functions, a simple `while`

loop iterates
until we get the correctly typed entry. They must also check to ensure we have
not reached the end of the list. We cannot rely on the user comparing against
`end()`

because the last item in the list might not be our required
type; therefore, the iterator has to carry around the value of
`end()`

. This has two small down-sides. The first is that the
iterator is twice the size of a conventional iterator. The second is that if the
list grows during an iteration, the iterators will be invalidated. The second
issue is no different to the problem seen with certain STL containers such as
vectors or the associative containers. Showing the code, I have stripped out a
lot of extraneous details from the classes (such as the const versions), and
reformatted slightly. If you want to see the full original, then please download
the source.

The shallow iterator:

template <typename T>
class CGenericTree
{
public:
template <typename child>
class typed_iterator
{
friend class CGenericTree<T>;
public:
typed_iterator<child>() :
m_iterator(),
m_end() {}
typed_iterator<child>( const typed_iterator<child> &src ) :
m_iterator( src.m_iterator ),
m_end( src.m_end ) {}
typed_iterator<child> &operator=( const typed_iterator<child> &rhs )
{
if ( this != &rhs )
{
m_iterator = rhs.m_iterator;
m_end = src.m_end;
}
return *this;
}
~typed_iterator<child>() {}
bool operator==( const typed_iterator<child> &rhs ) const
{
return m_iterator == rhs.m_iterator;
}
bool operator!=( const typed_iterator<child> &rhs ) const
{
return m_iterator != rhs.m_iterator;
}
child* operator*()
{
return dynamic_cast<child*>( *m_iterator );
}
child** operator->()
{
return &**this;
}
typename typed_iterator<child>& operator++();
typename typed_iterator<child> operator++(int)
{
typed_iterator<child> tmp = *this;
++*this;
return tmp;
}
private:
explicit typed_iterator<child>( const container_iterator &iter,
const container_iterator &end );
container_iterator m_iterator;
container_iterator m_end;
};
template <typename child>
typename typed_iterator<child> begin_typed()
{
return typed_iterator<child>( m_children.begin(), m_children.end() );
}
template <typename child>
typename typed_iterator<child> end_typed()
{
return typed_iterator<child>( m_children.end(), m_children.end() );
}
};
template <typename T>
template <typename child>
typename CGenericTree<T>::typed_iterator<child>&
CGenericTree<T>::typed_iterator<child>::operator++()
{
++m_iterator;
while ( m_iterator != m_end && !dynamic_cast<child*>( *m_iterator ) )
++m_iterator;
return *this;
}
template <typename T>
template <typename child>
CGenericTree<T>::typed_iterator<child>::typed_iterator(
const container_iterator &iter, const container_iterator &end ) :
m_iterator( iter ),
m_end( end )
{
while ( m_iterator != m_end && !dynamic_cast<CHILD*>( *m_iterator ) )
++m_iterator;
}

The deep iterator:

template <typename T>
class CGenericTree
{
template <typename child>
class typed_deep_iterator
{
friend class CGenericTree<T>;
public:
typed_deep_iterator<child>() : m_iterator( NULL ), m_end( NULL ) {}
typed_deep_iterator<child>( const typed_deep_iterator<child> &src ) :
m_iterator( src.m_iterator ), m_end( src.m_end ) {}
typed_deep_iterator<child>
&operator=( const typed_deep_iterator<child> &rhs )
{
if ( this != &rhs )
{
m_iterator = rhs.m_iterator;
m_end = rhs.m_end;
}
return *this;
}
~typed_deep_iterator<child>()
{
m_iterator = NULL;
m_end = NULL;
}
bool operator==( const typed_deep_iterator<child> &rhs ) const
{
return m_iterator == rhs.m_iterator;
}
bool operator!=( const typed_deep_iterator<child> &rhs ) const
{
return m_iterator != rhs.m_iterator;
}
child* operator*()
{
return dynamic_cast<child*>( m_iterator );
}
child** operator->()
{
return &**this;
}
typed_deep_iterator<child>& operator++()
{
increment();
while( m_iterator != m_end && !dynamic_cast<child*>( m_iterator ) )
increment();
return *this;
}
typed_deep_iterator<child> operator++(int)
{
typed_deep_iterator tmp = *this;
++*this;
return tmp;
}
private:
explicit typed_deep_iterator<child>( T *src, T *end ) :
m_iterator( src ), m_end( end )
{
while ( m_iterator != m_end && !dynamic_cast<child*>( m_iterator ) )
increment();
}
void increment()
{
if ( m_iterator )
m_iterator = m_iterator->GetNext();
}
T* m_iterator;
T* m_end;
};
template < typename child>
typename typed_deep_iterator<child> begin_deep_typed()
{
return typed_deep_iterator<child>( static_cast<T*>(this), end_val() );
}
template <typename child>
typename typed_deep_iterator<child> end_deep_typed()
{
return typed_deep_iterator<child>( end_val(), end_val() );
}
};

This code demonstrates iterating over the children of the node
`head`

only returning nodes of type `CNodeDerived1`

.

CNodeBase::typed_iterator<CNodeDerived1> iter =
head->begin_typed<CNodeDerived1>();
for ( ; iter != head->end_typed<CNodeDerived1>(); ++iter )
cout << (*iter)->GetId() << " " << (*iter)->GetType() << endl;

The next example does the same but uses deep iteration:

CNodeBase::typed_deep_iterator<CNodeDerived1> iter =
head->begin_deep_typed<CNodeDerived1>();
for ( ; iter != head->end_deep_typed<CNodeDerived1>(); ++iter )
cout << (*iter)->GetId() << " " << (*iter)->GetType() << endl;

## Points of Interest

A few quick points to note. The first is the syntax required for templates
defined inside templates. This fooled me for a while as I wrote this class.
Especially, the syntax when you are defining the function bodies outside the
class. I specifically wrote some functions outside the class definition in the
`typed_iterator`

to demonstrate this point. Note the fact that you
have to use the `template <typename T>`

syntax twice. Once for
the outer class and once for the inner class. Once you realize that, the rest
makes sense.

The second point to note is the use of the member function template in order
to generate the necessary begin and end functions to work with the typed
iterators. This again has some oddities with the syntax, most notably the fact
that, in use, you have to specify the template argument (unlike most other
function templates). This is due to the fact that the begin and end functions
differ from each other only in return type, so the static polymorphism of the
compiler cannot resolve the correct one. In use, you would do

iter =
begin<MyType>()

.

The more astute reader will notice that the typed iterator can be used as a
standard shallow or deep iterator simply by passing in the base type as the
template parameter. At first glance, this appears wasteful; however, there is a
way to more efficiently implement this using explicit template instantiation. I
will not go through the detail here, unless there are specific requests from any
readers.

## History

- 6 Oct 04 : Version 1 released.
- 10 Oct 04 : Version 2 released to resolve crash in remove functions.