What data structure would fit a sequential event dispatch system of events and listeners?

Question

I need to find a suitable data structure for the following case. I have written a simple event dispatch system with events and listeners. The system is completely sequential, so no concurrency and synchronization issues whatsoever.

Requirements and Thoughts

• Each listener registers to a predefined (compile time) 1 or more types of events.
• Listeners can register and deregister during runtime.
• The order in which listeners register must be maintained since it is the order in which they receive events (listeners are always added at the end, but can be removed from anywhere).
• An event type can have 0 or more listeners registered to receive it at any time.

A visualization of this relationship can be explained as a table:

       | Listener1 | Listener2 | Listener3 | Listner5
-----------------------------------------------------
Event1 |     X     |           |     X     |    X
-----------------------------------------------------
Event2 |           |     X     |     X     |    X
-----------------------------------------------------
Event3 |           |           |           |
-----------------------------------------------------
Event4 |           |           |           |    X
-----------------------------------------------------

• The order of the rows is irrelevant.
• The order of the columns must be maintained.
• Columns can be added and removed.
• The number of rows is constant during runtime.

My thoughts are:

• When dispatching an event, I need to know which listeners are registered to receive the event type. I'm thinking about an Event -> Collection<Listener> mapping where the keys are unordered. The collection of listeners needs to maintain insertion order (or not, if the following point can be used for this instead).
• I need to keep a collection of listeners that maintains insertion order regardless of the events they are registered to (this demand comes from the objects the listeners are attached to). Because even if the Collection<Listener> above is insertion-ordered, it's per event type and not global. I'm thinking about an OrderedCollection<Listener>.
• When deregistering, I need to find all the event types a listener has registered to so it can be remove. I'm thinking about a Listener -> Collection<Event>, unless the mapping in the first point can do a removeAll(Listener) operation on the lists in the value position, but this can leave empty lists instead of completely removing the key.

It seems to me like a bidirectional multimap would fit this case. The backing multimaps are an UnorderedMap<Event, OrderedCollection<Listener>> and an OrderedMap<Listener, UnorderedCollection<Event>>. The OrderedCollection<Listener> might not need to be ordered if the ordering from the OrderedMap can be used. Obviously, any unordered data structure can be ordered, but it's unnecessary.

Alternatively, I've seen ideas of a single multimap with a reverse/invert operation to get the opposite mapping. My concern is twofold:

1. I don't know if one side can have its keys ordered while the other doesn't.
2. This seems like an expensive operation, and if i need to reverse the mapping all the time it can be inefficient.

Pseudocode usage

Registering a listener:

// somewhere
Listener1 listener = new Listener1();
listener.register(); 

// class definition
class Listener1 extends AbstractListener {

    void register() {

        DataStructure.put(Event1.class, this);
        DataStructure.put(Event2.class, this);

        // or
                                 // some collection
        DataStructure.put(this, [Event1.class, Event2.class])
    }
}

Dispatching an event:

// somewhere
EventManager.dispatch(new Event2());

// class definition
class EventManager {

    static void dispatch(Event event) {

        OrderedCollection<Listener> listeners = DataStructure.get(event);
        listeners.forEach(l -> l.processEvent(event)); // forEach maintains the order
    }
}

Deregistering a listener:

Listener2 listener = ...;        // got it from somewhere
DataStructure.remove(listener);  // remove from everywhere and if a key is left with an empty list remove that key

Final Details and Question

If it matters, there are about 30 event types and the amount of concurrent registered listeners is O(10), though over the lifetime of the program there could be O(100) listeners - most of them deregister and GC'd.

A note about the ordering. Since the listeners have an incremental unique int id field, I might be able to ensure that ordering by id number is equivalent to ordering by registration (insertion) order. The discrepancy currently is that the id is set on initialization of the listener, while registration is done afterwards (and another listener could be both created and registered in that gap). If there is an advantage to using sorted collections over ordered collections in this case, I can put in some work to guarantee that sorting by id is equivalent to insertion order.

