virtual void VisitCard(Card*);
        virtual void VisitChassis(Chassis*);
        virtual void VisitBus(Bus*);
    
        // and so on for other concrete subclasses of Equipment
    protected:
        EquipmentVisitor();
    };
</PRE>

<A NAME="auto1069"></A>
<P><CODE>Equipment</CODE> subclasses define <CODE>Accept</CODE> in
basically the same way: It calls the
<CODE>EquipmentVisitor</CODE> operation that corresponds to the class
that received the <CODE>Accept</CODE> request, like this:</P>

<A NAME="auto1070"></A>
<PRE>
    void FloppyDisk::Accept (EquipmentVisitor&amp; visitor) {
       visitor.VisitFloppyDisk(this);
    }
</PRE>

<A NAME="auto1071"></A>
<P>Equipment that contains other equipment (in particular, subclasses of
<CODE>CompositeEquipment</CODE> in the Composite pattern) implements
<CODE>Accept</CODE> by iterating over its children and calling
<CODE>Accept</CODE> on each of them. Then it calls the
<CODE>Visit</CODE> operation as usual.
For example, <CODE>Chassis::Accept</CODE> could traverse
all the parts in the chassis as follows:</P>

<A NAME="auto1072"></A>
<PRE>
    void Chassis::Accept (EquipmentVisitor&amp; visitor) {
        for (
            ListIterator<Equipment*> i(_parts);
            !i.IsDone();
            i.Next()
        ) {
            i.CurrentItem()->Accept(visitor);
        }
        visitor.VisitChassis(this);
    }
</PRE>

<A NAME="pricingvisitor"></A>
<P>Subclasses of <CODE>EquipmentVisitor</CODE> define particular algorithms
over the equipment structure. The <CODE>PricingVisitor</CODE> computes the
cost of the equipment structure. It computes the net price of all simple
equipment (e.g., floppies) and the discount price of all composite
equipment (e.g., chassis and buses).</P>

<A NAME="auto1073"></A>
<PRE>
    class PricingVisitor : public EquipmentVisitor {
    public:
        PricingVisitor();
    
        Currency&amp; GetTotalPrice();
    
        virtual void VisitFloppyDisk(FloppyDisk*);
        virtual void VisitCard(Card*);
        virtual void VisitChassis(Chassis*);
        virtual void VisitBus(Bus*);
        // ...
    private:
        Currency _total;
    };
    
    void PricingVisitor::VisitFloppyDisk (FloppyDisk* e) {
        _total += e->NetPrice();
    }
    
    void PricingVisitor::VisitChassis (Chassis* e) {
        _total += e->DiscountPrice();
    }
</PRE>

<A NAME="auto1074"></A>
<P><CODE>PricingVisitor</CODE> will compute the total cost of all nodes in the
equipment structure. Note that <CODE>PricingVisitor</CODE> chooses the
appropriate pricing policy for a class of equipment by dispatching to
the corresponding member function. What's more, we can change the
pricing policy of an equipment structure just by changing the
<CODE>PricingVisitor</CODE> class.</P>

<A NAME="auto1075"></A>
<P>We can define a visitor for computing inventory like this:

<A NAME="auto1076"></A>
<PRE>
    class InventoryVisitor : public EquipmentVisitor {
    public:
        InventoryVisitor();
    
        Inventory&amp; GetInventory();
    
        virtual void VisitFloppyDisk(FloppyDisk*);
        virtual void VisitCard(Card*);
        virtual void VisitChassis(Chassis*);
        virtual void VisitBus(Bus*);
        // ...
    
    private:
        Inventory _inventory;
    };
</PRE>

