ddsketch/canonical/mapping/
logarithmic.rs

1use datadog_protos::sketches::{index_mapping::Interpolation, IndexMapping as ProtoIndexMapping};
2
3use super::IndexMapping;
4use crate::canonical::error::ProtoConversionError;
5use crate::common::float_eq;
6
7/// Logarithmic index mapping.
8///
9/// Maps values to indices using: `index = ceil(log(value) / log(gamma))` where `gamma = (1 + alpha) / (1 - alpha)` and
10/// `alpha` is the relative accuracy.
11#[derive(Clone, Debug, PartialEq)]
12pub struct LogarithmicMapping {
13    /// The base of the logarithm, determines bin widths.
14    gamma: f64,
15
16    /// Precomputed 1/ln(gamma) for performance.
17    multiplier: f64,
18}
19
20impl LogarithmicMapping {
21    /// Creates a new `LogarithmicMapping` with the given relative accuracy.
22    ///
23    /// The relative accuracy must be between `0` and `1` (inclusive).
24    ///
25    /// # Errors
26    ///
27    /// If the relative accuracy is out of bounds, an error is returned.
28    ///
29    /// # Example
30    ///
31    /// ```
32    /// use ddsketch::canonical::mapping::LogarithmicMapping;
33    ///
34    /// // Create a mapping with 1% relative accuracy
35    /// let mapping = LogarithmicMapping::new(0.01).unwrap();
36    /// ```
37    pub fn new(relative_accuracy: f64) -> Result<Self, &'static str> {
38        if relative_accuracy <= 0.0 || relative_accuracy >= 1.0 {
39            return Err("relative accuracy must be between 0 and 1 (exclusive)");
40        }
41
42        let gamma = (1.0 + relative_accuracy) / (1.0 - relative_accuracy);
43        if gamma <= 1.0 {
44            return Err("gamma must be greater than 1");
45        }
46
47        let multiplier = 1.0 / gamma.ln();
48
49        Ok(Self { gamma, multiplier })
50    }
51}
52
53impl IndexMapping for LogarithmicMapping {
54    fn index(&self, value: f64) -> i32 {
55        let index = value.ln() * self.multiplier;
56        if index >= 0.0 {
57            index as i32
58        } else {
59            (index as i32) - 1
60        }
61    }
62
63    fn value(&self, index: i32) -> f64 {
64        self.lower_bound(index) * (1.0 + self.relative_accuracy())
65    }
66
67    fn lower_bound(&self, index: i32) -> f64 {
68        (index as f64 / self.multiplier).exp()
69    }
70
71    fn relative_accuracy(&self) -> f64 {
72        (self.gamma - 1.0) / (self.gamma + 1.0)
73    }
74
75    fn min_indexable_value(&self) -> f64 {
76        f64::MIN_POSITIVE.max(self.gamma.powf(i32::MIN as f64 + 1.0))
77    }
78
79    fn max_indexable_value(&self) -> f64 {
80        self.gamma.powf(i32::MAX as f64 - 1.0).min(f64::MAX / self.gamma)
81    }
82
83    fn gamma(&self) -> f64 {
84        self.gamma
85    }
86
87    fn index_offset(&self) -> f64 {
88        0.0
89    }
90
91    fn interpolation(&self) -> Interpolation {
92        Interpolation::NONE
93    }
94
95    fn validate_proto_mapping(&self, proto: &ProtoIndexMapping) -> Result<(), ProtoConversionError> {
96        // Check gamma matches (with floating-point tolerance)
97        if !float_eq(proto.gamma, self.gamma) {
98            return Err(ProtoConversionError::GammaMismatch {
99                expected: self.gamma,
100                actual: proto.gamma,
101            });
102        }
103
104        // Check indexOffset is 0.0 (LogarithmicMapping doesn't use offset)
105        if proto.indexOffset != 0.0 {
106            return Err(ProtoConversionError::NonZeroIndexOffset {
107                actual: proto.indexOffset,
108            });
109        }
110
111        // Check interpolation is NONE (LogarithmicMapping uses exact log)
112        let interpolation = proto.interpolation.enum_value_or_default();
113        if interpolation != Interpolation::NONE {
114            return Err(ProtoConversionError::UnsupportedInterpolation {
115                actual: interpolation as i32,
116            });
117        }
118
119        Ok(())
120    }
121
122    fn to_proto(&self) -> ProtoIndexMapping {
123        let mut proto = ProtoIndexMapping::new();
124        proto.gamma = self.gamma;
125        proto.indexOffset = 0.0;
126        proto.interpolation = protobuf::EnumOrUnknown::new(Interpolation::NONE);
127        proto
128    }
129}
130
131impl Default for LogarithmicMapping {
132    /// Creates a logarithmic mapping with 1% relative accuracy (the common default).
133    fn default() -> Self {
134        Self::new(0.01).expect("0.01 is a valid relative accuracy")
135    }
136}
137
138#[cfg(test)]
139mod tests {
140    use super::*;
141
142    #[test]
143    fn test_new_valid_accuracy() {
144        let mapping = LogarithmicMapping::new(0.01).unwrap();
145        assert!((mapping.relative_accuracy() - 0.01).abs() < 1e-10);
146    }
147
148    #[test]
149    fn test_new_invalid_accuracy_zero() {
150        assert!(LogarithmicMapping::new(0.0).is_err());
151    }
152
153    #[test]
154    fn test_new_invalid_accuracy_one() {
155        assert!(LogarithmicMapping::new(1.0).is_err());
156    }
157
158    #[test]
159    fn test_new_invalid_accuracy_negative() {
160        assert!(LogarithmicMapping::new(-0.1).is_err());
161    }
162
163    #[test]
164    fn test_index_value_roundtrip() {
165        let mapping = LogarithmicMapping::new(0.01).unwrap();
166
167        // For any index, the value at that index should map back to the same index
168        for i in -100..100 {
169            let value = mapping.value(i);
170            let recovered_index = mapping.index(value);
171            // Due to floating-point, we might be off by 1
172            assert!(
173                (recovered_index - i).abs() <= 1,
174                "index {} -> value {} -> index {}",
175                i,
176                value,
177                recovered_index
178            );
179        }
180    }
181
182    #[test]
183    fn test_bounds_ordering() {
184        let mapping = LogarithmicMapping::new(0.01).unwrap();
185
186        for i in -100..100 {
187            let lower = mapping.lower_bound(i);
188            let value = mapping.value(i);
189
190            assert!(
191                lower < value,
192                "lower {} should be < value {} for index {}",
193                lower,
194                value,
195                i
196            );
197        }
198    }
199
200    #[test]
201    fn test_gamma_calculation() {
202        let mapping = LogarithmicMapping::new(0.01).unwrap();
203        // gamma = (1 + 0.01) / (1 - 0.01) = 1.01 / 0.99
204        let expected_gamma = 1.01 / 0.99;
205        assert!((mapping.gamma() - expected_gamma).abs() < 1e-10);
206    }
207}
ddsketch/canonical/mapping/logarithmic.rs

ddsketch/canonical/mapping/
logarithmic.rs
