moving min max

Keep track of the minimum or maximum value in a sliding window.

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.

The algorithm is based on the description here.

The complexity of the operations are

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

use moving_min_max::MovingMin;

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

or

use moving_min_max::MovingMax;

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

assert_eq!(moving_max.max(), Some(&3));
assert_eq!(moving_max.pop(), Some(2));

assert_eq!(moving_max.max(), Some(&3));
assert_eq!(moving_max.pop(), Some(3));

assert_eq!(moving_max.max(), Some(&1));
assert_eq!(moving_max.pop(), Some(1));

assert_eq!(moving_max.max(), None);
assert_eq!(moving_max.pop(), None);