<A NAME="auto1077"></A>
<P>The <CODE>InventoryVisitor</CODE> accumulates the totals for each type of
equipment in the object structure. <CODE>InventoryVisitor</CODE> uses an
<CODE>Inventory</CODE> class that defines an interface for adding equipment
(which we won't bother defining here).</P>

<A NAME="auto1078"></A>
<PRE>
    void InventoryVisitor::VisitFloppyDisk (FloppyDisk* e) {
        _inventory.Accumulate(e);
    }
    
    void InventoryVisitor::VisitChassis (Chassis* e) {
        _inventory.Accumulate(e);
    }
</PRE>

<A NAME="auto1079"></A>
<P>Here's how we can use an <CODE>InventoryVisitor</CODE> on an
equipment structure:</P>

<A NAME="auto1080"></A>
<PRE>
    Equipment* component;
    InventoryVisitor visitor;
    
    component->Accept(visitor);
    cout &lt;&lt; "Inventory "
         &lt;&lt; component->Name()
         &lt;&lt; visitor.GetInventory();
</PRE>

<A NAME="auto1081"></A>
<P>Now we'll show how to implement the Smalltalk example from the Interpreter
pattern (see
<A HREF="pat5cfs-1.htm#Smalltalk_example_in_Interpreter" tppabs="http://ultra/development/DesignPatterns/lowres/pat5cfs.htm#Smalltalk_example_in_Interpreter" TARGET="_mainDisplayFrame">page 248</A>) with the
Visitor pattern. Like the previous example, this one is so small that
Visitor probably won't buy us much, but it provides a good illustration of
how to use the pattern. Further, it illustrates a situation in which
iteration is the visitor's responsibility.</P>

<A NAME="auto1082"></A>
<P>The object structure (regular expressions) is made of four classes,
and all of them have an <CODE>accept:</CODE> method that takes the
visitor as an argument.  In class <CODE>SequenceExpression</CODE>, the
<CODE>accept:</CODE> method is</P>

<A NAME="auto1083"></A>
<PRE>
    accept: aVisitor
         ^ aVisitor visitSequence: self
</PRE>

<A NAME="altexp"></A>
<A NAME="literalexp"></A>
<A NAME="repeatexp"></A>
<P>In class <CODE>RepeatExpression</CODE>, the <CODE>accept:</CODE> method
sends the <CODE>visitRepeat:</CODE> message.
In class <CODE>AlternationExpression</CODE>, it sends the
<CODE>visitAlternation:</CODE> message.
In class <CODE>LiteralExpression</CODE>, it sends the
<CODE>visitLiteral:</CODE> message.</P>

<A NAME="seqexp"></A>
<P>The four classes also must have accessing functions that the visitor
can use.  For <CODE>SequenceExpression</CODE> these are
<CODE>expression1</CODE> and <CODE>expression2</CODE>; for
<CODE>AlternationExpression</CODE> these are <CODE>alternative1</CODE>
and <CODE>alternative2</CODE>; for
<CODE>RepeatExpression</CODE> it is <CODE>repetition</CODE>; and for
<CODE>LiteralExpression</CODE> these are <CODE>components</CODE>.</P>

<A NAME="auto1084"></A>
<P>The ConcreteVisitor class is <CODE>REMatchingVisitor</CODE>.  It
is responsible for the traversal because its traversal algorithm
is irregular.  The biggest irregularity is that a
<CODE>RepeatExpression</CODE> will repeatedly traverse its component.
The class <CODE>REMatchingVisitor</CODE> has an instance variable
<CODE>inputState</CODE>.   Its methods are essentially the same as
the <CODE>match:</CODE> methods of the expression classes in the
Interpreter pattern except they
replace the argument named <CODE>inputState</CODE> with the
expression node being matched.  However, they
still return the set of streams that the expression would match
to identify the current state.</P>

<A NAME="auto1085"></A>
<PRE>
    visitSequence: sequenceExp
        inputState := sequenceExp expression1 accept: self.
        ^ sequenceExp expression2 accept: self.
    
    visitRepeat: repeatExp
        | finalState |
        finalState := inputState copy.
        [inputState isEmpty]
            whileFalse:
                [inputState := repeatExp repetition accept: self.
                finalState addAll: inputState].
        ^ finalState
    
    visitAlternation: alternateExp
        | finalState originalState |
        originalState := inputState.
        finalState := alternateExp alternative1 accept: self.
        inputState := originalState.
        finalState addAll: (alternateExp alternative2 accept: self).
        ^ finalState
    
    visitLiteral: literalExp
        | finalState tStream |
        finalState := Set new.
        inputState
            do:
                [:stream | tStream := stream copy.
                    (tStream nextAvailable:
                        literalExp components size
                    ) = literalExp components
                        ifTrue: [finalState add: tStream]
                ].
        ^ finalState
</PRE>

<A NAME="knownuses"><A>
<H2><A HREF="#relatedpatterns"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0 
ALT="next: Related Patterns"></A> Known Uses</H2> 

<A NAME="smalltalk-use-visitor"></A>
<P>The Smalltalk-80 compiler has a Visitor class called ProgramNodeEnumerator.
It's used primarily for algorithms that analyze source code.
It isn't used for code generation or pretty-printing, although it could be.</P>

<A NAME="auto1086"></A>
<P>IRIS Inventor [<A HREF="bibfs-1.htm#strauss_oopsla93" tppabs="http://ultra/development/DesignPatterns/lowres/bibfs.htm#strauss_oopsla93" TARGET="_mainDisplayFrame">Str93</A>]
is a toolkit for developing 3-D graphics applications. Inventor
represents a three-dimensional scene as a hierarchy of nodes, each
representing either a geometric object or an attribute of one.
Operations like rendering a scene or mapping an input event require
traversing this hierarchy in different ways. Inventor does this
using visitors called "actions." There are different visitors for
rendering, event handling, searching, filing, and determining
bounding boxes.</P>

<A NAME="auto1087"></A>
<P>To make adding new nodes easier, Inventor implements a
double-dispatch scheme for C++. The scheme relies on run-time type
information and a two-dimensional table in which rows represent
visitors and columns represent node classes.  The cells store a
pointer to the function bound to the visitor and node class.</P>

<A NAME="fresco"></A>
<A NAME="linton"></A>
<P>Mark Linton coined the term "Visitor" in the X Consortium's
Fresco Application Toolkit specification [<A HREF="bibfs-1.htm#fresco" tppabs="http://ultra/development/DesignPatterns/lowres/bibfs.htm#fresco" TARGET="_mainDisplayFrame">LP93</A>].</P>

<A NAME="relatedpatterns"></A>
<H2><A HREF="#last"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0 ALT="next: 
navigation"></A> Related Patterns</H2> 

<A NAME="auto1088"></A>
<P><A HREF="pat4cfs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/pat4cfs.htm" TARGET="_mainDisplayFrame">Composite (163)</A>:
Visitors can be used to apply an operation over an object structure
defined by the Composite pattern.</P>

<A NAME="auto1089"></A>
<P><A HREF="pat5cfs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/pat5cfs.htm" TARGET="_mainDisplayFrame">Interpreter (243)</A>:
Visitor may be applied to do the interpretation.</P>

<A NAME="last"></A>
<P><A HREF="#intent"><IMG SRC="up3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/up3.gif" BORDER=0></A><BR>
<A HREF="disc5fs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/disc5fs.htm" TARGET="_mainDisplayFrame"><IMG SRC="rightar3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/rightar3.gif"
        ALIGN=TOP BORDER=0></A> <A HREF="disc5fs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/disc5fs.htm"
        TARGET="_mainDisplayFrame">Discussion of Behavioral Patterns</A><BR>
<A HREF="pat5jfs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/pat5jfs.htm" TARGET="_mainDisplayFrame"><IMG SRC="leftarr3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/leftarr3.gif"
        ALIGN=TOP BORDER=0></A> <A HREF="pat5jfs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/pat5jfs.htm"
        TARGET="_mainDisplayFrame">Template Method</A>
</P>

<HR>

<A NAME="footnote10"></A>
<P><SUP>10</SUP>We could use function overloading to give these operations
the same simple name, like <CODE>Visit</CODE>, since the operations are
already differentiated by the parameter they're passed.  There are
pros and cons to such overloading.  On the one hand, it reinforces the
fact that each operation involves the same analysis, albeit on a
different argument.  On the other hand, that might make what's going
on at the call site less obvious to someone reading the code.  It
really boils down to whether you believe function overloading is good
or not.
</P>

<A NAME="footnote11"></A>
<P><SUP>11</SUP>If we can have <EM>double</EM>-dispatch, then why not
<EM>triple</EM> or <EM>quadruple</EM>, or any other number?  Actually,
double-dispatch is just a special case of <STRONG>multiple
dispatch</STRONG>, in which the operation is chosen based on any number of
types.  (CLOS actually supports multiple dispatch.)  Languages that
support double- or multiple dispatch lessen the need for the
Visitor pattern.
</P>

</BODY>

</HTML>