Design patterns Visitor Pattern Traversing large objects
Example
The visitor Pattern can be used to traverse structures.
class GraphVisitor;
class Graph
{
public:
class Node
{
using Link = std::set<Node>::iterator;
std::set<Link> linkTo;
public:
void accept(GraphVisitor& visitor);
};
void accept(GraphVisitor& visitor);
private:
std::set<Node> nodes;
};
class GraphVisitor
{
std::set<Graph::Node*> visited;
public:
void visit(Graph& graph)
{
visited.clear();
doVisit(graph);
}
bool visit(Graph::Node& node)
{
if (visited.find(&node) != visited.end()) {
return false;
}
visited.insert(&node);
doVisit(node);
return true;
}
private:
virtual void doVisit(Graph& graph) = 0;
virtual void doVisit(Graph::Node& node) = 0;
};
void accept(GraphVisitor& visitor)
{
// Pass the graph to the visitor.
visitor.visit(*this);
// Then do a depth first search of the graph.
// In this situation it is the visitors responsibility
// to keep track of visited nodes.
for(auto& node: nodes) {
node.accept(visitor);
}
}
void Graph::Node::accept(GraphVisitor& visitor)
{
// Tell the visitor it is working on a node and see if it was
// previously visited.
if (visitor.visit(*this)) {
// The pass the visitor to all the linked nodes.
for(auto& link: linkTo) {
link->accept(visitor);
}
}
}
