1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

//! Implementations of the HyperLogLog algorithm for cardinality estimation.
//!
//! HyperLogLog is an probabilistic algorithm for estimating the number of
//! *distinct* elements (*cardinality*) of a multiset. The original algorithm,
//! described by P. Flajolet et al. in *HyperLogLog: the analysis of a
//! near-optimal cardinality estimation algorithm*, can estimate cardinalities
//! well beyond 10<sup>9</sup> with a typical accuracy of 2% while using memory
//! of 1.5 kilobytes. HyperLogLog variants can improve on those results.
//!
//! All HyperLogLog variants should implement the [`HyperLogLog`] trait.
//!
//! Current implementations:
//!
//! * [`HyperLogLogPF`]
//! * [`HyperLogLogPlus`]

#![cfg_attr(feature = "bench-units", feature(test))]
#![cfg_attr(not(feature = "std"), no_std)]

#[cfg(feature = "alloc")]
extern crate alloc;

mod common;
#[cfg(feature = "std")]
mod constants;
#[cfg(feature = "std")]
mod encoding;
mod hyperloglog;
#[cfg(feature = "std")]
mod hyperloglogplus;
#[cfg(not(feature = "std"))]
mod log;

use core::borrow::Borrow;
use core::fmt;
use core::hash::Hash;

// Available also with no_std.
pub use crate::hyperloglog::HyperLogLogPF;

// Available only with std.
#[cfg(feature = "std")]
pub use crate::hyperloglogplus::HyperLogLogPlus;

/// A trait that should be implemented by any HyperLogLog variant.
pub trait HyperLogLog<H: Hash + ?Sized> {
    /// Adds a new value to the multiset.
    #[deprecated(since = "0.3.0", note = "use insert() function instead.")]
    fn add(&mut self, value: &H);

    /// Inserts a new value to the multiset.
    fn insert<Q>(&mut self, value: &Q)
    where
        H: Borrow<Q>,
        Q: Hash + ?Sized;

    /// Estimates the cardinality of the multiset.
    fn count(&mut self) -> f64;
}

#[derive(Debug, PartialEq)]
pub enum HyperLogLogError {
    InvalidPrecision,
    IncompatiblePrecision,
}

impl fmt::Display for HyperLogLogError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            HyperLogLogError::InvalidPrecision => {
                "precision is out of bounds".fmt(f)
            },
            HyperLogLogError::IncompatiblePrecision => {
                "precisions must be equal".fmt(f)
            },
        }
    }
}

impl std::error::Error for HyperLogLogError {}