Struct intrusive_collections::rbtree::RBTree
[−]
[src]
pub struct RBTree<A: for<'a> TreeAdaptor<'a>> { // some fields omitted }
An intrusive red-black tree.
Methods
impl<A: for<'a> TreeAdaptor<'a>> RBTree<A>[src]
fn new(adaptor: A) -> RBTree<A>
Creates an empty RBTree.
fn is_empty(&self) -> bool
Returns true if theRBTree` is empty.
fn cursor(&self) -> Cursor<A>
Returns a null Cursor for this tree.
fn cursor_mut(&mut self) -> CursorMut<A>
Returns a null CursorMut for this tree.
unsafe fn cursor_from_ptr(&self, ptr: *const A::Container) -> 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.
unsafe fn cursor_mut_from_ptr(&mut self, ptr: *const A::Container) -> 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.
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.
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.
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.
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.
fn find<'a, Q: ?Sized + Ord>(&'a self, key: &Q) -> Cursor<'a, A> where 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.
fn find_mut<'a, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> CursorMut<'a, A> where 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.
fn lower_bound<'a, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A> where 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.
fn lower_bound_mut<'a, Q: ?Sized + Ord>(&'a mut self, bound: Bound<&Q>) -> CursorMut<'a, A> where 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.
fn upper_bound<'a, Q: ?Sized + Ord>(&'a self, bound: Bound<&Q>) -> Cursor<'a, A> where 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.
fn upper_bound_mut<'a, Q: ?Sized + Ord>(&'a mut self, bound: Bound<&Q>) -> CursorMut<'a, A> where 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.
fn insert(&mut self, val: IntrusiveRef<A::Container>)
Inserts a new element into the RBTree.
The new element will be inserted at the correct position in the tree based on its key.
Panics
Panics if the new element is already linked to a different intrusive collection.
fn range<'a, Min: ?Sized + Ord, Max: ?Sized + Ord>(&'a self, min: Bound<&Min>, max: Bound<&Max>) -> Iter<'a, A> where A::Key: Borrow<Min> + Borrow<Max>
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.
unsafe fn range_mut<'a, Min: ?Sized + Ord, Max: ?Sized + Ord>(&'a mut self, min: Bound<&Min>, max: Bound<&Max>) -> IterMut<'a, A> where A::Key: Borrow<Min> + Borrow<Max>
Constructs a double-ended mutable 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_mut(Unbounded, Unbounded) will yield the whole collection.
Safety
This iterator yields &mut references to objects in the RBTree
but makes no guarantee that these references are not aliased. You must
ensure that there are no live references (mutable or immutable) to any
object in the RBTree while the iterator is in use.
fn iter(&self) -> Iter<A>
Gets an iterator over the objects in the RBTree.
unsafe fn iter_mut(&mut self) -> IterMut<A>
Gets a mutable iterator over the objects in the RBTree.
Safety
This iterator yields &mut references to objects in the RBTree
but makes no guarantee that these references are not aliased. You must
ensure that there are no live references (mutable or immutable) to any
object in the RBTree while the iterator is in use.
fn drain<F>(&mut self, f: F) where F: FnMut(IntrusiveRef<A::Container>)
Calls the given function for each element in the RBTree and
removes it from the tree.
This will unlink all objects currently in the tree.
If the given function panics then all elements in the RBTree will
still be unlinked, but the function will not be called for any elements
after the one that panicked.
fn clear(&mut self)
Removes all elements from the RBTree.
This will unlink all object currently in the tree.
fn fast_clear(&mut self)
Empties the RBTree without unlinking 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
unsafe_unlink function on them.
This is the only function that can be safely called after an object has
been moved or dropped while still being linked into this RBTree.
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.
Trait Implementations
impl<A: for<'a> TreeAdaptor<'a> + Sync> Sync for RBTree<A> where A::Container: Sync[src]
impl<A: for<'a> TreeAdaptor<'a> + Send> Send for RBTree<A> where A::Container: Send[src]
impl<'a, A: for<'b> TreeAdaptor<'b> + 'a> IntoIterator for &'a RBTree<A>[src]
type Item = &'a A::Container
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. Read more