Sliding-Window Minimum-Gap Stream

Problem

Design MinimumGapStream to retain the latest values from a numeric stream and report the minimum gap between any two retained occurrences. Calls are sequential on one shared instance.

Requirements

Keep the latest window. add appends one occurrence after all earlier occurrences. If the size would exceed windowSize, the same call removes exactly the single oldest occurrence, so the window contains the latest min(total arrivals, windowSize) occurrences.
Report the minimum gap. When at least two occurrences are retained, getMinimumGap returns the minimum absolute difference across every unordered pair of distinct retained occurrences.
Treat duplicates as a zero-gap pair. Two or more equal retained occurrences are distinct stream items and make getMinimumGap return zero.
Evict one duplicate occurrence. Evicting the oldest occurrence removes only that occurrence. If at least two equal occurrences remain, the minimum gap remains zero.
Return null without a pair. getMinimumGap returns null when fewer than two occurrences are retained.
Bound update time. Each add, including any oldest-occurrence eviction and aggregate repair, runs in $O(\log(\text{windowSize}))$ time.
Keep queries constant time. Each getMinimumGap runs in $O(1)$ time.

API

Signature	Returns	Behavior
`MinimumGapStream(windowSize: integer)`	Not applicable	Creates an empty stream that retains at most `windowSize` occurrences.
`add(value: integer)`	`void`	Appends one occurrence and evicts the oldest occurrence when the window exceeds its fixed size.
`getMinimumGap()`	`integer or null`	Returns the current minimum pairwise absolute difference, or `null` when no pair exists.

Examples

For MinimumGapStream(3):

Step	Operation	Result
1	`getMinimumGap()`	`null`
2	`add(8)`	No return value
3	`getMinimumGap()`	`null`
4	`add(3)`	No return value
5	`add(10)`	No return value
6	`getMinimumGap()`	`2`
7	`add(20)`	No return value; `8` is evicted
8	`getMinimumGap()`	`7`

For MinimumGapStream(2), adding 5, 5, then 9 produces minimum gaps 0 and 4 after the second and third additions. The third addition evicts only the oldest 5.

Constraints

1 <= windowSize <= 100,000
-1,000,000,000 <= value <= 1,000,000,000
At most 200,000 public method calls occur per testcase.

Notes

Calls execute sequentially in invocation order. Each add completes its insertion and any required eviction before the next call begins. Inputs outside the constraints are not supplied or judged, and neither public method throws a domain error.