Struct Bjkst

pub struct Bjkst<T, S = BuildHasherDefault<DefaultHasher>> { /* private fields */ }

A BJKST data structure to estimate the number of distinct elements in a data stream.

Examples

use uniq_ch::Bjkst;

let mut bjkst = Bjkst::new();

// Add some elements, with duplicates.
bjkst.extend(0..75_000);
bjkst.extend(25_000..100_000);

// Count the distinct elements.
assert!((99_000..101_000).contains(&bjkst.len()));

Implementations

impl<T> Bjkst<T, BuildHasherDefault<DefaultHasher>>

pub fn new() -> Self

Creates an empty Bjkst.

Examples

use uniq_ch::Bjkst;

let bjkst = Bjkst::<usize>::new();

impl<T, S> Bjkst<T, S>

where S: Default,

pub fn with_precision(precision: Precision) -> Self

Creates an empty Bjkst with the specified precision.

Examples

use uniq_ch::{Bjkst, Precision};

let bjkst = Bjkst::<usize>::with_precision(Precision::P10);
assert_eq!(bjkst.precision(), Precision::P10);

impl<T, S> Bjkst<T, S>

pub fn with_precision_and_hasher(precision: Precision, hasher: S) -> Self

Creates an empty Bjkst with the specified precision, using hasher to hash values.

Warning: hasher is normally randomly generated, and is designed to allow Bjksts to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The hasher passed should implement the BuildHasher trait for the BJKST to be useful, see its documentation for details.

Examples

use std::collections::hash_map::RandomState;

use uniq_ch::{Bjkst, Precision};

let hasher = RandomState::new();
let mut bjkst = Bjkst::with_precision_and_hasher(Precision::P10, hasher);
bjkst.insert(&2);

pub fn with_hasher(hasher: S) -> Self

Creates a new empty Bjkst which will use the given hasher to hash values.

Warning: hasher is normally randomly generated, and is designed to allow Bjksts to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The hasher passed should implement the BuildHasher trait for the BJKST to be useful, see its documentation for details.

Examples

use std::collections::hash_map::RandomState;

use uniq_ch::Bjkst;

let hasher = RandomState::new();
let mut bjkst = Bjkst::with_hasher(hasher);
bjkst.insert(&2);

pub const fn precision(&self) -> Precision

Returns the precision of the Bjkst.

Examples

use uniq_ch::{Bjkst, Precision};

let bjkst = Bjkst::<usize>::with_precision(Precision::P10);
assert_eq!(bjkst.precision(), Precision::P10);

pub fn hasher(&self) -> &S

Returns a reference to the BJKST data structure’s BuildHasher.

Examples

use std::collections::hash_map::RandomState;

use uniq_ch::Bjkst;

let hasher = RandomState::new();
let bjkst = Bjkst::<usize, _>::with_hasher(hasher);
let hasher: &RandomState = bjkst.hasher();

pub fn clear(&mut self)

Clears the BJKST data structure, removing all values.

Examples

use uniq_ch::Bjkst;

let mut bjkst = Bjkst::new();
bjkst.insert(&1);
bjkst.clear();
assert!(bjkst.is_empty());

pub fn is_empty(&self) -> bool

Returns true if the BJKST data structure contains no elements.

Examples

use uniq_ch::Bjkst;

let mut bjkst = Bjkst::new();
assert!(bjkst.is_empty());
bjkst.insert(&1);
assert!(!bjkst.is_empty());

pub fn insert_hash(&mut self, hash: u64) -> bool

Adds a hash value to the BJKST data structure.

Returns whether the value was newly inserted. That is:

• If the value is not skipped, and the BJKST data structure did not previously contain this value, true is returned.
• If the value is skipped or the BJKST data structure already contained this value, false is returned.

This may be handy when the hash is previously computed, to avoid computing twice. Hash values need to be uniformly distributed over u64 for an accurate total count.

In all other cases, use insert instead.

Examples

use uniq_ch::Bjkst;

let mut bjkst = Bjkst::<usize>::new();

assert_eq!(bjkst.insert_hash(0x12345678), true);
assert_eq!(bjkst.insert_hash(0x12345678), false);
assert_eq!(bjkst.len(), 1);

