Visitor

From Wikibooks, open books for an open world
Jump to: navigation, search

Template method Computer Science Design Patterns
Visitor
Model–view–controller

The visitor pattern is something like a variation on the Iterator pattern except it allows even more encapsulation. The purpose is to provide a way of performing a certain operation (function, algorithm, etc) for each element in some sort of collection of elements. The basic premise is that you have a Visitor interface with a method named visit which take one argument, and the collection has a method (typically named foreach) which takes a Visitor as the argument. This method of the collection will use some encapsulated way of stepping through each of its elements, and for each element, it will invoke the Visitors's visit method, passing as the argument the current element.

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 what ever 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 a simple implementation of 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 which takes an int as it's only argument, and returns the character at that position in the string, as a char. We also have a method called length which takes no arguments, and returns an int which 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 which will take an instance that implements the CharacterVisitor interface (which we'll define, below), and calls its visit method for each character in the string. First we need to define what this CharacterVisitor interface looks like:

public interface CharacterVisitor {
 
  public void visit(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(CharacterVisitor 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. So what can we do with this? Well let's make a class called MyStringPrinter, which prints an instance of MyString to the standard output.

class MyStringPrinter implements CharacterVisitor {
 
  // We have to implement this method because we're implementing the CharacterVisitor
  // interface
  public void visit(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(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. 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's 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 at 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's 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 out visitor interface (assume Rock is already defined somewhere, we don't care what it is or what it does):

public interface RockVisitor {
  public void visit(Rock aRock);
}

Easy. Now out MyBoxOfRocks

public class MyBoxOfRocks {
 
  private Rock[] fRocks;
 
  //... some kind of instantiation code
 
  public void foreach(RockVisitor 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 which 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. 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(RockVisitor 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(Rock aRock, 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 (RockVisitor 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(RockVisitor aVisitor) {
 
  Thread t; // This should speed up the return
 
  int length = fRocks.length;
  for (int i = length-1; i >= 0; i--) {
    final Rock curr = fRocks[i]
    t = new Thread() {
      public void run() {
        aVisitor.visit(curr);
      }
    }; // End anonymous Thread class
 
    t.start(); // Run the thread we just created.
 
    current = current.iNext;
  }
}

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 a-running and it will start running, splitting cycles on the processor with other Threads, right away, it 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 just as long (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 curr in the above code, it's just a bit of a technicality for using anonymous classes: they can't access non final local variables. Even though fRocks doesn't fit into this category (it's not local, it's an instance variable), it 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 maybe it depends on the results of previous calls to visit. Well the implementation inside the foreach method is encapsulated from you, 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, they'll 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.

Implementation in Java

The following example is in the Java programming language:

interface CarElementVisitor {
    void visit(Wheel wheel);
    void visit(Engine engine);
    void visit(Body body);
    void visit(Car car);
}
interface CarElement {
    void accept(CarElementVisitor visitor); // CarElements have to provide accept().
}
class Wheel implements CarElement {
    private String name;
 
    public Wheel(String name) {
        this.name = name;
    }
 
    public String getName() {
        return this.name;
    }
 
    public void accept(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 {
    public void accept(CarElementVisitor visitor) {
        visitor.visit(this);
    }
}
class Body implements CarElement {
    public void accept(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(CarElementVisitor visitor) {    
        for(CarElement elem : elements) {
            elem.accept(visitor);
        }
        visitor.visit(this);    
    }
}
class CarElementPrintVisitor implements CarElementVisitor {
    public void visit(Wheel wheel) {      
        System.out.println("Visiting " + wheel.getName() + " wheel");
    }
 
    public void visit(Engine engine) {
        System.out.println("Visiting engine");
    }
 
    public void visit(Body body) {
        System.out.println("Visiting body");
    }
 
    public void visit(Car car) {      
        System.out.println("Visiting car");
    }
}
class CarElementDoVisitor implements CarElementVisitor {
    public void visit(Wheel wheel) {
        System.out.println("Kicking my " + wheel.getName() + " wheel");
    }
 
    public void visit(Engine engine) {
        System.out.println("Starting my engine");
    }
 
    public void visit(Body body) {
        System.out.println("Moving my body");
    }
 
    public void visit(Car car) {
        System.out.println("Starting my car");
    }
}
public class VisitorDemo {
    public static void main(String[] args) {
        CarElement car = new Car();
        car.accept(new CarElementPrintVisitor());
        car.accept(new CarElementDoVisitor());
    }
}
Implementation in D

The following example is in the D programming language:

import std.stdio;
import std.string;
 
interface CarElementVisitor {
    void visit(Wheel wheel);
    void visit(Engine engine);
    void visit(Body bod);
    void visitCar(Car car);
}
 
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(Engine engine) {
        writefln("Visiting engine");
    }
    public void visit(Body bod) {
        writefln("Visiting body");
    }
    public void visitCar(Car car) {
        writefln("\nVisiting car");
        foreach(CarElement element ; car.elements) {
            element.accept(this);
        }
        writefln("Visited car");
    }
}
 
class CarElementDoVisitor : CarElementVisitor {
    public void visit(Wheel wheel) {
        writefln("Kicking my "~ wheel.name);
    }
    public void visit(Engine engine) {
        writefln("Starting my engine");
    }
    public void visit(Body bod) {
        writefln("Moving my body");
    }
    public void visitCar(Car car) {
        writefln("\nStarting my car");
        foreach(CarElement carElement ; car.getElements()) {
            carElement.accept(this);
        }
        writefln("Started car");
    }
}
 
void main(){
    Car car = new Car;
    CarElementVisitor printVisitor = new CarElementPrintVisitor;
    CarElementVisitor doVisitor = new CarElementDoVisitor;
    printVisitor.visitCar(car);
    doVisitor.visitCar(car);
}
Implementation in C#

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 printVisitor = new CarElementPrintVisitor();
            CarElementVisitor doVisitor = new CarElementDoVisitor();
            printVisitor.visitCar(car);
            doVisitor.visitCar(car);
        }
    }
 
    public interface CarElementVisitor
    {
        void visit(Wheel wheel);
        void visit(Engine engine);
        void visit(Body body);
        void visitCar(Car car);
    }
    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(Wheel wheel)
        {
            Console.WriteLine("Visiting " + wheel.name + " wheel");
        }
        public void visit(Engine engine)
        {
            Console.WriteLine("Visiting engine");
        }
        public void visit(Body body)
        {
            Console.WriteLine("Visiting body");
        }
 
        public void visitCar(Car car)
        {
            Console.WriteLine("\nVisiting car");
            foreach (var element in car.elements)
            {
                element.accept(this);
            }
            Console.WriteLine("Visited car");
        }
    }
 
    public class CarElementDoVisitor : CarElementVisitor
    {
        public void visit(Wheel wheel)
        {
            Console.WriteLine("Kicking my " + wheel.name);
        }
        public void visit(Engine engine)
        {
            Console.WriteLine("Starting my engine");
        }
        public void visit(Body body)
        {
            Console.WriteLine("Moving my body");
        }
        public void visitCar(Car car)
        {
            Console.WriteLine("\nStarting my car");
            foreach (var element in car.elements)
            {
                element.accept(this);
            }
        }
 
    }
}
Implementation in Lisp
(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))
Implementation in Scala

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"&gt"
    case Less => "&lt"
    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: { &gt: 12 }
   Sql representation = WHERE price > 12


Clipboard

To do:
Add more illustrations.


Template method Computer Science Design Patterns
Visitor
Model–view–controller


You have questions about this page?
Ask it here:


Create a new page on this book: