Enum Node 

pub enum Node<T, S: Storage<T>> {
    Internal(InternalNode<T, S>),
    Leaf(LeafNode<T, S>),
}

B-tree node.

Variants

Internal(InternalNode<T, S>)

Internal node.

Leaf(LeafNode<T, S>)

Leaf node.

Implementations

impl<T, S: Storage<T>> Node<T, S>

pub fn binary( parent: Option<S::Node>, left_id: S::Node, median: T, right_id: S::Node, ) -> Self

pub fn leaf(parent: Option<S::Node>, item: T) -> Self

pub fn balance(&self) -> Balance

pub fn is_underflowing(&self) -> bool

pub fn is_overflowing(&self) -> bool

pub fn parent(&self) -> Option<S::Node>

pub fn set_parent(&mut self, p: Option<S::Node>)

pub fn item_count(&self) -> usize

pub fn child_count(&self) -> usize

pub fn child_index(&self, id: S::Node) -> Option<usize>

pub fn child_id(&self, index: usize) -> S::Node

pub fn child_id_opt(&self, index: usize) -> Option<S::Node>

pub fn get<Q: ?Sized>( &self, cmp: impl Fn(&T, &Q) -> Ordering, key: &Q, ) -> Result<Option<&T>, S::Node>

pub fn get_mut<Q: ?Sized>( &mut self, cmp: impl Fn(&T, &Q) -> Ordering, key: &Q, ) -> Result<Option<&mut T>, &mut S::Node>

Return the value associated to the given key, if any.

Return Err if thi key might be located in the returned child node.

pub fn offset_of<Q: ?Sized>( &self, cmp: impl Fn(&T, &Q) -> Ordering, key: &Q, ) -> Result<Offset, (usize, Option<S::Node>)>

Find the offset of the item matching the given key.

If the key matches no item in this node, this funtion returns the index and id of the child that may match the key, or Err(None) if it is a leaf.

pub fn item(&self, offset: Offset) -> Option<&T>

pub fn item_mut(&mut self, offset: Offset) -> Option<&mut T>

pub fn insert_by_key( &mut self, cmp: impl Fn(&T, &T) -> Ordering, item: T, ) -> Result<(Offset, Option<T>), InsertionError<T, S>>

Insert by key.

It is assumed that the node is not free. If it is a leaf node, there must be a free space in it for the inserted value.

pub fn split(&mut self) -> (usize, T, Node<T, S>)

Split the node. Return the length of the node after split, the median item and the right node.

pub fn merge( &mut self, left_index: usize, ) -> (usize, S::Node, S::Node, T, Balance)

pub fn append(&mut self, separator: T, other: Node<T, S>) -> Offset

Return the offset of the separator.

pub fn push_left(&mut self, item: T, opt_child_id: Option<S::Node>)

pub fn pop_left(&mut self) -> Result<LeftItem<T, S>, WouldUnderflow>

pub fn push_right(&mut self, item: T, opt_child_id: Option<S::Node>) -> Offset

pub fn pop_right(&mut self) -> Result<RightItem<T, S>, WouldUnderflow>

pub fn leaf_remove(&mut self, offset: Offset) -> Option<Result<T, S::Node>>

pub fn remove_rightmost_leaf(&mut self) -> Result<T, S::Node>

pub fn insert( &mut self, offset: Offset, item: T, opt_right_child_id: Option<S::Node>, )

Put an item in a node.

It is assumed that the node will not overflow.

pub fn replace(&mut self, offset: Offset, item: T) -> T

pub fn separators(&self, i: usize) -> (Option<&T>, Option<&T>)

pub fn children(&self) -> Children<'_, T, S>

pub fn children_with_separators(&self) -> ChildrenWithSeparators<'_, T, S>

pub fn visit_from_leaves(&self, nodes: &S, f: impl FnMut(S::Node))

pub fn visit_from_leaves_with(&self, nodes: &S, f: &mut impl FnMut(S::Node))

pub fn visit_from_leaves_mut( &self, nodes: &mut S, f: impl FnMut(S::Node, &mut Self), )

pub fn visit_from_leaves_mut_with( &self, nodes: &mut S, f: &mut impl FnMut(S::Node, &mut Self), )

pub fn forget(&mut self)

Forget the node content, without running the items destructors.

The node’s children must be manually dropped.

pub fn validate( &self, cmp: impl Fn(&T, &T) -> Ordering, parent: Option<S::Node>, min: Option<&T>, max: Option<&T>, )