Crate sliding_extrema

source ·
Expand description

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

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.