traaains/utils/interval_tree/
mod.rs

1mod heap;
2mod stack;
3
4pub use heap::IntervalBitmapVec;
5pub use stack::IntervalBitmap;
6
7/// Calculates how many nodes an interval tree should have for the given interval size.
8/// Rounds to nearest power of two to generate a complete binary tree.
9pub const fn interval_to_nodes(size: usize) -> usize {
10    2 * size.next_power_of_two() - 1
11}
12
13/// Calculates with how many bitfields an interval tree should be backed by to hold the given number of nodes.
14pub const fn nodes_to_bitfields(nodes: usize) -> usize {
15    nodes / usize::BITS as usize + 1
16}
17
18pub const fn interval_to_bitfields(size: usize) -> usize {
19    nodes_to_bitfields(interval_to_nodes(size))
20}
21
22/// Calculates the number of internal nodes from interval size.
23/// Rounds to nearest power of two to generate a complete binary tree.
24pub const fn interval_to_internal(size: usize) -> usize {
25    size.next_power_of_two() - 1
26}
27
28/// Calculates the depth of what would be a complete binary tree from the interval size.
29pub const fn leaves_to_depth(size: usize) -> usize {
30    size.next_power_of_two().ilog2() as usize
31}
32
33/// Get parent index for an index
34/// Returns none if the node has no parent (index == 0)
35pub fn parent_for(index: usize) -> Option<usize> {
36    index.checked_sub(1)?.checked_div(2)
37}
38
39/// Returns index for the left child of `index`.
40/// Unlike `parent_for`, this method is unchecked. One must track how many nodes are actually in the tree and react accordingly.
41pub fn left_child(index: usize) -> usize {
42    index * 2 + 1
43}
44
45pub fn right_child(index: usize) -> usize {
46    index * 2 + 2
47}
traaains/utils/interval_tree/mod.rs

traaains/utils/interval_tree/
mod.rs
