General window

WindowedAssociativeOp{T,Op,Op!,V<:AbstractVector{T}}(previous_cumsum::V, values::V)
WindowedAssociativeOp{T,Op,Op!}()
WindowedAssociativeOp{T,Op}()

State associated with a windowed aggregation of a binary associative operator.

If Op! is not specified, it will default to Op. However, for non-bitstypes, it can be beneficial to provide this method to reduce memory allocations.

V will default to a Vector{T}. For windows of a fixed and known length, a circular buffer will be more efficient — see FixedWindowAssociativeOp.

Method

Wherever summation is discussed, we can consider any alternative binary, associative, operator. For example: +, *, max, min, &&, union

NB. It is interesting to observe that commutativity is not required by this algorithm.

Conceptually the window is maintained in two buffers:

    [---- A ---)[----- B ------)
        <                      >    <-- current window finishes at the end of B, and
                                        starts somewhere in A.

A is stored as a sequence of cumulative sums, such that as the "<" advances we merely pick out the correct element:

    x_i,   x_i-1 + x_i,  x_i-2 + x_i-1 + x_i

B is stored as both:

• The sequence of values seen: x_i+1, x_i+2, x_i+3, ...
• The total of that sequence: x_i+1 + x_i+2 + x_i+3 + ...

When the "<" advances from A to B, we discard A, and the subset of B remaining after < becomes the new A. In becoming A, we transform its representation into that of the cumulative sums. We create a new, empty, B.

O(1) amortized runtime complexity, and O(L) space complexity, where L is the typical window length.

Type parameters

• T: The type of the values in the window.
• Op: Any binary, associative, function.
• Op!: Op!(x, y) will perform x + y, storing the result in x.
• V: The subtype of AbstractVector{T} used for internal state.

Fields (for internal use only)

• previous_cumsum::Vector{T}: Corresponds to array A above.
• ri_previous_cumsum::Int: A reverse index into previous_cumsum, once it contains values. It should be subtracted from end in order to obtain the appropriate index.
• values::Vector{T}: Corresponds to array B above.
• sum::T: The sum of the elements in values.

function window_size(state::WindowedAssociativeOp)::Int

Get the current size of the window in state.

Arguments:

• state::WindowedAssociativeOp: The state to query.

Returns:

• Int: The current size of the window.

window_value(state::WindowedAssociativeOp{T})::T where T

Get the value currently represented by the state.

Behaviour is undefined if this is called when the window is empty.

Arguments:

• state::WindowedAssociativeOp{T}: The state to query.

Returns:

• T: The result of aggregating over the values in the window.

popfirst!(state::WindowedAssociativeOp, n::Integer=1) -> state

Drop n values from the start of state.

push!(state::WindowedAssociativeOp{T}, value) -> state

Push value onto the end of state.

Arguments

• state::WindowedAssociativeOp: The state to update (will be mutated).
• value: The value to add to the end of the window - must be convertible to a T.