Visitor Pattern

Working on implementing a SceneGraph, I came across the problem of allowing for operations on each node, without polluting the Node class itself. For example, for debugging purposes, I might want to have each node print out its type. So, I would have a Node.getType function, which returns the type of the node.

But, I wouldn't want to have a Node.printType function that prints its type and also recursively traverses its children to print their types.

The visitor pattern does exactly this. Conceptually, it allows for a virtual function to be added to an entire class hierarchy, without having to put the function within the class hierarchy itself. Below is a example for a usage of the pattern. Note that double-dispatch won't be required in case the class hierarchy places a constraint on the visitors to treat the visited nodes transparently, which is perhaps too much of a restriction. 

#include <iostream>
#include <list>
#include <string>

using namespace std;

class Asteroid;
class MyAsteroid;

class IAsteroidVisitor
{
public:
    virtual void visit(Asteroid&) = 0;
    virtual void visit(MyAsteroid&) = 0;
};

class Asteroid
{
public:
    virtual string getType()
    {
        return "Asteroid";
    }

    virtual void accept(IAsteroidVisitor& visitor)
    {
        visitor.visit(*this);
    }
    
};

class MyAsteroid : public Asteroid
{
public:
    string getType() override
    {
        return "My Asteroid";
    }

    string doFunkyStuff()
    {
        return "I do something the normal asteroid can't!";
    }

    void accept(IAsteroidVisitor& visitor) override
    {
        visitor.visit(*this);
    }
};

class AsteroidList
{
private:
    list<Asteroid*> m_pAsteroidList;
public:
    AsteroidList()
    {
        m_pAsteroidList.push_back(new Asteroid());
        m_pAsteroidList.push_back(new MyAsteroid());
    }

    void accept(IAsteroidVisitor& visitor)
    {
        for (list<Asteroid*>::const_iterator i = m_pAsteroidList.cbegin(); i != m_pAsteroidList.cend(); i++)
        {
            (*i)->accept(visitor);
        }
    }
};

class AsteroidPrintVisitor : public IAsteroidVisitor
{
public:
    void visit(Asteroid& a) override
    {
        cout<<a.getType()<<endl;
    }

    void visit(MyAsteroid &ma) override
    {
        cout<<ma.getType()<<endl;
        cout<<ma.doFunkyStuff()<<endl;
    }
};

int main(int argc, char *argv[])
{
    AsteroidList al;
    AsteroidPrintVisitor p;
    al.accept(p);
    return 0;
}

Static type resolution and double-dispatch

Double dispatch is required due to the same reasons as mentioned  here. The fact that overload resolution is done with the static type leads to issues such as the call to a.collideWith shown below, and double dispatch provides a solution to this - look at the call to s.collideWith(a) and the associated sequence of operations in the subsequent comment.

//Double dispatch as mentioned @ http://en.wikipedia.org/wiki/Double_dispatch
#include <iostream>

using namespace std;

class SpaceShip;
class MySpaceShip;

class Asteroid
{
public:
    virtual void collideWith(SpaceShip&)
    {
        cout<<"Asteroid Collided with SpaceShip";
    }

    virtual void collideWith(MySpaceShip&)
    {
        cout<<"Asteroid Collided with mySpaceShip";
    }
};

class MyAsteroid : public Asteroid
{
public:
    void collideWith(SpaceShip&) override
    {
        cout<<"My asteroid collided with spaceShip";
    }

    void collideWith(MySpaceShip &) override
    {
        cout<<"My asteroid collided with mySpaceShip";
    }
};

class SpaceShip
{
public:
    virtual void collideWith(Asteroid& a)
    {
        a.collideWith(*this);
    }
};

class MySpaceShip : public SpaceShip
{
public:
    void collideWith(Asteroid& a) override
    {
        a.collideWith(*this);
    }
};

int main(int argc, char *argv[])
{
    MyAsteroid m;
    Asteroid& a = m;
    MySpaceShip myS;
    SpaceShip &s = myS;
    a.collideWith(s); //overloading is done by static
                      //type -> vfptr lookup, 
                      //myAsteroid.collideWith(Asteroid&)

    s.collideWith(a); //double-dispatch operates -> 
                      //vfptr lookup, 
                      //myspaceShip.collideWith(Asteroid&), 
                      //typeof(*this) = MySpaceShip,
                      //vfptr lookup, 
                      //myAsteroid.collideWith(MySpaceShip&)
    return 0;
}