ddsketch/canonical/mapping/
mod.rs

1//! Index mapping.
2
3use datadog_protos::sketches::{index_mapping::Interpolation, IndexMapping as ProtoIndexMapping};
4
5use super::error::ProtoConversionError;
6
7mod fixed;
8pub use self::fixed::FixedLogarithmicMapping;
9
10mod logarithmic;
11pub use self::logarithmic::LogarithmicMapping;
12
13/// Maps values to bin indices and vice versa.
14///
15/// The mapping defines the relationship between floating-point values and integer bin indices, determining the relative
16/// accuracy of the sketch.
17pub trait IndexMapping: Clone + Send + Sync {
18    /// Returns the index of the bin for the given positive value.
19    ///
20    /// The value must be positive. For negative values, use the index of the absolute value and store in the negative
21    /// store.
22    fn index(&self, value: f64) -> i32;
23
24    /// Returns the representative value for the given index.
25    ///
26    /// This is typically the geometric mean of the bin's lower and upper bounds.
27    fn value(&self, index: i32) -> f64;
28
29    /// Returns the lower bound of the bin at the given index.
30    fn lower_bound(&self, index: i32) -> f64;
31
32    /// Returns the relative accuracy of this mapping.
33    ///
34    /// The relative accuracy is the maximum relative error guaranteed for any quantile query.
35    fn relative_accuracy(&self) -> f64;
36
37    /// Returns the minimum positive value that can be indexed.
38    fn min_indexable_value(&self) -> f64;
39
40    /// Returns the maximum positive value that can be indexed.
41    fn max_indexable_value(&self) -> f64;
42
43    /// Returns the gamma value (base of the logarithm) for this mapping.
44    fn gamma(&self) -> f64;
45
46    /// Returns the index offset used by this mapping.
47    ///
48    /// The index offset shifts all bin indices by a constant value.
49    fn index_offset(&self) -> f64;
50
51    /// Returns the interpolation mode used by this mapping.
52    ///
53    /// The interpolation mode determines how the logarithm is approximated.
54    fn interpolation(&self) -> Interpolation;
55
56    /// Validates that a protobuf `IndexMapping` is compatible with this mapping.
57    ///
58    /// # Errors
59    ///
60    /// If the given protobuf mapping parameters don't match this mapping's configuration, an error describing the
61    /// mismatch is returned.
62    fn validate_proto_mapping(&self, proto: &ProtoIndexMapping) -> Result<(), ProtoConversionError>;
63
64    /// Converts this mapping to a protobuf `IndexMapping`.
65    fn to_proto(&self) -> ProtoIndexMapping;
66}
67
68#[cfg(test)]
69pub(crate) mod conformance {
70    use super::IndexMapping;
71
72    /// Asserts the shared [`IndexMapping`] contract that every mapping implementation must satisfy.
73    ///
74    /// Rather than hand-duplicate the index/value round-trip, bound-ordering, and protobuf self-validation checks
75    /// across each sibling mapping's tests, both implementations call this helper. Constructor-specific behavior
76    /// (accuracy-bound validation, zero-sizedness, cross-implementation agreement) is still tested inline.
77    ///
78    /// `expected_relative_accuracy` is the accuracy the mapping is configured for; it's checked both directly and for
79    /// internal consistency with the mapping's gamma (`alpha = (gamma - 1) / (gamma + 1)`).
80    #[track_caller]
81    pub(crate) fn assert_index_mapping_conformance<M: IndexMapping>(mapping: &M, expected_relative_accuracy: f64) {
82        assert!(
83            (mapping.relative_accuracy() - expected_relative_accuracy).abs() < 1e-10,
84            "relative accuracy {} should match expected {}",
85            mapping.relative_accuracy(),
86            expected_relative_accuracy
87        );
88
89        let gamma = mapping.gamma();
90        let derived_accuracy = (gamma - 1.0) / (gamma + 1.0);
91        assert!(
92            (mapping.relative_accuracy() - derived_accuracy).abs() < 1e-10,
93            "relative accuracy {} should be consistent with gamma {} (derived {})",
94            mapping.relative_accuracy(),
95            gamma,
96            derived_accuracy
97        );
98
99        for i in -100..100 {
100            // The representative value must sit strictly above the bin's lower bound.
101            let lower = mapping.lower_bound(i);
102            let value = mapping.value(i);
103            assert!(
104                lower < value,
105                "lower bound {} should be < value {} at index {}",
106                lower,
107                value,
108                i
109            );
110
111            // Mapping an index to its value and back must recover the index (within one bin, due to floating-point).
112            let recovered = mapping.index(value);
113            assert!(
114                (recovered - i).abs() <= 1,
115                "index {} -> value {} -> index {} should round-trip within one bin",
116                i,
117                value,
118                recovered
119            );
120        }
121
122        // A mapping must accept its own protobuf representation.
123        assert!(
124            mapping.validate_proto_mapping(&mapping.to_proto()).is_ok(),
125            "mapping should validate its own protobuf representation"
126        );
127    }
128}
ddsketch/canonical/mapping/mod.rs

ddsketch/canonical/mapping/
mod.rs
