Struct Forest 

pub struct Forest(/* private fields */);

A compact representation of trees in a forest. Used in the Merkle forest (MMR).

Each active bit of the stored number represents a disjoint tree with number of leaves equal to the bit position.

The forest value has the following interpretations:

• its value is the number of leaves in the forest
• the version number (MMR is append only so the number of leaves always increases)
• bit count corresponds to the number of trees (trees) in the forest
• each true bit position determines the depth of a tree in the forest

Examples:

• Forest(0) is a forest with no trees.
• Forest(0b01) is a forest with a single leaf/node (the smallest tree possible).
• Forest(0b10) is a forest with a single binary tree with 2 leaves (3 nodes).
• Forest(0b11) is a forest with two trees: one with 1 leaf (1 node), and one with 2 leaves (3 nodes).
• Forest(0b1010) is a forest with two trees: one with 8 leaves (15 nodes), one with 2 leaves (3 nodes).
• Forest(0b1000) is a forest with one tree, which has 8 leaves (15 nodes).

Implementations

impl Forest

pub const fn empty() -> Forest

Creates an empty forest (no trees).

pub const fn new(num_leaves: usize) -> Forest

Creates a forest with num_leaves leaves.

pub const fn with_height(height: usize) -> Forest

Creates a forest with a given height.

This is equivalent to Forest::new(1 << height).

Panics

This will panic if height is greater than usize::BITS - 1.

pub fn is_empty(self) -> bool

Returns true if there are no trees in the forest.

pub fn append_leaf(&mut self)

Adds exactly one more leaf to the capacity of this forest.

Some smaller trees might be merged together.

pub fn num_leaves(self) -> usize

Returns a count of leaves in the entire underlying forest (MMR).

pub const fn num_nodes(self) -> usize

Return the total number of nodes of a given forest.

Panics

This will panic if the forest has size greater than usize::MAX / 2 + 1.

pub const fn num_trees(self) -> usize

Return the total number of trees of a given forest (the number of active bits).

pub fn largest_tree_height_unchecked(self) -> usize

Returns the height (bit position) of the largest tree in the forest.

Panics

This will panic if the forest is empty.

pub fn largest_tree_height(self) -> Option<usize>

Returns the height (bit position) of the largest tree in the forest.

If the forest cannot be empty, use largest_tree_height_unchecked for performance.

pub fn largest_tree_unchecked(self) -> Forest

Returns a forest with only the largest tree present.

Panics

This will panic if the forest is empty.

pub fn largest_tree(self) -> Forest

Returns a forest with only the largest tree present.

If forest cannot be empty, use largest_tree for better performance.

pub fn smallest_tree_height_unchecked(self) -> usize

Returns the height (bit position) of the smallest tree in the forest.

Panics

This will panic if the forest is empty.

pub fn smallest_tree_height(self) -> Option<usize>

Returns the height (bit position) of the smallest tree in the forest.

If the forest cannot be empty, use smallest_tree_height_unchecked for better performance.

pub fn smallest_tree_unchecked(self) -> Forest

Returns a forest with only the smallest tree present.

Panics

This will panic if the forest is empty.

pub fn smallest_tree(self) -> Forest

Returns a forest with only the smallest tree present.

If forest cannot be empty, use smallest_tree for performance.

pub fn trees_larger_than(self, tree_idx: u32) -> Forest

Keeps only trees larger than the reference tree.

For example, if we start with the bit pattern 0b0101_0110, and keep only the trees larger than tree index 1, that targets this bit:

Forest(0b0101_0110).trees_larger_than(1)
                       ^
Becomes:      0b0101_0100
                       ^

And keeps only trees after that bit, meaning that the tree at tree_idx is also removed, resulting in 0b0101_0100.

let range = Forest::new(0b0101_0110);
assert_eq!(range.trees_larger_than(1), Forest::new(0b0101_0100));

pub fn all_smaller_trees_unchecked(self) -> Forest

Creates a new forest with all possible trees smaller than the smallest tree in this forest.

This forest must have exactly one tree.

Panics

With debug assertions enabled, this function panics if this forest does not have exactly one tree.

