Prerequisite-Aware Delivery Queue
Problem
Design DeliveryQueue to register callback subscribers and synchronously deliver each JSON message to matching subscribers after their prerequisites succeed. The queue owns the current subscriber topology and is used sequentially.
Requirements
- Manage subscribers.
addSubscriberatomically registers one unique subscriber whose distinct prerequisite ids are already registered. It rejects malformed subscriber data and malformed patterns.removeSubscriberremoves an existing subscriber and every dependency edge that mentions it. A rejected change leaves state unchanged. - Deliver matching messages. For each publication, invoke exactly the subscribers whose
filterPatternmatches the completemessageJson. Matching is case-sensitive. A pattern contains literal Unicode scalar values,.for any one scalar value, and postfix*for zero or more occurrences of the preceding literal or dot. Pass the original JSON text unchanged, and complete sequential publications in call order. - Honor prerequisites. A matching subscriber may begin only after all direct and transitive prerequisites match the same message and succeed. Process each subscriber successfully at most once per message, including prerequisites shared by several dependents.
- Retry callback failures. If
onMessageraises a processing exception, retry that subscriber with the unchanged message until it succeeds ormaxRetriesadditional attempts have failed. - Isolate failed branches. A nonmatching subscriber or one that fails every attempt is unsuccessful for that message, so none of its transitive dependents are invoked. Continue processing matching subscribers whose prerequisite chains can succeed.
API
| Signature | Returns | Behavior |
|---|---|---|
DeliveryQueue(maxRetries: integer) | Not applicable | Creates an empty queue. Raises InvalidArgumentError unless maxRetries is between 1 and 20 inclusive. |
addSubscriber(subscriber: Subscriber, prerequisiteIds: string[]) | void | Registers the subscriber and its prerequisite edges. Raises InvalidArgumentError for a null subscriber, empty id, null callback, malformed pattern, repeated prerequisite id, or self-reference; SubscriberExistsError for a live duplicate id; or SubscriberNotFoundError for an unknown prerequisite. Any error leaves state unchanged. |
removeSubscriber(subscriberId: string) | boolean | Removes the subscriber and all incoming and outgoing dependency edges, returning true. Returns false when the id is missing. Raises InvalidArgumentError for an empty id without changing state. |
publish(messageJson: string) | void | Synchronously processes one nonempty valid JSON text against the current topology. Callback exceptions are retried and contained. No order is promised between subscribers unrelated by prerequisites. |
Subscriber is a provided non-null collaborator with immutable nonempty subscriberId and filterPattern strings and an onMessage(messageJson: string) -> void callback. The callback may raise a processing exception. Implement DeliveryQueue, not Subscriber.
A pattern is malformed when it is empty, begins with *, has a * without a preceding literal or ., or contains consecutive *. No escape, alternation, grouping, character class, or anchor syntax exists. Implement matching directly with dynamic programming or equivalent string logic. Do not call a standard-library or third-party regular-expression engine.
Examples
Create DeliveryQueue(2). Register audit with pattern .*"type":"order".*; register charge with the same pattern and prerequisite audit; and register independent notify with the same pattern. Suppose audit succeeds, charge fails once and then succeeds, and notify always fails.
| Step | Operation | Result |
|---|---|---|
| 1 | publish("{\"type\":\"order\",\"id\":7}") | audit runs once before charge; charge runs twice and succeeds; notify runs three times; publish returns normally. |
| 2 | removeSubscriber("audit") | Returns true; the edge from charge to audit is removed. |
| 3 | publish("{\"type\":\"order\",\"id\":8}") | charge no longer waits for audit; unrelated callback order remains unspecified. |
Constraints
1 <= maxRetries <= 20.- Subscriber ids contain at most 100 Unicode scalar values, and patterns contain at most 500.
- A pattern uses only literals,
., and one optional postfix*per atom. Matching is full-string and case-sensitive. - Implement pattern matching directly without a regular-expression library.
- Each
messageJsonis a nonempty valid JSON text of at most 10,000 Unicode scalar values. The queue treats it as opaque text. - At most 1,000 subscribers, 100 direct prerequisites per subscriber, and 10,000 method calls occur per testcase.
- Every callback attempt terminates by returning or raising a processing exception.
- Implement pending-message storage without a standard-library queue or deque abstraction.
Notes
All calls are sequential, and callbacks do not call back into the queue. Callback side effects that occur before an exception are not rolled back. The queue retains no replayable message or delivery history after publish returns.