[−][src]Struct intrusive_collections::rbtree::RBTree
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]
pub fn new(adapter: A) -> RBTree<A>
[src]
Creates an empty RBTree
.
pub fn is_empty(&self) -> bool
[src]
Returns true
if the RBTree
is empty.
pub fn cursor(&self) -> Cursor<A>
[src]
Returns a null Cursor
for this tree.
pub fn cursor_mut(&mut self) -> CursorMut<A>
[src]
Returns a null CursorMut
for this tree.
pub unsafe fn cursor_from_ptr(&self, ptr: *const A::Value) -> Cursor<A>
[src]
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>
[src]
&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>
[src]
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>
[src]
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>
[src]
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>
[src]
Returns a CursorMut
pointing to the last element of the tree. If the
tree is empty then a null cursor is returned.
ⓘImportant traits for Iter<'a, A>pub fn iter(&self) -> Iter<A>
[src]
Gets an iterator over the objects in the RBTree
, in ascending key
order.
pub fn clear(&mut self)
[src]
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)
[src]
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,
[src]
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]
pub fn find<'a, Q: ?Sized + Ord>(&'a self, key: &Q) -> Cursor<'a, A> where
<A as KeyAdapter<'a>>::Key: Borrow<Q>,
[src]
<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>,
[src]
<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>,
[src]
&'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>,
[src]
&'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>,
[src]
&'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>,
[src]
&'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,
[src]
<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>,
[src]
<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.
ⓘImportant traits for Iter<'a, A>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,
[src]
&'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,
[src]
A::Value: Debug,
impl<A: Adapter<Link = Link>> Drop for RBTree<A>
[src]
impl<A: Adapter<Link = Link> + Send> Send for RBTree<A> where
A::Pointer: Send,
[src]
A::Pointer: Send,
impl<A: Adapter<Link = Link> + Sync> Sync for RBTree<A> where
A::Value: Sync,
[src]
A::Value: Sync,
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?
ⓘImportant traits for IntoIter<A>fn into_iter(self) -> IntoIter<A>
[src]
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?
ⓘImportant traits for Iter<'a, A>fn into_iter(self) -> Iter<'a, A>
[src]
impl<A: Adapter<Link = Link> + Default> Default for RBTree<A>
[src]
Auto Trait Implementations
impl<A> Unpin for RBTree<A> where
A: Unpin,
A: Unpin,
impl<A> !UnwindSafe for RBTree<A>
impl<A> !RefUnwindSafe for RBTree<A>
Blanket Implementations
impl<T> From<T> for T
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = !
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<I> IntoIterator for I where
I: Iterator,
[src]
I: Iterator,
type Item = <I as Iterator>::Item
The type of the elements being iterated over.
type IntoIter = I
Which kind of iterator are we turning this into?
fn into_iter(self) -> I
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,