# Median accumulator

Simple, space-efficient algorithm to compute the median of an accumulation of elements.

* **Push-only** (no running window)
* Median is **updated at each push** (getting the median is always `O(1)`)
* **Space-efficient**: `O(D)` space, D being the number of _different_ samples, not the _total_ number of samples
* **Time-efficient**: push is `O(log(N))`
* **Generic**: `T: Clone + Ord`
* **No unsafe**
* **no_std** (optional): supports generic collections

Faster than other implementations if lots of samples have the same value. If this is not your case, you should use another implementation.

## Use

```rust
use median_accumulator::*;

let mut acc = vec::MedianAcc::new();

assert_eq!(acc.get_median(), None);
acc.push(7);
assert_eq!(acc.get_median(), Some(MedianResult::One(7)));
acc.push(5);
assert_eq!(acc.get_median(), Some(MedianResult::Two(5, 7)));
acc.push(7);
assert_eq!(acc.get_median(), Some(MedianResult::One(7)));
```

If you ever encounter an `unreachable` panic, please file an issue or send me an e-mail.

## no_std

Example with [smallvec](https://crates.io/crates/smallvec): (`smallvec` feature required)

```rust
use median_accumulator::*;

let mut acc = MedianAcc::<i32, smallvec::SmallVec<[(i32, u32); 64]>>::new();
```

For other collections than `Vec` or `SmallVec`, you must implement [cc-traits](https://crates.io/crates/cc-traits) and `InsertIndex`.

## License

CopyLeft 2022-2024 Pascal Engélibert [(why copyleft?)](https://txmn.tk/blog/why-copyleft/)

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, version 3 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.

You should have received a copy of the GNU Affero General Public License along with this program. If not, see https://www.gnu.org/licenses/.