Struct generic_btree::BTree

pub struct BTree<B: BTreeTrait> { /* private fields */ }

Implementations

impl<T: Mergeable, B: BTreeTrait<Elem = T>> BTree<B>

pub fn get_mergeable_num(&self) -> usize

This will return the number of mergeable elements. Ideally this should be zero. This is provided for debugging and optimization

pub fn try_merge_to_neighbors(&mut self, start: QueryResult, end: QueryResult)

Try to merge the elements at the given range. This operation will invalidate the path if succeed.

impl<B: BTreeTrait> BTree<B>

pub fn new() -> Self

pub fn set_listener(&mut self, listener: Option<MoveListener<B::Elem>>)

Register/Unregister an element move event listener.

This is called when a element is moved from one leaf node to another. It could happen when:

• Leaf node split
• Leaf nodes merge
• Elements moving from one leaf node to another to keep the balance of the BTree

It’s useful when you try to track an element’s position in the BTree.

pub fn node_len(&self) -> usize

pub fn insert<Q>(&mut self, tree_index: &Q::QueryArg, data: B::Elem)where Q: Query<B>,

pub fn insert_by_query_result(&mut self, result: QueryResult, data: B::Elem)

It will invoke BTreeTrait::insert

pub fn insert_many_by_query_result( &mut self, result: &QueryResult, data: impl IntoIterator<Item = B::Elem> )where B::Elem: Clone,

Insert many elements into the tree at once

It will invoke BTreeTrait::insert_batch

NOTE: Currently this method don’t guarantee after inserting many elements the tree is still balance

pub fn batch_insert_by_query_result( &mut self, result: &QueryResult, data: impl IntoIterator<Item = B::Elem> )where B::Elem: Clone,

pub fn delete<Q>(&mut self, query: &Q::QueryArg) -> Option<B::Elem>where Q: Query<B>,

pub fn query<Q>(&self, query: &Q::QueryArg) -> QueryResultwhere Q: Query<B>,

pub fn shift_path_by_one_offset(&self, path: QueryResult) -> Option<QueryResult>where B::Elem: HasLength,

Shift by offset 1.

It will not stay on empty spans but scan forward

pub fn query_with_finder_return<Q>( &self, query: &Q::QueryArg ) -> (QueryResult, Q)where Q: Query<B>,

pub fn get_elem(&mut self, q: &QueryResult) -> Option<&B::Elem>

pub fn get_elem_mut(&mut self, q: &QueryResult) -> Option<&mut B::Elem>

pub fn drain<Q>(&mut self, range: Range<Q::QueryArg>) -> Drain<'_, B, Q>where Q: Query<B>,

pub fn update<F>(&mut self, range: Range<&QueryResult>, f: &mut F)where F: FnMut(MutElemArrSlice<'_, B::Elem>) -> (bool, Option<B::CacheDiff>),

Update the elements in place

F should returns true if the cache need to be updated

This method may break the balance of the tree

If the given range has zero length, f will still be called, and the slice will have same start and end field

TODO: need better test coverage TODO: make range: Range since it’s now a Copy type

pub fn update_with_filter<F>( &mut self, range: Range<&QueryResult>, f: &mut F, filter: &dyn Fn(&B::Cache) -> bool )where F: FnMut(MutElemArrSlice<'_, B::Elem>) -> (bool, Option<B::CacheDiff>),

Update the elements in place with filter to skip subtrees in advance

F should returns true if the cache need to be updated

This method may break the balance of the tree

If the given range has zero length, f will still be called, and the slice will have same start and end field

TODO: need better test coverage TODO: make range: Range since it’s now a Copy type

pub fn update_leaf( &mut self, node_idx: ArenaIndex, f: impl FnOnce(&mut Vec<B::Elem>) -> (bool, Option<B::CacheDiff>) )

update leaf node’s elements, return true if cache need to be updated

pub fn update2_leaf( &mut self, a_idx: ArenaIndex, b_idx: ArenaIndex, f: impl FnMut(&mut Vec<B::Elem>, Option<ArenaIndex>) -> bool )

pub fn iter(&self) -> impl Iterator<Item = &B::Elem> + '_

pub fn first_leaf(&self) -> ArenaIndex

pub fn last_leaf(&self) -> ArenaIndex

pub fn range<Q>(&self, range: Range<Q::QueryArg>) -> Range<QueryResult>where Q: Query<B>,

pub fn iter_range( &self, range: impl RangeBounds<QueryResult> ) -> impl Iterator<Item = ElemSlice<'_, B::Elem>> + '_

pub fn first_full_path(&self) -> QueryResult

pub fn last_full_path(&self) -> QueryResult

pub fn get_node(&self, index: ArenaIndex) -> &Node<B>

pub fn recursive_update_cache( &mut self, node_idx: ArenaIndex, can_use_diff: bool, cache_diff: Option<B::CacheDiff> )

Sometimes we cannot use diff because no only the given node is changed, but also its siblings. For example, after delete a range of nodes, we cannot use the diff from child to infer the diff of parent.

pub fn next_same_level_node(&self, node_idx: ArenaIndex) -> Option<ArenaIndex>

pub fn prev_same_level_node(&self, node_idx: ArenaIndex) -> Option<ArenaIndex>

pub fn root_cache(&self) -> &B::Cache

pub fn clear(&mut self)

This method will release the memory back to OS. Currently, it’s just *self = Self::new()

pub fn is_empty(&self) -> bool

pub fn push(&mut self, elem: B::Elem)

pub fn prepend(&mut self, elem: B::Elem)

pub fn notify_batch_move(&self, leaf: ArenaIndex, elements: &[B::Elem])

This method only works when MoveListener listener is registered

pub fn notify_elem_move(&self, leaf: ArenaIndex, elem: &B::Elem)

pub fn compare_pos(&self, a: QueryResult, b: QueryResult) -> Ordering

compare the position of a and b

impl<B: BTreeTrait> BTree<B>

pub fn check(&self)

Trait Implementations

impl<Elem: Clone, B: BTreeTrait<Elem = Elem>> Clone for BTree<B>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Cache: Debug, Elem: Debug, B: BTreeTrait<Elem = Elem, Cache = Cache>> Debug for BTree<B>

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

Formats the value using the given formatter.

impl<B: BTreeTrait> Default for BTree<B>

fn default() -> Self

Returns the “default value” for a type.