traaains/utils/interval_tree/
heap.rs

1use bitmap::bitmap::BitmapVec;
2
3use crate::utils::interval_tree::{
4    interval_to_bitfields, interval_to_internal, left_child, parent_for, right_child,
5};
6
7/// A dynamically allocated interval tree backed by a bitmap spanning an interval of size `interval_size`.
8/// `interval_size` must be a power of two. Steps are taken to treat incorrect input (rounded to nearest power).
9#[derive(Clone, Debug, Default)]
10pub struct IntervalBitmapVec {
11    inner: BitmapVec<usize>,
12    interval_size: usize,
13}
14
15impl IntervalBitmapVec {
16    pub fn new(size: usize) -> Self {
17        Self {
18            inner: BitmapVec::with_items(interval_to_bitfields(size)),
19            interval_size: size.next_power_of_two(),
20        }
21    }
22
23    pub fn interval_size(&self) -> usize {
24        self.interval_size
25    }
26}
27
28impl IntervalBitmapVec {
29    /// Sets the item at position `index` from the underlying interval to `value`.
30    /// - `index` - index in the underlying interval
31    /// - `value` - the specified value
32    pub fn set_at(&mut self, index: usize, value: bool) {
33        assert!(index < self.interval_size);
34
35        let mut curr_index = index + interval_to_internal(self.interval_size);
36
37        // set leaf
38        self.inner.set(curr_index, value);
39
40        while let Some(parent) = parent_for(curr_index) {
41            let value = self.inner.get(left_child(parent)) && self.inner.get(right_child(parent));
42            self.inner.set(parent, value);
43            curr_index = parent;
44        }
45    }
46
47    /// Gets the item at position `index` from the underlying interval
48    pub fn get_at(&self, index: usize) -> bool {
49        self.inner
50            .get(index + interval_to_internal(self.interval_size))
51    }
52
53    /// Gets the item at position `index` from the tree
54    pub fn get_at_tree(&self, index: usize) -> bool {
55        self.inner.get(index)
56    }
57}
traaains/utils/interval_tree/heap.rs

traaains/utils/interval_tree/
heap.rs
