Function flat_tree::full_roots
source · pub fn full_roots(i: u64, nodes: &mut Vec<u64>)
Expand description
Returns a list of all the full roots (subtrees where all nodes have either 2
or 0 children) <
index.
For example fullRoots(8)
returns [3]
since the subtree rooted at 3
spans 0 -> 6
, and the tree rooted at 7
has a child located at 9
which
is >= 8
.
Panics
If an uneven index is passed.
Examples
use flat_tree::full_roots;
let mut nodes = Vec::with_capacity(16);
full_roots(0, &mut nodes);
assert_eq!(nodes, []);
let mut nodes = Vec::with_capacity(16);
full_roots(2, &mut nodes);
assert_eq!(nodes, [0]);
let mut nodes = Vec::with_capacity(16);
full_roots(8, &mut nodes);
assert_eq!(nodes, [3]);
let mut nodes = Vec::with_capacity(16);
full_roots(20, &mut nodes);
assert_eq!(nodes, [7, 17]);
let mut nodes = Vec::with_capacity(16);
full_roots(18, &mut nodes);
assert_eq!(nodes, [7, 16]);
let mut nodes = Vec::with_capacity(16);
full_roots(16, &mut nodes);
assert_eq!(nodes, [7]);
let mut nodes = Vec::with_capacity(16);
full_roots(30, &mut nodes);
assert_eq!(nodes, [7, 19, 25, 28]);