Struct BTree 

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

Implementations

impl<B: BTreeTrait> BTree<B>

pub fn new() -> Self

pub fn node_len(&self) -> usize

Get the number of nodes in the tree. It includes all the internal nodes and the leaf nodes.

pub fn insert<Q>( &mut self, q: &Q::QueryArg, data: B::Elem, ) -> (Cursor, SplittedLeaves)

where Q: Query<B>,

Insert new element to the tree.

Returns (insert_pos, splitted_leaves)

pub fn insert_by_path( &mut self, cursor: Cursor, data: B::Elem, ) -> (Cursor, SplittedLeaves)

pub fn insert_many_by_cursor( &mut self, cursor: Option<Cursor>, data_iter: impl Iterator<Item = B::Elem>, )

Insert many elements into the tree at once

It will invoke [BTreeTrait::insert_batch]

pub fn shift_path_by_one_offset(&self, path: Cursor) -> Option<Cursor>

where B::Elem: HasLength,

Shift by offset 1.

It will not stay on empty spans but scan forward

pub fn query<Q>(&self, query: &Q::QueryArg) -> Option<QueryResult>

where Q: Query<B>,

Query the tree by custom query type

Return None if the tree is empty

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

where Q: Query<B>,

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

pub fn get_elem(&self, leaf: LeafIndex) -> Option<&<B as BTreeTrait>::Elem>

pub fn remove_leaf(&mut self, path: Cursor) -> Option<B::Elem>

Remove leaf node from the tree

If it’s already removed, this method will return None

pub fn update<F>(&mut self, range: Range<Cursor>, f: &mut F) -> SplittedLeaves

where F: FnMut(&mut B::Elem) -> Option<B::CacheDiff>,

Update the elements in place.

If the range.start or range.end is in the middle of a leaf node, the leaf node will be splitted into two leaf nodes. The new leaf nodes will be returned.

F should returns Some(cache_diff) if cache needs to be updated. Otherwise, returns None.

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

pub fn prefer_right(&self, path: Cursor) -> Option<Cursor>

Prefer begin of the next leaf node than end of the current leaf node

When path.offset == leaf.rle_len(), this method will return the next leaf node with offset 0

pub fn prefer_left(&self, path: Cursor) -> Option<Cursor>

Prefer end of the previous leaf node than begin of the current leaf node

When path.offset == 0, this method will return the previous leaf node with offset leaf.rle_len()

pub fn update_leaf_by_search<Q: Query<B>>( &mut self, q: &Q::QueryArg, f: impl FnOnce(&mut B::Elem, QueryResult) -> Option<(B::CacheDiff, Option<B::Elem>, Option<B::Elem>)>, ) -> (Option<Cursor>, SplittedLeaves)

Update leaf node’s elements.

f returns Option<(cache_diff, new_insert_1, new_insert2)>

• If returned value is None, the cache will not be updated.
• If leaf_node.can_remove(), it will be removed from the tree.

Returns (path, splitted_leaves), if is is still valid after this method. (If the leaf node is removed, the path will be None)

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

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

f returns (is_cache_updated, cache_diff, new_insert_1, new_insert2)

• If leaf_node.can_remove(), it will be removed from the tree.

Returns true if the node_idx is still valid. (If the leaf node is removed, it will return false).

pub fn update_leaves_with_arg_in_ranges<A: Debug>( &mut self, args: Vec<(LeafIndex, Range<usize>, A)>, f: impl FnMut(&mut B::Elem, &A), ) -> Vec<LeafIndex>

Update the given leaves with the given function in the given range.

• The range descibes the range inside the leaf node.
• There can be multiple ranges in the same leaf node.
• The cahce will be recalculated for each affected node
• It doesn’t guarantee the applying order

Currently, the time complexity is O(m^2) for each leaf node, where m is the number of ranges inside the same leaf node. If we have a really large m, this function need to be optimized.

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

pub fn drain(&mut self, range: Range<QueryResult>) -> Drain<'_, B>

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

pub fn first_leaf(&self) -> Option<LeafIndex>

pub fn last_leaf(&self) -> Option<LeafIndex>

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

where Q: Query<B>,

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

pub fn start_cursor(&self) -> Option<Cursor>

pub fn end_cursor(&self) -> Option<Cursor>

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

pub fn get_leaf_mut(&mut self, index: ArenaIndex) -> &mut LeafNode<B::Elem>

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

Panic

If the given index is not valid or deleted

pub fn get_leaf(&self, index: ArenaIndex) -> &LeafNode<B::Elem>

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_elem(&self, path: Cursor) -> Option<Cursor>

find the next element in the tree

pub fn prev_elem(&self, path: Cursor) -> Option<Cursor>

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) -> Cursor

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

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

compare the position of a and b

pub fn visit_previous_caches<F>(&self, cursor: Cursor, f: F)

where F: FnMut(PreviousCache<'_, B>),

Iterate the caches of previous nodes/elements. This method will visit as less caches as possible. For example, if all nodes in a subtree need to be visited, we will only visit the root cache.

f: (node_cache, previous_sibling_elem, (this_elem, offset))

pub fn diagnose_balance(&self)

pub fn iter_with_filter<'a, R: Default + Copy + AddAssign + 'a>( &'a self, f: impl FnMut(&B::Cache) -> (bool, R) + 'a, ) -> impl Iterator<Item = (R, &B::Elem)> + '_

Iterate over the leaf elements in the tree if the filter returns true for all its ancestors’ caches, including its own cache.

pub fn update_cache_and_elem_with_filter<'a>( &'a mut self, f: impl FnMut(&mut B::Cache) -> bool + 'a, g: impl FnMut(&mut B::Elem) + 'a, )

This method allows users to update the caches and the elements with a filter.

If f returns true for a node, it will drill down into the subtree whose root is the node.

It’s the caller’s responsibility to ensure the invariance of caches being up to date.

pub fn depth(&self) -> usize

pub fn internal_avg_children_num(&self) -> f64

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 duplicate 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.

impl<B: BTreeTrait, T: Into<B::Elem>> FromIterator<T> for BTree<B>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.