Event pattern

Table of Contents

I like object composition and proper enforcing properly invariants of objects. As I believe the code should be written in a way that it is hard to make it inconsistent and break things. For a some time I've been using certain pattern for this task, that I think can be interesting to write about. This thing is text is specific to C++!

Imagine that you have class B that stores data:


struct MyStruct{
    int val; 
    int pwr;
};

class B {
public: 
    std::vector<MyStruct> data; 
};

and that you have class A that is overlay over container:

template< typename T >
class A {
    T storage;
public:
    auto begin()
    {
        return storage.begin();
    }
    auto end()
    {
        return storage.end();
    }
}

A does not do anything, but we want to make it hold an invariant over it's storage. It will expect that 'T' is container of MyStruct and will hold an 'item.pwr = item.val << 1;' invariant over it.

But how to make that happen? We can write push_back() method for A:

  void push_back(MyStruct item)
  {
      item.pwr = item.val << 1;
      storage.data.push_back(item);
  }

and we can repeat the same process for other methods of std::vector inside the class B.

But! what if we introduce this

class C {
public:
    std::list<MyStruct> data;
}

So, now we have to introduce necessary methods to work with std::list and again write them in a way that the invariant of A is always OK. This way write a lot of 'overlay' methods in A, that are simply more or the same everytime... 'overlay method of storage'.

Events

I actually run into that problem with Graphs, I have multiple (5 different types of graph) graphs in my code, I have one implementation of search algorithm (Anytime D* Lite). That algorithm given it's nature holds state over the vertexes of the graph (it's anytime, so it uses results between searches of shortest path). The "D* Lite" familly of algorithms also have the nice property, that they can find shortest path even in case the graph changes (vertexes/edges added/removed) during the search, but the algortihm has to be notified of it.

This is same situation as in the simple case above, 'AnytimeDStarLiteOverlay' is a class that expects T to be Graph, stores it inside and holds it inside itself, to keep the invariant of the search algorithm. (Each time new vertexes are added via the overlay API, the algorithm takes steps ...).

And believeme, in case there is an a bug, and the graph changes witout the overlay knowing about it, finding the reason why the shortest path is not correct is really pain in the ass.

So, I can use the same trick as above yeah? Well I did and the result was not nice, each of the 5 graph have general methods to make vertexes (emplaceVertex/addEdge), but also some specific for each graph - usually methods that creates/remove a batch of vertexes at one moment. So the Overlay had a lot of methods that were there, doing the same - overlaying the methods of various graphs that can exist under it. Not to mention the fact that if I would publish this as library, graphs of other users that uses something specific not taken care of the overlay can ... simply use different library :) (but it still sucks!)

So, what is the alternative? templates and visitors! At first I converted each method that is not shared between graphs, such as this:

void SomeGraph::itsSpecialMethod(Arg1 arg1, Arg2 arg2);

into:

struct SomeGraphSpecialMethodEvent
{
    Arg1 arg1;
    Arg2 arg2;
};
void SomeGraph::event(SomeGraphSpecialMethodEvent event);

The codebase is practically same, the method just now needs to extract the arguments from the event. What does this mean for the overlay? well overlay now has to implement only one method for the methods that are not shared between graphs:

template< typename Event >
void Overlay::event(Event event)
{
    graph.event(event);
}

All the methods that were previously written in overlay are not needed! finally we simplified the Overlay a lot (or it resulted in simplification in my case...). But... this can break the invariant that overlay needs to hold, no? yeah this definetly will, but that can be solved, let's introduce a visitor!


class IVisitor
{
    void onNewVertex(Vertex&) = 0;
    void onNewEdge(Edge&) = 0;
    void onDeletedVertex(Vertex&) = 0;
    void onDeletedEdge(Edge&) = 0;
};

template< typename Visitor >
void SomeGraph::event(SomeGraphSpecialMethodEvent event, Visitor visitor);

Of course all the implementations of event in SomeGraph has to correctly call all methods of visitor in cases when they happen...

The API of Overlay than changed to:

template< typename Event >
void Overlay::event(Event event)
{
    OverlayVisitor vis{*this};
    graph.event(event, vis);
}

OverlayVisitor is simply another class that has the overlay itself as attribute and on each event made by graph, notifies the overlay of changes... (in some cases, you can effectively do graph.event(event, *this))

And tadaaaah, now we have an Overlay that needs only one method and one visitor to take care of any graph-specific API. This way it is also possible to export the overlay as library, because other codes just have to use the event mechanism for graph-specific methods.

Does this seem overly-complex? yeah, the alternative is actually worse. To converty graph specific methods to this 'events' is not much work (it only introduces a new structures...) and the code of methods is same. You have to take care of the visitor correctly, but keep in mind that you would have to do the same eventually, in case 'normal' methods are used, the overlay has to be notified of the changes to graph somehow anyway, and while there are simpler methods, for complex cases you end up with Visitor anyway.

so, what do you think?