Struct MovingMin

pub struct MovingMin<T> { /* private fields */ }

Keep track of the minimum value in a sliding window.

The implementation is taken from https://github.com/spebern/moving_min_max/blob/master/src/lib.rs

moving min max provides one data structure for keeping track of the minimum value and one for keeping track of the maximum value in a sliding window.

Each element is stored with the current min/max. One stack to push and another one for pop. If pop stack is empty, push to this stack all elements popped from first stack while updating their current min/max. Now pop from the second stack (MovingMin/Max struct works as a queue). To find the minimum element of the queue, look at the smallest/largest two elements of the individual stacks, then take the minimum of those two values.

The complexity of the operations are

• O(1) for getting the minimum/maximum
• O(1) for push
• amortized O(1) for pop

let mut moving_min = MovingMin::<i32>::new();
moving_min.push(2);
moving_min.push(1);
moving_min.push(3);

assert_eq!(moving_min.min(), Some(&1));
assert_eq!(moving_min.pop(), Some(2));

assert_eq!(moving_min.min(), Some(&1));
assert_eq!(moving_min.pop(), Some(1));

assert_eq!(moving_min.min(), Some(&3));
assert_eq!(moving_min.pop(), Some(3));

assert_eq!(moving_min.min(), None);
assert_eq!(moving_min.pop(), None);

Implementations

impl<T: Clone + PartialOrd> MovingMin<T>

pub fn new() -> Self

Creates a new MovingMin to keep track of the minimum in a sliding window.

pub fn with_capacity(capacity: usize) -> Self

Creates a new MovingMin to keep track of the minimum in a sliding window with capacity allocated slots.

pub fn min(&self) -> Option<&T>

Returns the minimum of the sliding window or None if the window is empty.

pub fn push(&mut self, val: T)

Pushes a new element into the sliding window.

pub fn pop(&mut self) -> Option<T>

Removes and returns the last value of the sliding window.

pub fn len(&self) -> usize

Returns the number of elements stored in the sliding window.

pub fn is_empty(&self) -> bool

Returns true if the moving window contains no elements.

Trait Implementations

impl<T: Debug> Debug for MovingMin<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Clone + PartialOrd> Default for MovingMin<T>

fn default() -> Self

Returns the “default value” for a type.