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    /// Constant shift applied to all computed indices.
17    index_offset: f64,
18
19    /// Precomputed 1/ln(gamma) for performance.
20    multiplier: f64,
21}
22
23impl LogarithmicMapping {
24    /// Creates a new `LogarithmicMapping` with the given relative accuracy.
25    ///
26    /// The relative accuracy must be between `0` and `1` (inclusive).
27    ///
28    /// # Errors
29    ///
30    /// If the relative accuracy is out of bounds, an error is returned.
31    ///
32    /// # Example
33    ///
34    /// ```
35    /// use ddsketch::canonical::mapping::LogarithmicMapping;
36    ///
37    /// // Create a mapping with 1% relative accuracy
38    /// let mapping = LogarithmicMapping::new(0.01).unwrap();
39    /// ```
40    pub fn new(relative_accuracy: f64) -> Result<Self, &'static str> {
41        if relative_accuracy <= 0.0 || relative_accuracy >= 1.0 {
42            return Err("relative accuracy must be between 0 and 1 (exclusive)");
43        }
44
45        let gamma = (1.0 + relative_accuracy) / (1.0 - relative_accuracy);
46        if gamma <= 1.0 {
47            return Err("gamma must be greater than 1");
48        }
49
50        let multiplier = 1.0 / gamma.ln();
51
52        Ok(Self {
53            gamma,
54            index_offset: 0.0,
55            multiplier,
56        })
57    }
58
59    /// Creates a new `LogarithmicMapping` from an explicit logarithmic base.
60    ///
61    /// This constructor is useful when the caller already knows the desired `gamma`
62    /// and wants to build the mapping directly instead of deriving it from relative
63    /// accuracy.
64    ///
65    /// `gamma` must be greater than `1.0`, otherwise the logarithmic mapping is
66    /// invalid.
67    ///
68    /// # Errors
69    ///
70    /// Returns an error if `gamma <= 1.0`.
71    pub fn new_with_gamma(gamma: f64) -> Result<Self, &'static str> {
72        Self::new_with_gamma_and_offset(gamma, 0.0)
73    }
74
75    /// Creates a new `LogarithmicMapping` from an explicit logarithmic base and index offset.
76    ///
77    /// `gamma` must be greater than `1.0`, otherwise the logarithmic mapping is
78    /// invalid.
79    ///
80    /// # Errors
81    ///
82    /// Returns an error if `gamma <= 1.0`.
83    pub fn new_with_gamma_and_offset(gamma: f64, index_offset: f64) -> Result<Self, &'static str> {
84        if gamma <= 1.0 {
85            return Err("gamma must be greater than 1");
86        }
87        let multiplier = 1.0 / gamma.ln();
88        Ok(Self {
89            gamma,
90            index_offset,
91            multiplier,
92        })
93    }
94}
95
96impl IndexMapping for LogarithmicMapping {
97    fn index(&self, value: f64) -> i32 {
98        let index = value.ln() * self.multiplier + self.index_offset;
99        if index >= 0.0 {
100            index as i32
101        } else {
102            (index as i32) - 1
103        }
104    }
105
106    fn value(&self, index: i32) -> f64 {
107        self.lower_bound(index) * (1.0 + self.relative_accuracy())
108    }
109
110    fn lower_bound(&self, index: i32) -> f64 {
111        ((index as f64 - self.index_offset) / self.multiplier).exp()
112    }
113
114    fn relative_accuracy(&self) -> f64 {
115        (self.gamma - 1.0) / (self.gamma + 1.0)
116    }
117
118    fn min_indexable_value(&self) -> f64 {
119        f64::MIN_POSITIVE.max((((i32::MIN as f64) - self.index_offset) / self.multiplier + 1.0).exp())
120    }
121
122    fn max_indexable_value(&self) -> f64 {
123        ((((i32::MAX as f64) - self.index_offset) / self.multiplier - 1.0).exp()).min(f64::MAX / self.gamma)
124    }
125
126    fn gamma(&self) -> f64 {
127        self.gamma
128    }
129
130    fn index_offset(&self) -> f64 {
131        self.index_offset
132    }
133
134    fn interpolation(&self) -> Interpolation {
135        Interpolation::NONE
136    }
137
138    fn validate_proto_mapping(&self, proto: &ProtoIndexMapping) -> Result<(), ProtoConversionError> {
139        // Check gamma matches (with floating-point tolerance)
140        if !float_eq(proto.gamma, self.gamma) {
141            return Err(ProtoConversionError::GammaMismatch {
142                expected: self.gamma,
143                actual: proto.gamma,
144            });
145        }
146
147        // Check indexOffset matches (with floating-point tolerance)
148        if !float_eq(proto.indexOffset, self.index_offset) {
149            return Err(ProtoConversionError::NonZeroIndexOffset {
150                actual: proto.indexOffset,
151            });
152        }
153
154        // Check interpolation is NONE (LogarithmicMapping uses exact log)
155        let interpolation = proto.interpolation.enum_value_or_default();
156        if interpolation != Interpolation::NONE {
157            return Err(ProtoConversionError::UnsupportedInterpolation {
158                actual: interpolation as i32,
159            });
160        }
161
162        Ok(())
163    }
164
165    fn to_proto(&self) -> ProtoIndexMapping {
166        let mut proto = ProtoIndexMapping::new();
167        proto.gamma = self.gamma;
168        proto.indexOffset = self.index_offset;
169        proto.interpolation = protobuf::EnumOrUnknown::new(Interpolation::NONE);
170        proto
171    }
172}
173
174impl Default for LogarithmicMapping {
175    /// Creates a logarithmic mapping with 1% relative accuracy (the common default).
176    fn default() -> Self {
177        Self::new(0.01).expect("0.01 is a valid relative accuracy")
178    }
179}
180
181#[cfg(test)]
182mod tests {
183    use super::*;
184
185    // Shared `IndexMapping` conformance suite (round-trip, bound ordering, gamma/accuracy consistency, proto
186    // self-validation).
187    #[test]
188    fn conforms_to_index_mapping_contract() {
189        let mapping = LogarithmicMapping::new(0.01).unwrap();
190        crate::canonical::mapping::conformance::assert_index_mapping_conformance(&mapping, 0.01);
191    }
192
193    // Constructor accuracy-bound validation is specific to the runtime-configured `LogarithmicMapping`.
194    #[test]
195    fn new_rejects_accuracy_of_zero() {
196        assert!(LogarithmicMapping::new(0.0).is_err());
197    }
198
199    #[test]
200    fn new_rejects_accuracy_of_one() {
201        assert!(LogarithmicMapping::new(1.0).is_err());
202    }
203
204    #[test]
205    fn new_rejects_negative_accuracy() {
206        assert!(LogarithmicMapping::new(-0.1).is_err());
207    }
208
209    #[test]
210    fn gamma_is_derived_from_accuracy() {
211        let mapping = LogarithmicMapping::new(0.01).unwrap();
212        // gamma = (1 + 0.01) / (1 - 0.01) = 1.01 / 0.99
213        let expected_gamma = 1.01 / 0.99;
214        assert!((mapping.gamma() - expected_gamma).abs() < 1e-10);
215    }
216}
ddsketch/canonical/mapping/logarithmic.rs

ddsketch/canonical/mapping/
logarithmic.rs
