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. Instances contains usually parameters that further refine the
14/// behavior and the precision of the estimator.
15///
16/// The trait contain 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 array of
35/// estimators sharing the same logic.
36///
37/// If you plan to use a small number of non-related estimators, we suggest you
38/// [create](EstimationLogic::new_estimator) them and use their methods. More
39/// complex applications, coordinating large numbers of estimators, will find
40/// backed-based methods useful.
41pub trait EstimationLogic {
42    /// The type of items.
43    type Item;
44    /// The type of the backend.
45    type Backend: ?Sized;
46    /// The type of an estimator.
47    type Estimator<'a>: EstimatorMut<Self>
48    where
49        Self: 'a;
50
51    /// Adds an element to an estimator with the given backend.
52    fn add(&self, backend: &mut Self::Backend, element: impl Borrow<Self::Item>);
53
54    /// Returns an estimation of the number of distinct elements that have been
55    /// added to an estimator with the given backend so far.
56    fn estimate(&self, backend: &Self::Backend) -> f64;
57
58    /// Clears a backend, making it empty.
59    fn clear(&self, backend: &mut Self::Backend);
60
61    /// Sets the contents of `dst` to the contents of `src`.
62    fn set(&self, dst: &mut Self::Backend, src: &Self::Backend);
63
64    /// Creates a new empty estimator using this logic.
65    fn new_estimator(&self) -> Self::Estimator<'_>;
66}
67
68/// An extension of [`EstimationLogic`] providing methods to merge backends.
69///
70/// Some kind of estimators make available a *merge* operation, which,
71/// given two estimators, returns an estimator with the same state
72/// one would obtain by adding to an empty estimator all the elements
73/// added to the two estimators, computing, in practice, a set union.
74pub trait MergeEstimationLogic: EstimationLogic {
75    /// The type of the helper use in merge calculations.
76    ///
77    /// Merge calculation might require temporary allocations. To mitigate
78    /// excessive allocation, it is possible to [obtain a
79    /// helper](MergeEstimationLogic::new_helper) and reusing it for several
80    /// [merge operations](MergeEstimationLogic::merge_with_helper)
81    type Helper;
82
83    /// Creates a new helper to use in merge operations.
84    fn new_helper(&self) -> Self::Helper;
85
86    /// Merges `src` into `dst`.
87    fn merge(&self, dst: &mut Self::Backend, src: &Self::Backend) {
88        let mut helper = self.new_helper();
89        self.merge_with_helper(dst, src, &mut helper);
90    }
91
92    /// Merges `src` into `dst` using the provided helper to avoid allocations.
93    fn merge_with_helper(
94        &self,
95        dst: &mut Self::Backend,
96        src: &Self::Backend,
97        helper: &mut Self::Helper,
98    );
99}
100
101/// Trait implemented by [estimation logics](EstimationLogic) whose backend is a
102/// slice of elements of some type.
103pub trait SliceEstimationLogic<T>: EstimationLogic<Backend = [T]> {
104    /// The number of elements of type `T` in a backend.
105    fn backend_len(&self) -> usize;
106}
107
108/// An immutable estimator.
109///
110/// Immutable estimators are usually immutable views over some larger structure,
111/// or they contain some useful immutable state that can be reused.
112///
113/// An estimator must implement [`AsRef`] so to return a reference to its backend.
114pub trait Estimator<L: EstimationLogic + ?Sized>: AsRef<L::Backend> {
115    /// The type returned by [`Estimator::into_owned`].
116    type OwnedEstimator: EstimatorMut<L>;
117
118    /// Returns the logic of the estimator.
119    fn logic(&self) -> &L;
120
121    /// Returns an estimation of the number of distinct elements that have been
122    /// added to the estimator so far.
123    fn estimate(&self) -> f64;
124
125    /// Converts this estimator into an owned version capable of mutation.
126    fn into_owned(self) -> Self::OwnedEstimator;
127}
128
129/// A mutable estimator.
130///
131/// A mutable estimator must implement [`AsMut`] so to return a mutable
132/// reference to its backend.
133pub trait EstimatorMut<L: EstimationLogic + ?Sized>: Estimator<L> + AsMut<L::Backend> {
134    /// Adds an element to the estimator.
135    fn add(&mut self, element: impl Borrow<L::Item>);
136
137    /// Clears the estimator, making it empty.
138    fn clear(&mut self);
139
140    /// Sets the contents of `self` to the the given backend.
141    ///
142    /// If you need to set to the content of another estimator, just use
143    /// [`as_ref`](AsRef) on the estimator. This approach makes it
144    /// possible to extract content from both owned and non-owned estimators.
145    fn set(&mut self, backend: &L::Backend);
146}
147
148/// An estimator capable of merging.
149pub trait MergeEstimator<L: MergeEstimationLogic + ?Sized>: EstimatorMut<L> {
150    /// Merges a backend into `self`.
151    ///
152    /// If you need to merge with the content of another estimator, just use
153    /// [`as_ref`](AsRef) on the estimator. This approach
154    /// makes it possible to merge both owned and non-owned estimators.
155    fn merge(&mut self, backend: &L::Backend) {
156        let mut helper = self.logic().new_helper();
157        self.merge_with_helper(backend, &mut helper);
158    }
159
160    /// Merges a backend into `self` using the provided helper to avoid
161    /// excessive allocations.
162    ///
163    /// If you need to merge with the content of another estimator, just use
164    /// [`as_ref`](AsRef) on the estimator. This approach makes it
165    /// possible to merge both owned and non-owned estimators.
166    fn merge_with_helper(&mut self, backend: &L::Backend, helper: &mut L::Helper);
167}
card_est_array/traits/estimator.rs

card_est_array/traits/
estimator.rs