impl<T, S> Bjkst<T, S>

where T: Hash, S: BuildHasher,

pub fn insert(&mut self, value: &T) -> bool

Adds a value to the BJKST data structure.

Returns whether the value was newly inserted. That is:

• If the value is not skipped, and the BJKST data structure did not previously contain this value, true is returned.
• If the value is skipped or the BJKST data structure already contained this value, false is returned.

Examples

use uniq_ch::Bjkst;

let mut bjkst = Bjkst::new();

assert_eq!(bjkst.insert(&2), true);
assert_eq!(bjkst.insert(&2), false);
assert_eq!(bjkst.len(), 1);

pub fn len(&self) -> usize

Calculates the approximate number of different elements.

Examples

use uniq_ch::Bjkst;

let mut bjkst = Bjkst::new();
for i in 0..100_000 {
    bjkst.insert(&i);
}
assert!((99_000..=101_000).contains(&bjkst.len()));

Trait Implementations

impl<T, H> BitOr<&Bjkst<T, BuildHasherDefault<H>>> for &Bjkst<T, BuildHasherDefault<H>>

where T: Hash, H: Default + Hasher,

fn bitor(self, rhs: &Bjkst<T, BuildHasherDefault<H>>) -> Self::Output

Returns the union of self and rhs as a new Bjkst<S, T>.

Examples

use uniq_ch::Bjkst;

let lhs = Bjkst::<i32>::from_iter(0..75_000);
let rhs = Bjkst::<i32>::from_iter(25_000..100_000);
let bjkst = &lhs | &rhs;
assert!((99_000..=101_000).contains(&bjkst.len()));

type Output = Bjkst<T, BuildHasherDefault<H>>

The resulting type after applying the | operator.

impl<T, H> BitOrAssign<&Bjkst<T, BuildHasherDefault<H>>> for Bjkst<T, BuildHasherDefault<H>>

where T: Hash, H: Default + Hasher,

fn bitor_assign(&mut self, rhs: &Bjkst<T, BuildHasherDefault<H>>)

Merges self and rhs into self.

Examples

use uniq_ch::Bjkst;

let mut lhs = Bjkst::<i32>::from_iter(1..75_000);
let rhs = Bjkst::<i32>::from_iter(25_000..100_000);
lhs |= &rhs;
assert!((99_000..=101_000).contains(&lhs.len()));

impl<T, S> Clone for Bjkst<T, S>

where S: Clone,

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug, S: Debug> Debug for Bjkst<T, S>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, S> Default for Bjkst<T, S>

where S: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, T, S> Deserialize<'de> for Bjkst<T, S>

where S: Default,

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<'a, T, S> Extend<&'a T> for Bjkst<T, S>

where T: Hash + 'a, S: BuildHasher,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = &'a T>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, S> Extend<T> for Bjkst<T, S>

where T: Hash, S: BuildHasher,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = T>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T, S, const N: usize> From<[&'a T; N]> for Bjkst<T, S>

where T: Hash, S: BuildHasher + Default,

fn from(values: [&'a T; N]) -> Self

Converts to this type from the input type.

impl<T, S, const N: usize> From<[T; N]> for Bjkst<T, S>

where T: Hash, S: BuildHasher + Default,

fn from(values: [T; N]) -> Self

Creates a new Bjkst<T, S> from an array of T.

Examples

use uniq_ch::Bjkst;

let bjkst1 = Bjkst::<i32>::from([1, 2, 3, 4, 5]);
let bjkst2: Bjkst<i32> = [1, 2, 3, 4, 5].into();
assert_eq!(bjkst1.len(), bjkst2.len());

impl<'a, T, S> FromIterator<&'a T> for Bjkst<T, S>

where T: Hash + 'a, S: BuildHasher + Default,

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = &'a T>,

Creates a value from an iterator.

impl<T, S> FromIterator<T> for Bjkst<T, S>

where T: Hash, S: BuildHasher + Default,

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<T, S> Serialize for Bjkst<T, S>

where S: Default,

fn serialize<R>(&self, serializer: R) -> Result<R::Ok, R::Error>

where R: Serializer,

Serialize this value into the given Serde serializer.