miden_crypto/merkle/mmr/inorder.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
//! Index for nodes of a binary tree based on an in-order tree walk.
//!
//! In-order walks have the parent node index split its left and right subtrees. All the left
//! children have indexes lower than the parent, meanwhile all the right subtree higher indexes.
//! This property makes it is easy to compute changes to the index by adding or subtracting the
//! leaves count.
use core::num::NonZeroUsize;
use winter_utils::{Deserializable, Serializable};
// IN-ORDER INDEX
// ================================================================================================
/// Index of nodes in a perfectly balanced binary tree based on an in-order tree walk.
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct InOrderIndex {
idx: usize,
}
impl InOrderIndex {
// CONSTRUCTORS
// --------------------------------------------------------------------------------------------
/// Returns a new [InOrderIndex] instantiated from the provided value.
pub fn new(idx: NonZeroUsize) -> InOrderIndex {
InOrderIndex { idx: idx.get() }
}
/// Return a new [InOrderIndex] instantiated from the specified leaf position.
///
/// # Panics:
/// If `leaf` is higher than or equal to `usize::MAX / 2`.
pub fn from_leaf_pos(leaf: usize) -> InOrderIndex {
// Convert the position from 0-indexed to 1-indexed, since the bit manipulation in this
// implementation only works 1-indexed counting.
let pos = leaf + 1;
InOrderIndex { idx: pos * 2 - 1 }
}
// PUBLIC ACCESSORS
// --------------------------------------------------------------------------------------------
/// True if the index is pointing at a leaf.
///
/// Every odd number represents a leaf.
pub fn is_leaf(&self) -> bool {
self.idx & 1 == 1
}
/// Returns true if this note is a left child of its parent.
pub fn is_left_child(&self) -> bool {
self.parent().left_child() == *self
}
/// Returns the level of the index.
///
/// Starts at level zero for leaves and increases by one for each parent.
pub fn level(&self) -> u32 {
self.idx.trailing_zeros()
}
/// Returns the index of the left child.
///
/// # Panics:
/// If the index corresponds to a leaf.
pub fn left_child(&self) -> InOrderIndex {
// The left child is itself a parent, with an index that splits its left/right subtrees. To
// go from the parent index to its left child, it is only necessary to subtract the count
// of elements on the child's right subtree + 1.
let els = 1 << (self.level() - 1);
InOrderIndex { idx: self.idx - els }
}
/// Returns the index of the right child.
///
/// # Panics:
/// If the index corresponds to a leaf.
pub fn right_child(&self) -> InOrderIndex {
// To compute the index of the parent of the right subtree it is sufficient to add the size
// of its left subtree + 1.
let els = 1 << (self.level() - 1);
InOrderIndex { idx: self.idx + els }
}
/// Returns the index of the parent node.
pub fn parent(&self) -> InOrderIndex {
// If the current index corresponds to a node in a left tree, to go up a level it is
// required to add the number of nodes of the right sibling, analogously if the node is a
// right child, going up requires subtracting the number of nodes in its left subtree.
//
// Both of the above operations can be performed by bitwise manipulation. Below the mask
// sets the number of trailing zeros to be equal the new level of the index, and the bit
// marks the parent.
let target = self.level() + 1;
let bit = 1 << target;
let mask = bit - 1;
let idx = self.idx ^ (self.idx & mask);
InOrderIndex { idx: idx | bit }
}
/// Returns the index of the sibling node.
pub fn sibling(&self) -> InOrderIndex {
let parent = self.parent();
if *self > parent {
parent.left_child()
} else {
parent.right_child()
}
}
/// Returns the inner value of this [InOrderIndex].
pub fn inner(&self) -> u64 {
self.idx as u64
}
}
impl Serializable for InOrderIndex {
fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
target.write_usize(self.idx);
}
}
impl Deserializable for InOrderIndex {
fn read_from<R: winter_utils::ByteReader>(
source: &mut R,
) -> Result<Self, winter_utils::DeserializationError> {
let idx = source.read_usize()?;
Ok(InOrderIndex { idx })
}
}
// CONVERSIONS FROM IN-ORDER INDEX
// ------------------------------------------------------------------------------------------------
impl From<InOrderIndex> for u64 {
fn from(index: InOrderIndex) -> Self {
index.idx as u64
}
}
// TESTS
// ================================================================================================
#[cfg(test)]
mod test {
use proptest::prelude::*;
use winter_utils::{Deserializable, Serializable};
use super::InOrderIndex;
proptest! {
#[test]
fn proptest_inorder_index_random(count in 1..1000usize) {
let left_pos = count * 2;
let right_pos = count * 2 + 1;
let left = InOrderIndex::from_leaf_pos(left_pos);
let right = InOrderIndex::from_leaf_pos(right_pos);
assert!(left.is_leaf());
assert!(right.is_leaf());
assert_eq!(left.parent(), right.parent());
assert_eq!(left.parent().right_child(), right);
assert_eq!(left, right.parent().left_child());
assert_eq!(left.sibling(), right);
assert_eq!(left, right.sibling());
}
}
#[test]
fn test_inorder_index_basic() {
let left = InOrderIndex::from_leaf_pos(0);
let right = InOrderIndex::from_leaf_pos(1);
assert!(left.is_leaf());
assert!(right.is_leaf());
assert_eq!(left.parent(), right.parent());
assert_eq!(left.parent().right_child(), right);
assert_eq!(left, right.parent().left_child());
assert_eq!(left.sibling(), right);
assert_eq!(left, right.sibling());
}
#[test]
fn test_inorder_index_serialization() {
let index = InOrderIndex::from_leaf_pos(5);
let bytes = index.to_bytes();
let index2 = InOrderIndex::read_from_bytes(&bytes).unwrap();
assert_eq!(index, index2);
}
}