A very flexible visitor pattern with no run-time overheads

BACKGROUND

I am working on an implementation of the A* algorithm that would be employed by academic researchers (such as myself) to experiment with novel variants of A*. The two main design goals are: total flexibility (i.e. any variant can be implemented) and no run-time overheads, which means that all the user-defined handlers must be bound at compile time.

My first attempt was to use policy-based design as described by the Modern C++ Design (Alexandrescu, 2001), but coming up with orthogonal policies quickly became a challenge.

In this post, I would like to share a new design that I am very much excited about. This design is not specific to A*, so it might be relevant to others.

DESIGN GOALS

The starting point is visitors, of course, somewhat similar to the visitors that the Boost Graph Library uses for its algorithms. A visitor specifies a handler for one or more events generated by the algorithm. For the purposes of this project, the handlers must possess the following properties:

• To achieve maximum flexibility, a handler must have access to the data that the algorithm makes available to the visitors.

• Handlers are bound to events at compile-time.

• A handler can return a value that provides feedback to the algorithm. (In the case of A*, when a node is selected, the handler of that event might tell the algorithm that this node should not be expanded, but should be re-inserted into the Open List, e.g. because the handler was able to increase the cost of the node). A handler can return void as well, in which case there should be no run-time cost for handling the return value.

IMPLEMENTATION

We define a base class for visitors with the handlers that do nothing:

struct VisitorBase {
    template <class Algorithm>
    static void OnEvent1(Algorithm &alg) {(void)alg;}

    template <class Algorithm>
    static void OnEvent2(Algorithm &alg) {(void)alg;}
};

The alg parameter gives the visitors access to:

• All the data that the algorithm makes available and

• The return types for the events.

A user might define a visitor as follows:

struct UserVisitor: public VisitorBase {
    template <class Algorithm>
    static typename Algorithm::ResultOfHandlingEvent1 OnEvent1(Algorithm &alg) {
        std::cout << "In VisitorForEvent1! data1 = " << alg.data1 << std::endl;
        return Algorithm::ResultOfHandlingEvent1::EVENT1_ACTION1;
    }
};

Here is a class that defines the things available to the visitors:

struct AlgorithmBase {
    enum class ResultOfHandlingEvent1 {EVENT1_ACTION1, EVENT1_ACTION2};
    enum class ResultOfHandlingEvent2 {EVENT2_ACTION1, EVENT2_ACTION2};
    int data1 = 5;
};

Finally, an algorithm would look like this:

template <class Visitor>
struct Algorithm: AlgorithmBase {
    void run() {
        constexpr bool ReturnTypeFlagOfOnEvent1 =
            std::is_same<decltype(Visitor::OnEvent1(*this)),
                         AlgorithmBase::ResultOfHandlingEvent1>::value;
        handleEvent1(std::integral_constant<bool, ReturnTypeFlagOfOnEvent1>());

        constexpr bool ReturnTypeFlagOfOnEvent2 =
            std::is_same<decltype(Visitor::OnEvent2(*this)),
                         AlgorithmBase::ResultOfHandlingEvent2>::value;
        handleEvent2(std::integral_constant<bool, ReturnTypeFlagOfOnEvent2>());
    }

private:
    void handleEvent1(std::true_type) {
        auto res = Visitor::OnEvent1((AlgorithmBase &)*this);
        std::cout << "Will switch on the result of handling event 1!"
                  << std::endl;
        (void)res; // but a switch statement will appear here
    }
    void handleEvent1(std::false_type) {
        Visitor::OnEvent1((AlgorithmBase &)*this);
        std::cout << "Nothing to be done for the result of handling event 1!"
                  << std::endl;
    }

    void handleEvent2(std::true_type) {
        auto res = Visitor::OnEvent2((AlgorithmBase &)*this);
        std::cout << "Will switch on the result of handling event 2!"
                  << std::endl;
        (void)res; // but a switch statement will appear here
    }
    void handleEvent2(std::false_type) {
        Visitor::OnEvent2((AlgorithmBase &)*this);
        std::cout << "Nothing to be done for the result of handling event 2!"
                  << std::endl;
    }
};

Let's give it a test run:

int main() {
    Algorithm<UserVisitor> a;
    a.run();
    return 0;
}

We get the output:

In VisitorForEvent1! data1 = 5
Will switch on the result of handling event 1!
Nothing to be done for the result of handling event 2!

THE REQUEST

I am a researcher myself and am learning C++ for this project. Hence, I would like to ask the experts here to point out to me if I made mistakes that unseasoned designers and programmers tend to make. Thank you in advance.