algae_mmr/
utils.rs

1/*
2    Appellation: utils <module>
3    Contrib: FL03 <jo3mccain@icloud.com>
4    Description:
5*/
6
7/// This function takes in the index and calculates if the node is the right child node or not.
8/// If the node is the tree root it will still give the answer as if it is a child of a node.
9/// This function is an iterative function as we might have to subtract the largest left_most tree.
10pub fn is_node_right(index: usize) -> bool {
11    let mut height_counter = 0;
12    while index >= ((1 << (height_counter + 2)) - 2) {
13        // find the height of the tree by finding if we can subtract the  height +1
14        height_counter += 1;
15    }
16    let height_index = (1 << (height_counter + 1)) - 2;
17    if index == height_index {
18        // If this is the first peak then subtracting the height of first peak will be 0
19        return false;
20    };
21    if index == (height_index + ((1 << (height_counter + 1)) - 1)) {
22        // we are looking if its the right sibling
23        return true;
24    };
25    // if we are here means it was not a right node at height counter, we therefor search lower
26    let new_index = index - height_index - 1;
27    is_node_right(new_index)
28}
29
30/// This function takes in the index and calculates the height of the node
31/// This function is an iterative function as we might have to subtract the largest left_most tree.
32pub fn get_node_height(index: usize) -> usize {
33    let mut height_counter = 0;
34    while index >= ((1 << (height_counter + 2)) - 2) {
35        // find the height of the tree by finding if we can subtract the  height +1
36        height_counter += 1;
37    }
38    let height_index = (1 << (height_counter + 1)) - 2;
39    if index == height_index {
40        // If this is the first peak then subtracting the height of first peak will be 0
41        return height_counter;
42    };
43    if index == (height_index + ((1 << (height_counter + 1)) - 1)) {
44        // we are looking if its the right sibling
45        return height_counter;
46    };
47    // if we are here means it was not a right node at height counter, we therefor search lower
48    let new_index = index - height_index - 1;
49    get_node_height(new_index)
50}
51
52/// This function takes in the index and calculates the index of the sibling.
53pub fn sibling_index(index: usize) -> usize {
54    let height = get_node_height(index);
55    let index_count = (1 << (height + 1)) - 1;
56    if is_node_right(index) {
57        index - index_count
58    } else {
59        index + index_count
60    }
61}
algae_mmr/utils.rs

algae_mmr/
utils.rs
