2694. Event Emitter

Problem Description

The problem requires designing an EventEmitter class that mimics the basic behavior of event emitter systems found in many programming environments such as Node.js or the web's Event Target interface.

An EventEmitter is essentially a mechanism that allows different parts of an application to communicate with each other by emitting events to which other parts have subscribed.

Two core functionalities are required:

• Subscribing to events: The subscribe method should allow clients to register a callback function that is to be executed when a particular event is emitted. Each event can have multiple subscribers, and upon the event being emitted, the callbacks should be executed in the order they were added.
• Emitting events: The emit method should trigger all the callbacks associated with the event name it receives as an argument. If the event has associated arguments, they should be passed to the callback functions.

Additionally, when a client subscribes to an event, a subscription object with an unsubscribe method should be returned. This method, when called, will remove the callback from the event's list of subscribers.

Intuition

To achieve the functionality described, the EventEmitter class must maintain a data structure that can keep track of all the callbacks associated with each event. To do this in an efficient and orderly way, a Map can be used where the key is the event name, and the value is a Set of callback functions. A Set is chosen because it inherently avoids duplicate entries, which is desirable as it's stated that no callbacks passed to subscribe are referentially identical.

For the subscribe method, we implement the following steps:

1. Retrieve the set of callbacks for the event from the map, or create a new set if it doesn't exist.
2. Add the callback to the set.
3. Return an object with an unsubscribe method that, when invoked, will delete the callback from the set of callbacks associated with the event.

For the emit method, we need to:

1. Retrieve the set of callbacks for the given event name.
2. If the event has no callbacks, we return an empty array as specified.
3. Iterate over the set of callbacks, executing each with the provided arguments, and collect the results.
4. Return the array with the results from all the executed callbacks.

This implementation ensures that all the requirements for the EventEmitter class are fulfilled, allowing for flexible event-driven programming patterns.

Solution Approach

The EventEmitter class is implemented using TypeScript which provides type-safety over JavaScript. Here's an approach to how the solution is crafted:

Data Structures

JavaScript's Map and Set are used to implement the subscription mechanism.

• A Map is used to associate each event with a set of callbacks (Set<Callback>). This allows efficient retrieval and management of callbacks per event.
• Set is used to store callbacks for each event to ensure each callback is unique.

Implementation Details

subscribe Method

1. When a subscriber calls subscribe, it passes the eventName and the callback.
2. The method retrieves the callbacks set associated with eventName using this.d.get(eventName), or initializes a new Set if none exists.
3. It adds the callback to the set with .add(callback).
4. The method returns an object containing an unsubscribe method. Inside this method, it removes the callback from the callbacks set when called.

The use of a Set here ensures that the order of callbacks will be preserved, and duplicates are prevented without extra logic.

emit Method

1. This method takes eventName and optionally an array of args.
2. It fetches the set of callbacks associated with eventName. If none are found, it returns an empty array.
3. It uses the spread syntax [...callbacks] to convert the set into an array that can be iterated over.
4. map is used to invoke each callback with the provided args, collecting the results in an array that is returned.

The spread and map operations ensure that callbacks are called in the order they were added.

To summarize, the algorithm for this solution is straightforward: use Map for event-to-callback(s) association, and Set for maintaining callbacks. Subscribing adds the callback to the set, and emitting iterates over and invokes these callbacks, while unsubscribing removes a callback from the set.

Example Walkthrough

Let's demonstrate the solution approach with a small example. Consider we want our EventEmitter to handle 'data' and 'error' events.

First, we create an instance of EventEmitter.

1let emitter = new EventEmitter();

Now, let's subscribe to the 'data' event with two different callbacks.

1let dataSubscription1 = emitter.subscribe('data', (data) => `Received ${data}`);
2let dataSubscription2 = emitter.subscribe('data', (data) => `Processed ${data}`);

According to the solution approach, the subscribe method will add each callback to a set associated with the 'data' event in the emitter's internal map. Each subscription returns an object with an unsubscribe method.

Next, we will emit the 'data' event with a piece of data, let's say 'example data'.

1let result = emitter.emit('data', 'example data');

When the emit method is called, it will look up the associated set of callbacks for the 'data' event and invoke each callback in the order they were added, passing 'example data' to them. The result will be an array of callback outputs:

1console.log(result); // Output: ["Received example data", "Processed example data"]

Finally, let's demonstrate unsubscribing from an event. We decide to unsubscribe dataSubscription1.

1dataSubscription1.unsubscribe();

Now, if we emit the 'data' event again:

1result = emitter.emit('data', 'new example data');

This time, the output will only reflect the remaining subscription:

1console.log(result); // Output: ["Processed new example data"]

The unsubscribe method removed dataSubscription1 from the emitter's callback set, so invoking the 'data' event no longer triggers the first callback.

This example has shown how the EventEmitter class can subscribe to events with callbacks, emit events which trigger those callbacks, and unsubscribe from events to remove callbacks—all following the explained solution approach using JavaScript's Map and Set.

Solution Implementation

Time and Space Complexity

Time Complexity

• subscribe(eventName: string, callback: Callback): Subscription

  • The time complexity for subscribing is O(1) since adding an event to a Map and adding a callback to a Set are both constant time operations.

• unsubscribe()

  • The time complexity for unsubscribing is O(1) because it involves a single call to delete on a Set, which is a constant time operation.

• emit(eventName: string, args: any[] = []): any

  • The time complexity for emitting an event depends on the number of callbacks subscribed to the event. If n is the number of callbacks, the complexity is O(n) because it maps each callback and applies it to the arguments.

Space Complexity

• Overall space complexity for the EventEmitter class would be O(m * n) where m is the number of unique events and n is the average number of subscribers per event since a Set of callbacks is stored for each event.

Additionally, the space complexity for emitting an event (emit) is also worth noting:

• emit(eventName: string, args: any[] = []): any
  • The space complexity for emitting is O(n) because it creates an array of the return values from each callback, where n is the number of callbacks.

Do note that this analysis assumes the size of the event names and the footprint of each callback function are not significant compared to the numbers of events and subscribers, which is a common assumption in complexity analysis.