Struct Internal 

pub struct Internal<T, S: Storage<T>> { /* private fields */ }

Internal node.

An internal node is a node where each item is surrounded by edges to child nodes.

Implementations

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

pub fn new( parent: Option<S::Node>, first_child: S::Node, other_children: Array<Branch<T, S>, M>, ) -> Self

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

Creates a binary node (with a single item and two children).

pub fn forget(&mut self)

Forget the node content, without running the items destructors.

The node’s children must be manually dropped.

pub fn balance(&self) -> Balance

Returns the current balance of the node.

pub fn is_overflowing(&self) -> bool

pub fn is_underflowing(&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 first_child_id(&self) -> S::Node

pub fn branches(&self) -> &[Branch<T, S>]

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 separators(&self, index: usize) -> (Option<&T>, Option<&T>)

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

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

pub fn offset_of<Q: ?Sized>( &self, cmp: impl Fn(&T, &Q) -> Ordering, key: &Q, ) -> Result<Offset, (usize, 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.

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

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

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, T), InsertionError<T, S>>

Insert by key.

pub fn insert(&mut self, offset: Offset, item: T, right_node_id: S::Node)

Insert item at the given offset.

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

Replace the item at the given offset.

pub fn remove(&mut self, offset: Offset) -> (S::Node, T, S::Node)

Remove the item at the given offset. Return the child id on the left of the item, the item, and the child id on the right (which is also removed).

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

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

Merge the children at the given indexes.

It is supposed that left_index is right_index-1. This method returns the identifier of the left node in the tree, the identifier of the right node, the item removed from this node to be merged with the merged children and the balance status of this node after the merging operation.

pub fn push_left(&mut self, item: T, child_id: S::Node)

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

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

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

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

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