Struct AvlTree 

pub struct AvlTree<P, Tag>
where
    P: Pointer,
    P::Target: AvlItem<Tag>,
{ /* private fields */ }

Available on crate feature avl only.

An intrusive AVL tree (balanced binary search tree).

Elements in the tree must implement the AvlItem trait. The tree supports various pointer types (Box, Arc, Rc, etc.) through the Pointer trait.

Implementations

impl<P, Tag> AvlTree<P, Tag>

where P: Pointer, P::Target: AvlItem<Tag>,

pub fn new() -> Self

Creates a new, empty AvlTree.

pub fn drain(&mut self) -> AvlDrain<'_, P, Tag>

Returns an iterator that removes all elements from the tree in post-order.

This is an optimized, non-recursive, and stack-less traversal that preserves tree invariants during destruction.

pub fn is_empty(&self) -> bool

pub fn len(&self) -> usize

pub fn add(&mut self, node: P) -> bool

Adds a new element to the tree， takes the ownership of P.

The cmp_func should compare two elements to determine their relative order. Returns true if the element was added, false if an equivalent element already exists (in which case the provided node is dropped).

pub fn insert(&mut self, new_data: P, w: AvlSearchResult<'_, P>)

Inserts a new node into the tree at the location specified by a search result.

This is typically used after a find operation didn’t find an exact match.

Safety

Once the tree structure changed, previous search result is not safe to use anymore.

You should detach() the result before calling insert, to avoid the borrowing issue.

Panics

Panics if the search result is an exact match (i.e. node already exists).

Examples

use embed_collections::avl::{AvlTree, AvlItem, AvlNode};
use core::cell::UnsafeCell;
extern crate alloc;
use alloc::sync::Arc;

struct MyNode {
    value: i32,
    avl_node: UnsafeCell<AvlNode<MyNode, ()>>,
}

unsafe impl AvlItem<()> for MyNode {
    type Key = i32;

    fn get_node(&self) -> &mut AvlNode<MyNode, ()> {
        unsafe { &mut *self.avl_node.get() }
    }

    fn borrow_key(&self) -> &Self::Key {
        &self.value
    }
}

let mut tree = AvlTree::<Arc<MyNode>, ()>::new();
let key = 42;
let result = tree.find(&key);

if !result.is_exact() {
    let new_node = Arc::new(MyNode {
        value: key,
        avl_node: UnsafeCell::new(Default::default()),
    });
    tree.insert(new_node, unsafe{result.detach()});
}

pub fn _insert( &mut self, new_data: P, here: *const P::Target, which_child: AvlDirection, )

pub unsafe fn insert_here( &mut self, new_data: P, here: AvlSearchResult<'_, P>, direction: AvlDirection, )

Insert “new_data” in “tree” in the given “direction” either after or before AvlDirection::After, AvlDirection::Before) the data “here”.

Insertions can only be done at empty leaf points in the tree, therefore if the given child of the node is already present we move to either the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since every other node in the tree is a leaf, this always works.

Safety

Once the tree structure changed, previous search result is not safe to use anymore.

You should detach() the result before calling insert, to avoid the borrowing issue.

pub unsafe fn remove(&mut self, del: *const P::Target)

Requires del to be a valid pointer to a node in this tree.

Safety

It does not drop the node data, only unlinks it. Caller is responsible for re-taking ownership (e.g. via from_raw) and dropping if needed.

For Arc/Rc, use Self::remove_ref() instead.

pub fn remove_by_key( &mut self, val: &<P::Target as AvlItem<Tag>>::Key, ) -> Option<P>

Removes a node from the tree by key.

The cmp_func should compare the key K with the elements in the tree. Returns Some(P) if an exact match was found and removed, None otherwise.

pub fn remove_with(&mut self, result: AvlSearchResult<'_, P>) -> Option<P>

remove with a previous search result

• If the result is exact match, return the removed element ownership
• If the result is not exact match, return None

Safety

Once the tree structure changed, previous search result is not safe to use anymore.

You should detach() the result before calling insert, to avoid the borrowing issue.

pub fn find<'a>( &'a self, val: &<P::Target as AvlItem<Tag>>::Key, ) -> AvlSearchResult<'a, P>

Searches for an element in the tree.

Returns an AvlSearchResult which indicates if an exact match was found, or where a new element should be inserted.

pub fn find_contained<'a>( &'a self, val: &<P::Target as AvlItem<Tag>>::Key, ) -> Option<&'a P::Target>

pub fn find_larger_eq<'a>( &'a self, val: &<P::Target as AvlItem<Tag>>::Key, ) -> AvlSearchResult<'a, P>

pub fn find_nearest<'a, K>( &'a self, val: &<P::Target as AvlItem<Tag>>::Key, ) -> AvlSearchResult<'a, P>

For range tree

pub fn iter(&self) -> AvlIter<'_, P, Tag>

return a iterator to get the reference

NOTE: If you use the Iterator interface (for iteration), you only get &P::Target.

you can use AvlIter::next_ref() to get &P.

pub fn iter_rev(&self) -> AvlIter<'_, P, Tag>

return a reversed iterator to get the reference.

NOTE: If you use the Iterator interface (for iteration), you only get &P::Target.

you can use AvlIter::next_ref() to get &P.

pub fn next<'a>(&'a self, data: &'a P::Target) -> Option<&'a P::Target>

pub fn prev<'a>(&'a self, data: &'a P::Target) -> Option<&'a P::Target>

pub fn first(&self) -> Option<&P::Target>

pub fn last(&self) -> Option<&P::Target>

pub fn nearest<'a>( &'a self, current: &AvlSearchResult<'a, P>, direction: AvlDirection, ) -> AvlSearchResult<'a, P>

pub fn validate(&self)

impl<T, Tag> AvlTree<Arc<T>, Tag>

where T: AvlItem<Tag>,

pub fn remove_ref(&mut self, node: &Arc<T>)

impl<T, Tag> AvlTree<Rc<T>, Tag>

where T: AvlItem<Tag>,

pub fn remove_ref(&mut self, node: &Rc<T>)

Trait Implementations

impl<P, Tag> Drop for AvlTree<P, Tag>

where P: Pointer, P::Target: AvlItem<Tag>,

fn drop(&mut self)

Executes the destructor for this type.

impl<P, Tag> Send for AvlTree<P, Tag>

where P: Pointer + Send, P::Target: AvlItem<Tag>,