Visitor Pattern
Visitor pattern from my perspective does an important aspect of helping the evolution of heterogenous operations on a data structure and the structure of data independently. A formal definition of this pattern can be had from GoF Book on Design Pattern and other well known sources and authority on design pattern.
However this post is just a capture of snapshot of my thoughts on how we could implement with an intent defined in next section. I will be immensely happy for viewer's comments on how this could be improved.
Intent:
Sometime back; i was drawn to write some examples on few operations on trees and graphs. The moment that thought crossed my mind i wanted to model these operations as an entity or a hierarchy of entities and allow it to be passed inside the structure of interest. The intent was to have the following common behavioral methods in any of the operational entities such as
- method(s) for when operating on whole of structure or on individual elements
- method for when doing something with that element
- A getter method to keep an audit trail/collection of results of interest accrued / accumulated over visiting trail. (Perhaps this behavior could be added as a decorator or some other pattern)
Example with trees
A basic entity for visiting a tree could perhaps be as follows:
/**
*
*/
package algos.trees.visitors;
import algos.trees.Element;
import algos.trees.Tree;
/**
* Visitor interface for a element of type T in a {@link Tree} that might return
* of type R and may have collected Results in a type of C.
*
* @author vmurthy
*
* @param <T>
* is the type of the node in the {@link Tree}
* @param <R>
* is the type of the result computed over each visit
* @param <C>
* is the collection of result accumulated over every visit of
* {@link Element} in {@link Tree}
*/
public interface Visitor<T extends Comparable<T>, R, C> {
/**
* Visiting at the top of the tree. Can be used for any action/function to
* be done at the start of visit
*
* @param t
* is the tree
* @return R the result type
*/
R visit(Tree<T> t);
/**
* Visiting an element
*
* @param e
* the {@link Element element}
* @return R the result type
*/
R visit(Element<T> e);
/**
* Do some operation on the data node itself
*
* @param e
* the {@link Element element} upon which to do something
* @return R the result type
*/
R doSomethingOnElement(Element<T> e);
/**
* Return a collection of some interesting results accumulated over the
* visiting trail.
*
* @return C collection of results perhaps different than R
*/
C collection();
}
*
*/
package algos.trees.visitors;
import algos.trees.Element;
import algos.trees.Tree;
/**
* Visitor interface for a element of type T in a {@link Tree} that might return
* of type R and may have collected Results in a type of C.
*
* @author vmurthy
*
* @param <T>
* is the type of the node in the {@link Tree}
* @param <R>
* is the type of the result computed over each visit
* @param <C>
* is the collection of result accumulated over every visit of
* {@link Element} in {@link Tree}
*/
public interface Visitor<T extends Comparable<T>, R, C> {
/**
* Visiting at the top of the tree. Can be used for any action/function to
* be done at the start of visit
*
* @param t
* is the tree
* @return R the result type
*/
R visit(Tree<T> t);
/**
* Visiting an element
*
* @param e
* the {@link Element element}
* @return R the result type
*/
R visit(Element<T> e);
/**
* Do some operation on the data node itself
*
* @param e
* the {@link Element element} upon which to do something
* @return R the result type
*/
R doSomethingOnElement(Element<T> e);
/**
* Return a collection of some interesting results accumulated over the
* visiting trail.
*
* @return C collection of results perhaps different than R
*/
C collection();
}
A simple example of operation on tree could be such as printing all the vertical paths from root node leading to leaf node as follows. I have used lombok annotations to keep the code relatively clutter free.
package algos.trees.visitors;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import lombok.AccessLevel;
import lombok.Data;
import lombok.EqualsAndHashCode;
import lombok.val;
import lombok.experimental.Accessors;
import lombok.experimental.FieldDefaults;
import lombok.experimental.NonFinal;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import org.apache.logging.log4j.message.StringFormatterMessageFactory;
import org.springframework.util.StringUtils;
import algos.trees.Element;
import algos.trees.Tree;
/**
* The Class PrintVerticalPathVisitor prints all vertical path from root of tree
* to each leaf node
*
* @param <T>
* the generic type
*/
@Data
@Accessors(fluent = true, chain = true)
@EqualsAndHashCode(callSuper = false)
@FieldDefaults(level = AccessLevel.PRIVATE, makeFinal = true)
public class PrintVerticalPathVisitor<T extends Comparable<T>> implements
Visitor<T, Void, List<List<T>>> {
public static <Y extends Comparable<Y>> PrintVerticalPathVisitor<Y> of(Boolean headToTail) {
return new PrintVerticalPathVisitor<Y>(headToTail);
}
static final Logger log = LogManager.getLogger(StringFormatterMessageFactory.INSTANCE);
Deque<T> queue = new ArrayDeque<T>();
// We need this collection Deque list for outside access so keep name
List<List<T>> collection = new ArrayList<List<T>>();
Boolean headToTail;
@NonFinal
static Void v;
@Override
public Void visit(Tree<T> t) {
visit(t.root());
return v;
}
@Override
public Void visit(Element<T> e) {
if (headToTail) queue.addLast(e.value());
else queue.addFirst(e.value());
if (e.isBachelor()) printStack();
else {
if (e.hasLeft()) visit(e.left());
if (e.hasRight()) visit(e.right());
}
if (headToTail) queue.removeLast();
else queue.removeFirst();
return v;
}
@Override
public Void doSomethingOnElement(Element<T> e) {
throw new UnsupportedOperationException();
}
/**
* print stack of collected
*/
private void printStack() {
collection.add(new ArrayList<T>(queue));
log.debug(StringUtils.collectionToDelimitedString(queue, " "));
}
}
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import lombok.AccessLevel;
import lombok.Data;
import lombok.EqualsAndHashCode;
import lombok.val;
import lombok.experimental.Accessors;
import lombok.experimental.FieldDefaults;
import lombok.experimental.NonFinal;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import org.apache.logging.log4j.message.StringFormatterMessageFactory;
import org.springframework.util.StringUtils;
import algos.trees.Element;
import algos.trees.Tree;
/**
* The Class PrintVerticalPathVisitor prints all vertical path from root of tree
* to each leaf node
*
* @param <T>
* the generic type
*/
@Data
@Accessors(fluent = true, chain = true)
@EqualsAndHashCode(callSuper = false)
@FieldDefaults(level = AccessLevel.PRIVATE, makeFinal = true)
public class PrintVerticalPathVisitor<T extends Comparable<T>> implements
Visitor<T, Void, List<List<T>>> {
public static <Y extends Comparable<Y>> PrintVerticalPathVisitor<Y> of(Boolean headToTail) {
return new PrintVerticalPathVisitor<Y>(headToTail);
}
static final Logger log = LogManager.getLogger(StringFormatterMessageFactory.INSTANCE);
Deque<T> queue = new ArrayDeque<T>();
// We need this collection Deque list for outside access so keep name
List<List<T>> collection = new ArrayList<List<T>>();
Boolean headToTail;
@NonFinal
static Void v;
@Override
public Void visit(Tree<T> t) {
visit(t.root());
return v;
}
@Override
public Void visit(Element<T> e) {
if (headToTail) queue.addLast(e.value());
else queue.addFirst(e.value());
if (e.isBachelor()) printStack();
else {
if (e.hasLeft()) visit(e.left());
if (e.hasRight()) visit(e.right());
}
if (headToTail) queue.removeLast();
else queue.removeFirst();
return v;
}
@Override
public Void doSomethingOnElement(Element<T> e) {
throw new UnsupportedOperationException();
}
/**
* print stack of collected
*/
private void printStack() {
collection.add(new ArrayList<T>(queue));
log.debug(StringUtils.collectionToDelimitedString(queue, " "));
}
}
NOTE: This code uses Lombok annotations and hence doesn't require get/set methods to be written explicitly while many of the mundane stuff such as declaring private, final, equals method etc are also automatically taken care. The instance variable collection is strategically named so that; lombok auto generates the getter method for the same which in turn satisfies interface requirements(therefore you don't see getCollection() or collection() method here in this code).
Also In this example doSomethingOnElement is not required as its just a matter of printing.
While PrintVerticalPath may be one use case there could be many. A few of which i have captured in my code repository for tree visitors.
Use in Graph
An another slight modification is to bring in a template for structure and call the structure as Visitable
public interface Visitable<T>{
//void pre();
void accept(Visitor<Visitable<T>,?,?> visitor);
//void post();
}
But here the Visitor could be simplified as now there is no tree look-alike graph. Perhaps may be we could generically use the below Visitor for both tree and graph.
public interface Visitor<T, R, C> {
/**
* visit an instance of {@link Visitable<T>}
*
* @param t
* an instance of Visitable
* @return a result R
*/
R visit(T t);
/**
* @return a Collection/Aggregation of result accumulated over each visit
*/
C collection();
}
A simple example of building Prim's algorithm as follows in the following code snippet in my repository :
@Accessors(fluent = true)
@Data//(staticConstructor = "of")
@FieldDefaults(level = AccessLevel.PRIVATE, makeFinal = true)
static class Prim<Type extends Comparable<Type>> implements
Visitor<VertexInterface<Type>, Void, Set<VertexInterface<Type>>> {
public static<Y extends Comparable<Y>> Prim<Y> of(GraphInterface<Y> g){
return new Prim<Y>(g);
}
/**
* Passed in Graph G
*/
GraphInterface<Type> G;
/**
* Collected results. Keep it always named as collection so u dont have
* to code getCollection()/collection() method.
*/
@NonFinal Set<VertexInterface<Type>> collection = new LinkedHashSet<VertexInterface<Type>>();
@Override public Void visit(VertexInterface<Type> s) {
/**
* The Breadth First {@link Queue}
*/
Queue<VertexInterface<Type>> Q = new PriorityQueue<VertexInterface<Type>>(
G.verticies().size(),
new Comparator<VertexInterface<Type>>() {
@Override public int compare(VertexInterface<Type> o1,
VertexInterface<Type> o2) {
if (o1.weight() == o2.weight())
return 0;
else
return o1.weight() < o2.weight() ? -1 : 1;
}
});
// Initialize pi,and distance to INF
for (val u : G.verticies())
if(!u.equals(s))
u.weight(INFINITY).pi(null);
// Mark root alone to zero while all are INF add to priority
// queue
s.weight(0d);
Q.addAll(G.verticies());
while (!Q.isEmpty()) {
// Pick up the vertex u and find the adjV
val u = Q.remove(); // this is extract first or extract top
for (val v : G.adjV(u)) {
val edge = G.findEdge(u, v);
if (Q.contains(v) && edge != null
&& edge.cost() < v.weight())
v.pi(u).weight(edge.cost());
}
}
return v_o_i_d;
}
}
Conclusion:
The example of data structure/algorithmic cases are incidental here as my interests are more focused towards clear / clean design. As can be seen this template of visitor is re-usable in many cases such as traversals and many other interesting operations on trees and graphs. By no means this is a complete article; and wish to solicit other's opinion on the same.
No comments:
Post a Comment