General window

A state to represent a window of arbitrarily variable capacity.

We push new values onto the window with Base.push!. We can remove old values from the window with Base.popfirst!.

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

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.


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.


  • state::WindowedAssociativeOp: The state to query.


  • 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.


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


  • 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.


  • 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.