Trait TreeIndex

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

    // Required methods
    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;

    // Provided methods
    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.

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

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.

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.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types

impl TreeIndex for u32

const NONE: u32 = 0u32

const ROOT: u32 = 1u32

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 = 0u64

const ROOT: u64 = 1u64

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

Implementors