# 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!`

.

`AssociativeWindowAggregation.WindowedAssociativeOp`

— Type```
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.

`AssociativeWindowAggregation.window_size`

— Method`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.

`AssociativeWindowAggregation.window_value`

— Method`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.

`Base.popfirst!`

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

Drop `n`

values from the start of `state`

.

`Base.push!`

— Method`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`

.