Visitor
The visitor pattern allows you to easily perform a given operation (function, algorithm, etc…) on each element of a complex structure. The benefit is that you can easily add other operations to perform and you can easily change the structure of the elements. The principle is that the classes that are used to perform the operations and the classes that scroll the structures are different. It also means that, if you know that you will always have only one operation to perform on the structure, this pattern is useless.
Let's take the simple data class:
| Element |
We want to perform an operation on it. Instead of implementing it inside of the class, we will use a visitor class. A visitor class is a class that performs an action on an object. It will perform an action on a whole structure by being called for each element. However, for now, we only have one object. The visitor will be called by the visit method by the data object, and the object will be called by the accept method by the client:
|
 |
| ||||||
 |
 | |||||||
|
| |||||||
 |
||||||||
|
Then you can define a structure of data object and each object will call the accept() method on its sub-elements. You may think that the main drawback of this pattern is that even if the visitor can process all the elements, it does not process it as a whole, i.e. it can't connect the different elements together, so the pattern is limited. Not at all. The visitor can keep information about the elements it has already visited (for example to log lines with appropriate indentation). If the visitor needs information from all the elements (for example to compute a percentage based on the sum), it can visit all the elements, store information, and actually process all the information after the last visit using another method. In other words, you can add states to your visitor.
This process is essentially equivalent to getting the collection's iterator, and using a while(iterator.hasNext()) loop to invoke visitor.visit(iterator.next()). The key difference is that the collection can decide exactly how to step through the elements. If you're familiar with iterators, you may be thinking that the iterator can decide how to step through, too, and the iterator is usually defined by the collection, so what's the difference? The difference is that the iterator is still bound to a while loop, visiting each element in succession, one at a time. With the visitor pattern, the collection could conceivably create a separate thread for each element and have the visitor visiting them concurrently. That's just one example of ways that the collection may decide to vary the method of visitation in a manner that can't be mimicked by an iterator. The point is, it's encapsulated, and the collection can implement the pattern in whatever way it feels is best. More importantly, it can change the implementation at any time, without affecting client code, because the implementation is encapsulated in the foreach method.
An example implementation of Visitor Pattern: String
To illustrate the visitor pattern, let's imagine we're reinventing Java's String class (it'll be a pretty ridiculous reinvention, but it'll be good for this exercise). We're not going to implement very much of the class, but let's assume that we're storing a set of chars that make up the string, and we have a method called getCharAt that takes an int as its only argument, and returns the character at that position in the string, as a char. We also have a method called length that takes no arguments, and returns an int that gives the number of characters in the string. Let's also assume that we want to provide an implementation of the visitor pattern for this class that will take an instance that implements the ICharacterVisitor interface (that we'll define, below), and calls its visit method for each character in the string. First we need to define what this ICharacterVisitor interface looks like:
public interface ICharacterVisitor {
public void visit(final char aChar);
}
Easy enough. Now, let's get down to our class, which we'll call MyString, and it looks something like this:
public class MyString {
// … other methods, fields
// Our main implementation of the visitor pattern
public void foreach(final ICharacterVisitor aVisitor) {
int length = this.length();
// Loop over all the characters in the string
for (int i = 0; i < length; i++) {
// Get the current character, and let the visitor visit it.
aVisitor.visit(this.getCharAt(i));
}
}
// … other methods, fields
}// end class MyString
So, that was pretty painless. What can we do with this? Well, let's make a class called MyStringPrinter, which prints an instance of MyString to the standard output.
public class MyStringPrinter implements ICharacterVisitor {
// We have to implement this method because we're implementing the ICharacterVisitor
// interface
public void visit(final char aChar) {
// All we're going to do is print the current character to the standard output
System.out.print(aChar);
}
// This is the method you call when you want to print a string
public void print(final MyString aStr) {
// we'll let the string determine how to get each character, and
// we already defined what to do with each character in our
// visit method.
aStr.foreach(this);
}
} // end class MyStringPrinter
That was simple too. Of course, it could've been a lot simpler, right? We didn't need the foreach method in MyString, and we didn't need MyStringPrinter to implement the visitor, we could have just used the MyString classes getCharAt and length methods to set up our own for loop ourselves and printed each char inside the loop. Well, sure you could, but what if MyString isn't MyString but instead is MyBoxOfRocks.
Another example implementation of Visitor Pattern: Rock
In a box of rocks, is there a set order that the rocks are in? Unlikely. Of course MyBoxOfRocks has to store the rocks somehow. Maybe, it stores them in an array, and there is actually a set order of the rocks, even if it is artificially introduced for the sake of storage. On the other hand, maybe it doesn't. The point is once again that it is an implementation detail that you as the client of MyBoxOfRocks shouldn't have to worry about, and should never rely on.
Presumably, MyBoxOfRocks wants to provide someway for clients to get to the rocks inside it. It could, once again, introduce an artificial order to the rocks; assign each rock an index and provide a method like public Rock getRock(int aRockNumber). Or maybe it wants to put names on all the rocks and let you access it like public Rock getRock(String aRockName). But maybe it's really just a box of rocks, and there are no names, no numbers, no way of identifying which rock you want; all you know is you want the rocks. Alright, let's try it with the visitor pattern. First, our visitor interface (assume Rock is already defined somewhere, we don't care what it is or what it does):
public interface IRockVisitor {
public void visit(final Rock aRock);
}
Easy. Now out MyBoxOfRocks
public class MyBoxOfRocks {
private Rock[] fRocks;
//… some kind of instantiation code
public void foreach(final IRockVisitor aVisitor) {
int length = fRocks.length;
for (int i = 0; i < length; i++) {
aVisitor.visit(fRocks[i]);
}
}
} // End class MyBoxOfRocks
Huh, what do you know, it does store them in an array. But what do we care now? We already wrote the visitor interface, and all we have to do now is implement it in some class that defines the actions to take for each rock, which we would have to do inside a for loop anyway. Besides, the array is private, our visitor doesn't have any access to that.
And what if the implementor of MyBoxOfRocks did a little homework and found out that comparing a number to zero is infinitesimally faster than comparing it to a non-zero value? Infinitesimal, sure, but maybe when you're iterating over 10 million rocks, it makes a difference (maybe!). So, he decides to change the implementation:
public void foreach(final IRockVisitor aVisitor) {
int length = fRocks.length;
for (int i = length - 1; i >= 0; i--) {
aVisitor.visit(fRocks[i]);
}
}
Now, he's iterating backwards through the array and saving a (very) little time. He's changed the implementation because he found a better way. You didn't have to worry about finding the best way, and you didn't have to change your code because the implementation is encapsulated. And that's not the half of it. Maybe, a new coder takes control of the project, and maybe this coder hates arrays and decides to totally change it:
public class MyBoxOfRocks {
// This coder really likes Linked Lists
private class RockNode {
Rock iRock;
RockNode iNext;
RockNode(final Rock aRock, final RockNode aNext) {
this.iRock = aRock;
this.iNext = aNext;
}
} // end inner class RockNode
private RockNode fFirstRock;
// … some instantiation code goes in here
// Our new implementation
public void foreach (final IRockVisitor aVisitor) {
RockNode current = this.fFirstRock;
// a null value indicates the list is ended
while (current != null) {
// have the visitor visit the current rock
aVisitor.visit(current.iRock);
// step to the next rock
current = current.iNext;
}
}
}
Now, maybe in this instance, linked lists were a poor idea, not as fast as a nice lean array and a for loop. On the other hand, you don't know what else this class is supposed to do. Maybe, providing access to the rocks is only a small part of what it does, and linked lists fit in better with the rest of the requirements. In case I haven't said it enough yet, the point is that you as the client of MyBoxOfRocks don't have to worry about changes to the implementation, the visitor pattern protects you from it.
I have one more trick up my sleeve. Maybe, the implementor of MyBoxOfRocks notices that a lot of visitors are taking a really long time to visit each rock, and it's taking far too long for the foreach method to return because it has to wait for all visitors to finish. He decides it can't wait that long, and he also decides that some of these operations can probably be going on all at once. So, he decides to do something about it, namely, this:
// Back to our backward-array model
public void foreach(final IRockVisitor aVisitor) {
Thread t; // This should speed up the return
int length = fRocks.length;
for (int i = length - 1; i >= 0; i--) {
final Rock current = fRocks[i];
t = new Thread() {
public void run() {
aVisitor.visit(current);
}
}; // End anonymous Thread class
t.start(); // Run the thread we just created.
}
}
If you're familiar with threads, you'll understand what's going on here. If you're not, I'll quickly summarize: a Thread is basically something that can run "simultaneously" with other threads on the same machine. They don't actually run simultaneously of course, unless maybe you have a multi-processor machine, but as far as Java is concerned, they do. So, for instance, when we created this new Thread called t, and defined what happens when the Thread is run (with the run method, naturally), we can then start the Thread, and it will start running, splitting cycles on the processor with other Threads, right away, doesn't have to wait for the current method to return. Likewise, we can start it running and then continue on our own way immediately, without waiting for it to return. So, with the above implementation, the only time we need to spend in this method is the time it takes to instantiate all the threads, start them running, and loop over the array; we don't have to wait for the visitor to actually visit each Rock before we can loop, we just loop right away, and the visitor does its thing on whatever CPU cycles it can swipe. The whole visiting process might take a long time – maybe even longer, if it looses some cycles because of the multiple threads, but the thread from which foreach was invoked doesn't have to wait for it to finish: it can return from the method and be on it's way much faster.
If you're confused about the use of the final Rock called "current" in the above code, it's just a bit of technicality using anonymous classes: they can't access non-final local variables. Even though fRocks doesn't fit into this category (it's not local, but an instance variable), i does. If you tried to remove this line and simply put fRocks[i] in the run method, it wouldn't compile.
So, what happens if you're the visitor, and you decide that you need to visit each rock one at a time? There's a number of reasons this might happen such as, if your visit method changes your instance variables, or it depends on the results of previous calls of visit. Well, the implementation inside the foreach method is encapsulated, so you don't know if it's using separate threads or not. Sure, you could figure it out with some fancy debugging, or some clever printing to std out, but wouldn't it be nice, if you didn't have to? And if you could be sure that, if they change it in the next version, your code will still work properly? Well, fortunately, Java provides the synchronize mechanism, which is basically an elaborate device for locking up blocks of code so that only one Thread can access them at a time. This won't conflict with the interests of the multi-threaded implementation either, because the locked-out thread still won't block the thread that created them, but they will just sit and wait patiently, only blocking code on itself. That's all well beyond the scope of this section, however, but be aware that it's available and probably worth looking into, if you're going to be using synchronicity-sensitive visitors.
Examples
Cost
This pattern is flexible enough not to block you. At worst, you will need to spend time thinking about how to solve problems, but this pattern will never block you.
Creation
This pattern is expensive to create, if your code already exists.
Maintenance
It is easy to adapt the code with this pattern, even if there are new links between the item visits.
Removal
This pattern can be removed using refactoring operations from your IDE.
Advises
- Use the visitor and visit term to indicate the use of the pattern to the other developers.
- If you have and will always have only one visitor, you'd rather implement the composite pattern.
Implementations
The following example is an example in the C# programming language:
using System;
namespace VisitorPattern
{
class Program
{
static void Main(string[] args)
{
var car = new Car();
CarElementVisitor doVisitor = new CarElementDoVisitor();
CarElementVisitor printVisitor = new CarElementPrintVisitor();
printVisitor.visit(car);
doVisitor.visit(car);
}
}
public interface CarElementVisitor
{
void visit(Body body);
void visit(Car car);
void visit(Engine engine);
void visit(Wheel wheel);
}
public interface CarElement
{
void accept(CarElementVisitor visitor); // CarElements have to provide accept().
}
public class Wheel : CarElement
{
public String name { get; set; }
public void accept(CarElementVisitor visitor)
{
visitor.visit(this);
}
}
public class Engine : CarElement
{
public void accept(CarElementVisitor visitor)
{
visitor.visit(this);
}
}
public class Body : CarElement
{
public void accept(CarElementVisitor visitor)
{
visitor.visit(this);
}
}
public class Car
{
public CarElement[] elements { get; private set; }
public Car()
{
elements = new CarElement[]
{ new Wheel{name = "front left"}, new Wheel{name = "front right"},
new Wheel{name = "back left"} , new Wheel{name="back right"},
new Body(), new Engine() };
}
}
public class CarElementPrintVisitor : CarElementVisitor
{
public void visit(Body body)
{
Console.WriteLine("Visiting body");
}
public void visit(Car car)
{
Console.WriteLine("\nVisiting car");
foreach (var element in car.elements)
{
element.accept(this);
}
Console.WriteLine("Visited car");
}
public void visit(Engine engine)
{
Console.WriteLine("Visiting engine");
}
public void visit(Wheel wheel)
{
Console.WriteLine("Visiting " + wheel.name + " wheel");
}
}
public class CarElementDoVisitor : CarElementVisitor
{
public void visit(Body body)
{
Console.WriteLine("Moving my body");
}
public void visit(Car car)
{
Console.WriteLine("\nStarting my car");
foreach (var element in car.elements)
{
element.accept(this);
}
}
public void visit(Engine engine)
{
Console.WriteLine("Starting my engine");
}
public void visit(Wheel wheel)
{
Console.WriteLine("Kicking my " + wheel.name);
}
}
}
The following example is in the D programming language:
import std.stdio;
import std.string;
interface CarElementVisitor {
void visit(Body bod);
void visit(Car car);
void visit(Engine engine);
void visit(Wheel wheel);
}
interface CarElement{
void accept(CarElementVisitor visitor);
}
class Wheel : CarElement {
private string name;
this(string name) {
this.name = name;
}
string getName() {
return name;
}
public void accept(CarElementVisitor visitor) {
visitor.visit(this);
}
}
class Engine : CarElement {
public void accept(CarElementVisitor visitor) {
visitor.visit(this);
}
}
class Body : CarElement {
public void accept(CarElementVisitor visitor) {
visitor.visit(this);
}
}
class Car {
CarElement[] elements;
public CarElement[] getElements() {
return elements;
}
public this() {
elements =
[
cast(CarElement) new Wheel("front left"),
cast(CarElement) new Wheel("front right"),
cast(CarElement) new Wheel("back left"),
cast(CarElement) new Wheel("back right"),
cast(CarElement) new Body(),
cast(CarElement) new Engine()
];
}
}
class CarElementPrintVisitor : CarElementVisitor {
public void visit(Wheel wheel) {
writefln("Visiting "~ wheel.getName() ~ " wheel");
}
public void visit(Car car) {
writefln("\nVisiting car");
foreach(CarElement element ; car.elements) {
element.accept(this);
}
writefln("Visited car");
}
public void visit(Engine engine) {
writefln("Visiting engine");
}
public void visit(Body bod) {
writefln("Visiting body");
}
}
class CarElementDoVisitor : CarElementVisitor {
public void visit(Body bod) {
writefln("Moving my body");
}
public void visit(Car car) {
writefln("\nStarting my car");
foreach(CarElement carElement ; car.getElements()) {
carElement.accept(this);
}
writefln("Started car");
}
public void visit(Engine engine) {
writefln("Starting my engine");
}
public void visit(Wheel wheel) {
writefln("Kicking my "~ wheel.name);
}
}
void main() {
Car car = new Car;
CarElementVisitor printVisitor = new CarElementPrintVisitor;
CarElementVisitor doVisitor = new CarElementDoVisitor;
printVisitor.visit(car);
doVisitor.visit(car);
}
The following example is in the Java programming language:
interface CarElementVisitor {
void visit(Body body);
void visit(Car car);
void visit(Engine engine);
void visit(Wheel wheel);
}
interface CarElement {
void accept(CarElementVisitor visitor); // CarElements have to provide accept().
}
class Wheel implements CarElement {
private String name;
public Wheel(final String name) {
this.name = name;
}
public String getName() {
return this.name;
}
public void accept(final CarElementVisitor visitor) {
/*
* accept(CarElementVisitor) in Wheel implements
* accept(CarElementVisitor) in CarElement, so the call
* to accept is bound at run time. This can be considered
* the first dispatch. However, the decision to call
* visit(Wheel) (as opposed to visit(Engine) etc.) can be
* made during compile time since 'this' is known at compile
* time to be a Wheel. Moreover, each implementation of
* CarElementVisitor implements the visit(Wheel), which is
* another decision that is made at run time. This can be
* considered the second dispatch.
*/
visitor.visit(this);
}
}
class Engine implements CarElement {
/**
* Accept the visitor.
* This method will call the method visit(Engine)
* and not visit(Wheel) nor visit(Body)
* because <tt>this</tt> is declared as Engine.
* That's why we need to define this code in each car element class.
*/
public void accept(final CarElementVisitor visitor) {
visitor.visit(this);
}
}
class Body implements CarElement {
/**
* Accept the visitor.
* This method will call the method visit(Body)
* and not visit(Wheel) nor visit(Engine)
* because <tt>this</tt> is declared as Body.
* That's why we need to define this code in each car element class.
*/
public void accept(final CarElementVisitor visitor) {
visitor.visit(this);
}
}
class Car implements CarElement {
CarElement[] elements;
public Car() {
// Create new Array of elements
this.elements = new CarElement[] { new Wheel("front left"),
new Wheel("front right"), new Wheel("back left") ,
new Wheel("back right"), new Body(), new Engine() };
}
public void accept(final CarElementVisitor visitor) {
visitor.visit(this);
}
}
/**
* One visitor.
* You can define as many visitor as you want.
*/
class CarElementPrintVisitor implements CarElementVisitor {
public void visit(final Body body) {
System.out.println("Visiting body");
}
public void visit(final Car car) {
System.out.println("Visiting car");
for(CarElement element : elements) {
element.accept(visitor);
}
System.out.println("Visited car");
}
public void visit(final Engine engine) {
System.out.println("Visiting engine");
}
public void visit(final Wheel wheel) {
System.out.println("Visiting " + wheel.getName() + " wheel");
}
}
/**
* Another visitor.
* Each visitor has one functional purpose.
*/
class CarElementDoVisitor implements CarElementVisitor {
public void visit(final Body body) {
System.out.println("Moving my body");
}
public void visit(final Car car) {
System.out.println("Starting my car");
for(final CarElement element : elements) {
element.accept(visitor);
}
System.out.println("Started my car");
}
public void visit(final Engine engine) {
System.out.println("Starting my engine");
}
public void visit(final Wheel wheel) {
System.out.println("Kicking my " + wheel.getName() + " wheel");
}
}
public class VisitorDemo {
public static void main(final String[] arguments) {
final CarElement car = new Car();
car.accept(new CarElementPrintVisitor());
car.accept(new CarElementDoVisitor());
}
}
(defclass auto ()
((elements :initarg :elements)))
(defclass auto-part ()
((name :initarg :name :initform "<unnamed-car-part>")))
(defmethod print-object ((p auto-part) stream)
(print-object (slot-value p 'name) stream))
(defclass wheel (auto-part) ())
(defclass body (auto-part) ())
(defclass engine (auto-part) ())
(defgeneric traverse (function object other-object))
(defmethod traverse (function (a auto) other-object)
(with-slots (elements) a
(dolist (e elements)
(funcall function e other-object))))
;; do-something visitations
;; catch all
(defmethod do-something (object other-object)
(format t "don't know how ~s and ~s should interact~%" object other-object))
;; visitation involving wheel and integer
(defmethod do-something ((object wheel) (other-object integer))
(format t "kicking wheel ~s ~s times~%" object other-object))
;; visitation involving wheel and symbol
(defmethod do-something ((object wheel) (other-object symbol))
(format t "kicking wheel ~s symbolically using symbol ~s~%" object other-object))
(defmethod do-something ((object engine) (other-object integer))
(format t "starting engine ~s ~s times~%" object other-object))
(defmethod do-something ((object engine) (other-object symbol))
(format t "starting engine ~s symbolically using symbol ~s~%" object other-object))
(let ((a (make-instance 'auto
:elements `(,(make-instance 'wheel :name "front-left-wheel")
,(make-instance 'wheel :name "front-right-wheel")
,(make-instance 'wheel :name "rear-right-wheel")
,(make-instance 'wheel :name "rear-right-wheel")
,(make-instance 'body :name "body")
,(make-instance 'engine :name "engine")))))
;; traverse to print elements
;; stream *standard-output* plays the role of other-object here
(traverse #'print a *standard-output*)
(terpri) ;; print newline
;; traverse with arbitrary context from other object
(traverse #'do-something a 42)
;; traverse with arbitrary context from other object
(traverse #'do-something a 'abc))
The following example is an example in the Scala programming language:
trait Visitable {
def accept[T](visit: Visitor[T]): T = visit(this)
}
trait Visitor[T] {
def apply(visitable: Visitable): T
}
trait Node extends Visitable
trait Operand extends Node
case class IntegerLiteral(value: Long) extends Operand
case class PropertyReference(name: String) extends Operand
trait Operator extends Node
case object Greater extends Operator
case object Less extends Operator
case class ComparisonOperation(left: Operand, op: Operator, right: Operand) extends Node
class NoSqlStringifier extends Visitor[String] {
def apply(visitable: Visitable): String = visitable match {
case IntegerLiteral(value) => value.toString
case PropertyReference(name: String) => name
case Greater => s">"
case Less => "<"
case ComparisonOperation(left, operator, right) =>
s"${left.accept(this)}: { ${operator.accept(this)}: ${right.accept(this)} }"
}
}
class SqlStringifier extends Visitor[String] {
def apply(visitable: Visitable): String = visitable match {
case IntegerLiteral(value) => value.toString
case PropertyReference(name: String) => name
case Greater => ">"
case Less => "<"
case ComparisonOperation(left, operator, right) =>
s"WHERE ${ left.accept(this)} ${operator.accept(this)} ${right.accept(this) }"
}
}
object VisitorPatternTest {
def main(args: Array[String]) {
val condition: Node = ComparisonOperation(PropertyReference("price"), Greater, IntegerLiteral(12))
println(s"No sql representation = ${condition.accept(new NoSqlStringifier)}")
println(s"Sql representation = ${condition.accept(new SqlStringifier)}")
}
}
Output:
No sql representation = price: { >: 12 }
Sql representation = WHERE price > 12