Trait WavlTreeObserver 

pub trait WavlTreeObserver {
    type Target;

    // Provided methods
    fn record_insert(&self, _node: *mut Self::Target) { ... }
    fn record_insert_traverse(
        &self,
        _node: *mut Self::Target,
        _ancestor: *mut Self::Target,
    ) { ... }
    fn record_insert_collision(
        &self,
        _node: *mut Self::Target,
        _collision: *mut Self::Target,
    ) { ... }
    fn record_insert_replace(
        &self,
        _node: *mut Self::Target,
        _replacement: *mut Self::Target,
    ) { ... }
    fn record_insert_promote(&self) { ... }
    fn record_insert_rotation(&self) { ... }
    fn record_insert_double_rotation(&self) { ... }
    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,
    ) { ... }
    fn record_erase(
        &self,
        _node: *mut Self::Target,
        _invalidated: *mut Self::Target,
    ) { ... }
    fn record_erase_demote(&self) { ... }
    fn record_erase_rotation(&self) { ... }
    fn record_erase_double_rotation(&self) { ... }
    fn verify_rank_rule(
        &self,
        _node: *mut Self::Target,
        _left_most: *mut Self::Target,
        _right_most: *mut Self::Target,
        _sentinel: *mut Self::Target,
    ) { ... }
    fn verify_balance(&self, _size: usize, _depth: usize) { ... }
}

Trait defining an observer for a WavlTree.

Observers are used by the test framework to record the number of insert, erase, rank-promote, rank-demote, and rotation operations performed during usage. The default implementation does nothing and is optimized away.

Observers may also be used to maintain additional application-specific per-node invariants. For example, maintaining subtree min/max values is useful for multikey partition searching.

Note: Records of promotions and demotions are used by tests to demonstrate that the computational complexity of insert/erase rebalancing is amortized constant. Promotions and demotions which are side effects of the rotation phase of rebalancing are considered to be part of the cost of rotation and are not tallied in the overall promote/demote accounting.

Required Associated Types

type Target

The type pointed to by the tree pointers.

Provided Methods

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_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_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.

The following diagrams the relationship of the nodes in a left rotation:

            pivot                          parent                             |
           /     \                         /    \                             |
       parent  rl_child  <-----------  sibling  pivot                         |
       /    \                                   /   \                         |
  sibling  lr_child                       lr_child  rl_child                  |

In a right rotation, all of the relationships are reflected.

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.

The following diagrams the relationship of the erased and invalidated nodes:

       root                                                                   |
      /    \                                                                  |
     A      B    <---- Invalidated starting here on up to the root            |
    / \    / \                                                                |
   C   D  E   F  <---- Erased node                                            |

When the node to be erased has two children, it is first swapped with the leftmost child of the righthand subtree. In this case the invalidated node is the parent of the original leftmost child of the righthand subtree, as this is the deepest node to change after erasure.

       root                       root                                        |
      /    \                     /    \                                       |
     A      B                   A      B                                      |
    / \    / \                 / \    / \                                     |
   C   D  E   F  <--+         C   D  E   H    <---- Invalidated starting here |
             / \    | Swap              / \                                   |
            G   H <-+                  G   F  <---- Erased node               |

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.

Dyn Compatibility

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors

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