A "sliding window" of a designated span that supports insertion of tick "timestamps" that represent some state of interest during that tick. This data structure supports efficient querying of the ratio of {ticks for which that state existed} to the {total number of ticks spanned by the window}.

The primary use case is in displaying the "activity level" of a robot.

Efficiency considerations

The data retention of the window shall be maintained externally by invoking the discardGarbage function. However, we should not unconditionally invoke this function upon each game tick.

For efficiency, we do not want to iterate over every robot upon every tick; we only want to "visit" a robot if it is actually doing work that tick. Because of this, there may be some ticks in which the oldest element that is still stored falls outside of the nominal retention window while a robot is inactive.

One might think we could perform garbage collection whenever we execute queries. However, in the context in which the view powered by the query is generated, we are not permitted to mutate the "state" of the game (the type signature of the rendering function is AppState -> Widget Name).

Therefore, when we perform "queries" on the window, we must apply some filtering to exclude the "stragglers"; data members that have already fallen outside the window but have not yet been "garbage collected". We use a Set to allow this filtering to be performed in O(log n) time.

In the worst case, the entire dataset may "age out" without being garbage collected, so that an O(log n) filtering operation might be performed upon every "frame refresh" of the UI view. However, we also store the largest element of the window separately from the Set so that we can compare against it for a O(1) short-circuited path once every member ages out.

The maximum number of elements ever stored in the Set will be the width of the nominal span, even after some protracted failure to "garbage collect".

Values that can be offset by an integral amount

NOTE: We take the absolute value of the "window span" argument so that we can make guarantees about the output of getOccupancy.

Return the ratio of {members in the window} to the {integral span represented by the window}.

The "current time" should be at least as large as the largest element of the window.

A fully-contiguous collection of ticks would have an occupancy ratio of 1.

Unit interval guarantee

The returned ratio is guaranteed to lie on the unit interval, because:

• Both the numerator and denominator of the ratio are guaranteed positive, and
• discardGarbage guarantees that the set size is less than or equal to the nominal span.

Invocations of this function shall be guarded externally by the conditions meant to be tracked in the window.

Proper usage dictates that the value inserted should always be at least as large as the current largest element of the set.

The discardGarbage function is called from inside this function so that maintenance of the data structure is simplified.

Drop the leading elements that are not larger than the cutoff.

This function is already called by the insert function, so clients do not necessarily ever have to call this directly. However, there may be opportunity to call this even more often, i.e. in code paths where the robot is visited but the condition for insertion is not met.

Invariant

If the largest member of the set is the current time, then after calling this function, the difference between smallest and largest value in the set is strictly less than the "nominal span", and the size of the set is less than or equal to the nominal span.

For example, if the nominal span is 3, the current time is 7, and the set entails a contiguous sequence {2, 3, 4, 5, 6, 7}, then the pivot for split will be 7 - 3 = 4. The set becomes {5, 6, 7}, with cardinality equal to the nominal span.