Hierarchical Visitor Pattern with Code Example

What is Hierarchical Visitor Pattern:

"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 Visitor Pattern by allowing a programmer to track traversal depth and short-circuit branch traversal." - http://c2.com/cgi/wiki?HierarchicalVisitorPattern

Class Diagram:

Explanation:

Basically, Hierarchical Visitor pattern is an extended version of traditional Visitor pattern. Elements appear as node objects in a hierarchical object structure where a CompositeElement could have zero or many other Elements (either CompositeElement or LeafElement). Unlike traditional Visitor pattern, Hierarchical Visitor pattern is able to perform hierarchical navigation and conditional navigation.

Hierarchical Navigation:

The HierarchicalVisitor has 2 visit methods to process each CompositeElement object. In other words, each CompositeElement is visited twice by the same HierarchicalVisitor.

• visitEnter() - HierarchicalVisitor carries out the operation on the CompositeElement once the CompositeElement accepts this HierarchicalVisitor. After that, the HierarchicalVisitor leaves the CompositeElement and visits its child Element(s). The same process happens recursively to all the child Element(s) of each level that under this particular CompositeElement in the hierarchy until the LeafElement.
• visitExit() - After all child Element(s) of the mentioned CompositeElement are processed, HierarchicalVisitor then comes back to the CompositeElement and carries out the remaining operation on this CompositeElement right before it leave this CompositeElement completely. 

The HierarchicalVisitor has only 1 visit method to process a LeafElement object.

• visitLeaf() - HierarchicalVisitor carries out the operation on the LeafElement once the LeafElement accepts this HierarchicalVisitor. No more navigation to next level because LeafElement has no child Element. 

Conditional Navigation:

All visit methods return a boolean flag to indicate if the nodes traversal should be continued.

• visitEnter() - A boolean flag is returned to indicate if traverse to child Element(s) (if any) is required. 
• visitExit() - A boolean flag is returned to indicate if traverse to next sibling CompositeElement (if any) is required.
• visitLeaf() - A boolean flag is returned to indicate if traverse to next sibling LeafElement (if any) is required.

This is very useful because full traversal of a hierarchical object structure is not necessary. Whenever a condition is met, HierarchicalVisitor could skip from visiting the child Element(s), or next sibling Element, which lead to optimised navigation.

Participants:

Element (Employee): The common base for CompositeElement and LeafElement. An interface/class that defined the accept() protocol.

import com.hauchee.visitorpattern.visitor.IHierarchicalVisitor;

public abstract class Employee {
    
    private final String name;
    private final int salary;

    public Employee(String name, int salary) {
        this.name = name;
        this.salary = salary;
    }

    public int getSalary() {
        return salary;
    }

    public String getName() {
        return name;
    }
    
    public abstract boolean accept(IHierarchicalVisitor v);
}

CompositeElement (HierarchicalNode): Element that could contain child elements, either CompositeElement or LeafElement. It implements the accept() method so that the visitor could perform an operation on it. It also makes it child elements to accept the visitor, so that they could be visited and processed.

import com.hauchee.visitorpattern.visitor.IHierarchicalVisitor;
import java.util.List;

public class HierarchicalNode extends Employee {

    private List<Employee> subordinates;

    public HierarchicalNode(String name, int score) {
        super(name, score);
    }

    public void setSubordinate(List<Employee> subordinates) {
        this.subordinates = subordinates;
    }

    @Override
    public boolean accept(IHierarchicalVisitor v) {
        if (v.visitEnter(this)) {
            if (subordinates != null) {
                for (Employee cn : subordinates) {
                    boolean collectedAll = cn.accept(v);
                    if (collectedAll) {
                        break;
                    }
                }
            }
        }
        return v.visitExit(this);
    }
}

LeafElement (LeafNode): Element that does not have any child element. It implements the accept() method so that the visitor could perform an operation on it only.

import com.hauchee.visitorpattern.visitor.IHierarchicalVisitor;

public class LeafNode extends Employee {

    public LeafNode(String name, int score) {
        super(name, score);
    }

    @Override
    public boolean accept(IHierarchicalVisitor v) {
        return v.visitLeaf(this);
    }
}

HierarchicalVisitor (IHierarchicalVisitor): An interface that defined the protocol to visit CompositeElement and LeafElement.

import com.hauchee.visitorpattern.element.HierarchicalNode;
import com.hauchee.visitorpattern.element.LeafNode;

public interface IHierarchicalVisitor {

    boolean visitEnter(HierarchicalNode node);

    boolean visitExit(HierarchicalNode node); 

    boolean visitLeaf(LeafNode node);
}

ConcreteVisitor: HierarchicalVisitor implementation that perform operations on CompositeElement and LeafElement.

ReportingLineVisitor implements the operation to be carried out during hierarchical navigation.

import com.hauchee.visitorpattern.element.HierarchicalNode;
import com.hauchee.visitorpattern.element.LeafNode;
import java.util.ArrayList;
import java.util.List;

/**
 * Concrete visitor which collects all the reporting lines.
 */
public class ReportingLineVisitor implements IHierarchicalVisitor {

    private final List<String> reportingLines = new ArrayList<>();
    private final StringBuilder reportingLine = new StringBuilder();
    
