Conditional Iteration over a Composite using Functors

• Download demo project - 52.1 Kb
• Download source code - 9.02 Kb

Introduction

I've written two articles already about the composite pattern. The first built up a basic composite and covered methods of visiting the composite hierarchy in a variety of orders. The second article demonstrated a relatively clean way to iterate over a composite picking out objects of only one type. This article expands the concept of my second article to allow a functor to pick out objects to be returned during iteration.

Background

My first article on the Composites was Composites and Visitors. This article provided a generic composite, along with a variety of basic iterators for shallow and deep iteration over the composite. It also covered some strategies for defining visitation sequences over the composite.

My second article on Composites concerned the creation of new shallow and deep iterators that only returned objects of a particular type. This article can be found at: Typed Iteration over a Composite.

This article is a generalization of the second article. Providing shallow and deep iterators that return objects that return true from a function object or functor. The first thing to address is the obvious question "What is a functor?". In very simple terms, a functor is a class that contains on overloaded function call operator operator(). The functor can be passed around as if it is an object, but used as if it is a function: hence the name function object. They are effectively an object oriented way of doing something similar to function pointers, with the distinct advantage that the syntax is trivial. My base function object is declared inside the composite base class, primarily so that it can access the template parameter, although there is nothing to stop you declaring it in a separate file.

class base_functor
{
public:
    virtual ~base_functor() {}    // Force base functor to be virtual
    // Pure virtual operator() and Clone
    virtual bool operator()( const T* value ) const = 0;
    virtual base_functor *Clone() const = 0;
};

When you are inheriting off the base_functor, you are forced to declare the overloaded function call operator, as well as a Clone function. The function call operator will do the hard work, and the Clone function is a bit of plumbing to make sure that the iterator can copy the functors when needed.

As an example, I have created 2 functors, both of them are declared as inner classes inside my root composite node. The first is a simple type comparison functor, mirroring the functionality presented in my last article:

template <typename T>
class CTypeComparisonFunctor : public base_functor
{
public:
    virtual bool operator()( const CNodeBase* value ) const
    {
        return dynamic_cast<const T*>( value ) != NULL;
    }
    virtual base_functor *Clone() const
    {
        return new CTypeComparisonFunctor<T>( *this );
    }
};

As you can see, the function call operator simply performs a test cast on the passed in object to see whether it is the correct type, returning true if it is. This functor carries no state, so copying can be left to the default constructors.

The second example shows a basic functor that does carry state. You construct this functor from an ID, and it will only return nodes that have an ID less than the given value.

class CIDFilterFunctor : public base_functor
{
public:
    CIDFilterFunctor( unsigned long filter ) : m_filter( filter ) {}
    CIDFilterFunctor( const CIDFilterFunctor &src ) : m_filter( src.m_filter ) {}
    CIDFilterFunctor &operator=( const CIDFilterFunctor &src )
    {
        if ( this != &src )
            m_filter = src.m_filter;
        return *this;
    }
    virtual bool operator()( const CNodeBase* value ) const
    {
        return value->GetId() < m_filter;
    }
    virtual CIDFilterFunctor *Clone() const
    {
        return new CIDFilterFunctor( *this );
    }
private:
    unsigned long m_filter;
};

This type of functor is by far the most interesting. You could, for example, write a functor that only returned objects that have been edited by the user, or to only return objects that were created in the last hour. It provides a very neat way to extract sets of objects from a large composite hierarchy.

There is an alternative way to perform the same sort of searching, using the find_if STL algorithm. I'll demonstrate both ways of performing conditional iteration further down the article. As you will see, the method using conditional iterator that I have developed has slightly cleaner syntax, at the cost of larger iterators. The find_if method has more complex syntax, but does not require any additional implementation effort, and has smaller iterators. I'll leave the choice of which to use up to you, but my recommendation would be to write conditional iterators if you expect to have to use them a lot, otherwise stick with the STL algorithm method. There is one final advantage to use the conditional iterators. Using the find_if method, you don't have a begin and end iterator, so you can't easily feed the results into other STL algorithms. Having a proper begin and end iterator, albeit only basic forward iterators, allows you to use a wider range of STL algorithms.

Using the code

Firstly, I'll show you the code for the actual iterators.

The shallow iterator:

class functor_iterator
{
    friend class CGenericTree<T>;
public:
    // Normal constructors and destructors
    functor_iterator() : m_iterator(), m_end(), m_functor( NULL ) {}
    functor_iterator( const functor_iterator &src ) :
       m_iterator( src.m_iterator ), m_end( src.m_end ), 
       m_functor( src.m_functor->Clone() ) {}
    functor_iterator &operator=( const functor_iterator &rhs )
    {
        if ( this != &rhs )
        {
            m_iterator = rhs.m_iterator;
            m_end = rhs.m_end;
            m_functor = rhs.m_functor->Clone();
        }
        return *this;
    }
    ~functor_iterator()
    {
        if ( m_functor )
            delete m_functor;
    }
    // Equality operators
    bool operator==( const functor_iterator &rhs ) const
    {
        return m_iterator == rhs.m_iterator;
    }
    bool operator!=( const functor_iterator &rhs ) const
    {
        return m_iterator != rhs.m_iterator;
    }
    // Referencing operators
    _tptr& operator*()
    {
        return *m_iterator;
    }
    _tptr* operator->()
    {
        return &**this;
    }
    // Increment/decrement operators
    typename functor_iterator& operator++()
    {
        ++m_iterator;
        while ( m_iterator != m_end && m_functor && !(*m_functor)( *m_iterator ) )
            ++m_iterator;
        return *this;
    }
    typename functor_iterator operator++(int)
    {
        functor_iterator tmp = *this;
        ++*this;
        return tmp;
    }
private:
    // Private constructor off a container iterator
    explicit functor_iterator(
        const container_iterator &src,
        const container_iterator &end,
        const base_functor &functor ) :
        m_iterator( src ), m_end( end ), m_functor( functor.Clone() )
    {
        while ( m_iterator != m_end && m_functor && !(*m_functor )( *m_iterator ) )
            ++m_iterator;
    }
    // Internal storage is a normal iterator
    container_iterator m_iterator;
    container_iterator m_end;
    const base_functor *m_functor;
};
functor_iterator begin_functor( const base_functor &functor )
{
    return functor_iterator( m_children.begin(), m_children.end(), functor );
}
functor_iterator end_functor( const base_functor &functor )
{
    return functor_iterator( m_children.end(), m_children.end(), functor );
}

