Struct WavlTreeAugmentedInvariantObserver 

pub struct WavlTreeAugmentedInvariantObserver<Tag, Traits, const ALLOW_FIND_COLLISION: bool = true, const ALLOW_REPLACE_COLLISION: bool = true> { /* private fields */ }

A WAVL tree observer that maintains augmented invariants.

Trait Implementations

impl<Tag, Traits, const ALLOW_FIND_COLLISION: bool, const ALLOW_REPLACE_COLLISION: bool> Default for WavlTreeAugmentedInvariantObserver<Tag, Traits, ALLOW_FIND_COLLISION, ALLOW_REPLACE_COLLISION>

fn default() -> Self

Returns the “default value” for a type.

impl<Tag, Traits, const ALLOW_FIND_COLLISION: bool, const ALLOW_REPLACE_COLLISION: bool> WavlTreeObserver for WavlTreeAugmentedInvariantObserver<Tag, Traits, ALLOW_FIND_COLLISION, ALLOW_REPLACE_COLLISION>

where Traits: WavlTreeAugmentedInvariantObserverTraits, Traits::Target: WavlTreeContainable<Traits::Target, Tag>,

type Target = <Traits as WavlTreeAugmentedInvariantObserverTraits>::Target

The type pointed to by the tree pointers.

fn record_insert(&self, node: *mut Self::Target)

Invoked on the newly inserted node before rebalancing.

fn record_insert_traverse( &self, _node: *mut Self::Target, _ancestor: *mut Self::Target, )

Invoked on the node to be inserted and each ancestor node while traversing the tree to find the initial insertion point.

fn record_insert_collision( &self, _node: *mut Self::Target, _collision: *mut Self::Target, )

Invoked on the node to be inserted and the colliding node with the same key, during an insert-or-find operation. This method is mutually exclusive with record_insert_replace, only one or the other is invoked during an insert operation.

fn record_insert_replace( &self, node: *mut Self::Target, replacement: *mut Self::Target, )

Invoked on an existing node and its replacement, before swapping the replacement into the tree, during an insert-or-replace operation. This method is mutually exclusive with record_insert_collision, only one or the other is invoked during an insert operation.

fn record_rotation( &self, pivot: *mut Self::Target, lr_child: *mut Self::Target, _rl_child: *mut Self::Target, parent: *mut Self::Target, sibling: *mut Self::Target, )

Invoked on the pivot node, its parent, children, and sibling before a rotation, just before updating the pointers in the relevant nodes. The chirality of the children and sibling is relative to the direction of rotation. The direction of rotation can be determined by comparing these arguments with the values returned by the left and right child properties of the pivot or parent arguments.

fn record_erase(&self, node: *mut Self::Target, invalidated: *mut Self::Target)

Invoked on the node to be erased and the node in the tree where the augmented invariants become invalid, leading up to the root. Called just after updating the pointers in the relevant nodes, but before rebalancing.

fn record_insert_promote(&self)

Invoked after each promotion during post-insert rebalancing.

fn record_insert_rotation(&self)

Invoked after a single rotation during post-insert rebalancing.

fn record_insert_double_rotation(&self)

Invoked after a double rotation during post-insert rebalancing.

fn record_erase_demote(&self)

Invoked after each demotion during post-erase rebalancing.

fn record_erase_rotation(&self)

Invoked after each single rotation during post-erase rebalancing.

fn record_erase_double_rotation(&self)

Invoked after each double rotation during post-erase rebalancing.

fn verify_rank_rule( &self, _node: *mut Self::Target, _left_most: *mut Self::Target, _right_most: *mut Self::Target, _sentinel: *mut Self::Target, )

Invoked during testing to verify WAVL tree rank rules for a given node.

fn verify_balance(&self, _size: usize, _depth: usize)

Invoked during testing to verify tree balance properties given the tree size and depth.