moving_min_max

Tracking minimum or maximum of sliding windows

10 releases(4 stable)

 1.3.0 Jul 4, 2020 Jun 24, 2020 Apr 11, 2020 Feb 3, 2020 Jan 15, 2020

#973 in Algorithms

MIT/Apache

14KB
212 lines

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