For a non-panicking version of this function, see Forest::all_smaller_trees().

pub fn all_smaller_trees(self) -> Option<Forest>

Creates a new forest with all possible trees smaller than the smallest tree in this forest, or returns None if this forest has more or less than one tree.

If the forest cannot have more or less than one tree, use Forest::all_smaller_trees_unchecked() for performance.

pub fn next_larger_tree(self) -> Forest

Returns a forest with exactly one tree, one size (depth) larger than the current one.

pub fn has_single_leaf_tree(self) -> bool

Returns true if the forest contains a single-node tree.

pub fn with_single_leaf(self) -> Forest

Add a single-node tree if not already present in the forest.

pub fn without_single_leaf(self) -> Forest

Remove the single-node tree if present in the forest.

pub fn without_trees(self, other: Forest) -> Forest

Returns a new forest that does not have the trees that other has.

pub fn tree_index(&self, leaf_idx: usize) -> usize

Returns index of the forest tree for a specified leaf index.

pub fn root_in_order_index(&self) -> InOrderIndex

Returns the smallest tree’s root element as an InOrderIndex.

This function takes the smallest tree in this forest, “pretends” that it is a subtree of a fully balanced binary tree, and returns the the in-order index of that balanced tree’s root node.

pub fn rightmost_in_order_index(&self) -> InOrderIndex

Returns the in-order index of the rightmost element (the smallest tree).

pub fn leaf_to_corresponding_tree(self, leaf_idx: usize) -> Option<u32>

Given a leaf index in the current forest, return the tree number responsible for the leaf.

Note: The result is a tree position p, it has the following interpretations:

• p+1 is the depth of the tree.
• Because the root element is not part of the proof, p is the length of the authentication path.
• 2^p is equal to the number of leaves in this particular tree.
• And 2^(p+1)-1 corresponds to the size of the tree.

For example, given a forest with 6 leaves whose forest is 0b110:

      __ tree 2 __
     /            \
   ____          ____         _ tree 1 _
  /    \        /    \       /          \
 0      1      2      3     4            5

Leaf indices 0..=3 are in the tree at index 2 and leaf indices 4..=5 are in the tree at index 1.

Trait Implementations

impl Binary for Forest

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl BitAnd for Forest

type Output = Forest

The resulting type after applying the & operator.

fn bitand(self, rhs: Forest) -> <Forest as BitAnd>::Output

Performs the & operation.

impl BitOr for Forest

type Output = Forest

The resulting type after applying the | operator.

fn bitor(self, rhs: Forest) -> <Forest as BitOr>::Output

Performs the | operation.

impl BitXor for Forest

type Output = Forest

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: Forest) -> <Forest as BitXor>::Output

Performs the ^ operation.

impl BitXorAssign for Forest

fn bitxor_assign(&mut self, rhs: Forest)

Performs the ^= operation.

impl Clone for Forest

fn clone(&self) -> Forest

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Forest

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl Default for Forest

fn default() -> Forest

Returns the “default value” for a type.

impl Deserializable for Forest

fn read_from<R>(source: &mut R) -> Result<Forest, DeserializationError>

where R: ByteReader,

Reads a sequence of bytes from the provided source, attempts to deserialize these bytes into Self, and returns the result.

fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError>

Attempts to deserialize the provided bytes into Self and returns the result.

impl Display for Forest

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl From<BaseElement> for Forest

fn from(value: BaseElement) -> Forest

Converts to this type from the input type.

impl From<Forest> for BaseElement

fn from(value: Forest) -> BaseElement

Converts to this type from the input type.

impl Ord for Forest

fn cmp(&self, other: &Forest) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for Forest

fn eq(&self, other: &Forest) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for Forest

fn partial_cmp(&self, other: &Forest) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Serializable for Forest

fn write_into<W>(&self, target: &mut W)

where W: ByteWriter,

Serializes self into bytes and writes these bytes into the target.

fn to_bytes(&self) -> Vec<u8>

Serializes self into a vector of bytes.

fn get_size_hint(&self) -> usize

Returns an estimate of how many bytes are needed to represent self.

impl Copy for Forest

impl Eq for Forest

impl StructuralPartialEq for Forest