Struct WavlTree 

pub struct WavlTree<K, P, Tag = DefaultObjectTag, S = NonTrackingSize, O = DefaultWavlTreeObserver<<P as PtrTraits>::Target>>
where
    P: PtrTraits,
    P::Target: WavlTreeContainable<P::Target, Tag> + WavlTreeKeyable<K>,
    K: Ord,
    S: SizeTracker,
    O: WavlTreeObserver<Target = P::Target>,
{ /* private fields */ }

Implementations

impl<K, P, Tag, S, O> WavlTree<K, P, Tag, S, O>

where P: PtrTraits, P::Target: WavlTreeContainable<P::Target, Tag> + WavlTreeKeyable<K>, K: Ord, S: SizeTracker, O: WavlTreeObserver<Target = P::Target>,

pub fn project<'__pin>( self: Pin<&'__pin mut Self>, ) -> WavlTreeProjection<'__pin, K, P, Tag, S, O>

Pin-projects all fields of Self.

These fields are structurally pinned:

• _pin

These fields are not structurally pinned:

• root
• left_most
• right_most
• size
• observer
• _phantom

impl<K, P, Tag, S, O> WavlTree<K, P, Tag, S, O>

where P: PtrTraits, P::Target: WavlTreeContainable<P::Target, Tag> + WavlTreeKeyable<K>, K: Ord, S: SizeTracker, O: WavlTreeObserver<Target = P::Target>,

pub fn new_with_observer(observer: O) -> impl PinInit<Self, Infallible>

Creates a new, empty tree with a custom observer.

pub fn new() -> impl PinInit<Self, Infallible>

where O: Default,

Creates a new, empty tree.

pub fn is_empty(&self) -> bool

Returns true if the tree is empty.

pub fn front(&self) -> Option<&P::Target>

Returns a reference to the first (smallest) element of the tree, or None if it is empty.

pub fn back(&self) -> Option<&P::Target>

Returns a reference to the last (largest) element of the tree, or None if it is empty.

pub fn insert(&mut self, ptr: P)

where P: ManagedPtr,

Inserts an element into the tree.

For raw pointers, use [insert_raw] instead.

pub unsafe fn insert_raw(&mut self, ptr: P)

Inserts an element into the tree.

Safety

The caller must ensure that ptr is a valid pointer to a T and that the object outlives the reference from the tree.

