Struct SplayTree

Source
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>,

Source

pub const fn new() -> Self

Construct a new, empty tree.

Source

pub fn is_empty(&self) -> bool

Is this tree empty?

Source

pub fn root(&self) -> Option<&'a T::Elem>

Get a reference to the root element, if any exists.

Source

pub fn find<K>(&mut self, key: &K) -> Option<&'a T::Elem>
where K: ?Sized + TreeOrd<'a, T>,

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.

Source

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.

Source

pub fn remove<K>(&mut self, key: &K) -> Option<&'a T::Elem>
where K: ?Sized + TreeOrd<'a, T>,

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

pub fn walk<F, C>(&self, f: F) -> Option<C::Result>
where F: FnMut(&'a T::Elem) -> C, C: WalkControl,

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> Debug for SplayTree<'a, T>
where T: 'a + IntrusiveNode<'a>, T::Elem: 'a + Debug,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<'a, T> Default for SplayTree<'a, T>
where T: 'a + IntrusiveNode<'a>, T::Elem: 'a,

Source§

fn default() -> SplayTree<'a, T>

Returns the “default value” for a type. Read more
Source§

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)

Extends a collection with the contents of an iterator. Read more
Source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
Source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)
Reserves capacity in a collection for the given number of additional elements. Read more
Source§

impl<'a, T> FromIterator<&'a <T as IntrusiveNode<'a>>::Elem> for SplayTree<'a, T>
where T: 'a + IntrusiveNode<'a>, T::Elem: Debug,

Source§

fn from_iter<I: IntoIterator<Item = &'a T::Elem>>(iter: I) -> Self

Creates a value from an iterator. Read more

Auto Trait Implementations§

§

impl<'a, T> Freeze for SplayTree<'a, T>

§

impl<'a, T> !RefUnwindSafe for SplayTree<'a, T>

§

impl<'a, T> !Send for SplayTree<'a, T>

§

impl<'a, T> !Sync for SplayTree<'a, T>

§

impl<'a, T> Unpin for SplayTree<'a, T>

§

impl<'a, T> !UnwindSafe for SplayTree<'a, T>

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.