pub struct SplayTree<'a, T>where
T: IntrusiveNode<'a>,
T::Elem: 'a,{ /* private fields */ }
Expand description
An intrusive splay tree.
The tree is parameterized by some marker type T
whose IntrusiveNode
implementation defines:
- the element type contained in this tree:
T::Elem
, - how to get the intrusive node for this tree within an element,
- and how to get the container element from a given intrusive node for this tree.
Implementations§
Source§impl<'a, T> SplayTree<'a, T>where
T: 'a + IntrusiveNode<'a>,
impl<'a, T> SplayTree<'a, T>where
T: 'a + IntrusiveNode<'a>,
Sourcepub fn find<K>(&mut self, key: &K) -> Option<&'a T::Elem>
pub fn find<K>(&mut self, key: &K) -> Option<&'a T::Elem>
Find an element in the tree.
This operation will splay the queried element to the root of the tree.
The key
must be of a type that implements TreeOrd
for this tree’s
T
type. The element type T::Elem
must always implement TreeOrd<T>
,
so you can search the tree by element. You can also implement
TreeOrd<T>
for additional key types. This allows you to search the
tree without constructing a full element.
Sourcepub fn insert(&mut self, elem: &'a T::Elem) -> bool
pub fn insert(&mut self, elem: &'a T::Elem) -> bool
Insert a new element into this tree.
Returns true
if the element was inserted into the tree.
Returns false
if there was already an element in the tree for which
TreeOrd
returned Ordering::Equal
. In this case, the extant element
is left in the tree, and elem
is not inserted.
This operation will splay the inserted element to the root of the tree.
It is a logic error to insert an element that is already inserted in a
T
tree.
§Panics
If debug_assertions
are enabled, then this function may panic if
elem
is already in a T
tree. If debug_assertions
are not defined,
the behavior is safe, but unspecified.
Sourcepub fn remove<K>(&mut self, key: &K) -> Option<&'a T::Elem>
pub fn remove<K>(&mut self, key: &K) -> Option<&'a T::Elem>
Find and remove an element from the tree.
If a matching element is found and removed, then Some(removed_element)
is returned. Otherwise None
is returned.
The key
must be of a type that implements TreeOrd
for this tree’s
T
type. The element type T::Elem
must always implement TreeOrd<T>
,
so you can remove an element directly. You can also implement
TreeOrd<T>
for additional key types. This allows you to search the
tree without constructing a full element, and remove the element that
matches the given key, if any.
Sourcepub fn pop_root(&mut self) -> Option<&'a T::Elem>
pub fn pop_root(&mut self) -> Option<&'a T::Elem>
Pop the root element from the tree.
If the tree has a root, it is removed and Some(root)
is
returned. Otherwise, None
is returned.
Sourcepub fn min(&mut self) -> Option<&'a T::Elem>
pub fn min(&mut self) -> Option<&'a T::Elem>
Get the minimum element in the tree.
If the tree is non-empty, then the minimum element is splayed to the
root and Some(min_elem)
is returned. Otherwise, None
is returned.
Sourcepub fn pop_min(&mut self) -> Option<&'a T::Elem>
pub fn pop_min(&mut self) -> Option<&'a T::Elem>
Pop the minimum element from the tree.
If the tree is non-empty, then the minimum element is removed and
Some(_)
is returned. Otherwise, None
is returned.
Sourcepub fn max(&mut self) -> Option<&'a T::Elem>
pub fn max(&mut self) -> Option<&'a T::Elem>
Get the maximum element in the tree.
If the tree is non-empty, then the maximum element is splayed to the
root and Some(max_elem)
is returned. Otherwise, None
is returned.
Sourcepub fn pop_max(&mut self) -> Option<&'a T::Elem>
pub fn pop_max(&mut self) -> Option<&'a T::Elem>
Pop the maximum element from the tree.
If the tree is non-empty, then the maximum element is removed and
Some(_)
is returned. Otherwise, None
is returned.
Sourcepub fn walk<F, C>(&self, f: F) -> Option<C::Result>
pub fn walk<F, C>(&self, f: F) -> Option<C::Result>
Walk the tree in order.
The C
type controls whether iteration should continue, or break and
return a C::Result
value. You can use ()
as C
, and that always
continues iteration. Using Result<(), E>
as C
allows you to halt
iteration on error, and propagate the error value. Using Option<T>
as
C
allows you to search for some value, halt iteration when its found,
and return it.
Trait Implementations§
Source§impl<'a, T> Extend<&'a <T as IntrusiveNode<'a>>::Elem> for SplayTree<'a, T>where
T: 'a + IntrusiveNode<'a>,
impl<'a, T> Extend<&'a <T as IntrusiveNode<'a>>::Elem> for SplayTree<'a, T>where
T: 'a + IntrusiveNode<'a>,
Source§fn extend<I: IntoIterator<Item = &'a T::Elem>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = &'a T::Elem>>(&mut self, iter: I)
Source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)