    @Override
    public boolean visitEnter(HierarchicalNode node) {
        reportingLine.append(node.getName()).append("/");
        /**
         * Always true to continue traverse to the node's
         * child nodes (if any).
         */
        return true;
    }

    @Override
    public boolean visitExit(HierarchicalNode node) {
        // When exit from the node, remove its name from reportingLine.
        reportingLine.delete(reportingLine.lastIndexOf(node.getName()),
                reportingLine.length() + 1);
        /**
         * Return false to continue traverse to the node's sibling.
         * Only return true when all nodes were processed.
         */
        return reportingLine.length() == 0; 
    }

    @Override
    public boolean visitLeaf(LeafNode node) {
        reportingLines.add(reportingLine.toString() + node.getName());
        /**
         * Return false to continue traverse to the node's sibling.
         */
        return false;
    }

    public List<String> getPaths() {
        return reportingLines;
    }
}

TotalSalaryVisitor implements the operation to be carried out during conditional navigation.

import com.hauchee.visitorpattern.element.Employee;
import com.hauchee.visitorpattern.element.HierarchicalNode;
import com.hauchee.visitorpattern.element.LeafNode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Concrete visitor which accumulate all salary of a given reporting line.
 */
public class TotalSalaryVisitor implements IHierarchicalVisitor {

    private final List<String> reportingLine;
    private int salary;
    
    public TotalSalaryVisitor(String reportingLine) {
        this.reportingLine = new ArrayList<>(Arrays.asList(reportingLine.split("/")));
    }

    public int getSalary() {
        return salary;
    }
    
    private boolean process(Employee employee) {
        if (reportingLine.isEmpty()) {
            return false;
        }
        if (employee.getName().equals(reportingLine.get(0))
                && reportingLine.size() >= 1) {
            salary += employee.getSalary();
            reportingLine.remove(0);
            return true;
        }
        return false;
    }
    
    @Override
    public boolean visitEnter(HierarchicalNode node) {
        return process(node);
    }  

    @Override
    public boolean visitExit(HierarchicalNode node) {
        return reportingLine.isEmpty();
    }

    @Override
    public boolean visitLeaf(LeafNode node) {
        return process(node);
    }
}

Client (App): The client application that has objects in hierarchical object structure and make use of different ConcreteVisitor(s) to perform operations on those objects.

import com.hauchee.visitorpattern.element.HierarchicalNode;
import com.hauchee.visitorpattern.element.Employee;
import com.hauchee.visitorpattern.element.LeafNode;
import com.hauchee.visitorpattern.visitor.ReportingLineVisitor;
import com.hauchee.visitorpattern.visitor.TotalSalaryVisitor;
import java.util.ArrayList;
import java.util.List;

public class App {

    public static void main(String[] args) {

        /**
         * Construct employees reporting line in hierarchical structure as
         * below.
         *
         * Boss 
         *  - HR Manager 
         *      - HR Staff 1 
         *      - HR Staff 2 
         *      - HR Staff 3 
         *  - Sales Manager 
         *      - Sales Staff 1 
         *      - Sales Staff 2
         *  - Finance Manager
         */
        HierarchicalNode boss = new HierarchicalNode("Boss", 1000000);

        List<Employee> management = new ArrayList<>();

        HierarchicalNode hrManager = new HierarchicalNode("HR Manager", 6000);
        management.add(hrManager);
        List<Employee> hrStaffs = new ArrayList<>();
        hrStaffs.add(new LeafNode("HR Staff 1", 2000));
        hrStaffs.add(new LeafNode("HR Staff 2", 2500));
        hrStaffs.add(new LeafNode("HR Staff 3", 2500));
        hrManager.setSubordinate(hrStaffs);

        HierarchicalNode salesManager = new HierarchicalNode("Sales Manager", 8000);
        management.add(salesManager);
        List<Employee> salesStaffs = new ArrayList<>();
        salesStaffs.add(new LeafNode("Sales Staff 1", 4000));
        salesStaffs.add(new LeafNode("Sales Staff 2", 5500));
        salesManager.setSubordinate(salesStaffs);

        management.add(new LeafNode("Finance Manager", 9000));

        boss.setSubordinate(management);

        /**
         * Print all reporting lines.
         */
        ReportingLineVisitor rlVisitor = new ReportingLineVisitor();
        boss.accept(rlVisitor);
        for(String path : rlVisitor.getPaths()) {
            System.out.println(path);
        }
        
        /**
         * Total up the salary of employees in a specific reporting line.
         */
        TotalSalaryVisitor tsVisitor = new TotalSalaryVisitor("Boss/Sales Manager");
        boolean success = boss.accept(tsVisitor);
        if (success) {
            System.out.println(tsVisitor.getSalary());
        }
    }
}

Boss/HR Manager/HR Staff 1
Boss/HR Manager/HR Staff 2
Boss/HR Manager/HR Staff 3
Boss/Sales Manager/Sales Staff 1
Boss/Sales Manager/Sales Staff 2
Boss/Finance Manager
1008000

References:
http://c2.com/cgi/wiki?HierarchicalVisitorPattern
https://en.wikipedia.org/wiki/Visitor_pattern