Module diem_types::proof::position

source ·
Expand description

This module provides an abstraction for positioning a node in a binary tree, A Position uniquely identifies the location of a node

In this implementation, Position is represented by the in-order-traversal sequence number of the node. The process of locating a node and jumping between nodes is done through in-order position calculation, which can be done with bit manipulation.

For example

     3
    /  \
   /    \
  1      5 <-[Node index, a.k.a, Position]
 / \    / \
0   2  4   6

0   1  2   3 <[Leaf index]

Note1: The in-order-traversal counts from 0 Note2: The level of tree counts from leaf level, start from 0 Note3: The leaf index starting from left-most leaf, starts from 0

Structs

  • AncestorIterator
    AncestorIterator generates current position and moves itself to its parent position for each iteration.
  • AncestorSiblingIterator
    AncestorSiblingIterator generates current sibling position and moves itself to its parent position for each iteration.
  • FrozenSubTreeIterator
    Traverse leaves from left to right in groups that forms full subtrees, yielding root positions of such subtrees. Note that each 1-bit in num_leaves corresponds to a full subtree. For example, in the below tree of 5=0b101 leaves, the two 1-bits corresponds to Fzn2 and L4 accordingly.
  • FrozenSubtreeSiblingIterator
    Given an accumulator of size current_num_leaves, FrozenSubtreeSiblingIterator yields the positions of required subtrees if we want to append these subtrees to the existing accumulator to generate a bigger one of size new_num_leaves.
  • Position

Enums

Functions

  • inorder_to_postorder
    Given node, an index in an in-order traversal of a perfect binary tree, what order would the node be visited in in post-order traversal? For example, consider this tree of in-order nodes.
  • postorder_to_inorder