/sliding-window-aggregation

SWAg

Primary LanguageRust

sliding-window-aggregation

Crates.io: sliding-window-aggregation Documentation Build Status License: MIT

This crate provides an implementation of the Sliding Window Aggregation (SWAg) data structure.

SWAg is basically a queue with a fast folding operation. SWAg supports the following operations, each one of which takes amortized O(1) time:

  • push_back: push an element to the back of the queue.
  • pop_front: pop an element from the front of the queue.
  • fold_all: for an operation op, compute the fold of all elements in the queue, i.e. a1 op a2 op ... op an if the queue's content is [a1, a2, ..., an].

A detailed explanation is given in https://scrapbox.io/data-structures/Sliding_Window_Aggregation.