What data structure(s) would fit my needs? Do I need to write my own (I rather not reinvent the wheel) or is there one(s) implemented already (Guava, I'm looking at you)?

Answer 1

If I well understood your question, the best structure seems to be an array of lists of AbstractListener.

List<AbstractListener>[]

---

Here a description requirement by requirement:

Requirement: Listeners can register and deregister during runtime.

A List can handle add and remove without problems

Requirements: The order in which listeners register must be maintained since it is the order in which they receive events (listeners are always added at the end, but can be removed from anywhere).

A List mantains the order. From javadoc

An ordered collection (also known as a sequence)

Requirement: An event type can have 0 or more listeners registered to receive it at any time.

A List can hold 0 or more elements.

Requirement: The order of the columns must be maintained.

A List mantains the order of elements.

Requirement: Columns can be added and removed.

A List can add or remove elements (columns)

Requirement: The order of the rows is irrelevant.

No problem with any data structure

Requirement: The number of rows is constant during runtime.

An array has constant size

---

From your comments to the answer is seems that another possible solution is to define a class that holds all events:

public interface Listener {
    public void handleEvent(Event event);
}

public class EventGenerator {
    private List<Listener> listeners;

    public void addListener(Listener listener) {
        listeners.add(listener);
    }

    public void removeListener(Listener listener) {
        listeners.remove(listener);
    }

    public void doSomething(Event event) {
        for (Listener listener : listeners) {
            listener.handleEvent(event);
        }
    }
}

Than for each kind of event you can do something like that:

// Create an event generator for each kind of event
EventGenerator eventGenerator1 = new EventGenerator();

EventGenerator eventGenerator2 = new EventGenerator();

// Register listeners to eventGenerators
eventGenerator1.addListener(listener1);
eventGenerator1.addListener(listener2);
eventGenerator1.addListener(listener3);

eventGenerator2.addListener(listener1);
eventGenerator2.addListener(listener2);
eventGenerator2.addListener(listener3);

...

// Eventually remove a listener
eventGenerator2.removeListener(listener2);

...

// When doSomething is invoked all listeners on that eventGenerator are invoked
eventGenerator1.doSomething(event1);  // Dispatched to listener 1, 2 and 3
eventGenerator1.doSomething(event2);  // Dispatched to listener 1, 2 and 3
eventGenerator1.doSomething(event3);  // Dispatched to listener 1, 2 and 3
eventGenerator1.doSomething(event4);  // Dispatched to listener 1, 2 and 3

eventGenerator1.removeListener(listener3);

eventGenerator1.doSomething(event5);  // Dispatched to listener 1, 2

eventGenerator1.removeListener(listener1);

eventGenerator1.doSomething(event6);  // Dispatched to listener 2

Answer 2

Since a listener can be attached to many event, I would try to "linearize" the problem by making unique the relation between an Event and a Listener:

public final class Relation {
    private final Class<? extends Event> eventType;
    private final Listener listener;

    public Relation(Class<? extends Event> eventType, Listener listener) {
        this.eventType = eventType;
        this.listener = listener;
    }

    public Class<? extends Event> getEventType() {
        return eventType;
    }

    public Listener getListener() {
        return listener;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Relation) {
            Relation that = (Relation) obj;

            return this.eventType.equals(that.eventType) && this.listener.equals(that.listener);
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(eventType, listener);
    }
}

The EventManager should encapsulate the whole data structure used to store these relations

public final class EventManager {

    private Set<Relation> relations = new LinkedHashSet<>();

    public void dispatch(Event e)
    {
        relations.stream()
                 .filter(r -> r.getEventType().isInstance(e))
                 .forEach(r -> r.getListener().processEvent(e));
    }

    public void register(Class<? extends Event> e, Listener l)
    {
        relations.add(new Relation(e, l));
    }

    public void unregister(Listener l)
    {
        relations = relations.stream()
                             .filter(r -> !r.getListener().equals(l))
                             .collect(Collectors.toCollection(LinkedHashSet::new));
    }

    public static void main(String[] args) {
        Event e1 = new Event1();
        Event e2 = new Event2();
        Event e4 = new Event4();
        Listener l1 = new Listener1();
        Listener l2 = new Listener2();
        Listener l3 = new Listener3();
        Listener l5 = new Listener5();
        EventManager em = new EventManager();

        em.register(Event1.class, l1);
        em.register(Event1.class, l3);
        em.register(Event1.class, l5);
        em.register(Event2.class, l2);
        em.register(Event2.class, l3);
        em.register(Event2.class, l5);
        em.register(Event4.class, l5);

        System.out.println("After register");
        em.dispatch(e1); //prints hello from 1, 3, 5
        em.dispatch(e2); //prints hello from 2, 3, 5
        em.dispatch(e4); //prints hello from 5

        em.unregister(l3);

        System.out.println("After unregistering l3");
        em.dispatch(e1); //prints hello from 1, 5
        em.dispatch(e2); //prints hello from 2, 5
        em.dispatch(e4); //prints hello from 5

        em.unregister(l5);

        System.out.println("After unregistering l5");
        em.dispatch(e1); //prints hello from 1
        em.dispatch(e2); //prints hello from 2
        em.dispatch(e4); //prints nothing
    }
}