Struct SumTree 

pub struct SumTree<T: Item>(/* private fields */);

A B+ tree in which each leaf node contains Items of type T and a Summarys for each Item. Each internal node contains a Summary of the items in its subtree.

The maximum number of items per node is TREE_BASE * 2.

Any Dimension supported by the Summary type can be used to seek to a specific location in the tree.

Implementations

impl<T: Item> SumTree<T>

pub fn new(cx: <T::Summary as Summary>::Context<'_>) -> Self

pub fn from_summary(summary: T::Summary) -> Self

Useful in cases where the item type has a non-trivial context type, but the zero value of the summary type doesn’t depend on that context.

pub fn from_item(item: T, cx: <T::Summary as Summary>::Context<'_>) -> Self

pub fn from_iter<I: IntoIterator<Item = T>>( iter: I, cx: <T::Summary as Summary>::Context<'_>, ) -> Self

pub fn from_par_iter<I, Iter>( iter: I, cx: <T::Summary as Summary>::Context<'_>, ) -> Self

where I: IntoParallelIterator<Iter = Iter>, Iter: IndexedParallelIterator<Item = T>, T: Send + Sync, T::Summary: Send + Sync, for<'a> <T::Summary as Summary>::Context<'a>: Sync,

pub fn items<'a>(&'a self, cx: <T::Summary as Summary>::Context<'a>) -> Vec<T>

pub fn iter(&self) -> Iter<'_, T>

pub fn cursor<'a, 'b, S>( &'a self, cx: <T::Summary as Summary>::Context<'b>, ) -> Cursor<'a, 'b, T, S>

where S: Dimension<'a, T::Summary>,

pub fn filter<'a, 'b, F, U>( &'a self, cx: <T::Summary as Summary>::Context<'b>, filter_node: F, ) -> FilterCursor<'a, 'b, F, T, U>

where F: FnMut(&T::Summary) -> bool, U: Dimension<'a, T::Summary>,

Note: If the summary type requires a non () context, then the filter cursor that is returned cannot be used with Rust’s iterators.

pub fn first(&self) -> Option<&T>

pub fn last(&self) -> Option<&T>

pub fn update_last( &mut self, f: impl FnOnce(&mut T), cx: <T::Summary as Summary>::Context<'_>, )

pub fn extent<'a, D: Dimension<'a, T::Summary>>( &'a self, cx: <T::Summary as Summary>::Context<'_>, ) -> D

pub fn summary(&self) -> &T::Summary

pub fn is_empty(&self) -> bool

pub fn extend<I>(&mut self, iter: I, cx: <T::Summary as Summary>::Context<'_>)

where I: IntoIterator<Item = T>,

pub fn par_extend<I, Iter>( &mut self, iter: I, cx: <T::Summary as Summary>::Context<'_>, )

where I: IntoParallelIterator<Iter = Iter>, Iter: IndexedParallelIterator<Item = T>, T: Send + Sync, T::Summary: Send + Sync, for<'a> <T::Summary as Summary>::Context<'a>: Sync,

pub fn push(&mut self, item: T, cx: <T::Summary as Summary>::Context<'_>)

pub fn append(&mut self, other: Self, cx: <T::Summary as Summary>::Context<'_>)

impl<T: KeyedItem> SumTree<T>

pub fn insert_or_replace<'a, 'b>( &'a mut self, item: T, cx: <T::Summary as Summary>::Context<'b>, ) -> Option<T>

pub fn remove( &mut self, key: &T::Key, cx: <T::Summary as Summary>::Context<'_>, ) -> Option<T>

pub fn edit( &mut self, edits: Vec<Edit<T>>, cx: <T::Summary as Summary>::Context<'_>, ) -> Vec<T>

pub fn get<'a>( &'a self, key: &T::Key, cx: <T::Summary as Summary>::Context<'a>, ) -> Option<&'a T>

Trait Implementations

impl<T: Clone + Item> Clone for SumTree<T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for SumTree<T>

where T: Debug + Item, T::Summary: Debug,

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

Formats the value using the given formatter.

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

where T: Item<Summary = S>, S: for<'a> Summary<Context<'a> = ()>,

fn default() -> Self

Returns the “default value” for a type.

impl<T: Item + PartialEq> PartialEq for SumTree<T>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Item + Eq> Eq for SumTree<T>