inc_stats/
utils.rs

1//! Various utilities
2use num_traits::{Float, FromPrimitive};
3use std::error::Error;
4use std::fmt::{self, Display, Formatter};
5
6/// Any error from this library
7#[derive(Debug)]
8pub struct StatsError(String);
9
10impl StatsError {
11    pub fn new(msg: String) -> StatsError {
12        StatsError(msg)
13    }
14}
15
16impl<'a> From<&'a str> for StatsError {
17    fn from(msg: &'a str) -> StatsError {
18        StatsError(String::from(msg))
19    }
20}
21
22impl Display for StatsError {
23    fn fmt(&self, formatter: &mut Formatter) -> Result<(), fmt::Error> {
24        write!(formatter, "statistical error: {}", self.0)
25    }
26}
27
28impl Error for StatsError {}
29
30/// An iterator that does BFS assuming slice is a full binary tree
31pub struct InsideOut<'a, T> {
32    elems: &'a [T],
33    current: usize,
34    step: usize,
35}
36
37impl<'a, T> Iterator for InsideOut<'a, T> {
38    type Item = &'a T;
39
40    fn next(&mut self) -> Option<Self::Item> {
41        self.current += self.step;
42        match self.elems.get(self.current) {
43            Some(elem) => Some(elem),
44            _ if self.step <= 2 => None,
45            _ => {
46                self.step /= 2;
47                self.current = (self.step / 2) - 1;
48                Some(&self.elems[self.current])
49            }
50        }
51    }
52}
53
54/// Compute the step involved
55fn checked_step(len: usize) -> Option<usize> {
56    len.checked_add(1)?
57        .checked_next_power_of_two()?
58        .checked_mul(2)
59}
60
61/// Create an iterator that does BFS treating the slice as a maximal tree
62///
63/// Errors if the input is too long
64pub fn inside_out<'a, T>(elems: &'a [T]) -> Result<InsideOut<'a, T>, StatsError> {
65    let step = checked_step(elems.len())
66        .ok_or(StatsError::from("elems to long to efficiently alternate"))?;
67    Ok(InsideOut {
68        elems,
69        current: 0,
70        step,
71    })
72}
73
74/// weighted average between two values, weight given to high
75pub fn weighted_average<T: Float + FromPrimitive>(low: T, high: T, weight: f64) -> Option<T> {
76    Some(low * T::from_f64(1.0 - weight)? + high * T::from_f64(weight)?)
77}
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn inside_out_tests() {
85        let best_case: Vec<_> = (0..7).collect();
86        let best_actual: Vec<_> = inside_out(&best_case).unwrap().copied().collect();
87        assert_eq!(best_actual, vec!(3, 1, 5, 0, 2, 4, 6));
88
89        let worst_case: Vec<_> = (0..8).collect();
90        let worst_actual: Vec<_> = inside_out(&worst_case).unwrap().copied().collect();
91        assert_eq!(worst_actual, vec!(7, 3, 1, 5, 0, 2, 4, 6));
92
93        let middle_case: Vec<_> = (0..5).collect();
94        let middle_actual: Vec<_> = inside_out(&middle_case).unwrap().copied().collect();
95        assert_eq!(middle_actual, vec!(3, 1, 0, 2, 4));
96    }
97}
inc_stats/utils.rs

inc_stats/
utils.rs
