Crate sliding_extrema 

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.

An 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);

A more generic example, with a closure comparator instead of relying on Ord:

extern crate sliding_extrema;
use sliding_extrema::SlidingExtrema;

let mut queue = SlidingExtrema::new_dynamic(|a:&u32,b:&u32|(*a).max(*b));

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);

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

Structs

CustomExtremum

An implementation of ExtremumFunction, delegating to a function pointer.

ExtremumOrdMax

An implementation of ExtremumFunction for any type that is Ord, returning the maximum value.

ExtremumOrdMin

An implementation of ExtremumFunction for any type that is Ord, returning the minimum value.

SlidingExtrema

T is the datatype of the items in the queue. F is a function that compares two items and returns the extreme value. I.e, if you’re implementing a ‘max’-function, F should be a function returning the largest of two values.

Traits

ExtremumFunction

Functions

sliding_max

A sliding max queue, for any type T that is Ord.

sliding_min

A sliding min queue, for any type T that is Ord.