base2histogram 0.2.2

A Rust histogram library using base-2 logarithmic bucketing for fast percentile estimation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

use super::log_scale::LogScale;

/// A reference to a bucket's geometry in a log scale.
///
/// Provides access to left, right, width, and midpoint without carrying
/// histogram data (count). Created by [`LogScale::bucket_span`].
#[derive(Debug, Clone, Copy)]
pub struct BucketSpan<'a> {
    log_scale: &'a LogScale,
    index: usize,
}

impl<'a> BucketSpan<'a> {
    pub(crate) fn new(log_scale: &'a LogScale, index: usize) -> Self {
        Self { log_scale, index }
    }

    /// Bucket index.
    #[inline]
    pub fn index(&self) -> usize {
        self.index
    }

    /// Left (inclusive) boundary.
    #[inline]
    pub fn left(&self) -> u64 {
        self.log_scale.bucket_min_values[self.index]
    }

    /// Returns `true` if this is the terminal bucket that contains `u64::MAX`.
    #[inline]
    pub fn is_last(&self) -> bool {
        self.index + 1 == self.log_scale.bucket_min_values.len()
    }

    /// Upper boundary.
    ///
    /// This is exclusive for every bucket except the last one.
    /// The terminal bucket returns `u64::MAX` and includes that value.
    #[inline]
    pub fn right(&self) -> u64 {
        if !self.is_last() {
            self.log_scale.bucket_min_values[self.index + 1]
        } else {
            u64::MAX
        }
    }

    /// Number of integer values represented by this bucket.
    #[inline]
    pub fn width(&self) -> u64 {
        let span = self.right() - self.left();
        if self.is_last() { span + 1 } else { span }
    }

    /// Midpoint of the bucket's value range.
    #[inline]
    pub fn midpoint(&self) -> u64 {
        self.left() + (self.right() - self.left()) / 2
    }
}

#[cfg(test)]
mod tests {
    use crate::histogram::scale::LogScale;

    #[test]
    fn test_bucket_span() {
        let scale = LogScale::get(3);

        // [0,1): width=1, midpoint=0
        let b = scale.bucket_span(0);
        assert_eq!(
            (b.index(), b.left(), b.right(), b.width(), b.midpoint()),
            (0, 0, 1, 1, 0)
        );

        // [5,6): width=1, midpoint=5
        let b = scale.bucket_span(5);
        assert_eq!(
            (b.index(), b.left(), b.right(), b.width(), b.midpoint()),
            (5, 5, 6, 1, 5)
        );

        // [8,10): width=2, midpoint=9
        let b = scale.bucket_span(8);
        assert_eq!(
            (b.index(), b.left(), b.right(), b.width(), b.midpoint()),
            (8, 8, 10, 2, 9)
        );

        // [16,20): width=4, midpoint=18
        let b = scale.bucket_span(12);
        assert_eq!(
            (b.index(), b.left(), b.right(), b.width(), b.midpoint()),
            (12, 16, 20, 4, 18)
        );

        // [32,40): width=8, midpoint=36
        let b = scale.bucket_span(16);
        assert_eq!(
            (b.index(), b.left(), b.right(), b.width(), b.midpoint()),
            (16, 32, 40, 8, 36)
        );

        // Last bucket (251): [0b111<<61, u64::MAX]
        let b = scale.bucket_span(251);
        assert_eq!(b.index(), 251);
        assert_eq!(b.left(), 0b111 << 61);
        assert_eq!(b.right(), u64::MAX);
        assert!(b.is_last());
        assert_eq!(b.width(), u64::MAX - (0b111 << 61) + 1);
        assert_eq!(b.midpoint(), (0b111 << 61) + (u64::MAX - (0b111 << 61)) / 2);
    }
}