Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- pub fn non_leaf_nodes_left(data_index: u128) -> u128 {
- // This formula is derived as follows:
- // To get the heights of peaks before this data index was inserted, bit-decompose
- // the number of leaves before it was inserted.
- // Number of leaves in tree of height h = 2^h
- // Number of nodes in tree of height h = 2^(h + 1) - 1
- // Number of non-leaves is `#(nodes) - #(leaves)`.
- let mut ret = 0;
- for h in 0..u128::BITS {
- if (1 << h) & data_index != 0 {
- ret += (1 << h) - 1;
- }
- }
- ret
- }
Advertisement
Advertisement