IDevResource.com VS.NET channel - Visitor Pattern by Shivesh Viswanathan

The Developer's Resource & Community Site

COM	XML	ASP	Java & Misc.	NEW: VS.NET
International	This Week	Forums	Author Central	Find a Job

Visitor Pattern

Author: Shivesh Viswanathan
Date Submitted: April 12 2000

Introduction

Visitor pattern is a behavioral design pattern. One of the main considerations in deciding upon a data structure for your application is the type of operations you would like to perform on that particular data, in other words, the behavior of your program. Visitor pattern is used when your product development life cycle requires frequent addition/removal of operations which are to be performed on the data structure. Like many other design patterns, it can be used with any data structure.

Target

Visitor design pattern targets the kind of applications in which your structure of data doesn't change very often (best if it doesn't), but the operations keep changing very often as you progress with your product development.

The pattern

Let's take the example of a tree which consisting of one type of node. In C, your preorder algorithm would probably look like this:


travPreorder( struct node* root, HandlerFunc operation )
{
	// You traverse to reach a node Node
	// you say ....
	operation( Node );
}

What are we achieving here? We have effectively separated out the operations to be performed on the tree from the iterator module as long as the operations adhere to the HandlerFunc protocol.

So, the essence of such a code is:

You want to define different operations on your tree and be able to integrate them seamlessly
Your operations are willing to adhere to the standard.

The C++ solution to such a problem would be to declare an abstract base class called, say COperation:


Class COperation
{
	HandleNode( struct node* node )  =  0;
};

Your specific operations can derive from it, which give their own definition of how they want to handle the node passed to them. In the client code, you instantiate an object of such an operation and pass it to your visiting logic, whose prototype will look something like this:


Visitor( struct node* root, COperation* operation )
{
	// You traverse to reach a node Node
	// you say ....
	operation->HandleNode( Node );
}

This was basically a subset of visitor pattern. Note here that this is not specific to tree data structure alone. A little thought would make it clear that this can be applied to any iterator for any kind of structure. And this is also not restricted by the nodes that form your structure. The case we discussed above was for homogeneous data structures. Visitor pattern works equally well with a heterogeneous data structure. And herein lies the true power of this pattern.

Now let's see what changes will have to be made if this design is to work with such a structure. The objective here is to call a function based on two attributes; the node type and the operation type¹.For that, what you do is, ask the node to accept an operation (and due to dynamic linking, you reach the correct node) and let it call "into" that operation (and due to dynamic linking again, you reach the correct operation). This node can access only the part of operation pertaining to itself. Instead of confusing anymore, I will take you to some code.

Your Visitor() changes to this:


Visitor( struct node* root, COperation* operation )
{
	// You traverse to reach a node Node
	// you say ....
	Node->AcceptOperation( operation );
}

The AcceptOperation() function is overloaded in each node class and looks like this:


CAtypeNode::AcceptOperation( COperation* operation )
{
	operation->HandleAtypeNode( this );
}

CBtypeNode::AcceptOperation( COperation* operation )
{
	operation->HandleBtypeNode( this );
}

Operation class has one function for each type of node:


Class COperation
{
	HandleAtypeNode( struct anode* node )  =  0;
	HandleBtypeNode( struct bnode* node )  =  0;
	HandleCtypeNode( struct cnode* node )  =  0;
	// And so on......
};

Hence, which of these functions is called depends on two things: Which node's AcceptOperation() is called and which operation's HandleXXXNode() is called.

So you see, traversal algorithms remain independent of the nodes and operations. However, the major drawback of Visitor pattern lies here. Each time you add a type of node, you modify operation to make it "aware" of that node.

Drawbacks

Visitor pattern can only be used in case you have your hierarchy of nodes well defined. If you add a node, you have to add a function HandleThattypeNode() to the abstract class COperation, breaking the whole structure from top to bottom, which could be a pretty bad idea.
The operation object needs to access the node to perform the operation over it. This requires node to expose its internal structure to the operation. Now if the operation is considered as a logical extension to the node (as most C++ fans would put it!), the operation could be given "special privilege". In C++, you can do this by having the operation as "friend" of node.

Specific advantages

Visitor pattern may be used for totally unrelated node types as long as you can traverse them. You might want to do a "View" on a bitmap or on a GIF/JPEG. Visitor pattern doesn't care if your bitmap and GIF/JPEG are related through inheritance hierarchy or not.

1) The technique wherein an "operation" is performed depending on two "destinations", is called "Double dispatching". Basically, here, the operation is dependant on two attributes, the operation and the node. C++ does not support double dispatching. Smalltalk supports multiple dispatching.

Mail a question to the author!!

As part of the IDevResource commitment to Open Publishing, all of our authors are available to answer all of your trickiest questions at Author Central. For information about the authors, or to mail a question, visit them at Author Central.

Contribute to IDR:

To contribute an article to IDR, a click here.

To contact us at IDevResource.com, use our feedback form, or email us.

To comment on the site contact our webmaster.