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.
75pub trait MergeEstimationLogic: EstimationLogic {
76    /// The type of the helper used in merge calculations.
77    ///
78    /// Merge calculation might require temporary allocations. To mitigate
79    /// excessive allocation, it is possible to [obtain a
80    /// helper](MergeEstimationLogic::new_helper) and reuse it for several
81    /// [merge operations](MergeEstimationLogic::merge_with_helper).
82    type Helper;
83
84    /// Creates a new helper to use in merge operations.
85    fn new_helper(&self) -> Self::Helper;
86
87    /// Merges `src` into `dst`.
88    fn merge(&self, dst: &mut Self::Backend, src: &Self::Backend) {
89        let mut helper = self.new_helper();
90        self.merge_with_helper(dst, src, &mut helper);
91    }
92
93    /// Merges `src` into `dst` using the provided helper to avoid allocations.
94    fn merge_with_helper(
95        &self,
96        dst: &mut Self::Backend,
97        src: &Self::Backend,
98        helper: &mut Self::Helper,
99    );
100}
101
102/// Trait implemented by [estimation logics](EstimationLogic) whose backend is a
103/// slice of elements of some type.
104pub trait SliceEstimationLogic<T>: EstimationLogic<Backend = [T]> {
105    /// The number of elements of type `T` in a backend.
106    fn backend_len(&self) -> usize;
107}
108
109/// An immutable estimator.
110///
111/// Immutable estimators are usually immutable views over some larger structure,
112/// or they contain some useful immutable state that can be reused.
113///
114/// An estimator must implement [`AsRef`] to return a reference to its backend.
115pub trait Estimator<L: EstimationLogic + ?Sized>: AsRef<L::Backend> {
116    /// The type returned by [`Estimator::into_owned`].
117    type OwnedEstimator: EstimatorMut<L>;
118
119    /// Returns the logic of the estimator.
120    fn logic(&self) -> &L;
121
122    /// Returns an estimation of the number of distinct elements that have been
123    /// added to the estimator so far.
124    fn estimate(&self) -> f64;
125
126    /// Converts this estimator into an owned version capable of mutation.
127    fn into_owned(self) -> Self::OwnedEstimator;
128}
129
130/// A mutable estimator.
131///
132/// A mutable estimator must implement [`AsMut`] to return a mutable
133/// reference to its backend.
134pub trait EstimatorMut<L: EstimationLogic + ?Sized>: Estimator<L> + AsMut<L::Backend> {
135    /// Adds an element to the estimator.
136    fn add(&mut self, element: impl Borrow<L::Item>);
137
138    /// Clears the estimator, making it empty.
139    fn clear(&mut self);
140
141    /// Sets the contents of `self` to the given backend.
142    ///
143    /// If you need to set to the content of another estimator, just use
144    /// [`as_ref`](AsRef) on the estimator. This approach makes it
145    /// possible to extract content from both owned and non-owned estimators.
146    fn set(&mut self, backend: &L::Backend);
147}
148
149/// An estimator capable of merging.
150pub trait MergeEstimator<L: MergeEstimationLogic + ?Sized>: EstimatorMut<L> {
151    /// Merges a backend into `self`.
152    ///
153    /// If you need to merge with the content of another estimator, just use
154    /// [`as_ref`](AsRef) on the estimator. This approach
155    /// makes it possible to merge both owned and non-owned estimators.
156    fn merge(&mut self, backend: &L::Backend) {
157        let mut helper = self.logic().new_helper();
158        self.merge_with_helper(backend, &mut helper);
159    }
160
161    /// Merges a backend into `self` using the provided helper to avoid
162    /// excessive allocations.
163    ///
164    /// If you need to merge with the content of another estimator, just use
165    /// [`as_ref`](AsRef) on the estimator. This approach makes it
166    /// possible to merge both owned and non-owned estimators.
167    fn merge_with_helper(&mut self, backend: &L::Backend, helper: &mut L::Helper);
168}
card_est_array/traits/estimator.rs

card_est_array/traits/
estimator.rs
