Struct AvlTree 

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

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 is_empty(&self) -> bool

pub fn len(&self) -> usize

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

where P::Target: Ord,

Adds a new node to the tree, requires P::Target has Ord.

(If you want more freedom of Ordering, see also Self::entry_with)

• Returns Ok(()) if the node was added, takes the ownership of P.
• Err(P) if an equivalent node already exists

pub fn remove_by_key<K>(&mut self, key: &K) -> Option<P>

where P::Target: Borrow<K>, K: Ord,

remove a node from the tree (need P::Target to impl Borrow)

pub fn remove(&mut self, node: &P)

where P::Target: Ord,

remove a node from the tree (useful if P is multiple ownership)

pub fn entry<'a, K>(&'a mut self, key: K) -> Entry<'a, P, Tag, K>

where P::Target: Borrow<K>, K: Ord,

Searches for an element in the tree with key, requires P::Target can borrow to K type, and have a total ordering by K.

pub fn entry_with<'a, K, F>( &'a mut self, key: K, cmp_f: F, ) -> Entry<'a, P, Tag, K>

where F: Fn(&K, &P::Target) -> Ordering,

Searches for an element in the tree with key and custom compare function.

pub fn get<'a, K>(&'a self, key: &K) -> Option<AvlNodeRef<'a, P>>

where P::Target: Borrow<K>, K: Ord,

pub fn get_with<'a, F>(&'a self, cmp_f: F) -> Option<AvlNodeRef<'a, P>>

where F: Fn(&P::Target) -> Ordering,

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

return a iterator to get the reference

NOTE: The iterator yield AvlNodeRef, so that you can clone the reference if it’s Arc

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

return a reversed iterator to get the reference.

NOTE: The iterator yield AvlNodeRef, so that you can clone the reference if it’s Arc

pub fn into_iter_rev(self) -> AvlIntoIter<P, Tag>

Into reversed order iterator that consume the items

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

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

pub fn first<'a>(&'a self) -> Option<AvlNodeRef<'a, P>>

pub fn last<'a>(&'a self) -> Option<AvlNodeRef<'a, P>>

pub fn first_entry<'a>(&'a mut self) -> Entry<'a, P, Tag, First>

Get the last entry

You can use Entry::prepend or Entry::prepend_unchecked on it to batch insert

pub fn last_entry<'a>(&'a mut self) -> Entry<'a, P, Tag, Last>

Get the last entry

You can use Entry::append or Entry::append_unchecked on it to batch insert

pub fn dump<F>(&self, print_cb: F)

where F: Fn(&P::Target, usize),

pub fn validate(&self)

where P::Target: Ord,

Trait Implementations

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

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

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

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

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

fn default() -> Self

Returns the “default value” for a type.

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.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<'a, P, Tag> IntoIterator for &'a AvlTree<P, Tag>

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

type Item = AvlNodeRef<'a, P>

The type of the elements being iterated over.

type IntoIter = AvlIter<'a, P, Tag>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

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

type Item = P

The type of the elements being iterated over.

type IntoIter = AvlIntoIter<P, Tag>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

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

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

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