Struct merkle_log::TreeID

pub struct TreeID(_);

Unique identifiers for binary tree nodes. Reproduced from flat-tree.

Implementations

impl TreeID

pub const fn new(depth: u8, index: u64) -> Self

Returns a node’s unique id within the tree, given its depth and index.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::new(0, 0), 0usize);
assert_eq!(TreeID::new(0, 1), 2usize);
assert_eq!(TreeID::new(0, 2), 4usize);
assert_eq!(TreeID::new(1, 2), 9usize);
assert_eq!(TreeID::new(1, 3), 13usize);
assert_eq!(TreeID::new(2, 1), 11usize);
assert_eq!(TreeID::new(2, 2), 19usize);
assert_eq!(TreeID::new(3, 0), 7usize);
assert_eq!(TreeID::new(3, 1), 23usize);

pub const fn index(&self) -> u64

Returns a node’s index among nodes of the same depth.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::from(0).index(), 0);
assert_eq!(TreeID::from(1).index(), 0);
assert_eq!(TreeID::from(2).index(), 1);
assert_eq!(TreeID::from(3).index(), 0);
assert_eq!(TreeID::from(4).index(), 2);

pub const fn depth(&self) -> u8

Returns a node’s depth in the tree.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::from(0).depth(), 0);
assert_eq!(TreeID::from(1).depth(), 1);
assert_eq!(TreeID::from(2).depth(), 0);
assert_eq!(TreeID::from(3).depth(), 2);
assert_eq!(TreeID::from(4).depth(), 0);

pub const fn parent(&self) -> Self

Returns the parent id of a node.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::from(0).parent(), 1usize);
assert_eq!(TreeID::from(1).parent(), 3usize);
assert_eq!(TreeID::from(2).parent(), 1usize);
assert_eq!(TreeID::from(3).parent(), 7usize);
assert_eq!(TreeID::from(4).parent(), 5usize);
assert_eq!(TreeID::from(5).parent(), 3usize);
assert_eq!(TreeID::from(6).parent(), 5usize);
assert_eq!(TreeID::from(7).parent(), 15usize);
assert_eq!(TreeID::from(8).parent(), 9usize);

pub const fn sibling(&self) -> Self

Returns the sibling id of a node.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::from(0).sibling(), 2usize);
assert_eq!(TreeID::from(2).sibling(), 0usize);
assert_eq!(TreeID::from(1).sibling(), 5usize);
assert_eq!(TreeID::from(5).sibling(), 1usize);

pub const fn uncle(&self) -> Self

Given a node, returns its parent’s sibling’s id.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::from(0).uncle(), 5usize);
assert_eq!(TreeID::from(2).uncle(), 5usize);
assert_eq!(TreeID::from(1).uncle(), 11usize);
assert_eq!(TreeID::from(5).uncle(), 11usize);
assert_eq!(TreeID::from(9).uncle(), 3usize);

pub const fn left(&self) -> Option<Self>

Returns the id of the node’s left child.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::from(0).left(), None);
assert_eq!(TreeID::from(1).left(), Some(TreeID::from(0)));
assert_eq!(TreeID::from(3).left(), Some(TreeID::from(1)));

pub const fn right(&self) -> Option<Self>

Returns the id of the node’s right child.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::from(0).right(), None);
assert_eq!(TreeID::from(1).right(), Some(TreeID::from(2)));
assert_eq!(TreeID::from(3).right(), Some(TreeID::from(5)));

pub const fn span(&self) -> (Self, Self)

Returns the left- and right-most node ids in the tree the node spans.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::from(0).span(), (TreeID::from(0), TreeID::from(0)));
assert_eq!(TreeID::from(1).span(), (TreeID::from(0), TreeID::from(2)));
assert_eq!(TreeID::from(3).span(), (TreeID::from(0), TreeID::from(6)));
assert_eq!(TreeID::from(23).span(), (TreeID::from(16), TreeID::from(30)));
assert_eq!(TreeID::from(27).span(), (TreeID::from(24), TreeID::from(30)));

pub fn spans(&self, other: &Self) -> bool

Determines if the id’s tree spans (i.e. contains) another id.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::from(0).spans(&TreeID::from(0)), true);
assert_eq!(TreeID::from(0).spans(&TreeID::from(1)), false);
assert_eq!(TreeID::from(1).spans(&TreeID::from(0)), true);
assert_eq!(TreeID::from(1).spans(&TreeID::from(1)), true);
assert_eq!(TreeID::from(1).spans(&TreeID::from(2)), true);
assert_eq!(TreeID::from(3).spans(&TreeID::from(1)), true);
assert_eq!(TreeID::from(3).spans(&TreeID::from(5)), true);
assert_eq!(TreeID::from(3).spans(&TreeID::from(7)), false);

pub fn subroots(size: u64) -> Vec<Self>

The root ids of the highest complete subtrees within a log of a given size.

Examples

use merkle_log::TreeID;

assert_eq!(TreeID::subroots(0), Vec::<TreeID>::new());
assert_eq!(TreeID::subroots(1), &[TreeID::from(0)]);
assert_eq!(TreeID::subroots(2), &[TreeID::from(1)]);
assert_eq!(TreeID::subroots(3), &[TreeID::from(1), TreeID::from(4)]);
assert_eq!(TreeID::subroots(4), &[TreeID::from(3)]);
assert_eq!(TreeID::subroots(5), &[TreeID::from(3), TreeID::from(8)]);
assert_eq!(TreeID::subroots(6), &[TreeID::from(3), TreeID::from(9)]);
assert_eq!(TreeID::subroots(7), &[TreeID::from(3), TreeID::from(9), TreeID::from(12)]);
assert_eq!(TreeID::subroots(8), &[TreeID::from(7)]);
assert_eq!(TreeID::subroots(9), &[TreeID::from(7), TreeID::from(16)]);
assert_eq!(TreeID::subroots(10), &[TreeID::from(7), TreeID::from(17)]);

Trait Implementations

impl Clone for TreeID

fn clone(&self) -> TreeID

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Copy for TreeID

impl Debug for TreeID

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

Formats the value using the given formatter.

impl Eq for TreeID

impl From<u64> for TreeID

fn from(id: u64) -> Self

Performs the conversion.

impl Hash for TreeID

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

pub fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl Ord for TreeID

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

This method returns an Ordering between self and other.

#[must_use]pub fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]pub fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]pub fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

impl PartialEq<TreeID> for TreeID

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

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.

impl PartialEq<u16> for TreeID

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

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl PartialEq<u32> for TreeID

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

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl PartialEq<u64> for TreeID

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

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl PartialEq<u8> for TreeID

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

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl PartialEq<usize> for TreeID

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

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl PartialOrd<TreeID> for TreeID

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

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

#[must_use]pub fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use]pub fn le(&self, other: &Rhs) -> bool

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

#[must_use]pub fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use]pub fn ge(&self, other: &Rhs) -> bool

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

impl StructuralEq for TreeID

impl StructuralPartialEq for TreeID