wabi_tree 0.1.2

Order-statistic B-tree map and set with O(log n) rank operations. Drop-in replacements for BTreeMap/BTreeSet.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

use core::num::NonZero;

use super::handle::Handle;

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[repr(transparent)]
pub(crate) struct Size(Handle);

impl Size {
    pub(crate) const MAX: usize = Handle::MAX;
    pub(crate) const ZERO: Self = Self::from_usize(0);

    #[inline]
    pub(crate) const fn from_usize(size: usize) -> Self {
        assert!(size <= Self::MAX, "`Size::from_usize()` - `size` > `Size::MAX`!");
        Self(Handle::from_index(size))
    }

    #[inline]
    pub(crate) const fn to_usize(self) -> usize {
        self.0.to_index()
    }
}

#[cfg(test)]
#[cfg_attr(coverage_nightly, coverage(off))]
mod tests {
    use super::*;
    use proptest::prelude::*;
    use static_assertions::assert_eq_size;

    // Verify our assumptions about `Size` and the niche optimization.
    assert_eq_size!(Size, Option<Size>);
    assert_eq_size!(Size, Handle);

    #[test]
    #[should_panic(expected = "`Size::from_usize()` - `size` > `Size::MAX`!")]
    fn invalid_size() {
        let _ = Size::from_usize(Size::MAX + 1);
    }

    proptest! {
        #[test]
        fn size_round_trip(index in 0..=Size::MAX) {
            let size = Size::from_usize(index);
            assert_eq!(size.to_usize(), index);
        }
    }
}