card_est_array/traits/estimator.rs
1/*
2 * SPDX-FileCopyrightText: 2024 Matteo Dell'Acqua
3 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4 *
5 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6 */
7
8use std::borrow::Borrow;
9
10/// A kind of cardinality estimator.
11///
12/// Implementations of this trait describe the behavior of a kind of cardinality
13/// estimator. An instance usually contains parameters that further refine the
14/// behavior and the precision of the estimator.
15///
16/// The trait contains the following items:
17///
18/// * Three associated types:
19/// - `Item`: the type of items the estimator accepts.
20/// - `Backend`: the type of the estimator backend, that is, the raw,
21/// concrete representation of the estimator state.
22/// - `Estimator<'a>`: the type of an estimator of this kind.
23/// * A method to create a new estimator:
24/// [`new_estimator`](EstimationLogic::new_estimator).
25/// * A method to add elements to an estimator, given its backend:
26/// [`add`](EstimationLogic::add).
27/// * Methods to manipulate backends: [`estimate`](EstimationLogic::estimate),
28/// [`clear`](EstimationLogic::clear), and [`set`](EstimationLogic::set).
29///
30/// By providing methods based on backends, an [`EstimationLogic`] can be used
31/// to manipulate families of estimators with the same backend and the same
32/// configuration (i.e., precision) in a controlled way, and saving space by
33/// sharing common parameters. This is particularly useful to build [arrays of
34/// cardinality estimators](crate::traits::EstimatorArray), which are arrays of
35/// estimators sharing the same logic, but the same technique can be applied
36/// to any kind of container (e.g., hash maps or sets of backends).
37///
38/// If you plan to use a small number of non-related estimators, we suggest you
39/// [create](EstimationLogic::new_estimator) them and use their methods. More
40/// complex applications, coordinating large numbers of estimators, will find
41/// backend-based methods useful.
42pub trait EstimationLogic {
43 /// The type of items.
44 type Item;
45 /// The type of the backend.
46 type Backend: ?Sized;
47 /// The type of an estimator.
48 type Estimator<'a>: EstimatorMut<Self>
49 where
50 Self: 'a;
51
52 /// Adds an element to an estimator with the given backend.
53 fn add(&self, backend: &mut Self::Backend, element: impl Borrow<Self::Item>);
54
55 /// Returns an estimation of the number of distinct elements that have been
56 /// added to an estimator with the given backend so far.
57 fn estimate(&self, backend: &Self::Backend) -> f64;
58
59 /// Clears a backend, making it empty.
60 fn clear(&self, backend: &mut Self::Backend);
61
62 /// Sets the contents of `dst` to the contents of `src`.
63 fn set(&self, dst: &mut Self::Backend, src: &Self::Backend);
64
65 /// Creates a new empty estimator using this logic.
66 fn new_estimator(&self) -> Self::Estimator<'_>;
67}
68
69/// An extension of [`EstimationLogic`] providing methods to merge backends.
70///
71/// Some kind of estimators make available a *merge* operation, which,
72/// given two estimators, returns an estimator with the same state
73/// one would obtain by adding to an empty estimator all the elements
74/// added to the two estimators, computing, in practice, a set union.
75///
76/// Since often merging requires additional allocation (usually, to hold
77/// temporary results sized like a backend), this trait provides two methods:
78/// [`merge`](MergeEstimationLogic::merge) and
79/// [`merge_with_helper`](MergeEstimationLogic::merge_with_helper). The first
80/// one is simpler to use, but it might cause excessive allocation if used
81/// repeatedly. The second one requires a helper to be provided, but it allows
82/// to reuse the helper for several merge operations.
83pub trait MergeEstimationLogic: EstimationLogic {
84 /// The type of the helper used in merge calculations.
85 ///
86 /// Merge calculation might require temporary allocations. To mitigate
87 /// excessive allocation, it is possible to [obtain a
88 /// helper](MergeEstimationLogic::new_helper) and reuse it for several
89 /// [merge operations](MergeEstimationLogic::merge_with_helper).
90 type Helper;
91
92 /// Creates a new helper to use in merge operations.
93 fn new_helper(&self) -> Self::Helper;
94
95 /// Merges `src` into `dst`.
96 fn merge(&self, dst: &mut Self::Backend, src: &Self::Backend) {
97 let mut helper = self.new_helper();
98 self.merge_with_helper(dst, src, &mut helper);
99 }
100
101 /// Merges `src` into `dst` using the provided helper to avoid allocations.
102 fn merge_with_helper(
103 &self,
104 dst: &mut Self::Backend,
105 src: &Self::Backend,
106 helper: &mut Self::Helper,
107 );
108}
109
110/// Trait implemented by [estimation logics](EstimationLogic) whose backend is a
111/// slice of elements of some type.
112pub trait SliceEstimationLogic<T>: EstimationLogic<Backend = [T]> {
113 /// The number of elements of type `T` in a backend.
114 fn backend_len(&self) -> usize;
115}
116
117/// Asserts that a backend slice has the expected length for the given
118/// [`SliceEstimationLogic`].
119macro_rules! assert_backend_len {
120 ($logic:expr, $backend:expr) => {
121 assert_eq!(
122 $backend.len(),
123 $logic.backend_len(),
124 "backend length ({}) does not match the expected length ({})",
125 $backend.len(),
126 $logic.backend_len()
127 )
128 };
129}
130
131pub(crate) use assert_backend_len;
132
133/// An immutable estimator.
134///
135/// Immutable estimators are usually immutable views over some larger structure,
136/// or they contain some useful immutable state that can be reused.
137///
138/// An estimator must implement [`AsRef`] to return a reference to its backend.
139pub trait Estimator<L: EstimationLogic + ?Sized>: AsRef<L::Backend> {
140 /// The type returned by [`Estimator::into_owned`].
141 type OwnedEstimator: EstimatorMut<L>;
142
143 /// Returns the logic of the estimator.
144 fn logic(&self) -> &L;
145
146 /// Returns an estimation of the number of distinct elements that have been
147 /// added to the estimator so far.
148 fn estimate(&self) -> f64;
149
150 /// Converts this estimator into an owned version capable of mutation.
151 fn into_owned(self) -> Self::OwnedEstimator;
152}
153
154/// A mutable estimator.
155///
156/// A mutable estimator must implement [`AsMut`] to return a mutable
157/// reference to its backend.
158pub trait EstimatorMut<L: EstimationLogic + ?Sized>: Estimator<L> + AsMut<L::Backend> {
159 /// Adds an element to the estimator.
160 fn add(&mut self, element: impl Borrow<L::Item>);
161
162 /// Clears the estimator, making it empty.
163 fn clear(&mut self);
164
165 /// Sets the contents of `self` to the given backend.
166 ///
167 /// If you need to set to the content of another estimator, just use
168 /// [`as_ref`](AsRef) on the estimator. This approach makes it
169 /// possible to extract content from both owned and non-owned estimators.
170 fn set(&mut self, backend: &L::Backend);
171}
172
173/// An estimator capable of merging.
174pub trait MergeEstimator<L: MergeEstimationLogic + ?Sized>: EstimatorMut<L> {
175 /// Merges a backend into `self`.
176 ///
177 /// If you need to merge with the content of another estimator, just use
178 /// [`as_ref`](AsRef) on the estimator. This approach
179 /// makes it possible to merge both owned and non-owned estimators.
180 fn merge(&mut self, backend: &L::Backend) {
181 let mut helper = self.logic().new_helper();
182 self.merge_with_helper(backend, &mut helper);
183 }
184
185 /// Merges a backend into `self` using the provided helper to avoid
186 /// excessive allocations.
187 ///
188 /// If you need to merge with the content of another estimator, just use
189 /// [`as_ref`](AsRef) on the estimator. This approach makes it
190 /// possible to merge both owned and non-owned estimators.
191 fn merge_with_helper(&mut self, backend: &L::Backend, helper: &mut L::Helper);
192}