#queue #sliding #sliding-window #extrema

sliding_extrema

Queue data structure with support for an O(1) extrema function over contents (for example, to obtain min and max over a sliding window of samples)

6 releases

Uses old Rust 2015

new 0.2.0 Nov 19, 2023
0.1.4 Aug 20, 2019
0.1.2 Apr 9, 2018

#488 in Data structures

Download history 16/week @ 2023-07-31 61/week @ 2023-08-07 7/week @ 2023-08-14 14/week @ 2023-08-21 7/week @ 2023-08-28 7/week @ 2023-09-04 6/week @ 2023-09-11 1/week @ 2023-09-18 5/week @ 2023-09-25 2/week @ 2023-10-02 6/week @ 2023-10-09 16/week @ 2023-10-16 14/week @ 2023-10-23 30/week @ 2023-10-30 1/week @ 2023-11-06 57/week @ 2023-11-13

102 downloads per month

MIT/Apache

13KB
222 lines

This is a simple implementation of the algorithm described by 'adamax' at:

https://stackoverflow.com/questions/4802038/implement-a-queue-in-which-push-rear-pop-front-and-get-min-are-all-consta

It implements a Queue with push and pop, with FIFO semantics, and a get_extrema() method, all with amortized O(1) time complexity.

The get_extrema method returns the extrema of all items in the queue, using a user-supplied metric. Examples of extrema-functions are max, min, but not 'average' or 'mean'.

This structure can be used to implement a super-efficient max/min function for a sliding window of many samples.

Simple example:

extern crate sliding_extrema;

let mut queue = sliding_extrema::sliding_max();

queue.push(42);
queue.push(15);
queue.push(8);

assert_eq!(queue.get_extrema().unwrap(),42);

queue.pop();

assert_eq!(queue.get_extrema().unwrap(),15);

See docs and test for more advanced examples.

The structure is covered by an automatic fuzz-test, that should provide 100% test coverage.

No runtime deps