Trait balanced_tree_index::TreeIndex

pub trait TreeIndex: Copy + Eq + PartialEq + CMov {
    const NONE: Self;
    const ROOT: Self;

    fn parent(&self, i: u32) -> Self;
    fn height(&self) -> u32;
    fn common_ancestor_distance_of_peers(&self, other: &Self) -> u32;
    fn random_child_at_height<R: RngCore>(
        &self, 
        height: u32, 
        rng: &mut R
    ) -> Self;

    fn common_ancestor_height(&self, other: &Self) -> u32 { ... }
    fn parents(&self) -> ParentsIterator<Self> { ... }
}

Trait representing a type that can represent a tree index in a balanced binary tree, using the numbering where the root is 1, and nodes are labelled consecutively level by level, using lexicographic order within a level.

All operations here should be constant time, leaking nothing about the input and &self, unless otherwise stated.

Associated Constants

const NONE: Self

The Zero index that is unused and does not actually refer to a node in the tree.

const ROOT: Self

The index of the root of the tree, logically 1. The parent of ROOT is NONE.

Loading content...

Required methods

fn parent(&self, i: u32) -> Self

Find the i’th parent of a node.

fn height(&self) -> u32

Find the height of a node. This returns u32 because rust’s count_leading_zeros does. It is illegal to call this when self is the NONE value.

fn common_ancestor_distance_of_peers(&self, other: &Self) -> u32

For two nodes promised to be “peers” i.e. at the same height, compute the distance from (either) to their common ancestor in the tree. This is the number of times you have to compute “parent” before they are equal. It is illegal to call this if the height of the two arguments is not the same. Should not reveal anything else about the arguments.

fn random_child_at_height<R: RngCore>(&self, height: u32, rng: &mut R) -> Self

Random child at a given height. This height must be the same or less than the height of the given node, otherwise the call is illegal. It is legal to call this on the NONE value, it will be as if ROOT was passed.

Loading content...

Provided methods

fn common_ancestor_height(&self, other: &Self) -> u32

Compute the height of the common ancestor of any two nodes. It is illegal to call this when either of the inputs is the NONE value.

fn parents(&self) -> ParentsIterator<Self>

Iterate over the parents of this node, including self. Access patterns when evaluating this iterator reveal the height of self, but not more than that.

Loading content...

Implementors

impl TreeIndex for u32

const NONE: u32

const ROOT: u32

fn parent(&self, i: u32) -> Self

fn height(&self) -> u32

fn common_ancestor_distance_of_peers(&self, other: &Self) -> u32

fn random_child_at_height<R: RngCore>(&self, height: u32, rng: &mut R) -> Self

impl TreeIndex for u64

const NONE: u64

const ROOT: u64

fn parent(&self, i: u32) -> Self

fn height(&self) -> u32

fn common_ancestor_distance_of_peers(&self, other: &Self) -> u32

fn random_child_at_height<R: RngCore>(&self, height: u32, rng: &mut R) -> Self

Loading content...