Function flat_tree::full_roots

pub fn full_roots(i: usize, nodes: &mut Vec<usize>)

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]);