Struct mz_persist_client::internal::merge::MergeTree

pub struct MergeTree<T> {
    pub(crate) max_len: usize,
    pub(crate) levels: Vec<Vec<T>>,
    merge_fn: Box<dyn Fn(Vec<T>) -> T + Sync + Send>,
}

A merge tree.

Invariants and guarantees:

• This structure preserves the order in which elements are pushed.
• Merging also preserves order: only adjacent elements will be merged together, and the result will have the same place in the ordering as the input did.
• The tree will store at most O(K log N) elements at once, where K is the provided max len and N is the number of elements pushed.
• finish will return at most K elements.
• The “depth” of the merge tree - the number of merges any particular element may undergo - is O(log N).

Fields

max_len: usize

levels: Vec<Vec<T>>

merge_fn: Box<dyn Fn(Vec<T>) -> T + Sync + Send>

Implementations

impl<T> MergeTree<T>

pub fn new( max_len: usize, merge_fn: impl Fn(Vec<T>) -> T + Send + Sync + 'static, ) -> Self

Create a new merge tree. max_len limits both the number of parts to keep at each level of the tree, and the number of parts that Self::finish will return… and if we exceed that limit, the provided merge_fn is used to combine adjacent elements together.

pub fn iter(&self) -> impl Iterator<Item = &T> + DoubleEndedIterator

Iterate over (references to) the parts in this tree in first-to-latest order.

pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> + DoubleEndedIterator

Iterate over (mutable references to) the parts in this tree in first-to-latest order.

pub fn push(&mut self, part: T)

Push a new part onto the end of this tree, possibly triggering a merge.

pub fn finish(self) -> Vec<T>

Return the contents of this merge tree, flattened into at most max_len parts.

pub(crate) fn assert_invariants(&self)

Trait Implementations

impl<T: Debug> Debug for MergeTree<T>

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

Formats the value using the given formatter.