Implement a Stateful Chatter Message Store

Problem Statement

In real-time chat platforms, message services need to store chronologically ordered messages, retrieve surrounding message contexts for rendering, track message revisions without losing history, and merge overlapping range fetches to minimize redundant reads.

Implement the ChatterStore class with the following methods:

• __init__(): Initializes an empty message store.
• append_batch(messages: list[tuple[int, str]]) -> None: Ingests a batch of messages. Each message is a tuple of (id, text). Incoming batches are guaranteed to be sorted in strictly ascending order by id, and all IDs in the batch are strictly greater than any previously ingested ID.
• edit_message(message_id: int, new_text: str) -> bool: Updates the message text to new_text and records the edit history. Returns True if the message exists, or False if message_id is not found.
• get_neighborhood(message_id: int, k_before: int, k_after: int) -> list[tuple[int, str]] | None: Returns up to k_before messages immediately preceding message_id, the target message itself (with its current text), and up to k_after messages immediately following message_id, in ascending order of ID. Returns None if message_id does not exist.
• merge_read_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]: Merges a list of closed message ID intervals [start_id, end_id] such that overlapping or directly adjacent intervals (e.g., [1, 5] and [6, 10]) are combined into a single consolidated interval. The output must be sorted in ascending order of start IDs.

Input & Output Format

• messages: A list of tuples (id: int, text: str).
• intervals: A list of tuples (start_id: int, end_id: int) where start_id <= end_id.
• get_neighborhood: Returns a list of (id, current_text) tuples, or None.

Constraints

• 1 <= id <= 10^12 (IDs can be 64-bit integers).
• 1 <= len(text) <= 1000.
• Total messages stored across all calls <= 2 * 10^5.
• 0 <= k_before, k_after <= 100.
• intervals length <= 10^4.
• All method calls except merge_read_intervals should run in O(1) or O(log N + k) time, where N is the total message count and k = k_before + k_after.

Example

store = ChatterStore()
store.append_batch([(10, "hello"), (20, "world"), (30, "foo"), (40, "bar")])

# Context query around ID 20 with 1 before and 1 after
assert store.get_neighborhood(20, 1, 1) == [(10, "hello"), (20, "world"), (30, "foo")]

# Edit a message
assert store.edit_message(20, "everyone") == True
assert store.get_neighborhood(20, 0, 1) == [(20, "everyone"), (30, "foo")]

# Non-existent ID
assert store.get_neighborhood(99, 1, 1) is None
assert store.edit_message(99, "test") == False

# Merge read intervals
raw_intervals = [(10, 20), (30, 45), (21, 25), (40, 50)]
assert store.merge_read_intervals(raw_intervals) == [(10, 25), (30, 50)]

Edge Cases

• Boundaries for neighborhood lookups: requesting more before/after items than exist in the store should return as many available items as possible without error.
• k_before or k_after equal to 0.
• Adjacent discrete intervals like [1, 5] and [6, 10] must be merged into [1, 10] because discrete IDs leave no gap in between.