rolling_median/
lib.rs

1// SPDX-License-Identifier: 0BSD
2// rolling-median
3// Copyright (C) 2025-2026 by LoRd_MuldeR <mulder2@gmx.de>
4
5#![allow(clippy::needless_doctest_main)]
6#![allow(clippy::unnecessary_map_or)]
7
8//! # rolling-median
9//!
10//! Computes the [**median**](https://en.wikipedia.org/wiki/Median) of a data set, using a “rolling” (online) algorithm.
11//!
12//! It uses two heaps (a “min” heap and a “max” heap) to efficiently keep track of the “middle” element.
13//!
14//! ## Complexity
15//!
16//! The `push()` operation has a complexity of: **`O(log(n))`**
17//!
18//! The `get()` operation has a complexity of: **`O(1)`**
19//!
20//! ## Usage
21//!
22//! Here is a simple example that demonstrates how to use it in your code:
23//!
24//! ```rust
25//! use rolling_median::Median;
26//!
27//! const VALUES: [f64; 6usize] = [3.27f64, 4.60f64, 5.95f64, 9.93f64, 7.79f64, 4.73f64];
28//!
29//! fn main() {
30//!     let mut rolling_median = Median::new();
31//!
32//!     for value in VALUES {
33//!         rolling_median.push(value).expect("Invalid value!");
34//!         println!("Median, so far: {}", rolling_median.get().expect("No result!"))
35//!     }
36//!
37//!     println!("Final median: {}", rolling_median.get().expect("No result!"))
38//! }
39//! ```
40//!
41//! &#128073; Please see the [`Median`] struct for details!
42
43pub mod float_utils;
44
45use crate::float_utils::{FloatOrd, FloatType, InvalidValue};
46use std::{cmp::Reverse, collections::BinaryHeap};
47
48// --------------------------------------------------------------------------
49// Rolling median
50// --------------------------------------------------------------------------
51
52/// Computes the median of a data set, using a "rolling" (online) algorithm
53pub struct Median<T: FloatType> {
54    heap_lo: BinaryHeap<FloatOrd<T>>,
55    heap_hi: BinaryHeap<Reverse<FloatOrd<T>>>,
56}
57
58impl<T: FloatType> Median<T> {
59    /// Initializes a new rolling median computation
60    pub fn new() -> Self {
61        Median { heap_lo: BinaryHeap::new(), heap_hi: BinaryHeap::new() }
62    }
63
64    /// Insert the next value
65    ///
66    /// Returns `Ok(())`, if the value was inserted, or `Err(InvalidValue)`, if an attempt to insert `NaN` was made.
67    ///
68    /// This operation has a complexity of **`O(log(n))`**.
69    pub fn push(&mut self, value: T) -> Result<(), InvalidValue> {
70        let value = FloatOrd::new(value)?;
71
72        if self.heap_lo.peek().map_or(true, |peek| value <= *peek) {
73            self.heap_lo.push(value);
74        } else {
75            self.heap_hi.push(Reverse(value));
76        }
77
78        if self.heap_lo.len() > self.heap_hi.len().checked_add(1usize).unwrap() {
79            if let Some(value) = self.heap_lo.pop() {
80                self.heap_hi.push(Reverse(value));
81            }
82        } else if self.heap_hi.len() > self.heap_lo.len() {
83            if let Some(Reverse(value)) = self.heap_hi.pop() {
84                self.heap_lo.push(value);
85            }
86        }
87
88        Ok(())
89    }
90
91    /// Get the current median
92    ///
93    /// Returns `Some(median_value)`, if at least one value was inserted; otherwise `None`.
94    ///
95    /// This operation has a complexity of **`O(1)`**.
96    pub fn get(&self) -> Option<T> {
97        if self.heap_lo.is_empty() {
98            None
99        } else if self.heap_lo.len() == self.heap_hi.len() {
100            let lo_top = *self.heap_lo.peek().unwrap();
101            let hi_top = self.heap_hi.peek().unwrap().0;
102            Some(lo_top.midpoint(hi_top))
103        } else {
104            Some(self.heap_lo.peek().unwrap().into_inner())
105        }
106    }
107
108    /// Returns the number of values that have been inserted so far
109    pub fn len(&self) -> usize {
110        self.heap_lo.len().saturating_add(self.heap_hi.len())
111    }
112
113    /// Returns `true`, if **no** values have been inserted yet; otherwise `false`
114    pub fn is_empty(&self) -> bool {
115        self.heap_lo.is_empty() && self.heap_hi.is_empty()
116    }
117
118    /// Clear all values and restart the median computation from scratch
119    pub fn clear(&mut self) {
120        self.heap_lo.clear();
121        self.heap_hi.clear();
122    }
123}
124
125impl<T: FloatType> Default for Median<T> {
126    /// Initializes a new rolling median computation
127    fn default() -> Self {
128        Self::new()
129    }
130}
rolling_median/lib.rs

rolling_median/
lib.rs
