Tree - Visitor (Design Pattern)

1 - About

Even if the visitor pattern can be applied to a list, it's usually associated to a Tree structure (Composites).

It separates the operation on the nodes of a tree from its structure. The node are then independent of the operations that apply to them.

The operations are packaged in a separate object, called a visitor. The visitor is then passed to the node of the tree as it’s traversed. If an node “accepts” the visitor, the visitor will then execute the operation for that node. (The node is an argument of the visitor method).

See Visitor

3 - Pro/Cons

The visitor pattern extracts all operations on node from the tree structure because

  • Distributing all operations across the various tree node classes leads to a system that’s hard to understand, maintain, and change.
  • it's confusing to have mixed code such as pretty-printing code or flow analysis code.
  • adding a new operation usually requires recompiling all of these classes.

Others:

  • Accumulating state. Visitors can accumulate state as they visit each element in the object structure. Without a visitor, this state would be passed as extra arguments to the operations that perform the traversal, or they might appear as global variables.
  • It can visit objects that don’t have a common parent class. You can add any type of object to a Visitor interface.

4 - Implementation

With the Visitor pattern, you define two class hierarchies:

  • one for the elements being operated on (the Node hierarchy)
  • and one for the visitors that define operations on the elements (the NodeVisitor hierarchy).

This is the key to the Visitor pattern: The operation that gets executed depends on both the type of Visitor and the type of Node it visits.

5 - Double dispatch

Effectively, the Visitor pattern lets you add operations to classes without changing them. In fact, some programming languages support it directly (CLOS, for example). Languages like C + + and Smalltalk support single-dispatch.

“Double-dispatch” simply means the operation that gets executed depends on:

  • the kind of request
  • and the types of two receivers.

Accept is a double-dispatch operation. Its meaning depends on two types:

  • the Visitor’s
  • and the Element’s. (Node)

An internal iterator will not cause double-dispatching— it will call an operation on the visitor with an element as an argument as opposed to calling an operation on the element with the visitor as an argument.

6 - Structure and Iteration

Often the object structure is responsible for iteration.

  • A collection will simply iterate over its elements, calling the Accept operation on each.
  • A composite (tree) will commonly traverse itself by having each Accept operation traverse the element’s children and call Accept on each of them recursively.

The main reason to put the traversal strategy in the visitor is to implement a particularly complex traversal, one that depends on the results of the operations on the object structure.

  • Visitors can be used to apply an operation over an object structure defined by the Composite pattern.
  • Interpreter: Visitor may be applied to do the interpretation.

8 - Documentation / Reference

data/type/tree/visitor.txt · Last modified: 2017/12/19 11:07 by gerardnico