The Visitor Pattern is well-known for its ability to iterate a structure without needing cast-operators for each node-type. That means, it is type-checked at compile-time (Java-like). Cast-operators check the type at runtime only (Smalltalk-like). In real life this means that the compiler detects your errors, not your impatient customer :-)
This Blog is about a visitor that also can modify the structure it is visiting, and thus keeps all iteration logic in just one place.
I am talking about lists, trees or graphs containing nodes of different types. Example would be an application menu. It contains clickable action-items and/or folder-items, folders again contain actions and/or folders, and so on. The actions could be push-buttons, checkboxes or radio-buttons. We could call that a "heterogenous tree".
Let's assume everything that is in a menu, be it folder or action, is an Item that has a technical id and a human-readable label:
public abstract class Item
{
/** Immutable id of this item. */
public final String id;
private String label;
/** Protected constructor, to be called by sub-classes only. */
protected Item(String id) {
assert id != null;
this.id = id;
}
/** Human readable label of this item. */
public String getLabel() {
return (label != null) ? label : id;
}
public void setLabel(String label) {
this.label = label;
}
@Override
public String toString() {
return id+"@"+hashCode();
}
}
From this, we will derive something that enables us to iterate the menu by a Visitor.
Here is a special visitor that also returns values from its visit() methods. I will explain that speciality later.
/**
* Callers of <code>Item.accept()</code> need to implement this.
*/
public interface Visitor
{
/**
* @param actionItem the currently visited action.
* @return false by default to visit the whole tree,
* true to terminate the iteration now and return the
* given item from <code>accept()</code>.
*/
boolean visit(ActionItem actionItem);
/**
* @param itemList the currently visited list.
* @return false by default to visit the whole structure,
* true to terminate the iteration now and return the
* given itemList from <code>accept()</code>.
*/
boolean visit(ItemList itemList);
}
And here is the according visitable Item super-class for all types of items:
public abstract class VisitableItem extends Item
{
protected VisitableItem(String id) {
super(id);
}
/**
* This iterates recursively, with the option to break the iteration.
* Should encapsulate the iteration once-and-only-once.
* An implementation would call the visitor's <code>visit(this)</code>,
* and <code>accept(visitor)</code> for all child items.
* @param visitor interface implementation that visits the structure and
* decides when the iteration is terminated.
* @return the action item (or list) where the visitor returned true
* from <code>visit(item)</code>, or null.
*/
public abstract VisitableItem accept(Visitor visitor);
}
This is the classical Visitor Pattern where an interface must be implemented for every use-case that wants to iterate the graph. All items of the structure must provide some accept() implementation that, at least, calls back to the visit() method of the given visitor. Folders would also call all their children's accept() method, this implements the iteration.
And that accept() is the place where the return-speciality comes in. The visitor can break the iteration by returning true from its visit() implementation. That saves time when, for example, searching just the first matching item. The item's accept() method would then return itself, being the search result. A simple and useful visitor-convenience, see examples on bottom for more evidence.
Here is the menu-action class:
public class ActionItem extends VisitableItem
{
public ActionItem(String id) {
super(id);
}
/** To be called when user clicks this item. */
public void perform() {
throw new RuntimeException("implement me!");
}
@Override
public final VisitableItem accept(Visitor visitor) {
return visitor.visit(this) ? this : null;
}
}
Mind that accept() returns itself when the visitor returns true. This is for searching, see below.
Following is the menu-folder:
public class ItemList extends VisitableItem
{
private List<VisitableItem> items = new ArrayList<>();
/**
* @param id required, the id of this list-item.
* @param items the child items to be contained in this list, will be cloned.
*/
public ItemList(String id, List<VisitableItem> items) {
super(id);
this.items = items;
}
/**
* Iterate recursively with the option to break the iteration.
* This should implement the iteration once-and-only-once.
* @param visitor interface implementation that visits the tree and decides when the iteration is terminated.
* @return the action item (or list) where the visitor returned true from <code>visit(item)</code>, or null.
*/
@Override
public VisitableItem accept(Visitor visitor) {
if (visitor.visit(this))
return this;
for (VisitableItem item : items) {
final VisitableItem matched = item.accept(visitor);
if (matched != null)
return matched;
}
return null;
}
@Override
public String toString() {
return items.toString()+"_@"+hashCode();
}
}
The accept() method first checks whether the visitor returns true. In that case it returns itself as search result, like the menu-action implementation does. Then it checks whether one of its child-items returns not-null from accept(). When yes, this child is returned as search result.
That means, a search for just one item would not need to iterate the whole structure. This comes for the price of a contract between visit() and accept() returns.
Why would you need an editing visitor?
Because sometimes I need to edit the menu. Remove items the user has no permission for. Or add items dynamically in a certain application state.
But why do this with a visitor? For removing items there is the Iterator pattern!
If I have a separate Iterator, the structural logic would be duplicated. I want the go-into-sub-items logic to be implemented just once-and-only-once. Maybe because it will be subject to eager changes, or extensive configuration. For a visitor with editing capabilities, we must change the classes above a little. First we add a method to the visitor that exposes the children-list to possible editors.
/**
* Callers of <code>Item.accept()</code> need to implement this.
*/
public interface Visitor
{
....
....
/**
* Called after an <code>ItemList</code> was visited,
* and once before each visit of any of its elements.
* @param items the mutable list about to be iterated,
* mind that this iteration could be interrupted
* by going into a sub-list. (That's the reason
* why it is called each time an item is visited.)
*/
void setVisitedList(List<VisitableItem> items);
}
The new setVisitedList() method exposes the list of items to visitors. That means the visitor can modify it. From the Iterator pattern we know that modifying a list while iterating it is an error-prone thing.
Here is a simple and concurrent-modification-safe iteration that also calls the new visitor-method setVisitedList():
public class ItemList extends VisitableItem
{
....
@Override
public VisitableItem accept(Visitor visitor) {
if (visitor.visit(this))
return this;
for (VisitableItem item : new ArrayList<>(items)) { // safely iterate via clone
visitor.setVisitedList(items); // expose the parent-list for modifications
final VisitableItem matched = item.accept(visitor);
if (matched != null)
return matched;
}
return null;
}
....
}
By using a clone of the children list the iteration avoids any irritation by the editing visitor. The visitor receives the original list directly before any call to the child's accept() method.
That's it, no more. Enough to iterate the graph, and edit it at the same time. But because this is a very mimimal implementation, Visitor classes may have problems to make useful things out of this. Let's see how far we can go with it.
Here is a skeleton that generates test data. You can paste the different visitors below into it to test them.
public class Main
{
private ItemList buildMenu() {
final ActionItem fileSystem = new ActionItem("File System");
final ActionItem recent = new ActionItem("Recent");
final ItemList openMenu = new ItemList(
"Open",
new ArrayList<>(Arrays.asList(new VisitableItem [] { fileSystem, recent })));
final ActionItem exit = new ActionItem("Exit");
final ItemList fileMenu = new ItemList(
"File",
new ArrayList<>(Arrays.asList(new VisitableItem [] { openMenu, exit })));
final ActionItem cut = new ActionItem("Cut");
final ActionItem copy = new ActionItem("Copy");
final ActionItem paste = new ActionItem("Paste");
final ItemList editMenu = new ItemList(
"Edit",
new ArrayList<>(Arrays.asList(new VisitableItem [] { cut, copy, paste })));
final ActionItem help = new ActionItem("Help");
final ItemList menuBar = new ItemList(
"",
new ArrayList<>(Arrays.asList(new VisitableItem [] { fileMenu, editMenu, help })));
return menuBar;
}
.....
public static void main(String[] args) {
final Main menuTest = new Main();
final ItemList menuBar = menuTest.buildMenu();
....
}
}
A print-visitor that also counts items:
private void testPrint(ItemList menuBar) {
class PrintVisitor implements Visitor
{
int count;
private List<VisitableItem> currentlyVisitedList;
@Override
public boolean visit(ActionItem actionItem) {
count++;
System.out.println("ActionItem = "+actionItem+"\n parent = "+currentlyVisitedList);
return false;
}
@Override
public boolean visit(ItemList itemList) {
count++;
System.out.println("ItemList = "+itemList+"\n parent = "+currentlyVisitedList);
return false;
}
@Override
public void setVisitedList(List<VisitableItem> items) {
currentlyVisitedList = items;
}
};
final PrintVisitor printVisitor = new PrintVisitor();
menuBar.accept(printVisitor);
final int numberOfItems = 11;
assert printVisitor.count == numberOfItems : "Count of menu items is not "+numberOfItems+": "+printVisitor.count;
}
Following is a search-visitor:
private void testFind(ItemList menuBar, String id) {
final VisitableItem found = find(menuBar, id);
assert found.id.equals(id) : "Did not find item with id '"+id+"'!";
}
private VisitableItem find(ItemList menuBar, String id) {
return menuBar.accept(new Visitor() {
@Override
public boolean visit(ActionItem actionItem) {
return compareId(actionItem);
}
@Override
public boolean visit(ItemList actionList) {
return compareId(actionList);
}
@Override
public void setVisitedList(List<VisitableItem> itemsm) {
}
private boolean compareId(VisitableItem item) {
return id.equals(item.id); // stop when id found
}
});
}
A remove-visitor can be implemented easily:
private void testRemove(ItemList menuBar, final String id) {
testFind(menuBar, id);
class RemoveVisitor implements Visitor
{
private List<VisitableItem> currentlyVisitedList;
@Override
public boolean visit(ActionItem actionItem) {
return removeWhenFound(actionItem);
}
@Override
public boolean visit(ItemList listItem) {
return removeWhenFound(listItem);
}
@Override
public void setVisitedList(List<VisitableItem> items) {
currentlyVisitedList = items;
}
private boolean removeWhenFound(VisitableItem item) {
if (id.equals(item.id)) {
assert currentlyVisitedList != null : "Can not remove "+id+", it seems to be root!";
currentlyVisitedList.remove(item);
return true;
}
return false;
}
};
menuBar.accept(new RemoveVisitor());
assert find(menuBar, id) == null : "Could not remove item with id '"+id+"'!";
}
Finally a clone-visitor. That was really hard to implement, and also may be a little hard to understand :-)
private void testClone(ItemList menuBar) {
/**
* Builds on the fact that setVisitedList()
* is called immediately after visit(ListItem listItem).
*/
class CloneVisitor implements Visitor
{
ItemList cloneRoot;
private Map<List<VisitableItem>,List<VisitableItem>> lists = new HashMap<>();
private List<VisitableItem> currentlyVisitedList;
@Override
public boolean visit(ActionItem actionItem) {
currentlyVisitedList.add(actionItem);
return false;
}
@Override
public boolean visit(ItemList itemList) {
final List<VisitableItem> cloneList = new ArrayList<>(); // create a clone
final ItemList clone = new ItemList(itemList.id, cloneList);
clone.setLabel(itemList.getLabel());
if (currentlyVisitedList == null) // root level
cloneRoot = clone;
else
currentlyVisitedList.add(clone); // add the clone to current parent
currentlyVisitedList = cloneList; // we are going inside now
return false;
}
@Override
public void setVisitedList(List<VisitableItem> items) {
List<VisitableItem> cloneItems = lists.get(items); // get the clone-list of incoming original
if (cloneItems == null) // create and store it when not found
lists.put(items, cloneItems = currentlyVisitedList);
currentlyVisitedList = cloneItems; // make sure we are inserting into the correct clone-list
}
};
final CloneVisitor cloneVisitor = new CloneVisitor();
menuBar.accept(cloneVisitor);
final ItemList clone = cloneVisitor.cloneRoot;
testPrint(clone);
assert clone != null && clone != menuBar : "Menu bar has not been cloned!";
assert find(clone, "Paste") != null : "Cloned menu bar does not contain 'Paste'!";
assert find(clone, "File") != find(menuBar, "File") : "Cloned 'File' menu is not different from original one!";
}
Here is the main() procedure that calls all these visitor tests.
public static void main(String[] args) {
final Main menuTest = new Main();
final ItemList menuBar = menuTest.buildMenu();
menuTest.testPrint(menuBar);
menuTest.testFind(menuBar, "Copy");
menuTest.testClone(menuBar);
menuTest.testRemove(menuBar, "Recent");
}
ɔ⃝ Fritz Ritzberger, 2017-09-22