merkle/
merkle.rs

1use std::{array::from_fn, fmt, ops::BitXor};
2
3use vec_entries::EntriesExt;
4
5struct DebugVec<'a, T>(&'a Vec<T>);
6
7impl<'a, T: fmt::Binary> fmt::Binary for DebugVec<'a, T> {
8    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
9        for (count, n) in self.0.iter().enumerate() {
10            if count != 0 {
11                write!(f, " ")?;
12            }
13            n.fmt(f)?;
14        }
15
16        Ok(())
17    }
18}
19
20fn merkle_step<T>(v: &mut Vec<T>, mut join: impl FnMut(T, T) -> T) {
21    v.entries(.., |e| {
22        while let Some(left) = e.remove() {
23            let Some(right) = e.remove() else {
24                // If we can't find a right, just insert the left and stop
25                let Ok(_) = e.try_insert_outside(left) else {
26                    unreachable!()
27                };
28                return;
29            };
30
31            // Combine the two items and insert the result
32            let joined = join(left, right);
33            let Ok(_) = e.try_insert_outside(joined) else {
34                unreachable!()
35            };
36        }
37    });
38}
39
40fn main() {
41    let v: [u64; 9] = from_fn(|i| 1 << i);
42    let mut v: Vec<_> = v.into();
43
44    println!("{:09b}", DebugVec(&v));
45    merkle_step(&mut v, BitXor::bitxor);
46    println!("{:09b}", DebugVec(&v));
47    merkle_step(&mut v, BitXor::bitxor);
48    println!("{:09b}", DebugVec(&v));
49    merkle_step(&mut v, BitXor::bitxor);
50    println!("{:09b}", DebugVec(&v));
51    merkle_step(&mut v, BitXor::bitxor);
52    println!("{:09b}", DebugVec(&v));
53    merkle_step(&mut v, BitXor::bitxor);
54    println!("{:09b}", DebugVec(&v));
55    merkle_step(&mut v, BitXor::bitxor);
56    println!("{:09b}", DebugVec(&v));
57}
merkle/merkle.rs

merkle/
merkle.rs
