How to adapt a visitor interface to an iterator interface?

Question

I'm wondering whether there is a good design pattern or idiom to realize the following:

You have an existing class that provides only a visitor interface, as follows

class Visitor {
public:
  virtual ~Visitor() { }
  virtual void visit(Node *n) = 0;
};

class Tree {
public:
  void accept(Visitor *v);
};

And you want to have an interface that can be used as follows, which should iterate through the tree in the same order that the visitor would have its visit function called.

for(iterator it(...), ite(...); it != ite; ++it) {
  /* process node */
}

The problem appears to be that when we just call visit, we are out of control, and can't temporarily "go back" to the loop body to execute the action for one node. This looks like it should occur regularly in real world programs. Any idea how to solve it?

Answer 1

I had this problem in a real-world setting with an R-tree implementation that provided a visitor interface, whereas I needed an iterator interface. The suggestion by Jerry above works only if you can accept storing all the results in a collection. That may result in high memory consumption if your result set is huge and you don't really need to store them.

One solution that will work for sure is to launch the visitor in a separate thread and start waiting on a conditional variable for the results. When a visit call is made, you store the current result into a shared temp location, and use another conditional variable to wait for the next request. You signal the caller (main) thread's conditional variable before you wait on your own. The caller, which is implementing the iterator interface can then return the value stored at the temp location. During the next iteration, it could signal the visitor thread's conditional variable, and wait on its own for the next item. Unfortunately, this is somewhat costly if you do it on a per-item basis. You can buffer some items to improve the performance.

What we really need is an extra stack and to alternate between two contexts. This abstraction is provided by coroutines. In C++, boost::coroutine provides a clean implementation. Below I include a full example of how visitor pattern can be adapted into an iterator pattern.

#include <iostream>
#include <boost/bind.hpp>
#include <boost/coroutine/coroutine.hpp>

template<typename Data>
class Visitor
{
public:
  virtual ~Visitor() { }
  virtual bool visit(Data const & data) = 0;
};

template <typename Data>
class Visitable    
{
public:
    virtual ~Visitable() {}
    virtual void performVisits(Visitor<Data> & visitor) = 0;
};

// Assume we cannot change the code that appears above

template<typename Data>
class VisitableIterator : public Visitor<Data>
{
private:
    typedef boost::coroutines::coroutine<void()> coro_t;
public:
    VisitableIterator(Visitable<Data> & visitable)
        : valid_(true), visitable_(visitable)
    {
        coro_ = coro_t(boost::bind(&VisitableIterator::visitCoro, this, _1));
    }
    bool isValid() const
    {
        return valid_;
    }
    Data const & getData() const
    {
        return *data_;
    }
    void moveToNext()
    {
        if(valid_) 
            coro_();
    }
private:
    void visitCoro(coro_t::caller_type & ca)
    {
        ca_ = & ca;
        visitable_.performVisits(*static_cast<Visitor<Data> *>(this));
        valid_ = false;
    }
    bool visit(Data const & data)
    {
        data_ = &data;
        (*ca_)();
        return false;
    }
private:
    bool valid_;
    Data const * data_;
    coro_t coro_;
    coro_t::caller_type * ca_;
    Visitable<Data> & visitable_;
};

// Example use below

class Counter : public Visitable<int>
{
public:
    Counter(int start, int end)
        : start_(start), end_(end) {}
    void performVisits(Visitor<int> & visitor)
    {
        bool terminated = false;
        for (int current=start_; !terminated && current<=end_; ++current)
            terminated = visitor.visit(current);
    }
private:
    int start_;
    int end_;
};

class CounterVisitor : public Visitor<int>
{
public:
    bool visit(int const & data)
    {
        std::cerr << data << std::endl;
        return false; // not terminated
    }
};

int main(void)
{
    { // using a visitor
        Counter counter(1, 100);
        CounterVisitor visitor;
        counter.performVisits(visitor);
    }
    { // using an iterator
        Counter counter(1, 100);
        VisitableIterator<int> iter(static_cast<Visitable<int>&>(counter));
        for (; iter.isValid(); iter.moveToNext()) {
            int data = iter.getData();
            std::cerr << data << std::endl;
        }
    }
    return EXIT_SUCCESS;
}

Answer 2

In the general case, I don't think it's possible, at least not cleanly.

At least as it's usually defined, an iterator expects to deal with a homogeneous collection. I.e., an iterator is normally defined something like:

template <class Element>
class iterator // ...

...so a specific iterator can only work with elements of one specific type. The most you can do to work with differing types is create an iterator to (a pointer/reference to) a base class, and let it deal with objects of derived classes.

By contrast, it's pretty easy to write a visitor like this:

class MyVisitor {
public:
    void VisitOneType(OneType const *element);
    void VisitAnotherType(AnotherType const *element);
};

This can visit nodes of either OneType or AnotherType, even if the two are completely unrelated. Basically, you have one Visit member function in your Visitor class for every different type of class that it will be able to visit.

Looked at from a slightly different direction, an iterator is basically a specialized form of visitor that only works for one type of object. You exchange a little more control over the visitation pattern in exchange for losing the ability to visit unrelated types of objects.

If you only need to deal with one type (though that one type may be a base class, and the visited objects are of various derived types), then the obvious method would be to build a "bridge" class that visits objects (Tree nodes, in your example), and when its visit is called, it just copies the address of the node it's visiting into some collection that supports iterators:

template <class T>
class Bridge { 
    std::vector<T *> nodes;
public:
    virtual void visit(T *n) { 
        nodes.push_back(n);
    }

    typedef std::vector<T *>::iterator iterator;

    iterator begin() { return nodes.begin(); }
    iterator end() { return nodes.end(); }
};

Using this would be a two-step process: first visit the nodes like a visitor normally would, then having collected together the nodes of interest you can iterate through them just like you would any other collection that provides iterators. At that point, your visitation pattern is limited only by the class of iterator provided by the collection you use in your bridge.

Answer 3

Building traversal logic in the visitors implementations is indeed not flexible. A usable way to cleanly separate traversing composite structures from visitation may be done via visitor combinators (there are other papers, feel free to google for them).

These slides about the same topic may also be of interest. They explain how to get clean syntax à la boost::spirit rules.