Struct mz_ore::stats::SlidingMinMax

pub struct SlidingMinMax<T> {
    stacks: Vec<(T, T, T)>,
    push_stack_len: usize,
}

Keeps track of the minimum and maximum value over a fixed-size sliding window of samples.

Inspired by the moving_min_max crate, see that crate’s documentation for a description of the high-level algorithm used here.

There are two major differences to moving_min_max:

• SlidingMinMax tracks both the minimum and the maximum value at the same time.
• SlidingMinMax assumes a fixed-size window. Pushing new samples automatically pops old ones and there is no support for manually popping samples.

The memory required for a SlidingMinMax value is size_of::<T> * 3 * window_size, plus a small constant overhead.

Fields

stacks: Vec<(T, T, T)>

The push stack and the pop stack, merged into one allocation to optimize memory usage.

The push stack is the first push_stack_len items, the pop stack is the rest. The push stack grows to the right, the pop stack grows to the left.

+––––––––––––––––+ | push stack –> | <– pop stack | +––––––––^—————^ push_stack_len

New samples are pushed to the push stack, together with the current minimum and maximum values. If the pop stack is not empty, each push implicitly pops an element from the pop stack, by increasing push_stack_len. Once the push stack has reached the window size (i.e. the capacity of stacks), we “flip” the stacks by converting the push stack into a full pop stack with an inverted order of samples and min/max values. After the flip, push_stack_len is zero again, and new samples can be pushed to the push stack.

push_stack_len: usize

The length of the push stack.

The top of the push stack is stacks[push_stack_len - 1]. The top of the pop stack is stacks[push_stack_len].

Implementations

impl<T> SlidingMinMax<T>

where T: Clone + PartialOrd,

pub fn new(window_size: usize) -> Self

Creates a new SlidingMinMax for the given window size.

fn top_of_push_stack(&self) -> Option<&(T, T, T)>

Returns a reference to the item at the top of the push stack.

fn top_of_pop_stack(&self) -> Option<&(T, T, T)>

Returns a reference to the item at the top of the pop stack.

pub fn add_sample(&mut self, sample: T)

Adds the given sample.

fn flip_stacks(&mut self)

Drains the push stack into the pop stack.

pub fn get(&self) -> Option<(&T, &T)>

Returns the current minimum and maximum values.

Trait Implementations

impl<T: Debug> Debug for SlidingMinMax<T>

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

Formats the value using the given formatter.