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

ddsketch/canonical/mapping/
logarithmic.rs
