Struct median::heap::Filter

pub struct Filter<T> { /* fields omitted */ }

An implementation of a median filter with linear complexity.

While the common naïve implementation of a median filter has a worst-case complexity of O(n^2) (due to having to sort the sliding window) the use of a combination of linked list and ring buffer allows for a worst-case complexity of O(n).

Implementations

impl<T> Filter<T> where
    T: Clone + PartialOrd, 

pub fn new(size: usize) -> Self

Creates a new median filter with a given window size.

pub fn len(&self) -> usize

Returns the window size of the filter.

pub fn is_empty(&self) -> usize

Returns true if the filter has a length of 0.

pub fn median(&self) -> T

Returns the filter buffer’s current median value, panicking if empty.

pub fn min(&self) -> T

Returns the filter buffer’s current min value, panicking if empty.

pub fn max(&self) -> T

Returns the filter buffer’s current max value, panicking if empty.

pub fn consume(&mut self, value: T) -> T

Applies a median filter to the consumed value.

Implementation

The algorithm makes use of a ring buffer of the same size as its filter window. Inserting values into the ring buffer appends them to a linked list that is embedded inside said ring buffer (using relative integer jump offsets as links).

Example

Given a sequence of values [3, 2, 4, 6, 5, 1] and a buffer of size 5, the buffer would be filled like this:

new(5)  consume(3)  consume(2)  consume(4)  consume(6)  consume(5)  consume(1)
▶︎[ ]      ▷[3]       ┌→[3]       ┌→[3]─┐     ┌→[3]─┐    ▶︎┌→[3]─┐      ▷[1]─┐
 [ ]      ▶︎[ ]      ▷└─[2]      ▷└─[2] │    ▷└─[2] │    ▷└─[2] │    ▶︎┌─[2]←┘
 [ ]       [ ]        ▶︎[ ]         [4]←┘     ┌─[4]←┘     ┌─[4]←┘     └→[4]─┐
 [ ]       [ ]         [ ]        ▶︎[ ]       └→[6]       │ [6]←┐     ┌→[6] │
 [ ]       [ ]         [ ]         [ ]        ▶︎[ ]       └→[5]─┘     └─[5]←┘

Algorithm

1. Remove node at current cursor (▶︎) from linked list, if it exists. (by re-wiring its predecessor to its successor).
2. Initialize current and median index to first node of linked list (▷).
3. Walk through linked list, searching for insertion point.
4. Shift median index on every other hop (thus ending up in the list’s median).
5. Insert value into ring buffer and linked list respectively.
6. Update index to linked list’s first node, if necessary.
7. Update ring buffer’s cursor.
8. Return median value.

(Based on Phil Ekstrom, Embedded Systems Programming, November 2000.)

Trait Implementations

impl<T: Clone> Clone for Filter<T>

fn clone(&self) -> Filter<T>

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for Filter<T>

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

Formats the value using the given formatter.