Hierarchical Visitor Pattern
Hierarchical Visitor PatternBackground
Hierarchical Visitor -- found to recur while working with the CompositePattern and other hierarchical data-structures. Occurrences of HierarchicalVisitorPattern included a logical and hierarchical grouping of network hosts, rules, Security Permissions and Roles, and the TestCase and TestSuite classes described in CppUtxOverview. I, along with some others have used the hierarchical visitor in favor of the traditional VisitorPattern for the last three years. I recently attempted to simplify or decompose this pattern further in HierarchicalVisitorDiscussion. While some great ideas were contributed, I still found this to be (for me) the most straight forward representation. -- RobertDiFalco
Intent
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.
Motivation
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: (a) fully qualifying a file name and (b) 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 don't need to search through the branches "root/foo1/*", "root/foo2/bar1/*", or even "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:
Applicability
Like the traditional VisitorPattern, the HierarchicalVisitorPattern combines a FunctorObject (the Visitor object itself) with InternalIterators (the accept members of the CompositePattern). Together, these form a generalized mechanism for tree traversal. These allow the HierarchicalVisitorPattern to be useful anywhere the traditional VisitorPattern would. The hierarchical visitor is then made more useful by allowing hierarchical navigation and conditional navigation.
Hierarchical navigation
Hierarchical navigation is important for any traversal that needs to know whether one node is the child of another or its sibling. The simplest example of this is tree listings where an indentation level needs to be maintained. With the traditional VisitorPattern, one can only determine when we are entering a node. This tells us that we may want to indent but gives us no clues about outdenting. We don't know if we have left the previous node before we entered the current node.
The HierarchicalVisitorPattern removes this limitation by defining a two method protocol when visiting nodes -- visitEnter and visitLeave. If we are entering the composite node bar before leaving the composite node foo, we can safely assume that bar is a child (and not a sibling) of the composite foo.
Conditional Navigation
Conditional navigation is required to skip unnecessary branches and all of their children. Consider the second operation of the File System example. The search for a specific file in a particular path can only be performed optimally if we can dispose of branches that have no possibility of providing a match. Consider the following graph:
* 1. * 1.1 * 1.2
* 1.3
* 2. * 2.1 * 2.2The traditional VisitorPattern would have to visit each leaf of the entire structure in order to find the leaf labeled "2.2"! Even though we can see that "1" does not match the root ancestor of "2.2", we would still have no choice but to perform a match for the leaf "1.3.1.1". The only way to avoid this is to abandon the traditional visitor and use another means of traversal. Most programmers violate the encapsulation provided by the traditional visitor when performing tree searches.
HierarchicalVisitorPattern allows us to solve this problem within a single visiting paradigm. It does so by having each invocation of accept answer a boolean traversal state for its depth of the tree. For example, if accept on a composite or leaf answers false, traversal immediately stops at that tree depth. In other words, no more of its siblings will be traversed, even if some of those siblings are composites with children of their own. Reconsider the example graph. As we visit the node labeled "1", we can cause its accept message to answer false like so:
boolean visitEnter( Composite node )
{
String sLabel = node.getLabel();
return sLabel.equals( "2.2", sLabel.length() );
}
If the composite's label does not match the first N characters of "2.2", we do not enter the node and we do not traverse its children. We then proceed directly to the node labeled "2". For this composite node, the expression will return true, causing us to continue searching its children. This strategy allows us to find the optimal path to "2.2". Furthermore, we cannot construct this strategy using the traditional visitor alone.
Participants
Collaborations
Hierarchical Visitor collaborates directly with Leaf and Composite objects. The members of the visitor interface are called indirectly by the implementation of accept in the Composite and Leaf classes.
When Composite accepts a visitor (e.g. composite.accept(Visitor)), it notifies the visitor that it is entering a new branch by sending the visitor the message:
boolean visitEnter( this )The this argument is the Composite object itself. We can use visitEnter to process the composite or wait for visitLeave - after its children have been visited. The composite's accept implementation uses the answer from visitEnter to determine whether its children should accept this visitor. So, if visitEnter answers true, accept is invoked on each of its children or until one of the accept invocations answers false. This essentially works like a do...while loop. The first child accept that answers false causes traversal at that level to stop. We then give accept method of this composite to answer true or false. This result comes from the answer to visitLeave. The whole Composite accept implementation looks like the following:
public boolean accept( Visitor v )
{
if ( v.visitEnter( this ) ) // enter this node?
m_children.doWhile( <each>.accept( v ) );
return visitLeave( this );
}
Remember that each Composite may itself be the child of another Composite. So, if visitLeave returns false, this would short-circuit visiting its sibling nodes. The Leaf implementation of accept is very simple. It just invokes visit on the passed Visitor with itself as the argument and uses the result for its return value:
boolean Leaf.accept( Visitor v )
{
return v.visit( this );
}
Any time a call to accept answers false, it signals the parent's accept member to stop processing children at that level in the tree.
Once a parent node has called accept for each of its children, it will call visitor.visitLeave. This lets the visitor FunctorObject know it is done with this branch and proceeding to either a sibling or parent Component node at the same tree-depth as this node.
Implementation
Consider the following interface for the Hierarchical Visitor:
public interface Visitor
{
boolean visitEnter( Composite node ); // going into a branch
boolean visitLeave( Composite node ); // coming out
boolean visit( Leaf node );
}
That's pretty much it. To make life a little easier I provide a NullObject (Default Implementation) visitor.
public interface Visitor
{
.
.
.
public static class Default implements Visitor
{
public boolean visitEnter( Composite node ) {
return true;
}
public boolean visitLeave( Composite node ) {
return true;
}
public boolean visit( Leaf node ) {
return true;
}
}
}
Now we just need to create the Composite structure. For details on this see CompositePattern. The only variation is the accept methods which both need to return a boolean. These members should be implemented as follows:
boolean Composite.accept( Visitor v )
{
if ( v.visitEnter( this ) ) // enter this node?
{
Iterator at = m_children.iterator();
while ( at.hasNext() )
if ( ! ((Component)at.next()).accept( v ) )
break;
}
return v.visitLeave( this );
}
And the leaf implementation:
boolean accept( Visitor visitor )
{
return visitor.visit( this );
}
Sample Code and Usage
In this example, the Composite node is a Directory and the Leaf node is a File object. We implement a Visitor that can construct the qualified path name for each File component. While this can be simply done using the HierarchicalVisitorPattern, it is quite difficult to achieve with the traditional VisitorPattern. Note that this example only shows the 'hierarchical navigation features of the hierarchical visitor and does not use any of its conditional features.
/**
* Maintains a string that when accessed in the "visit"
* member will return the current qualified file name.
*/
public abstract
classFilenameQualifier
implements FileVisitor
{
static final String SEPCHAR = "\\"; // path separator
private m_sPath = "";
// Entering a composite: Push its name on the Path
public boolean visitEnter( Directory node )
{
m_sPath += node.getName();
m_sPath += SEPCHAR; // NOTE: Don't forget the separator!
return true; // process leafs (i.e. files or subdirs)
}
// Leaving a composite: Pop its name from the Path
public boolean visitLeave( Directory node )
{
m_sPath.resize( m_sPath.size() - node.getName().size() );
return true; // go to next sibling
}
// Provide read-only access to the current qualifier
String currentPath()
{
return m_sPath;
}
}
We only added a protected member to access the current path for each call to visit. Because we are creating classes, we can extend them to add or refine behavior. For example, we can extend the qualifier to create a hierarchical listing of qualified file names:
public
classFileListingVisitor
extends FilenameQualifier
{
private int m_nLevel;// Indent Level
public boolean visitEnter( Directory node )
{
super.visitEnter( node );
println( node.getName() );
m_nLevel++; // increase indent level
return true;
}
public boolean visitLeave( Directory node )
{
super.visitLeave( node );
m_nLevel--; // decrease indent level
return true;
}
public boolean visit( File leaf )
{
println( currentPath() + leaf.getName() );
return true;
}
private void println( String s )
{
int N = m_nLevel * TABSIZE;
while ( N-- ) System.print( ' ' );
System.println( s );;
}
}
To use, you simply pass an instance of the FileListingVisitor to the accept member of any composite in the file system.
Directory dir = directoryAt( path ); dir.accept( new FileListingVisitor() );Here's an example of a composite hierarchy for this sample:
interface FileSystemObject
{
String getName();
boolean accept( Visitor v );
}
class Directory implements FileSystemObject
{
private Stringm_name;
private ItemArray m_contents = new ItemArray();
public Directory( String name )
{
m_name = name;
}
public String getName()
{
return m_name;
}
public void add( FileSystemObject child )
{
m_contents.add( child );
}
.
.
.
public boolean accept( Visitor v )
{
if ( v.visitEnter( this ) )
m_contents.detect( new Block() {
public boolean is( Object each ) {
return !((FileSystemObject)each).accept( v ); } } );
return v.visitLeave( this );
}
}
class File implements FileSystemObject
{
private String m_name;
public File( String name )
{
m_name = name;
}
public String getName()
{
return m_name;
}
public boolean accept( Visitor v )
{
return v.visit( this );
}
}
That's pretty much it. You add files to directories like so:
Directory root = new Directory( "root" ); Directory temp = new Directory( "temp" ); temp.add( new File( "foo.txt" ) ); root.add( temp ) root.add( new File( "bar.txt" ) );This creates the following file structure:
root | +--temp || |+--foo.txt | +--bar.txt
Sample Code for Filtered Processing
This example shows the extensibility of the Hierarchical Visitor. The following shows us building on the basic Hierarchical Visitor to create a new abstraction that allows us to add filter objects and processing objects to selectively process a composite.
First we define the interface for creating classes that filter nodes or operate on filtered nodes:
interface Filter
{
boolean canVisit( Composite node );
boolean canVisit( Leaf leaf );
}
interface Operator extends ClassicVisitor
{
void visit( Composite node );
void visit( Leaf leaf );
}
class FilteredVisitor extends HierarchicalVisitor
{
Items m_filters;// one or more filter conditions
Items m_operators;// one or more operators
...
// Add a filter
public void add( Filter filter ) {
m_filters.add( filter );
}
// Add an operator
public void add( Operator process ) {
m_operators.add( process );
}
...
// Filter this entire Branch?
public boolean visitEnter( Composite node )
{
// Return first that rejects this node
Object rejected =
m_filters.detect( new Block() {
public boolean is( Filter each ) {
return !each.canVisit( node ); } } );
return ( rejected == null );
}
// Visit non-rejected nodes
public boolean visitLeave( Composite node )
{
m_operators.enum( new Block() {
public void run( Operator each ) {
each.visit( node ); } } );
return true;
}
// Check reject state for each condition, process if not rejected
public boolean visit( Leaf node )
{
// Return first that rejects this leaf
Object rejected =
m_filters.detect( new Block() {
public boolean is( Filter each ) {
return !each.canVisit( node ); } } );
if ( rejected == null ) // no one rejected
m_operators.enum( new Block() {
public void run( Operator each ) {
each.visit( node ); } } );
return true;
}
}
This allows you to aggregate various filters and operators into the Hierarchical Visitor.
Existing Uses
Related Patterns
-- RobertDiFalcoSee also: HierarchicalVisitorDiscussion
CategoryPattern | CategoryBehavioralPatterns
EditText of this page
(last edited December 15, 2011)
or FindPage with title or text search