use crate::proof::definition::{LeafCount, MAX_ACCUMULATOR_LEAVES, MAX_ACCUMULATOR_PROOF_DEPTH};
use std::fmt;
#[cfg(test)]
mod position_test;
#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
pub struct Position(u64);
#[derive(Debug, Eq, PartialEq)]
pub enum NodeDirection {
Left,
Right,
}
impl Position {
pub fn level(self) -> u32 {
(!self.0).trailing_zeros()
}
fn is_leaf(self) -> bool {
self.0 & 1 == 0
}
#[cfg(test)]
fn pos_counting_from_left(self) -> u64 {
self.0 >> (self.level() + 1)
}
pub fn from_level_and_pos(level: u32, pos: u64) -> Self {
let level_one_bits = (1u64 << level) - 1;
let shifted_pos = pos << (level + 1);
Position(shifted_pos | level_one_bits)
}
pub fn from_inorder_index(index: u64) -> Self {
Position(index)
}
pub fn to_inorder_index(self) -> u64 {
self.0
}
pub fn from_postorder_index(index: u64) -> Self {
Position(postorder_to_inorder(index))
}
pub fn to_postorder_index(self) -> u64 {
inorder_to_postorder(self.to_inorder_index())
}
pub fn parent(self) -> Self {
Self(
(self.0 | isolate_rightmost_zero_bit(self.0))
& !(isolate_rightmost_zero_bit(self.0) << 1),
)
}
pub fn left_child(self) -> Self {
Self::child(self, NodeDirection::Left)
}
pub fn right_child(self) -> Self {
Self::child(self, NodeDirection::Right)
}
fn child(self, dir: NodeDirection) -> Self {
assert!(!self.is_leaf());
let direction_bit = match dir {
NodeDirection::Left => 0,
NodeDirection::Right => isolate_rightmost_zero_bit(self.0),
};
Self((self.0 | direction_bit) & !(isolate_rightmost_zero_bit(self.0) >> 1))
}
pub fn is_left_child(self) -> bool {
self.0 & (isolate_rightmost_zero_bit(self.0) << 1) == 0
}
pub fn is_right_child(self) -> bool {
!self.is_left_child()
}
pub fn from_leaf_index(leaf_index: u64) -> Self {
Self::from_level_and_pos(0, leaf_index)
}
pub fn sibling(self) -> Self {
Self(self.0 ^ (isolate_rightmost_zero_bit(self.0) << 1))
}
pub fn root_from_leaf_index(leaf_index: u64) -> Self {
let leaf = Self::from_leaf_index(leaf_index);
Self(smear_ones_for_u64(leaf.0) >> 1)
}
pub fn root_from_leaf_count(leaf_count: LeafCount) -> Self {
assert!(leaf_count > 0);
Self::root_from_leaf_index((leaf_count - 1) as u64)
}
pub fn root_level_from_leaf_count(leaf_count: LeafCount) -> u32 {
assert!(leaf_count > 0);
let index = (leaf_count - 1) as u64;
MAX_ACCUMULATOR_PROOF_DEPTH as u32 + 1 - index.leading_zeros()
}
pub fn right_most_child(self) -> Self {
let level = self.level();
Self(self.0 + (1_u64 << level) - 1)
}
pub fn left_most_child(self) -> Self {
let level = self.level();
Self(turn_off_right_most_n_bits(self.0, level))
}
}
fn smear_ones_for_u64(v: u64) -> u64 {
let mut n = v;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
n
}
fn turn_off_right_most_n_bits(v: u64, n: u32) -> u64 {
(v >> n) << n
}
fn isolate_rightmost_zero_bit(v: u64) -> u64 {
!v & (v + 1)
}
impl Position {
pub fn is_freezable(self, leaf_index: u64) -> bool {
let leaf = Self::from_leaf_index(leaf_index);
let right_most_child = self.right_most_child();
right_most_child.0 <= leaf.0
}
pub fn is_placeholder(self, leaf_index: u64) -> bool {
let leaf = Self::from_leaf_index(leaf_index);
if self.0 <= leaf.0 {
return false;
}
if self.left_most_child().0 <= leaf.0 {
return false;
}
true
}
pub fn iter_ancestor(self) -> AncestorIterator {
AncestorIterator { position: self }
}
pub fn iter_ancestor_sibling(self) -> AncestorSiblingIterator {
AncestorSiblingIterator { position: self }
}
}
impl fmt::Display for Position {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "Pos({})", self.to_inorder_index())
}
}
#[derive(Debug)]
pub struct AncestorSiblingIterator {
position: Position,
}
impl Iterator for AncestorSiblingIterator {
type Item = Position;
fn next(&mut self) -> Option<Position> {
let current_sibling_position = self.position.sibling();
self.position = self.position.parent();
Some(current_sibling_position)
}
}
#[derive(Debug)]
pub struct AncestorIterator {
position: Position,
}
impl Iterator for AncestorIterator {
type Item = Position;
fn next(&mut self) -> Option<Position> {
let current_position = self.position;
self.position = self.position.parent();
Some(current_position)
}
}
pub struct FrozenSubTreeIterator {
bitmap: u64,
seen_leaves: u64,
}
impl FrozenSubTreeIterator {
pub fn new(num_leaves: LeafCount) -> Self {
Self {
bitmap: num_leaves,
seen_leaves: 0,
}
}
}
impl Iterator for FrozenSubTreeIterator {
type Item = Position;
fn next(&mut self) -> Option<Position> {
if self.bitmap == 0 {
return None;
}
let root_offset = smear_ones_for_u64(self.bitmap) >> 1;
let num_leaves = root_offset + 1;
let leftmost_leaf = Position::from_leaf_index(self.seen_leaves);
let root = Position::from_inorder_index(leftmost_leaf.to_inorder_index() + root_offset);
self.bitmap &= !num_leaves;
self.seen_leaves += num_leaves;
Some(root)
}
}
pub struct FrozenSubtreeSiblingIterator {
current_num_leaves: LeafCount,
remaining_new_leaves: LeafCount,
}
impl FrozenSubtreeSiblingIterator {
pub fn new(current_num_leaves: LeafCount, new_num_leaves: LeafCount) -> Self {
assert!(
new_num_leaves <= MAX_ACCUMULATOR_LEAVES,
"An accumulator can have at most 2^{} leaves. Provided num_leaves: {}.",
MAX_ACCUMULATOR_PROOF_DEPTH,
new_num_leaves,
);
assert!(
current_num_leaves <= new_num_leaves,
"Number of leaves needs to be increasing: current_num_leaves: {}, new_num_leaves: {}",
current_num_leaves,
new_num_leaves
);
Self {
current_num_leaves,
remaining_new_leaves: new_num_leaves - current_num_leaves,
}
}
fn next_new_leaf_batch(&self) -> LeafCount {
let zeros = self.remaining_new_leaves.leading_zeros();
1 << (MAX_ACCUMULATOR_PROOF_DEPTH - zeros as usize)
}
}
impl Iterator for FrozenSubtreeSiblingIterator {
type Item = Position;
fn next(&mut self) -> Option<Self::Item> {
if self.remaining_new_leaves == 0 {
return None;
}
let next_subtree_leaves = if self.current_num_leaves > 0 {
let rightmost_frozen_subtree_leaves = 1 << self.current_num_leaves.trailing_zeros();
if self.remaining_new_leaves >= rightmost_frozen_subtree_leaves {
rightmost_frozen_subtree_leaves
} else {
self.next_new_leaf_batch()
}
} else {
self.next_new_leaf_batch()
};
let first_leaf_index = self.current_num_leaves;
let last_leaf_index = first_leaf_index + next_subtree_leaves - 1;
self.current_num_leaves += next_subtree_leaves;
self.remaining_new_leaves -= next_subtree_leaves;
Some(Position::from_inorder_index(
(first_leaf_index + last_leaf_index) as u64,
))
}
}
fn children_of_node(node: u64) -> u64 {
(isolate_rightmost_zero_bit(node) << 1) - 2
}
fn nodes_to_left_of(node: u64) -> u64 {
let ones_up_to_level = isolate_rightmost_zero_bit(node) - 1;
let unset_level_zeros = node ^ ones_up_to_level;
unset_level_zeros - u64::from(unset_level_zeros.count_ones())
}
pub fn inorder_to_postorder(node: u64) -> u64 {
let children = children_of_node(node);
let left_nodes = nodes_to_left_of(node);
children + left_nodes
}
pub fn postorder_to_inorder(mut node: u64) -> u64 {
let mut full_binary_size = !0u64;
let mut bitmap = 0u64;
for i in (0..64).rev() {
if node >= full_binary_size {
node -= full_binary_size;
bitmap |= 1 << i;
}
full_binary_size >>= 1;
}
let level = node as u32;
let pos = bitmap >> level;
Position::from_level_and_pos(level, pos).to_inorder_index()
}