Struct AvlTree 

pub struct AvlTree<P, Tag>
where
    P: Pointer,
    P::Target: AvlItem<Tag>,
{
    pub root: *const P::Target,
    /* 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.

Fields

root: *const P::Target

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 get_count(&self) -> i64

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

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

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;
use std::sync::Arc;

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

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

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

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.

pub fn remove_by_key<K>( &mut self, val: &K, cmp_func: AvlCmpFunc<K, P::Target>, ) -> 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, K>( &'a self, val: &K, cmp_func: AvlCmpFunc<K, P::Target>, ) -> AvlSearchResult<'a, P>

Searches for an element in the tree.

The cmp_func should compare the key K with the elements 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, K>( &'a self, val: &K, cmp_func: AvlCmpFunc<K, P::Target>, ) -> Option<&'a P::Target>

pub fn find_larger_eq<'a, K>( &'a self, val: &K, cmp_func: AvlCmpFunc<K, P::Target>, ) -> AvlSearchResult<'a, P>

pub fn find_nearest<'a, K>( &'a self, val: &K, cmp_func: AvlCmpFunc<K, P::Target>, ) -> AvlSearchResult<'a, P>

For range tree

pub fn walk<F: Fn(&P::Target)>(&self, cb: F)

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 nearest<'a>( &'a self, current: &AvlSearchResult<'a, P>, direction: AvlDirection, ) -> AvlSearchResult<'a, P>

pub fn validate(&self, cmp_func: AvlCmpFunc<P::Target, P::Target>)

pub fn add( &mut self, node: P, cmp_func: AvlCmpFunc<P::Target, P::Target>, ) -> 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).

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.