Struct intrusive_collections::rbtree::RBTree

pub struct RBTree<A: Adapter<Link = Link>> { /* private fields */ }

An intrusive red-black tree.

When this collection is dropped, all elements linked into it will be converted back to owned pointers and dropped.

Note that you are responsible for ensuring that the elements in a RBTree remain in ascending key order. This property can be violated, either because the key of an element was modified, or because the insert_before/insert_after methods of CursorMut were incorrectly used. If this situation occurs, memory safety will not be violated but the find, upper_bound, lower_bound and range may return incorrect results.

Implementations

impl<A: Adapter<Link = Link>> RBTree<A>

pub fn new(adapter: A) -> RBTree<A>

Creates an empty RBTree.

pub fn is_empty(&self) -> bool

Returns true if the RBTree is empty.

pub fn cursor(&self) -> Cursor<'_, A>

Returns a null Cursor for this tree.

pub fn cursor_mut(&mut self) -> CursorMut<'_, A>

Returns a null CursorMut for this tree.

pub unsafe fn cursor_from_ptr(&self, ptr: *const A::Value) -> Cursor<'_, A>

Creates a Cursor from a pointer to an element.

Safety

ptr must be a pointer to an object that is part of this tree.

pub unsafe fn cursor_mut_from_ptr(
    &mut self,
    ptr: *const A::Value
) -> CursorMut<'_, A>

Creates a CursorMut from a pointer to an element.

Safety

ptr must be a pointer to an object that is part of this tree.

pub fn front(&self) -> Cursor<'_, A>

Returns a Cursor pointing to the first element of the tree. If the tree is empty then a null cursor is returned.

pub fn front_mut(&mut self) -> CursorMut<'_, A>

Returns a CursorMut pointing to the first element of the tree. If the the tree is empty then a null cursor is returned.

pub fn back(&self) -> Cursor<'_, A>

Returns a Cursor pointing to the last element of the tree. If the tree is empty then a null cursor is returned.

pub fn back_mut(&mut self) -> CursorMut<'_, A>

Returns a CursorMut pointing to the last element of the tree. If the tree is empty then a null cursor is returned.

pub fn iter(&self) -> Iter<'_, A>

Gets an iterator over the objects in the RBTree, in ascending key order.

pub fn clear(&mut self)

Removes all elements from the RBTree.

This will unlink all object currently in the tree, which requires iterating through all elements in the RBTree. Each element is converted back to an owned pointer and then dropped.

pub fn fast_clear(&mut self)

Empties the RBTree without unlinking or freeing objects in it.

Since this does not unlink any objects, any attempts to link these objects into another RBTree will fail but will not cause any memory unsafety. To unlink those objects manually, you must call the force_unlink function on them.

pub fn take(&mut self) -> RBTree<A>where
    A: Clone,

Takes all the elements out of the RBTree, leaving it empty. The taken elements are returned as a new RBTree.

impl<A: for<'a> KeyAdapter<'a, Link = Link>> RBTree<A>

pub fn find<'a, Q: ?Sized + Ord>(&'a self, key: &Q) -> Cursor<'a, A>where
    <A as KeyAdapter<'a>>::Key: Borrow<Q>,

Returns a Cursor pointing to an element with the given key. If no such element is found then a null cursor is returned.

If multiple elements with an identical key are found then an arbitrary one is returned.

pub fn find_mut<'a, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> CursorMut<'a, A>where
    <A as KeyAdapter<'a>>::Key: Borrow<Q>,

Returns a CursorMut pointing to an element with the given key. If no such element is found then a null cursor is returned.

If multiple elements with an identical key are found then an arbitrary one is returned.

pub fn lower_bound<'a, Q: ?Sized + Ord>(
    &'a self,
    bound: Bound<&Q>
) -> Cursor<'a, A>where
    <A as KeyAdapter<'a>>::Key: Borrow<Q>,

Returns a Cursor pointing to the lowest element whose key is above the given bound. If no such element is found then a null cursor is returned.

pub fn lower_bound_mut<'a, Q: ?Sized + Ord>(
    &'a mut self,
    bound: Bound<&Q>
) -> CursorMut<'a, A>where
    <A as KeyAdapter<'a>>::Key: Borrow<Q>,

Returns a CursorMut pointing to the first element whose key is above the given bound. If no such element is found then a null cursor is returned.

pub fn upper_bound<'a, Q: ?Sized + Ord>(
    &'a self,
    bound: Bound<&Q>
) -> Cursor<'a, A>where
    <A as KeyAdapter<'a>>::Key: Borrow<Q>,

Returns a Cursor pointing to the last element whose key is below the given bound. If no such element is found then a null cursor is returned.

pub fn upper_bound_mut<'a, Q: ?Sized + Ord>(
    &'a mut self,
    bound: Bound<&Q>
) -> CursorMut<'a, A>where
    <A as KeyAdapter<'a>>::Key: Borrow<Q>,

Returns a CursorMut pointing to the last element whose key is below the given bound. If no such element is found then a null cursor is returned.

pub fn insert<'a>(&'a mut self, val: A::Pointer) -> CursorMut<'_, A>where
    <A as KeyAdapter<'a>>::Key: Ord,

Inserts a new element into the RBTree.

The new element will be inserted at the correct position in the tree based on its key.

Returns a mutable cursor pointing to the newly added element.

Panics

Panics if the new element is already linked to a different intrusive collection.

pub fn entry<'a, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> Entry<'a, A>where
    <A as KeyAdapter<'a>>::Key: Borrow<Q>,

Returns an Entry for the given key which contains a CursorMut to an element with the given key or an InsertCursor which points to a place in which to insert a new element with the given key.

This is more efficient than calling find followed by insert since the tree does not have to be searched a second time to find a place to insert the new element.

If multiple elements with an identical key are found then an arbitrary one is returned.

pub fn range<'a, Min: ?Sized + Ord, Max: ?Sized + Ord>(
    &'a self,
    min: Bound<&Min>,
    max: Bound<&Max>
) -> Iter<'a, A>where
    <A as KeyAdapter<'a>>::Key: Borrow<Min> + Borrow<Max>,
    <A as KeyAdapter<'a>>::Key: Ord,

Constructs a double-ended iterator over a sub-range of elements in the tree, starting at min, and ending at max. If min is Unbounded, then it will be treated as “negative infinity”, and if max is Unbounded, then it will be treated as “positive infinity”. Thus range(Unbounded, Unbounded) will yield the whole collection.

Trait Implementations

impl<A: Adapter<Link = Link>> Debug for RBTree<A>where
    A::Value: Debug,

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

Formats the value using the given formatter.

impl<A: Adapter<Link = Link> + Default> Default for RBTree<A>

fn default() -> RBTree<A>

Returns the “default value” for a type.

impl<A: Adapter<Link = Link>> Drop for RBTree<A>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, A: Adapter<Link = Link> + 'a> IntoIterator for &'a RBTree<A>

type Item = &'a <A as Adapter>::Value

The type of the elements being iterated over.

type IntoIter = Iter<'a, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, A>

Creates an iterator from a value.

impl<A: Adapter<Link = Link>> IntoIterator for RBTree<A>

type Item = <A as Adapter>::Pointer

The type of the elements being iterated over.

type IntoIter = IntoIter<A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<A>

Creates an iterator from a value.

impl<A: Adapter<Link = Link> + Send> Send for RBTree<A>where
    A::Pointer: Send,

impl<A: Adapter<Link = Link> + Sync> Sync for RBTree<A>where
    A::Value: Sync,