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>) -> CursorMut<A>
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.
fn entry<'a, Q: ?Sized + Ord>(&'a mut self, key: &Q) -> Entry<'a, A> where 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.
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.
fn iter(&self) -> Iter<A>
Gets an iterator over the objects in the RBTree, in ascending key
order.
fn drain<F>(&mut self, f: F) where F: FnMut(IntrusiveRef<A::Container>)
Calls the given function for each element in the RBTree before
removing it from the tree, in ascending key order.
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 + Sync[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