Struct MisraGries 

pub struct MisraGries<T: Ord> {
    inner: BTreeMap<T, usize>,
    k: usize,
}

Maintains a summary of “heavy hitters” in a presented collection of items.

Uses a BTreeMap internally so that repeated observations of the same element only allocate once (on first sighting). Tidy is performed when the number of distinct elements exceeds 2 * k, reducing to at most k entries.

Fields

inner: BTreeMap<T, usize>

k: usize

Implementations

impl<T: Ord> MisraGries<T>

pub fn insert(&mut self, element: T)

Inserts an additional element to the summary.

pub fn update(&mut self, element: T, count: usize)

Inserts multiple copies of an element to the summary.

pub fn done(self) -> Vec<(T, usize)>

Completes the summary, and extracts the items and their counts.

fn tidy(&mut self)

Reduces the summary down to at most k distinct items by subtracting the (k+1)-th largest count from all entries and discarding those that drop to zero or below.

impl MisraGries<Vec<u8>>

pub fn heap_size(&self, callback: &mut impl FnMut(usize, usize))

Visit contained allocations to determine their size and capacity.

BTreeMap exposes no capacity, so node storage is approximated as one logical entry per element; the owned key bytes are accounted exactly.

pub fn insert_ref(&mut self, element: &[u8])

Insert a borrowed byte slice, only allocating if the key is new.

Trait Implementations

impl<T: Ord> AddAssign for MisraGries<T>

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl<T: Clone + Ord> Clone for MisraGries<T>

fn clone(&self) -> MisraGries<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Ord> Debug for MisraGries<T>

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

Formats the value using the given formatter.

impl<T: Ord> Default for MisraGries<T>

fn default() -> Self

Returns the “default value” for a type.