The deep iterator:

class deep_functor_iterator
{
    friend class CGenericTree<T>;
public:
    // Normal constructors and destructors
    deep_functor_iterator() : m_iterator( NULL ), 
        m_end( NULL ), m_functor( NULL ) {}
    deep_functor_iterator( const deep_functor_iterator &src ) :
        m_iterator( src.m_iterator ), m_end( src.m_end ), 
        m_functor( src.m_functor->Clone() ) {}
    deep_functor_iterator &operator=( const deep_functor_iterator &rhs )
    {
        if ( this != &rhs )
        {
            m_iterator = rhs.m_iterator;
            m_end = rhs.m_end;
            m_functor = rhs.m_functor->Clone();
        }
        return *this;
    }
    ~deep_functor_iterator()
    {
        if ( m_functor )
            delete m_functor;
    }
    // Equality operators
    bool operator==( const deep_functor_iterator &rhs ) const
    {
        return m_iterator == rhs.m_iterator;
    }
    bool operator!=( const deep_functor_iterator &rhs ) const
    {
        return m_iterator != rhs.m_iterator;
    }
    // Referencing operators
    _tptr& operator*()
    {
        return m_iterator;
    }
    _tptr* operator->()
    {
        return &**this;
    }
    // Increment/decrement operators
    typename deep_functor_iterator& operator++()
    {
        increment();
        while ( m_iterator != m_end && m_functor && !(*m_functor)( m_iterator ) )
            increment();
        return *this;
    }
    typename deep_functor_iterator operator++(int)
    {
        deep_functor_iterator tmp = *this;
        ++*this;
        return tmp;
    }
private:
    // Private constructor off a container iterator
    explicit deep_functor_iterator( T *src, T *end, const base_functor &functor ) :
        m_iterator( src ), m_end( end ), m_functor( functor.Clone() )
    {
        while ( m_iterator != m_end && m_functor && !(*m_functor )( m_iterator ) )
            increment();
    }
    // Private increment operator
    void increment()
    {
        if ( m_iterator )
            m_iterator = m_iterator->GetNext();
    }
    // Internal storage is simply a pointer
    T* m_iterator;
    T* m_end;
    const base_functor *m_functor;
};
deep_functor_iterator begin_deep_functor( const base_functor &functor )
{
    return deep_functor_iterator( static_cast<T*>(this), end_val(), functor );
}
deep_functor_iterator end_deep_functor( const base_functor &functor )
{
    return deep_functor_iterator( end_val(), end_val(), functor );
}

In order to iterate over the entire tree from head only returning nodes with an ID less than 6, you would do the following:

CNodeBase::CIDFilterFunctor fun1( 6 );
CNodeBase::deep_functor_iterator iter_deep_functor = head->begin_deep_functor( fun1 );
for ( ; iter_deep_functor != head->end_deep_functor( fun1 ); ++iter_deep_functor )
    cout << (*iter_deep_functor)->GetId() 
         << " " << (*iter_deep_functor)->GetType() << endl;

To do a similar thing with STL algorithms:

CNodeBase::CIDFilterFunctor fun1( 6 );
CNodebase::deep_iterator iter = find_if( head->begin_deep(), head->end_deep(), fun1 );
for ( ; iter != head->end_deep(); iter = find_if( ++iter, head->end_deep(), fun1 ) )
    cout << (*iter)->GetId() << " " << (*iter)->GetType() << endl;

Conclusions

Composites are a very powerful pattern, usable in a wide variety of areas. By writing custom iterators within the composite, you can extend the power of the pattern a huge amount. The first and most obvious iterators to implement are deep and shallow iterators. These iterate over either an entire sub-tree, or a single layer of children below an object. It is possible to make deep and shallow iterators only return objects of a single type. Anyone who has used the composite pattern will probably have come across the classic problem of constantly needing to perform casts to get the objects in the correct type to do operations on the derived classes. Using typed iteration places all of the casting up in the base iterators and removes that complexity from the code.

Finally, these concepts can be extended to allow iterators to take functors. The functor decides whether a node will be returned in a particular iteration or not. Functors are nothing more than classes that have an overloaded function call operator, meaning that they act as both an object and a function at the same time. Using functor based iterators for conditional iteration is one solution to this problem; however, the same problem can be solved with the find_if STL algorithm. Both have uses under different circumstances, and it is left up to the reader to decide which is more suitable in each particular case.

I hope that over the course of the last three articles, I have enlightened you on some of the intricacies of the composite pattern, and given you some idea of the power of custom iterators. If you have any requests for custom iterators, please let me know and I will consider writing an article on the subject.

History

8 Oct 04: Version 1 released.