Struct median::stack::Filter [−][src]
pub struct Filter<T, N> where
N: ArrayLength<ListNode<T>>, { /* fields omitted */ }
An implementation of a median filter of fixed width 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)
.
Methods
impl<T, N> Filter<T, N> where
T: Clone + PartialOrd,
N: ArrayLength<ListNode<T>>,
[src]
impl<T, N> Filter<T, N> where
T: Clone + PartialOrd,
N: ArrayLength<ListNode<T>>,
pub fn new() -> Self
[src]
pub fn new() -> Self
Creates a new median filter with a given window size.
pub fn len(&self) -> usize
[src]
pub fn len(&self) -> usize
Returns the window size of the filter.
pub fn median(&self) -> T
[src]
pub fn median(&self) -> T
Returns the filter buffer's current median value, panicking if empty.
pub fn min(&self) -> T
[src]
pub fn min(&self) -> T
Returns the filter buffer's current min value, panicking if empty.
pub fn max(&self) -> T
[src]
pub fn max(&self) -> T
Returns the filter buffer's current max value, panicking if empty.
pub fn consume(&mut self, value: T) -> T
[src]
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
- Remove node at current cursor (
▶︎
) from linked list, if it exists. (by re-wiring its predecessor to its successor). - Initialize
current
andmedian
index to first node of linked list (▷
). - Walk through linked list, searching for insertion point.
- Shift median index on every other hop (thus ending up in the list's median).
- Insert value into ring buffer and linked list respectively.
- Update index to linked list's first node, if necessary.
- Update ring buffer's cursor.
- Return median value.
(Based on Phil Ekstrom, Embedded Systems Programming, November 2000.)
Trait Implementations
impl<T, N> Clone for Filter<T, N> where
T: Clone,
N: ArrayLength<ListNode<T>>,
[src]
impl<T, N> Clone for Filter<T, N> where
T: Clone,
N: ArrayLength<ListNode<T>>,
fn clone(&self) -> Self
[src]
fn clone(&self) -> Self
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
impl<T, N> Debug for Filter<T, N> where
T: Debug,
N: ArrayLength<ListNode<T>>,
[src]
impl<T, N> Debug for Filter<T, N> where
T: Debug,
N: ArrayLength<ListNode<T>>,