pub fn insert_or_find<'a>( &'a mut self, ptr: P, ) -> Result<(), (P, CursorMut<'a, K, P, Tag, S, O>)>

where P: ManagedPtr,

Inserts the object pointed to by ptr if it is not already in the tree, or finds the object that ptr collided with instead.

For raw pointers, use [insert_or_find_raw] instead.

Returns

• Ok(()) if there was no collision and the item was successfully inserted. In this case, the tree takes ownership of ptr.
• Err((ptr, cursor)) if there was a collision. In this case, the passed pointer ptr is returned back to the caller (not consumed), along with a CursorMut positioned at the colliding node already in the tree.

pub unsafe fn insert_or_find_raw<'a>( &'a mut self, ptr: P, ) -> Result<(), (P, CursorMut<'a, K, P, Tag, S, O>)>

Inserts the object pointed to by ptr if it is not already in the tree, or finds the object that ptr collided with instead.

Safety

The caller must ensure that ptr is a valid pointer to a T and that the object outlives the reference from the tree.

pub fn insert_or_replace(&mut self, ptr: P) -> Option<P>

where P: ManagedPtr,

Finds the element in the tree with the same key as *ptr and replaces it with ptr, returning the element which was replaced.

If no element in the tree shares a key with *ptr, simply adds ptr to the tree and returns None.

In both cases, the input pointer ptr is consumed.

For raw pointers, use [insert_or_replace_raw] instead.

Returns

Some(replaced) containing the previous element if a collision occurred, or None if the element was newly inserted.

pub unsafe fn insert_or_replace_raw(&mut self, ptr: P) -> Option<P>

Finds the element in the tree with the same key as *ptr and replaces it with ptr, returning the element which was replaced.

If no element in the tree shares a key with *ptr, simply adds ptr to the tree and returns None.

Safety

The caller must ensure that ptr is a valid pointer to a T and that the object outlives the reference from the tree.

pub fn pop_front(&mut self) -> Option<P>

Removes and returns the first (smallest) element of the tree, or None if it is empty.

pub fn pop_back(&mut self) -> Option<P>

Removes and returns the last (largest) element of the tree, or None if it is empty.

pub fn clear(&mut self)

Removes all elements from the tree.

pub fn swap(&mut self, other: &mut Self)

Swaps the contents of this tree with another tree.

This runs in O(1) time.

pub fn find(&self, key: &K) -> Option<&P::Target>

Finds an element in the tree by key.

pub fn find_cursor(&mut self, key: &K) -> CursorMut<'_, K, P, Tag, S, O>

Finds an element in the tree by key and returns a cursor positioned at it.

If the key is not found, the returned cursor is positioned at the sentinel (i.e. cursor.get() will return None).

pub fn lower_bound(&mut self, key: &K) -> CursorMut<'_, K, P, Tag, S, O>

Returns a cursor positioned at the lower bound of the key (the first element in the tree whose key is greater than or equal to key).

If no such element exists (e.g. all elements in the tree are smaller than key), the returned cursor is positioned at the sentinel.

pub fn upper_bound(&mut self, key: &K) -> CursorMut<'_, K, P, Tag, S, O>

Returns a cursor positioned at the upper bound of the key (the first element in the tree whose key is strictly greater than key).

If no such element exists (e.g. all elements in the tree are smaller than or equal to key), the returned cursor is positioned at the sentinel.

pub fn erase(&mut self, key: &K) -> Option<P>

Erases an element by key.

pub unsafe fn erase_raw(&mut self, obj: &P::Target) -> Option<P>

Erases an element by reference.

Safety

The caller must ensure that obj is currently contained within this tree instance.

pub fn cursor_mut(&mut self) -> CursorMut<'_, K, P, Tag, S, O>

Returns a cursor positioned at the front (smallest element) of the tree.

pub unsafe fn cursor_at(&self, obj: &P::Target) -> Cursor<'_, K, P, Tag, S, O>

Returns a read-only cursor positioned at the given element.

Safety

The caller must ensure that obj is a member of this tree. It is undefined behavior to use the returned cursor if obj is not in the tree, or if it is in a different tree.

pub unsafe fn cursor_mut_at( &mut self, obj: &P::Target, ) -> CursorMut<'_, K, P, Tag, S, O>

Returns a mutable cursor positioned at the given element.

Safety

The caller must ensure that obj is a member of this tree. It is undefined behavior to use the returned cursor if obj is not in the tree, or if it is in a different tree.

pub fn iter(&self) -> Iterator<'_, K, P, Tag, S, O>

Returns an iterator over the elements of the tree.

pub fn forward_iter(&self) -> ForwardIterator<'_, K, P, Tag, S, O>

Returns a unidirectional forward iterator over the elements of the tree.

pub fn reverse_iter(&self) -> ReverseIterator<'_, K, P, Tag, S, O>

Returns a unidirectional reverse iterator over the elements of the tree.

pub fn root_cursor(&self) -> Cursor<'_, K, P, Tag, S, O>

Returns a read-only cursor positioned at the root of the tree.

pub fn front_cursor(&self) -> Cursor<'_, K, P, Tag, S, O>

Returns a read-only cursor positioned at the first (smallest) element.

pub fn back_cursor(&self) -> Cursor<'_, K, P, Tag, S, O>

Returns a read-only cursor positioned at the last (largest) element.

pub fn len(&self) -> usize

Returns the number of elements in the tree.

impl<K, T, Tag, S, O> WavlTree<K, *mut T, Tag, S, O>

where T: WavlTreeContainable<T, Tag> + WavlTreeKeyable<K>, K: Ord, S: SizeTracker, O: WavlTreeObserver<Target = T>,

pub fn clear_unsafe(&mut self)

Unsafely removes all elements from the tree without modifying node memory.

This method resets the tree’s internal pointers, effectively emptying it, but does NOT modify the node state of the elements that were in the tree.

Safety

Because the nodes are not modified, they will still believe they are in a container (i.e. in_container() will return true for them). If these elements are subsequently dropped, they will trigger a debug_assert panic (as WavlTreeNode asserts on drop that it is not in a container).

The caller is responsible for manually clearing the node state of the elements, or ensuring they are never dropped while in this “dirty” state.

Only usable with containers of unmanaged pointers. Think carefully before calling this!

Trait Implementations

impl<K, P, Tag, S, O> Debug for WavlTree<K, P, Tag, S, O>

where P: PtrTraits, P::Target: WavlTreeContainable<P::Target, Tag> + WavlTreeKeyable<K> + Debug, K: Ord, S: SizeTracker, O: WavlTreeObserver<Target = P::Target>,

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

Formats the value using the given formatter.

impl<K, P, Tag, S, O> Drop for WavlTree<K, P, Tag, S, O>

where P: PtrTraits, P::Target: WavlTreeContainable<P::Target, Tag> + WavlTreeKeyable<K>, K: Ord, S: SizeTracker, O: WavlTreeObserver<Target = P::Target>,

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<K, P, Tag, S, O> HasPinData for WavlTree<K, P, Tag, S, O>

where P: PtrTraits, P::Target: WavlTreeContainable<P::Target, Tag> + WavlTreeKeyable<K>, K: Ord, S: SizeTracker, O: WavlTreeObserver<Target = P::Target>,

type PinData = __ThePinData<K, P, Tag, S, O>

unsafe fn __pin_data() -> Self::PinData

impl<K, P, Tag, S, O> PinnedDrop for WavlTree<K, P, Tag, S, O>

where P: PtrTraits, P::Target: WavlTreeContainable<P::Target, Tag> + WavlTreeKeyable<K>, K: Ord, S: SizeTracker, O: WavlTreeObserver<Target = P::Target>,

fn drop(self: Pin<&mut Self>, _: OnlyCallFromDrop)

Executes the pinned destructor of this type.