Boost logo

Boost :

From: Dave Harris (brangdon_at_[hidden])
Date: 2003-09-11 14:42:56

In-Reply-To: <bjmcgf$j1n$1_at_[hidden]>
On Wed, 10 Sep 2003 09:23:30 +0400 Vladimir Prus (ghost_at_[hidden]) wrote:
> > Right now my visitor throws an exception which the call catches
> > and ignores, but this doesn't seem very clean. Is there a better
> > way to do this?
> No, it's the only possible method (well, there's also setjump/longjump
> ;-), but that's no-no in C++ code).
> One other opinion is to make some visitor functions return bool. I
> believe Jeremy is not happy about this idea and I also too have
> reservations about it.
> The first problem is that its interface change. Even if we can do it,
> it means that some visitor function should return bool, even if it has
> never need to terminate search at all.
> Another possible problem is that performance may suffer. Personally, I
> don't know if this is true. The algorithm has a lot of code already,
> and single if statement might have negligible effect.

I've not looked at your specific graph visitor code, but I have some
general comments. In my experience with visitor it is best to move the
data traversal out of the nodes and into the visitor class itself, and
keep it separate from type discovery. This gives the author of a visitor
subclass more control, and allows him to use instance variables to
communicate instead of returning bools.

So for example we might get routines like:

    class Visitor {
        Visitor() : m_break(false) {
        virtual void visit_node( Node *pNode ) {
            traverse_node_with_speed( pNode );
        virtual void traverse_node_with_speed( Node *pNode ) {
            for (Node::iterator i = pNode->begin();
                    i != pNode->end(); ++i)
                i->accept( this );
        virtual void traverse_node_with_break( Node *pNode ) {
            for (Node::iterator i = pNode->begin();
                    i != pNode->end() && !m_break; ++i)
                i->accept( this );
        // ...
        void break_traverse() {
            m_break = true;

        bool m_break;

Here client subclasses can over-ride visit_node() to call whichever
version of traverse_node() they want. If they use
traverse_node_with_break(), they can call break_traverse() when they want
to stop.

Obviously you can juggle the protections and virtual functions to suit you
needs. For example, you can make Node::begin() etc private, make Visitor a
friend of Node and make the traverse_node() functions non-virtual, to keep
things encapsulated. Or you can make Node::begin() a public interface and
allow clients to write their own traverse_node() functions. You may want
to move the break infrastructure into a separate subclass of Visitor. Once
the traversal code is in the visitor, you have a lot of flexibility.

-- Dave Harris, Nottingham, UK

Boost list run by bdawes at, gregod at, cpdaniel at, john at