#![no_std]
#![deny(missing_docs)]
#![deny(unsafe_code)]
use aligned_cmov::{
subtle::{ConstantTimeEq, ConstantTimeLess},
CMov,
};
use rand_core::RngCore;
pub trait TreeIndex: Copy + Eq + PartialEq + CMov {
const NONE: Self;
const ROOT: Self;
fn parent(&self, i: u32) -> Self;
fn height(&self) -> u32;
fn common_ancestor_distance_of_peers(&self, other: &Self) -> u32;
fn common_ancestor_height(&self, other: &Self) -> u32 {
let ht_self = self.height();
let ht_other = other.height();
let ht_min = {
let mut ht_min = ht_self;
ht_min.cmov(ht_other.ct_lt(&ht_self), &ht_other);
ht_min
};
let adjusted_self = self.parent(ht_self.wrapping_sub(ht_min));
let adjusted_other = other.parent(ht_other.wrapping_sub(ht_min));
debug_assert!(adjusted_self.height() == ht_min);
debug_assert!(adjusted_other.height() == ht_min);
let dist = adjusted_self.common_ancestor_distance_of_peers(&adjusted_other);
debug_assert!(dist <= ht_min);
ht_min.wrapping_sub(dist)
}
fn random_child_at_height<R: RngCore>(&self, height: u32, rng: &mut R) -> Self;
fn parents(&self) -> ParentsIterator<Self> {
ParentsIterator::from(*self)
}
}
pub struct ParentsIterator<I: TreeIndex> {
internal: I,
}
impl<I: TreeIndex> Iterator for ParentsIterator<I> {
type Item = I;
fn next(&mut self) -> Option<Self::Item> {
if self.internal == I::NONE {
None
} else {
let temp = self.internal;
self.internal = self.internal.parent(1);
Some(temp)
}
}
}
impl<I: TreeIndex> From<I> for ParentsIterator<I> {
fn from(internal: I) -> Self {
Self { internal }
}
}
macro_rules! implement_tree_index_for_primitive {
($uint:ty) => {
impl TreeIndex for $uint {
const NONE: $uint = 0;
const ROOT: $uint = 1;
fn parent(&self, i: u32) -> Self {
self >> i
}
fn height(&self) -> u32 {
debug_assert!(*self != 0);
const DIGITS_MINUS_ONE: u32 = <$uint>::MAX.leading_ones() - 1;
DIGITS_MINUS_ONE.wrapping_sub(self.leading_zeros())
}
fn common_ancestor_distance_of_peers(&self, other: &Self) -> u32 {
debug_assert!(self.height() == other.height());
const DIGITS: u32 = <$uint>::MAX.leading_ones();
DIGITS.wrapping_sub((self ^ other).leading_zeros())
}
fn random_child_at_height<R: RngCore>(&self, height: u32, rng: &mut R) -> Self {
let mut myself = *self;
myself.cmov(myself.ct_eq(&Self::NONE), &Self::ROOT);
debug_assert!(height >= myself.height());
let num_bits_needed = height.wrapping_sub(myself.height());
let randomness =
(rng.next_u64() as $uint) & (((1 as $uint) << num_bits_needed) - 1);
(myself << num_bits_needed) ^ randomness
}
}
};
}
implement_tree_index_for_primitive!(u32);
implement_tree_index_for_primitive!(u64);
#[cfg(test)]
mod testing {
use super::*;
extern crate alloc;
use alloc::vec;
use alloc::vec::Vec;
fn collect_to_vec<I: TreeIndex>(it: ParentsIterator<I>) -> Vec<I> {
it.collect()
}
#[test]
fn test_height_u64() {
assert_eq!(1u64.height(), 0);
assert_eq!(2u64.height(), 1);
assert_eq!(3u64.height(), 1);
assert_eq!(4u64.height(), 2);
assert_eq!(5u64.height(), 2);
assert_eq!(6u64.height(), 2);
assert_eq!(7u64.height(), 2);
assert_eq!(8u64.height(), 3);
assert_eq!(9u64.height(), 3);
assert_eq!(10u64.height(), 3);
assert_eq!(11u64.height(), 3);
assert_eq!(12u64.height(), 3);
assert_eq!(13u64.height(), 3);
assert_eq!(14u64.height(), 3);
assert_eq!(15u64.height(), 3);
assert_eq!(16u64.height(), 4);
}
#[test]
fn test_height_u32() {
assert_eq!(1u32.height(), 0);
assert_eq!(2u32.height(), 1);
assert_eq!(3u32.height(), 1);
assert_eq!(4u32.height(), 2);
assert_eq!(5u32.height(), 2);
assert_eq!(6u32.height(), 2);
assert_eq!(7u32.height(), 2);
assert_eq!(8u32.height(), 3);
assert_eq!(9u32.height(), 3);
assert_eq!(10u32.height(), 3);
assert_eq!(11u32.height(), 3);
assert_eq!(12u32.height(), 3);
assert_eq!(13u32.height(), 3);
assert_eq!(14u32.height(), 3);
assert_eq!(15u32.height(), 3);
assert_eq!(16u32.height(), 4);
}
#[test]
fn test_random_child_at_height_u64() {
test_helper::run_with_several_seeds(|mut rng| {
for ht in 0..40 {
for _ in 0..10 {
let node = 1u64.random_child_at_height(ht, &mut rng);
assert_eq!(node.height(), ht);
}
}
for ht in 20..40 {
for _ in 0..10 {
let node = 10u64.random_child_at_height(ht, &mut rng);
assert_eq!(node.height(), ht);
assert!(node.parents().any(|x| x == 10u64))
}
}
})
}
#[test]
fn test_random_child_at_height_u32() {
test_helper::run_with_several_seeds(|mut rng| {
for ht in 0..30 {
for _ in 0..10 {
let node = 1u32.random_child_at_height(ht, &mut rng);
assert_eq!(node.height(), ht);
}
}
for ht in 20..30 {
for _ in 0..10 {
let node = 10u64.random_child_at_height(ht, &mut rng);
assert_eq!(node.height(), ht);
assert!(node.parents().any(|x| x == 10u64))
}
}
})
}
#[test]
fn test_parents_iterator_u64() {
assert_eq!(collect_to_vec(1u64.parents()), vec![0b1]);
assert_eq!(collect_to_vec(2u64.parents()), vec![0b10, 0b1]);
assert_eq!(collect_to_vec(3u64.parents()), vec![0b11, 0b1]);
assert_eq!(collect_to_vec(4u64.parents()), vec![0b100, 0b10, 0b1]);
assert_eq!(collect_to_vec(5u64.parents()), vec![0b101, 0b10, 0b1]);
assert_eq!(collect_to_vec(6u64.parents()), vec![0b110, 0b11, 0b1]);
assert_eq!(collect_to_vec(7u64.parents()), vec![0b111, 0b11, 0b1]);
assert_eq!(
collect_to_vec(8u64.parents()),
vec![0b1000, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(9u64.parents()),
vec![0b1001, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(10u64.parents()),
vec![0b1010, 0b101, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(11u64.parents()),
vec![0b1011, 0b101, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(12u64.parents()),
vec![0b1100, 0b110, 0b11, 0b1]
);
assert_eq!(
collect_to_vec(13u64.parents()),
vec![0b1101, 0b110, 0b11, 0b1]
);
assert_eq!(
collect_to_vec(14u64.parents()),
vec![0b1110, 0b111, 0b11, 0b1]
);
assert_eq!(
collect_to_vec(15u64.parents()),
vec![0b1111, 0b111, 0b11, 0b1]
);
assert_eq!(
collect_to_vec(16u64.parents()),
vec![0b10000, 0b1000, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(17u64.parents()),
vec![0b10001, 0b1000, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(18u64.parents()),
vec![0b10010, 0b1001, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(19u64.parents()),
vec![0b10011, 0b1001, 0b100, 0b10, 0b1]
);
}
#[test]
fn test_parents_iterator_u32() {
assert_eq!(collect_to_vec(1u32.parents()), vec![0b1]);
assert_eq!(collect_to_vec(2u32.parents()), vec![0b10, 0b1]);
assert_eq!(collect_to_vec(3u32.parents()), vec![0b11, 0b1]);
assert_eq!(collect_to_vec(4u32.parents()), vec![0b100, 0b10, 0b1]);
assert_eq!(collect_to_vec(5u32.parents()), vec![0b101, 0b10, 0b1]);
assert_eq!(collect_to_vec(6u32.parents()), vec![0b110, 0b11, 0b1]);
assert_eq!(collect_to_vec(7u32.parents()), vec![0b111, 0b11, 0b1]);
assert_eq!(
collect_to_vec(8u32.parents()),
vec![0b1000, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(9u32.parents()),
vec![0b1001, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(10u32.parents()),
vec![0b1010, 0b101, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(11u32.parents()),
vec![0b1011, 0b101, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(12u32.parents()),
vec![0b1100, 0b110, 0b11, 0b1]
);
assert_eq!(
collect_to_vec(13u32.parents()),
vec![0b1101, 0b110, 0b11, 0b1]
);
assert_eq!(
collect_to_vec(14u32.parents()),
vec![0b1110, 0b111, 0b11, 0b1]
);
assert_eq!(
collect_to_vec(15u32.parents()),
vec![0b1111, 0b111, 0b11, 0b1]
);
assert_eq!(
collect_to_vec(16u32.parents()),
vec![0b10000, 0b1000, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(17u32.parents()),
vec![0b10001, 0b1000, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(18u32.parents()),
vec![0b10010, 0b1001, 0b100, 0b10, 0b1]
);
assert_eq!(
collect_to_vec(19u32.parents()),
vec![0b10011, 0b1001, 0b100, 0b10, 0b1]
);
}
#[test]
fn test_common_ancestor_u64() {
assert_eq!(1u64.common_ancestor_distance_of_peers(&1u64), 0);
assert_eq!(2u64.common_ancestor_distance_of_peers(&2u64), 0);
assert_eq!(2u64.common_ancestor_distance_of_peers(&3u64), 1);
assert_eq!(3u64.common_ancestor_distance_of_peers(&3u64), 0);
assert_eq!(4u64.common_ancestor_distance_of_peers(&7u64), 2);
assert_eq!(4u64.common_ancestor_distance_of_peers(&5u64), 1);
assert_eq!(4u64.common_ancestor_distance_of_peers(&6u64), 2);
assert_eq!(7u64.common_ancestor_distance_of_peers(&7u64), 0);
assert_eq!(7u64.common_ancestor_distance_of_peers(&6u64), 1);
assert_eq!(7u64.common_ancestor_distance_of_peers(&5u64), 2);
assert_eq!(17u64.common_ancestor_distance_of_peers(&31u64), 4);
assert_eq!(17u64.common_ancestor_distance_of_peers(&23u64), 3);
assert_eq!(17u64.common_ancestor_distance_of_peers(&19u64), 2);
}
#[test]
fn test_common_ancestor_u32() {
assert_eq!(1u32.common_ancestor_distance_of_peers(&1u32), 0);
assert_eq!(2u32.common_ancestor_distance_of_peers(&2u32), 0);
assert_eq!(2u32.common_ancestor_distance_of_peers(&3u32), 1);
assert_eq!(3u32.common_ancestor_distance_of_peers(&3u32), 0);
assert_eq!(4u32.common_ancestor_distance_of_peers(&7u32), 2);
assert_eq!(4u32.common_ancestor_distance_of_peers(&5u32), 1);
assert_eq!(4u32.common_ancestor_distance_of_peers(&6u32), 2);
assert_eq!(7u32.common_ancestor_distance_of_peers(&7u32), 0);
assert_eq!(7u32.common_ancestor_distance_of_peers(&6u32), 1);
assert_eq!(7u32.common_ancestor_distance_of_peers(&5u32), 2);
assert_eq!(17u32.common_ancestor_distance_of_peers(&31u32), 4);
assert_eq!(17u32.common_ancestor_distance_of_peers(&23u32), 3);
assert_eq!(17u32.common_ancestor_distance_of_peers(&19u32), 2);
}
fn naive_common_ancestor_distance_of_peers<I: TreeIndex>(lhs: &I, rhs: &I) -> u32 {
let mut counter = 0u32;
let mut it1 = lhs.parents();
let mut it2 = rhs.parents();
while it1.next().unwrap() != it2.next().unwrap() {
counter = counter + 1;
}
counter
}
#[test]
fn common_ancestor_distance_conformance_u64() {
test_helper::run_with_several_seeds(|mut rng| {
for ht in 0..30 {
for _ in 0..10 {
let node = 1u64.random_child_at_height(ht, &mut rng);
let node2 = 1u64.random_child_at_height(ht, &mut rng);
assert_eq!(
node.common_ancestor_distance_of_peers(&node2),
naive_common_ancestor_distance_of_peers(&node, &node2)
);
}
}
for ht in 20..30 {
for _ in 0..10 {
let node = 16u64.random_child_at_height(ht, &mut rng);
let node2 = 16u64.random_child_at_height(ht, &mut rng);
assert_eq!(
node.common_ancestor_distance_of_peers(&node2),
naive_common_ancestor_distance_of_peers(&node, &node2)
);
}
}
})
}
#[test]
fn common_ancestor_distance_conformance_u32() {
test_helper::run_with_several_seeds(|mut rng| {
for ht in 0..30 {
for _ in 0..10 {
let node = 1u32.random_child_at_height(ht, &mut rng);
let node2 = 1u32.random_child_at_height(ht, &mut rng);
assert_eq!(
node.common_ancestor_distance_of_peers(&node2),
naive_common_ancestor_distance_of_peers(&node, &node2)
);
}
}
for ht in 20..30 {
for _ in 0..10 {
let node = 16u32.random_child_at_height(ht, &mut rng);
let node2 = 16u32.random_child_at_height(ht, &mut rng);
assert_eq!(
node.common_ancestor_distance_of_peers(&node2),
naive_common_ancestor_distance_of_peers(&node, &node2)
);
}
}
})
}
#[test]
fn common_ancestor_height_u64() {
assert_eq!(1u64.common_ancestor_height(&1u64), 0);
assert_eq!(2u64.common_ancestor_height(&2u64), 1);
assert_eq!(4u64.common_ancestor_height(&4u64), 2);
assert_eq!(8u64.common_ancestor_height(&8u64), 3);
assert_eq!(8u64.common_ancestor_height(&4u64), 2);
assert_eq!(8u64.common_ancestor_height(&7u64), 0);
assert_eq!(8u64.common_ancestor_height(&3u64), 0);
assert_eq!(8u64.common_ancestor_height(&9u64), 2);
assert_eq!(8u64.common_ancestor_height(&11u64), 1);
assert_eq!(8u64.common_ancestor_height(&13u64), 0);
assert_eq!(16u64.common_ancestor_height(&8u64), 3);
assert_eq!(16u64.common_ancestor_height(&4u64), 2);
assert_eq!(16u64.common_ancestor_height(&7u64), 0);
assert_eq!(16u64.common_ancestor_height(&3u64), 0);
assert_eq!(16u64.common_ancestor_height(&9u64), 2);
assert_eq!(16u64.common_ancestor_height(&11u64), 1);
assert_eq!(16u64.common_ancestor_height(&13u64), 0);
assert_eq!(17u64.common_ancestor_height(&15u64), 0);
assert_eq!(17u64.common_ancestor_height(&19u64), 2);
assert_eq!(17u64.common_ancestor_height(&21u64), 1);
assert_eq!(17u64.common_ancestor_height(&31u64), 0);
assert_eq!(17u64.common_ancestor_height(&63u64), 0);
assert_eq!(17u64.common_ancestor_height(&127u64), 0);
}
#[test]
fn common_ancestor_height_u32() {
assert_eq!(1u32.common_ancestor_height(&1u32), 0);
assert_eq!(2u32.common_ancestor_height(&2u32), 1);
assert_eq!(4u32.common_ancestor_height(&4u32), 2);
assert_eq!(8u32.common_ancestor_height(&8u32), 3);
assert_eq!(8u32.common_ancestor_height(&4u32), 2);
assert_eq!(8u32.common_ancestor_height(&7u32), 0);
assert_eq!(8u32.common_ancestor_height(&3u32), 0);
assert_eq!(8u32.common_ancestor_height(&9u32), 2);
assert_eq!(8u32.common_ancestor_height(&11u32), 1);
assert_eq!(8u32.common_ancestor_height(&13u32), 0);
assert_eq!(16u32.common_ancestor_height(&8u32), 3);
assert_eq!(16u32.common_ancestor_height(&4u32), 2);
assert_eq!(16u32.common_ancestor_height(&7u32), 0);
assert_eq!(16u32.common_ancestor_height(&3u32), 0);
assert_eq!(16u32.common_ancestor_height(&9u32), 2);
assert_eq!(16u32.common_ancestor_height(&11u32), 1);
assert_eq!(16u32.common_ancestor_height(&13u32), 0);
assert_eq!(17u32.common_ancestor_height(&15u32), 0);
assert_eq!(17u32.common_ancestor_height(&19u32), 2);
assert_eq!(17u32.common_ancestor_height(&21u32), 1);
assert_eq!(17u32.common_ancestor_height(&31u32), 0);
assert_eq!(17u32.common_ancestor_height(&63u32), 0);
assert_eq!(17u32.common_ancestor_height(&127u32), 0);
}
}