Struct intrusive_collections::rbtree::RBTree
[−]
[src]
pub struct RBTree<A: Adapter<Link=Link>> { /* fields omitted */ }
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.
Methods
impl<A: Adapter<Link=Link>> RBTree<A>
[src]
fn new(adapter: A) -> RBTree<A>
Creates an empty RBTree
.
fn is_empty(&self) -> bool
Returns true if the
RBTree` 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::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.
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.
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 iter(&self) -> Iter<A>
Gets an iterator over the objects in the RBTree
, in ascending key
order.
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.
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.
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>
[src]
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>
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>
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<'a>(&'a mut self, val: A::Pointer) -> CursorMut<A> where 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.
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>, A::Key: Ord
min: Bound<&Min>,
max: Bound<&Max>)
-> Iter<'a, A> where A::Key: Borrow<Min> + Borrow<Max>, 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> + Sync> Sync for RBTree<A> where A::Value: Sync
[src]
impl<A: Adapter<Link=Link> + Send> Send for RBTree<A> where A::Pointer: Send
[src]
impl<A: Adapter<Link=Link>> Drop for RBTree<A>
[src]
impl<A: Adapter<Link=Link>> IntoIterator for RBTree<A>
[src]
type Item = A::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. Read more
impl<'a, A: Adapter<Link=Link> + 'a> IntoIterator for &'a RBTree<A>
[src]
type Item = &'a A::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. Read more