Trait BTreeExtMut 

pub trait BTreeExtMut<K, V> {
    // Required methods
    fn set_len(&mut self, len: usize);
    fn set_root_id(&mut self, id: Option<usize>);
    fn node_mut(&mut self, id: usize) -> &mut Node<K, V>;
    fn get_mut_in(&mut self, key: &K, id: usize) -> Option<&mut V>
       where K: Ord;
    fn item_mut(&mut self, addr: Address) -> Option<&mut Item<K, V>>;
    fn insert_at(&mut self, addr: Address, item: Item<K, V>) -> Address;
    fn insert_exactly_at(
        &mut self,
        addr: Address,
        item: Item<K, V>,
        opt_right_id: Option<usize>,
    ) -> Address;
    fn replace_at(&mut self, addr: Address, key: K, value: V) -> (K, V);
    fn replace_value_at(&mut self, addr: Address, value: V) -> V;
    fn remove_at(&mut self, addr: Address) -> Option<(Item<K, V>, Address)>;
    fn rebalance(&mut self, node_id: usize, addr: Address) -> Address;
    fn update_in<T, F>(&mut self, id: usize, key: K, action: F) -> T
       where K: Ord,
             F: FnOnce(Option<V>) -> (Option<V>, T);
    fn update_at<T, F>(&mut self, addr: Address, action: F) -> T
       where K: Ord,
             F: FnOnce(V) -> (Option<V>, T);
    fn remove_rightmost_leaf_of(
        &mut self,
        node_id: usize,
    ) -> (Item<K, V>, usize);
    fn allocate_node(&mut self, node: Node<K, V>) -> usize;
    fn release_node(&mut self, id: usize) -> Node<K, V>;
}

Extended mutable API.

This trait can be imported to access and modify the internal functions of the B-Tree. These functions are not intended to be directly called by the users, but can be used to extends the data structure with new functionalities.

Correctness

The user of this trait is responsible to preserve the invariants of the data-structure. In particular, no item must be modified or inserted in a way that break the order between keys.

Required Methods

fn set_len(&mut self, len: usize)

Set the new known number of items in the tree.

fn set_root_id(&mut self, id: Option<usize>)

Set the root node identifier.

fn node_mut(&mut self, id: usize) -> &mut Node<K, V>

Get the node associated to the given id mutably.

Panics if id is out of bounds.

fn get_mut_in(&mut self, key: &K, id: usize) -> Option<&mut V>

where K: Ord,

Get a mutable reference to the value associated to the given key in the node id, if any.

fn item_mut(&mut self, addr: Address) -> Option<&mut Item<K, V>>

Get a mutable reference to the item located at the given address.

fn insert_at(&mut self, addr: Address, item: Item<K, V>) -> Address

Insert an item at the given address.

The address is first converted into a leaf address using BTreeExt::leaf_address and the item inserted using BTreeExtMut::insert_exactly_at.

fn insert_exactly_at( &mut self, addr: Address, item: Item<K, V>, opt_right_id: Option<usize>, ) -> Address

Insert an item at the given address.

If the address refers to an internal node, opt_right_id defines the identifier of the child node inserted on the right of the inserted item.

Returns the address of the inserted item in the tree (it may differ from the input address if the tree is rebalanced).

Correctness

It is assumed that it is btree-correct to insert the given item at the given address.

Panic

This function panics if the address refers to an internal node and opt_right_id is None.

fn replace_at(&mut self, addr: Address, key: K, value: V) -> (K, V)

Replaces the key-value binding at the given address.

fn replace_value_at(&mut self, addr: Address, value: V) -> V

Replaces the value at the given address.

fn remove_at(&mut self, addr: Address) -> Option<(Item<K, V>, Address)>

Removes the item at the given address, if any.

If an item is removed then this function returns a pair where the first hand side is the removed item, and the right hand side is the updated address where the item can be reinserted at.

fn rebalance(&mut self, node_id: usize, addr: Address) -> Address

Rebalance a node, if necessary.

fn update_in<T, F>(&mut self, id: usize, key: K, action: F) -> T

where K: Ord, F: FnOnce(Option<V>) -> (Option<V>, T),

Update a value in the given node node_id.

fn update_at<T, F>(&mut self, addr: Address, action: F) -> T

where K: Ord, F: FnOnce(V) -> (Option<V>, T),

Update a valud at the given address.

fn remove_rightmost_leaf_of(&mut self, node_id: usize) -> (Item<K, V>, usize)

Take the right-most leaf value in the given node.

Note that this does not change the registred length of the tree. The returned item is expected to be reinserted in the tree.

fn allocate_node(&mut self, node: Node<K, V>) -> usize

Allocate a free identifier for the given node.

fn release_node(&mut self, id: usize) -> Node<K, V>

Release the given node identifier and return the node it used to identify.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<K, V, C> BTreeExtMut<K, V> for BTreeMap<K, V, C>

where C: SimpleCollectionRef + SimpleCollectionMut + SlabMut<Node<K, V>>,