Behavioral Patterns  «Prev  Next»

Hierarchical Visitor Pattern


Provide a way to visit every node in a hierarchical data structure such as a tree.


Represent an operation to be performed on the nodes of a hierarchical object structure. Hierarchical Visitor lets one define new operations without changing the classes of the nodes on which it operates. Hierarchical Visitor overcomes the limitations of the traditional VisitorPattern by allowing a programmer to track traversal depth and short-circuit branch traversal.


Consider a file system represented using a hierarchical structure, such as that provided by the CompositePattern. The file objects are leaf nodes and the directories are the composite nodes. Now consider two operations on a file system:
  1. fully qualifying a file name and
  2. searching for a specific file.

To fully qualify a file name, we must traverse each of its parent composites. To do this, we start with a string representing the root composite, and concatenate each child composite until we reach the actual file object. We need to determine what composites (directories) are children of the root and which are its siblings. This requires we track when we are entering a composite and leaving a composite. If we enter the composite bar before we have left the composite foo, we know we have "foo/bar". However, if we leave foo before entering bar then foo and bar are siblings. This is quite impossible if equipped only with the traditional VisitorPattern as it only tells us when we are entering a composite node.
To search a file system optimally, we need to take advantage of fully qualified names. If we are searching for root/foo2/bar3/file.dat, we do not need to search through the branches
  1. root/foo1/*,
  2. "root/foo2/bar1/*", or even
  3. "root/foo2/bar2/*".
Unfortunately, because the traditional VisitorPattern does not have the ability to conditionally traverse a hierarchical structure, we are left with only two choices.
(a) use an alternative means of traversal or (b) search even those branches that have no possibility of a match.
These two examples summarize the advantages of the HierarchicalVisitorPattern. One no longer needs to rely on multiple traversal techniques when the limitations of the traditional visitor pattern must be exceeded. We can generalize these limitations as:
  1. hierarchical navigation: the traditional VisitorPattern has no concept of depth. As a result, visitor cannot determine if one composite is within another composite or beside it.
  2. conditional navigation: the traditional VisitorPattern does not allow branches to be skipped. As a result, visitor cannot stop, filter, or optimize traversal based on some condition.