evobench_tools/stats_tables/stats/
weighted.rs

1//! Weighted values
2//!
3//! E.g. for measurements taken with gaps, where the same value is
4//! assumed to be valid for the gaps.
5
6use std::{
7    collections::BTreeMap,
8    num::NonZeroU32,
9    ops::Bound::{Included, Unbounded},
10    ops::Index,
11};
12
13// Get the entry at key, or the next-lower one
14fn lookup<'m, K: Ord, V>(map: &'m BTreeMap<K, V>, key: &K) -> (&'m K, &'m V) {
15    map.range((Unbounded, Included(key)))
16        .next_back()
17        .expect("we fill in index 0 thus will always find a value")
18}
19
20pub const WEIGHT_ONE: NonZeroU32 = unsafe {
21    // 1 satisfies NonZero. There is no NonZeroU32::ONE, sadly.
22    NonZeroU32::new_unchecked(1)
23};
24
25/// Representation of statistical probes: their value with the count
26/// of skipped runs that need to be compensated for.
27#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
28pub struct WeightedValue {
29    // Keep the order of fields unchanged, it matters for the sorting
30    // order!
31    /// The original measured value
32    pub value: u64,
33    /// How many times this should be counted
34    pub weight: NonZeroU32,
35}
36
37/// As is, only guarantees to allow up to u32 inputs, as it uses u64
38/// as the index internally!
39#[derive(Debug, Clone)]
40pub struct IndexedNumbers {
41    index_to_value: BTreeMap<u64, u64>,
42    /// Index to position after the "end" of the last value
43    virtual_len: u64,
44}
45
46#[derive(Debug, Clone, thiserror::Error)]
47#[error("got too many or too heavily weighted values")]
48pub struct TooMuchIndexedNumbersWeightError;
49
50impl IndexedNumbers {
51    #[inline]
52    pub fn virtual_len(&self) -> u64 {
53        self.virtual_len
54    }
55
56    pub fn first(&self) -> Option<&u64> {
57        // self.index_to_value.get(&0)
58        self.index_to_value.first_key_value().map(|(_k, v)| v)
59    }
60
61    pub fn last(&self) -> Option<&u64> {
62        // self.index_to_value.get(&self.virtual_len)
63        self.index_to_value.last_key_value().map(|(_k, v)| v)
64    }
65
66    /// As is, only allows up to u32 inputs for sure, as it uses u64
67    /// as the index internally, and the weights are u32, too; returns
68    /// an error otherwise. Sorts the vec!
69    pub fn from_unsorted_weighted_value_vec(
70        weighted_values: &mut Vec<WeightedValue>,
71    ) -> Result<Self, TooMuchIndexedNumbersWeightError> {
72        weighted_values.sort();
73
74        let mut index_to_value = BTreeMap::new();
75        let mut virtual_len: u64 = 0;
76        for WeightedValue { value, weight } in weighted_values {
77            index_to_value.insert(virtual_len, *value);
78            let weight = u64::from(u32::from(*weight));
79            virtual_len = virtual_len
80                .checked_add(weight)
81                .ok_or(TooMuchIndexedNumbersWeightError)?;
82        }
83        Ok(IndexedNumbers {
84            index_to_value,
85            virtual_len,
86        })
87    }
88
89    /// Only returns None if `index >= self.virtual_len` (or Self
90    /// contains no entries, which is also covered by the former
91    /// statement).
92    pub fn get(&self, index: u64) -> Option<&u64> {
93        if index < self.virtual_len {
94            Some(lookup(&self.index_to_value, &index).1)
95        } else {
96            None
97        }
98    }
99}
100
101impl Index<u64> for IndexedNumbers {
102    type Output = u64;
103
104    fn index(&self, index: u64) -> &Self::Output {
105        self.get(index).expect(
106            "index must be smaller than the virtual_len, \
107             and IndexedNumbers must not be empty",
108        )
109    }
110}
111
112#[cfg(test)]
113mod tests {
114    use anyhow::Result;
115
116    use super::*;
117
118    #[test]
119    fn t_weight_one() {
120        assert_eq!(WEIGHT_ONE, NonZeroU32::try_from(1).unwrap());
121    }
122
123    #[test]
124    fn t_indexed_numbers() -> Result<()> {
125        let mut nums = vec![
126            WeightedValue {
127                value: 10,
128                weight: 1.try_into()?,
129            },
130            WeightedValue {
131                value: 100,
132                weight: 5.try_into()?,
133            },
134            WeightedValue {
135                value: 4,
136                weight: 2.try_into()?,
137            },
138            WeightedValue {
139                value: 105,
140                weight: 1.try_into()?,
141            },
142            WeightedValue {
143                value: 3,
144                weight: 2.try_into()?,
145            },
146        ];
147        let indexed_nums = IndexedNumbers::from_unsorted_weighted_value_vec(&mut nums)?;
148        dbg!((&nums, &indexed_nums));
149
150        assert_eq!(indexed_nums[0], 3);
151        assert_eq!(indexed_nums.first(), Some(&3));
152        assert_eq!(indexed_nums[10], 105);
153        assert_eq!(indexed_nums.last(), Some(&105));
154        assert_eq!(indexed_nums[2], 4);
155        assert_eq!(indexed_nums[3], 4);
156        assert_eq!(indexed_nums[4], 10);
157
158        assert_eq!(indexed_nums.get(10), Some(&105));
159        assert_eq!(indexed_nums.get(11), None);
160
161        Ok(())
162    }
163}
evobench_tools/stats_tables/stats/weighted.rs

evobench_tools/stats_tables/stats/
weighted.rs
