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);
        }
    }
}